遺傳算法架構 deap 簡介與使用

deap架構介紹

目前，有許多可用于遺傳算法的 Python 架構 —— GAFT，DEAP，Pyevolve 和 PyGMO 等。

其中，deap (Distributed Evolutionary Algorithms in Python) 架構支援使用遺傳算法以及其他進化計算技術快速開發解決方案，得到了廣泛的應用。deap 提供了各種資料結構和工具，這些資料和工具在實作各種基于遺傳算法的解決方案時必不可少。

creator子產品

creator 子產品可以作為元工廠，能夠通過添加新屬性來擴充現有類。

例如，已有一個名為 Employee 的類。使用 creator 工具，可以通過建立 Developer 類來擴充 Employee 類：

import deap import creator
creator.create("Developer",Employee,position="Developer",programmmingLanguage=set)      

傳遞給 create() 函數的第一個參數是新類的名稱。第二個參數是要擴充的現有類，接下來是使用其他參數定義新類的屬性。如果為參數配置設定了一個類(例如 dict 或 set )，它将作為構造函數中初始化的執行個體屬性添加到新類中。如果參數不是類(例如字元串)，則将其添加為靜态 (static) 屬性。

是以，建立的 Developer 類将擴充 Employee 類，并将具有一個靜态屬性 position，設定為 Developer，以及一個執行個體屬性，類型為 set 的 programmingLanguages，該屬性在構造函數中初始化。是以實際上等效于：

class Developer(Employee):
    position = "Developer"
    def __init__(self):
        self.programmmingLanguage = set()      

這個新類存在于 creator 子產品中，是以需要引用時使用 creator.Developer。

使用 deap 時，creator 子產品通常用于建立 Fitness 類以及 Individual 類。

建立适應度類

使用 deap 時，适應度封裝在 Fitness 類中。在 deap 架構中适應度可以有多個組成部分，每個組成部分都有自己的權重(weights)。這些權重的組合定義了适合給定問題的行為或政策。

定義适應度政策

為了快速定義适應度政策，deap 使用了抽象 base.Fitness 類，其中包含 weights 元組，以定義政策并使類可用。可以通過使用 creator 建立基礎 Fitness 類的擴充來完成，類似于建立 Developer 類：

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

上述代碼将産生一個 creator.FitnessMax 類，該類擴充了 base.Fitness 類，并将 weights 類屬性初始化為 (1.0,)值。需要注意的是：weights 參數是一個元組。

FitnessMax 類的政策是在遺傳算法過程中最大化單目标解的适應度值。相反，如果有一個單目标問題，需要使适應度值最小的解，則可以使用以下定義來建立最小化政策：

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

還可以定義具有優化多個目标且重要性不同的政策：

creator.create("FitnessCompound",base.Fitness,weights=(1.0,0.2,-0.5))      

這将産生一個 creator.FitnessCompound 類，它擁有三個不同的适應度組成部分。第一部分權重為 1.0，第二部分權重為 0.2，第三部分權重為 -0.5。這将傾向于使第一和第二部分(或目标)最大化，而使第三部分(或目标)最小化。

适應度存儲方式

雖然權重元組定義了适應度政策，但是一個對應的元組(稱為 values )用于将适應度值存儲在 base.Fitness 類中。這些值是從單獨定義的函數(通常稱為 evaluate() )獲得的。就像 weights 元組一樣，values 元組存儲每個适應度元件(對象)值。

元組 wvalues 包含通過将 values 元組的每個分量與其 weights 元組的對應分量相乘而獲得的權重值。隻要得到了執行個體的适應度值，就會計算權重值并将其插入 wvalues 中。這些值用于個體之間的适應度的比較操作。

建立個體類

在 deap 中，creator 工具的第二個常見用途是定義構成遺傳算法種群的個體。遺傳算法中的個體使用可以由遺傳算子操縱的染色體來表示，通過擴充表示染色體的基類來建立 Individual 類。另外，deap 中的每個個體執行個體都需要包含其适應度函數作為屬性。

為了滿足這兩個要求，利用 creator 來建立 creator.Individual 類：

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

該代碼片段具有以下兩個效果：

• 建立的 Individual 類擴充了 Python 的 list 類，這意味着使用的染色體是清單類型
• 建立的 Individual 類的每個執行個體将具有之前建立的 FitnessMax 屬性

