天天看點
傳回

遺傳算法實踐詳解(deap架構初體驗)

OneMax問題介紹

OneMax 問題是一個簡單的優化任務，通常作為遺傳算法的 Hello World。

OneMax 任務是查找給定長度的二進制串，最大化該二進制串中數字的總和。例如，對于長度為 5 的OneMax問題，10010 的數字總和為 2，01110 的數字總和為 3。

顯然，此問題的最優解為每位數字均為1的二進制串。但是對于遺傳算法而言，其并不具備此知識，是以需要使用其遺傳算子尋找最優解。算法的目标是在合理的時間内找到最優解，或者至少找到一個近似最優解。

遺傳算法實踐

在進行實踐前，應首先明确遺傳算法中所用到的要素定義。

  • 選擇染色體 由于 OneMax 問題涉及二進制串，是以每個個體的染色體直接利用代表候選解的二進制串表示是一個自然的選擇。在 Python中，将其實作為僅包含 0/1 整數值的清單。染色體的長度與 OneMax 問題的規模比對。例如，對于規模為 5 的 OneMax 問題，個體 10010 由清單 [1,0,0,1,0] 表示；
  • 适應度的計算 由于要最大化該二進制串中數字的總和，同時由于每個個體都由 0/1 整數值清單表示，是以适合度可以設計為清單中元素的總和，例如：sum([1,0,0,1,0])= 2；
  • 選擇遺傳算子 選擇遺傳算子并沒有統一的标準，通常可以嘗試幾種選擇方案，找到最适合的方案。其中`選擇算子`通常可以處理任何染色體類型，但是`交叉和突變算子`通常需要比對使用的染色體類型，否則可能會産生無效的染色體：
    • 選擇算子：此處選用錦标賽選擇
    • 交叉算子：此處選用單點交叉
    • 突變算子：此處選用位翻轉突變
  • 設定停止條件 限制繁衍的代際數通常是一個不錯的停止條件，它可以確定算法不會永遠運作。另外，由于我們知道了 OneMax 問題的最佳解決方案(一個全為 1 的二進制串，也就是說其适應度等于代表個體的清單長度)，是以可以将其用作另一個停止條件。但是，需要注意的是，對于現實世界中的多數問題而言，通常不存在這種可以公式化精确定義的先驗知識。

遺傳算法要素配置

在開始實際的遺傳算法流程之前，需要根據上述要素的設計利用代碼實作：

1. 首先導入所用包：

from deap import base
from deap import creator
from deap import tools
import random
import matplotlib.pyplot as plt

2. 接下來，聲明一些常量，這些常量用于設定 OneMax 問題的參數并控制遺傳算法的行為：

ONE_MAX_LENGTH = 100    #length of bit string to be optimized
POPULATION_SIZE = 200   #number of individuals in population
P_CROSSOVER = 0.9       #probability for crossover
P_MUTATION = 0.1        #probability for mutating an individual
MAX_GENERATION = 50     #max number of generations for stopping condition

3. 接下來，使用 Toolbox 類建立 zeroOrOne 操作，該操作用于自定義 random.randomint(a,b) 函數。通過将參數 a 和 b 固定為值 0 和 1，當在調用此運算時，zeroOrOne 運算符将随機傳回 0 或 1：

toolbox = base.Toolbox()#定義toolbox變量
toolbox.register("zeroOrOne",random.randint,0,1)#注冊zeroOrOne運算

4. 接下來，需要建立 Fitness 類。由于這裡隻有一個目标——最大化數字總和，是以選擇 FitnessMax 政策，使用具有單個正權重的權重元組：

creator.create("FitnessMax",base.Fitness,weights=(1.0,))

5. 在 deap 中，通常使用 Individual 的類來代表種群中的每個個體。使用 creator 工具建立該類，使用清單作為基類，用于表示個體的染色體。并為該類增加 Fitness 屬性，該屬性初始化為步驟 4 中定義的 FitnessMax 類：