Toolbox類

deap 架構提供的第二種高效建立遺傳算法的機制是 base.Toolbox 類。Toolbox 用作函數(或操作)的容器，能夠通過别名機制和自定義現有函數來建立新的運算符。

假設有一個函數 sumOfTwo()：

def sumOfTwo(a,b):
    return a + b      

使用 toolbox，可以建立一個新的運算，incrementByFive()，該運算符利用 sumOfTwo() 函數建立：

import base
toolbox = base.Toolbox()
toolbox.register("incrementByFive",sumOfTwo,b=5)      

傳遞給 register() 函數的第一個參數是新運算符所需的名稱(或别名)，第二個參數是被定制的現有函數。建立完成後，每當調用新運算符時，其他參數都會自動傳遞給建立的函數，如：

toolbox.incrementByFive(10)      

等效于：

sumOfTwo(10, 5)      

這是因為 b 的參數已由 incrementByFive 運算符定義為5。

建立遺傳算子

為了快速建構遺傳流程，可以使用 Toolbox 類定制 tools 子產品的現有函數。tools 子產品包含許多便捷的函數，這些函數包括選擇、交叉和變異的遺傳算子以及程式的初始化等。

例如，以下代碼定義了三個别名函數，用作遺傳算子：

from deap import tools
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.02)      

這三個别名函數的詳細說明：

1. select 注冊為 tools 函數 selTournament() 的别名，且 tournsize 參數設定為 3。這将建立 toolbox.select 運算符，其為錦标賽規模為 3 的錦标賽選擇算子
2. mate 注冊為 tools 函數 cxTwoPoint() 的别名，這将建立執行兩點交叉的toolbox.mate算子
3. mutate 注冊為 tools 函數 mutFlipBit() 的别名，并将 indpb 參數設定為 0.02，這将建立一個翻轉每個特征的機率為 0.02 的位翻轉突變算子

tools 子產品提供了各種遺傳算子的實作，以下列示常用遺傳算子的實作函數。

選擇算子主要包括：

selRoulette()               #輪盤選擇
selStochasticUniversalSampling()    #随機周遊采樣（SUS）
selTournament()             #錦标賽選擇      

交叉算子主要包括：

cxOnePoint()        #單點交叉
cxUniform()     #均勻交叉
cxOrdered()     #有序交叉
cxPartialyMatched() #實作部分比對交叉      

突變算子主要包括：

mutFlipBit()    #位翻轉突變
mutGaussian()   #正态分布突變      

建立物種

tools 子產品的 init.py 檔案包含用于建立和初始化遺傳算法的函數，其中包括initRepeat()，它接受三個參數：

1. 要放置結果對象的容器類型
2. 用于生成将放入容器的對象的函數
3. 要生成的對象數

如：

#産生含有30個随機數的清單，這些随機數介于0和1之間
randomList = tools.initRepeat(list,random.random,30)      

此示例中，list 是用作要填充的容器的類型，random.random 是生成器函數，而 30 是調用生成器函數以生成填充容器的值的次數。

如果想用 0 或 1 的整數随機數填充清單，則可以建立一個使用 random.radint() 生成随機值 0 或 1 的函數，然後将其用作 initRepeat() 的生成器函數：

def zeroOrOne():
    return random.randint(0,1)
randomList = tools.initRepeat(list,zeroOrOne,30)      

或者，可以利用 Toolbox：

#建立zeroOrOne運算符,使用參數0、1調用random.radint()
toolbox.register("zeroOrOne",random.randint,0,1)
randomList = tools.initRepeat(list,tools.zeroOrOne,30)      

計算适應度

雖然 Fitness 類定義了确定其政策(例如最大化或最小化)的适應度權重，但實際的适應度是從單獨定義的函數中獲得的。該适應度計算函數通常使用别名 evalidate 來注冊到 Toolbox 子產品中：

def someFitnessCalculationFunction(individual):
    """算給定個體的适應度"""
    return _some_calculation_of_of_the_fitness(individual)
#将evaluate注冊為someFitnessCalculationFunction()的别名
toolbox.register("evaluate",someFitnessCalculationFunction)      

使用deap架構解決OneMax問題

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