creator.create("Individual", list, fitness=creator.FitnessMax)

6. 接下來，注冊 individualCreator 操作，該操作建立 Individual 類的執行個體，并利用步驟 1 中自定義的 zeroOrOne 操作随機填充 0/1。注冊 individualCreator 操作使用基類 initRepeat 操作，并使用以下參數對基類進行執行個體化：

  • 将 creator.Individual 類作為放置結果對象的容器類型
  • zeroOrOne 操作是生成對象的函數
  • 常量 ONE_MAX_LENGTH 作為要生成的對象數目

由于 zeroOrOne 運算符生成的對象是 0/1 的随機數，是以，所得的 individualCreator 運算符将使用 100 個随機生成的 0 或 1 填充單個執行個體：

toolbox.register("individualCreator",tools.initRepeat,creator.Individual,toolbox.zeroOrOne,ONE_MAX_LENGTH)

7. 最後，注冊用于建立個體清單的 populationCreator 操作。該定義使用帶有以下參數的 initRepeat 基類操作：

  • 将清單類作為容器類型
  • 用于生成清單中對象的函數 —— personalCreator 運算符

這裡沒有傳入 initRepeat 的最後一個參數——要生成的對象數量。這意味着，當使用 populationCreator 操作時，需要指定此參數用于确定建立的個體數：

toolbox.register("populationCreator",tools.initRepeat,list,toolbox.individualCreator)

8. 為了簡化适應度(在 deap 中稱為 evaluation )的計算，首先定義一個獨立的函數，該函數接受 Individual 類的執行個體并傳回其适應度。

這裡定義 oneMaxFitness 函數，用于計算個體中 1 的數量。

def oneMaxFitness(individual):
    return sum(individual),#deap中的适用度表示為元組，是以，當傳回單個值時，需要用逗号将其聲明為元組

10. 接下來，将 evaluate 運算符定義為 oneMaxfitness() 函數的别名。使用 evaluate 别名來計算适應度是 deap 的一種約定：

toolbox.register("evaluate",oneMaxFitness)

11. 遺傳算子通常是通過對 tools 子產品中的現有函數進行别名命名，并根據需要設定參數值來建立的。根據上節設計的要素建立遺傳算子:

toolbox.register("select",tools.selTournament,tournsize=3)
toolbox.register("mate",tools.cxOnePoint)
# mutFlipBit函數周遊個體的所有特征，并且對于每個特征值，
# 都将使用indpb參數值作為翻轉（應用not運算符）該特征值的機率。
# 該值與突變機率無關，後者由P_MUTATION常數設定。
# 突變機率用于确定是否為種群中的給定個體調用mutFlipBit函數
toolbox.register("mutate",tools.mutFlipBit,indpb=1.0/ONE_MAX_LENGTH)

遺傳算法解的進化

遺傳流程如以下步驟所示：

1. 通過使用之前定義的 populationCreator 操作建立初始種群，并以 POPULATION_SIZE 常量作為該操作的參數。并初始化 generationCounter 變量，用于判斷代際數：

population = toolbox.populationCreator(n=POPULATION_SIZE)
generationCounter = 0

2. 為了計算初始種群中每個個體的适應度，使用 map() 函數将 evaluate 操作應用于種群中的每個個體。由于 evaluate 操作是 oneMaxFitness() 函數的别名，是以，疊代的結果由每個個體的計算出的适應度元組組成。 得到結果後将其轉換為元組清單：

fitnessValues = list(map(toolbox.evaluate,population)

3. 由于 fitnessValues 的項分别與 population (個體清單)中的項比對，是以可以使用 zip() 函數将它們組合并為每個個體配置設定相應的适應度元組：

for individual,fitnessValue in zip(population,fitnessValues):
    individual.fitness.values = fitnessValue

4. 接下來，由于适應度元組僅有一個值，是以從每個個體的适應度中提取第一個值以擷取統計資料：

fitnessValues = [indivalual.fitness.values[0] for individual in population]

5. 統計種群每一代的最大适應度和平均适應度。建立兩個清單用于存儲統計值：

maxFitnessValues = []
meanFitnessValues = []

6. 遺傳流程的主要準備工作已經完成，在循環時還需設定停止條件，通過限制代際數來設定一個停止條件，而通過檢測是否達到了最佳解(所有二進制串位都為 1 )作為另一個停止條件：

while max(fitnessValues)<ONE_MAX_LENGTH and generationCounter<MAX_GENERATIONS:

7. 接下來更新代際計數器：

generationCounter = generationCounter + 1

8. 遺傳算法的核心是遺傳運算符。第一個是 selection 運算符，使用先前利用 toolbox.select 定義的錦标賽選擇。由于我們已經在定義運算符時設定了錦标賽大小，是以隻需要将物種及其長度作為參數傳遞給選擇運算符：

offspring = toolbox.select(population,len(population))

9. 被選擇的個體被指派給 offspring 變量，接下來将其克隆，以便我們可以應用遺傳算子而不影響原始種群：

這裡需要注意的是：盡管被選擇的個體被命名為 offspring，但它們仍然是前一代的個體的克隆，我們仍然需要使用 crossover 運算符将它們配對以建立實際的後代。

offspring = list(map(toolbox.clone,offspring)

10. 下一個遺傳算子是交叉。已經在上節中定義為 toolbox.mate 運算符，并且其僅僅是單點交叉的别名。使用 Python 切片将 offspring 清單中的每個偶數索引項與奇數索引項對作為雙親。然後，以 P_CROSSOVER 常數設定的交叉機率進行交叉。這将決定這對個體是會交叉或保持不變。最後，删除後代的适應度值，因為它們現有的适應度已經不再有效：

for child1,child2 in zip(offspring[::2],offspring[1::2]): if random.random() < P_CROSSOVER: toolbox.mate(child1,child2) del child1.fitness.values del child2.fitness.values

11. 最後一個遺傳運算符是突變，先前已注冊為 toolbox.mutate 運算符，并設定為翻轉位突變操作。周遊所有後代項，将以由突變機率常數 P_MUTATION 設定的機率應用變異算子。如果個體發生突變，我們確定删除其适應性值。由于該值可能繼承自上一代，并且在突變後不再正确，需要重新計算：

for mutant in offspring:
        if random.random() < P_MUTATION:
            toolbox.mutate(mutant)
            del mutant.fitness.values

12. 沒有交叉或變異的個體保持不變，是以，它們的現有适應度值(已在上一代中計算出)就無需再次計算。其餘個體的适應度值為空。使用 Fitness 類的 valid 屬性查找這些新個體，然後以與原始适應性值計算相同的方式為其計算新适應性：

freshIndividuals = [ind for ind in offspring if not ind.fitness.valid]
    freshFitnessValues = list(map(toolbox.evaluate,freshIndividuals))
    for individual,fitnessValue in zip(freshIndividuals,freshFitnessValues):
        individual.fitness.values = fitnessValue

13. 遺傳算子全部完成後，就可以使用新的種群取代舊的種群了：

population[:] = offspring

14. 在繼續下一輪循環之前，将使用與上述相同的方法統計目前的适應度值以更新統計資訊：

fitnessValues = [ind.fitness.values[0] for ind in population]

15. 獲得最大和平均适應度值，将它們的值添加到統計清單中：

maxFitness = max(fitnessValues)
    meanFitness = sum(fitnessValues) / len(population)
    maxFitnessValues.append(maxFItness)
    meanFItnessValues.append(meanFItness)
    print("- Generation {}: Max Fitness = {}, Avg Fitness = {}".format(generationCounter,
    maxFitness, meanFitness)

16. 此外，使用得到的最大适應度值來找到最佳個體的索引，并列印出該個體：

best_index = fitnessValues.index(max(fitnessValues))
    print("Best Individual = ", *population[best_index], "\n")

17. 滿足停止條件并且遺傳算法流程結束後，可以使用擷取的統計資訊，使用matplotlib庫可視化算法執行過程中的統計資訊，展示各代個體的最佳和平均适應度值的變化：

plt.plot(maxFitnessValues,color='red')
plt.plot(meanFitnessValues,color='green')
plt.xlabel('Generation')
plt.ylabel('Max / Average Fitness')
plt.title('Max and Average fitness over Generation')
plt.show()

該部分完整代碼如下：

def main():
    population = toolbox.populationCreator(n=POPULATION_SIZE)
    generationCounter = 0
    fitnessValues = list(map(toolbox.evaluate,population))
    for individual,fitnessValue in zip(population,fitnessValues):
        individual.fitness.values = fitnessValue
    fitnessValues = [individual.fitness.values[0] for individual in population]
    maxFitnessValues = []
    meanFitnessValues = []
    while max(fitnessValues) < ONE_MAX_LENGTH and generationCounter < MAX_GENERATION:
        generationCounter = generationCounter + 1
        
        offspring = toolbox.select(population,len(population))
        offspring = list(map(toolbox.clone,offspring))
        for child1,child2 in zip(offspring[::2],offspring[1::2]):
            if random.random() < P_CROSSOVER:
                toolbox.mate(child1,child2)
                del child1.fitness.values
                del child2.fitness.values
        
        for mutant in offspring:
            if random.random() < P_MUTATION:
                toolbox.mutate(mutant)
                del mutant.fitness.values
        
        freshIndividuals = [ind for ind in offspring if not ind.fitness.valid]
        freshFitnessValues = list(map(toolbox.evaluate,freshIndividuals))
        for individual,fitnessValue in zip(freshIndividuals,freshFitnessValues):
            individual.fitness.values = fitnessValue
        
        population[:] = offspring
        fitnessValues = [ind.fitness.values[0] for ind in population]
        maxFitnessValue = max(fitnessValues)
        meanFitnessValue = sum(fitnessValues) / len(population)
        maxFitnessValues.append(maxFitnessValue)
        meanFitnessValues.append(meanFitnessValue)
        print("- Generation {}: Max Fitness = {}, Avg Fitness = {}".format(generationCounter,maxFitnessValue,meanFitnessValue))
        best_index = fitnessValues.index(max(fitnessValues))
        print("Best Indivadual = ", *population[best_index],"\n")
    plt.plot(maxFitnessValues,color="red")
    plt.plot(meanFitnessValues,color="green")
    plt.xlabel("Generation")
    plt.ylabel("Max / Average Fitness")
    plt.title("Max and Average fitness over Generation")
    plt.show()

至此可以開始測試我們的遺傳算法了，運作代碼以驗證其是否找到了 OneMax 問題的最優解。

算法運作 

if __name__ == "__main__":
    main()

運作程式時，可以看到程式運作輸出：

- Generation 27: Max Fitness = 99.0, Avg Fitness = 96.805
Best Indivadual =  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
- Generation 28: Max Fitness = 99.0, Avg Fitness = 97.235
Best Indivadual =  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
- Generation 29: Max Fitness = 99.0, Avg Fitness = 97.625
Best Indivadual =  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
- Generation 30: Max Fitness = 100.0, Avg Fitness = 98.1
Best Indivadual =  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

可以看到 30 代後算法找到全 1 解，結果适應度為 100，并停止了遺傳流程。平均适應度開始時僅為 53 左右，結束時接近 100。

繪制圖形如下所示：

遺傳算法實踐詳解(deap架構初體驗)

該圖說明了最大适應度與平均适應度是如何随着代數的增加而逐漸增加。

存儲 算法 資料可視化 索引 Python 容器 資料存儲python python使用存儲 python容器化 python字元串索引 python pandas存儲
上一篇: 日志系統新貴 Loki，真香！！
下一篇: python初學第一節課

繼續閱讀