前言

筆者最近開始學習如何用DEAP落實進化算法，本文既是教程，也是學習筆記，希望在幫助自己記憶理解的同時對同樣正在學習的同學能有所幫助。礙于筆者水平有限，又非運籌優(yōu)化科班出身，錯誤難免，請方家多多指正。

關(guān)于DEAP

DEAP是一個進化計算框架，能夠幫助我們快速實現(xiàn)和測試進化算法。由于它的靈活與強大，目前在Github上已經(jīng)有2848個star。

DEAP的特性：

• 各類遺傳算法
• 遺傳規(guī)劃
• 進化策略
• 多目標優(yōu)化
• 多種群之間的協(xié)作與競爭
• 并行計算
• 計算過程中設(shè)定檢查點
• 設(shè)置基準模塊，檢驗算法能力
• 支持粒子群算法、差分進化算法等

可以簡單的使用 pip install deap 來安裝，本文基于當前的最新版(deap - 1.2.2)。

進化算法簡介

什么是進化算法

進化算法(Evolutionary Algorithms)是一類元啟發(fā)式算法的統(tǒng)稱。這類算法借鑒大自然中生物的進化、選擇與淘汰機制，通常先產(chǎn)生一個族群，然后不斷進化與淘汰，最終產(chǎn)生能夠在嚴酷的自然環(huán)境中生存的優(yōu)異個體（也就是有較大適應(yīng)度函數(shù)的可行解）。它具有自組織、自適應(yīng)的特性，常被用來處理傳統(tǒng)優(yōu)化算法難以解決的問題。

進化算法的優(yōu)缺點

優(yōu)點：

• 泛用性強，對連續(xù)變量和離散變量都能適用；
• 不需要導數(shù)信息，因此不要求適應(yīng)度函數(shù)的連續(xù)和可微性質(zhì)(或者說不需要問題內(nèi)在機理的相關(guān)信息)；
• 可以在解空間內(nèi)大范圍并行搜索；
• 不容易陷入局部最優(yōu)；
• 高度并行化，并且容易與其他優(yōu)化方法整合。

缺點：

• 對于凸優(yōu)化問題，相對基于梯度的優(yōu)化方法（例如梯度下降法，牛頓/擬牛頓法）收斂速度更慢；
• 進化算法需要在搜索空間投放大量個體來搜索最優(yōu)解。對于高維問題，由于搜索空間隨維度指數(shù)級膨脹，需要投放的個體數(shù)也大幅增長，會導致收斂速度變慢；
• 設(shè)計編碼方式、適應(yīng)度函數(shù)以及變異規(guī)則需要大量經(jīng)驗。

進化算法的基本元素

寬泛來講，大部分進化算法都具有以下元素：

1. 個體編碼(Individual representation): 將問題的解空間編碼映射到搜索空間的過程。常用的編碼方式有二值編碼(Binary)，格雷編碼(Gray)，浮點編碼(Floating-point)等。
2. 評價(Evaluation): 設(shè)定一定的準則評價族群內(nèi)每個個體的優(yōu)秀程度。這種優(yōu)秀程度通常稱為適應(yīng)度(Fitness)。
3. 配種選擇(Mating selection): 建立準則從父代中選擇個體參與育種。盡可能選擇精英個體的同時也應(yīng)當維護種群的多樣性，避免算法過早陷入局部最優(yōu)。
4. 變異(Variation): 變異過程包括一系列受到生物啟發(fā)的操作，例如重組(Recombination)，突變(mutation)等。通過變異操作，父代的個體編碼以一定方式繼承和重新組合后，形成后代族群。
5. 環(huán)境選擇(Environmental selection): 將父代與子代重組成新的族群。這個過程中育種得到的后代被重新插入到父代種群中，替換父代種群的部分或全體，形成具有與前代相近規(guī)模的新族群。
6. 停止準則(Stopping crieterion): 確定算法何時停止，通常有兩種情況：算法已經(jīng)找到最優(yōu)解或者算法已經(jīng)選入局部最優(yōu)，不能繼續(xù)在解空間內(nèi)搜索。

利用這些元素，我們就可以依照流程圖組成一個進化算法：

flowchart

用文字表述實現(xiàn)一個簡單進化算法的過程如下：

Generate the initial population P(0) at random, and set t to 0.
repeat
    Evaluate the fitness of each individual in P(t).
    Select parents from P(t) based on their fitness.
    Obtain population P(t+1) by making variations to parents.
    Set t = t + 1
until Stopping crieterion satisfied

進化算法各元素的DEAP實現(xiàn)（一）：問題定義、個體編碼與創(chuàng)建初始族群

1.優(yōu)化問題的定義

單目標優(yōu)化：creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))

在創(chuàng)建單目標優(yōu)化問題時，weights用來指示最大化和最小化。此處-1.0即代表問題是一個最小化問題，對于最大化，應(yīng)將weights改為正數(shù)，如1.0。

另外即使是單目標優(yōu)化，weights也需要是一個tuple，以保證單目標和多目標優(yōu)化時數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一。

對于單目標優(yōu)化問題，weights 的絕對值沒有意義，只要符號選擇正確即可。

多目標優(yōu)化：creator.create('FitnessMulti', base.Fitness, weights=(-1.0, 1.0))

對于多目標優(yōu)化問題，weights用來指示多個優(yōu)化目標之間的相對重要程度以及最大化最小化。如示例中給出的(-1.0, 1.0)代表對第一個目標函數(shù)取最小值，對第二個目標函數(shù)取最大值。

2.個體編碼

實數(shù)編碼(Value encoding)：直接用實數(shù)對變量進行編碼。優(yōu)點是不用解碼，基因表達非常簡潔，而且能對應(yīng)連續(xù)區(qū)間。但是實數(shù)編碼后搜索區(qū)間連續(xù)，因此容易陷入局部最優(yōu)。

實數(shù)編碼DEAP實現(xiàn)：

from deap import base, creator, tools
import random
IND_SIZE = 5
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #優(yōu)化目標：單變量，求最小值
creator.create('Individual', list, fitness = creator.FitnessMin) #創(chuàng)建Individual類，繼承l(wèi)ist

toolbox = base.Toolbox()
toolbox.register('Attr_float', random.random)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)

ind1 = toolbox.Individual()
print(ind1)

# 結(jié)果：[0.8579615693371493, 0.05774821674048369, 0.8812411734389638, 0.5854279538236896, 0.12908399219828248]

這段代碼中用了random.random來產(chǎn)生隨機數(shù)，如果喜歡numpy的，也可以用np.random.rand代替，DEAP的靈活性還是很強的。

二進制編碼(Binary encoding)：在二進制編碼中，用01兩種數(shù)字模擬人類染色體中的4中堿基，用一定長度的01字符串來描述變量。其優(yōu)點在于種群多樣性大，但是需要解碼，而且不連續(xù)，容易產(chǎn)生Hamming cliff（例如0111=7, 1000=8，改動了全部的4位數(shù)字之后，實際值只變動了1），在接近局部最優(yōu)位置時，染色體稍有變動，就會使變量產(chǎn)生很大偏移（格雷編碼（Gray coding）能夠克服漢明距離的問題，但是實際問題復雜度較大時，格雷編碼很難精確描述問題）。

變量的二進制編碼：

由于通常情況下，搜索空間都是實數(shù)空間，因此在編碼時，需要建立實數(shù)空間到二進制編碼空間的映射。使用二進制不能對實數(shù)空間進行連續(xù)編碼，但是可以在給定精度下對連續(xù)空間進行離散化。

以例子來說明如何對變量進行二進制編碼，假設(shè)需要對一個在區(qū)間[-2, 2]上的變量進行二進制編碼：

選擇編碼長度：在需要6位精度的情況下，我們需要將該區(qū)間離散為個數(shù)。由于，我們至少需要22位二進制數(shù)字來滿足我們的精度要求。

設(shè)置解碼器：將二進制數(shù)字轉(zhuǎn)化為十進制之后（在python中可以用int('Binary number', 2)來實現(xiàn)），按照公式解碼，就可以得到一個在[-2,2]區(qū)間內(nèi)的實數(shù)。

二進制編碼DEAP實現(xiàn)：

以隨機生成一個長度為10的二進制編碼為例，本身DEAP庫中沒有內(nèi)置的Binary encoding，我們可以借助Scipy模塊中的伯努利分布來生成一個二進制序列。

from deap import base, creator, tools
from scipy.stats import bernoulli

creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #優(yōu)化目標：單變量，求最小值
creator.create('Individual', list, fitness = creator.FitnessMin) #創(chuàng)建Individual類，繼承l(wèi)ist

GENE_LENGTH = 10

toolbox = base.Toolbox()
toolbox.register('Binary', bernoulli.rvs, 0.5) #注冊一個Binary的alias，指向scipy.stats中的bernoulli.rvs，概率為0.5
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Binary, n = GENE_LENGTH) #用tools.initRepeat生成長度為GENE_LENGTH的Individual

ind1 = toolbox.Individual()
print(ind1)

# 結(jié)果：[1, 0, 0, 0, 0, 1, 0, 1, 1, 0]

序列編碼(Permutation encoding)：通常在求解順序問題時用到，例如TSP問題。序列編碼中的每個染色體都是一個序列。

序列編碼的DEAP實現(xiàn)：

from deap import base, creator, tools
import random
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

IND_SIZE=10

toolbox = base.Toolbox()
toolbox.register("Indices", random.sample, range(IND_SIZE), IND_SIZE)
toolbox.register("Individual", tools.initIterate, creator.Individual,toolbox.Indices)
ind1 = toolbox.Individual()
print(ind1)

#結(jié)果：[0, 1, 5, 8, 2, 3, 6, 7, 9, 4]

同樣的，這里的random.sampole也可以用np.random.permutation代替。

粒子(Particles)：粒子是一種特殊個體，主要用于粒子群算法。相比普通的個體，它額外具有速度、速度限制并且能記錄最優(yōu)位置。

粒子的DEAP實現(xiàn)：

import random
from deap import base, creator, tools

creator.create("FitnessMax", base.Fitness, weights=(1.0, 1.0))
creator.create("Particle", list, fitness=creator.FitnessMax, speed=None,
               smin=None, smax=None, best=None)

# 自定義的粒子初始化函數(shù)
def initParticle(pcls, size, pmin, pmax, smin, smax):
    part = pcls(random.uniform(pmin, pmax) for _ in range(size))
    part.speed = [random.uniform(smin, smax) for _ in range(size)]
    part.smin = smin
    part.smax = smax
    return part

toolbox = base.Toolbox()
toolbox.register("Particle", initParticle, creator.Particle, size=2, pmin=-6, pmax=6, smin=-3, smax=3) #為自己編寫的initParticle函數(shù)注冊一個alias "Particle"，調(diào)用時生成一個2維粒子，放在容器creator.Particle中，粒子的位置落在（-6,6）中，速度限制為（-3，3）

ind1 = toolbox.Particle()
print(ind1)
print(ind1.speed)
print(ind1.smin, ind1.smax)

# 結(jié)果：[-2.176528549934324, -3.0796558214905]
#[-2.9943676285620104, -0.3222138308543414]
#-3 3

print(ind1.fitness.valid)

# 結(jié)果：False
# 因為當前還沒有計算適應(yīng)度函數(shù)，所以粒子的最優(yōu)適應(yīng)度值還是invalid

3.初始族群的創(chuàng)建：

一般族群：這是最常用的族群類型，族群中沒有特別的順序或者子族群。

一般族群的DEAP實現(xiàn)：toolbox.register('population', tools.initRepeat, list, toolbox.individual)

以二進制編碼為例，以下代碼可以生成由10個長度為5的隨機二進制編碼個體組成的一般族群：

from deap import base, creator, tools
from scipy.stats import bernoulli

# 定義問題
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) # 單目標，最小化
creator.create('Individual', list, fitness = creator.FitnessMin)

# 生成個體
GENE_LENGTH = 5
toolbox = base.Toolbox() #實例化一個Toolbox
toolbox.register('Binary', bernoulli.rvs, 0.5)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Binary, n=GENE_LENGTH)

# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
toolbox.Population(n = N_POP)

# 結(jié)果：
# [[1, 0, 1, 1, 0],
# [0, 1, 1, 0, 0],
# [0, 1, 0, 0, 0],
# [1, 1, 0, 1, 0],
# [0, 1, 1, 1, 1],
# [0, 1, 1, 1, 1],
# [1, 0, 0, 0, 1],
# [1, 1, 0, 1, 0],
# [0, 1, 1, 0, 1],
# [1, 0, 0, 0, 0]]

同類群(Demes)：同類群即一個族群中包含幾個子族群。在有些算法中，會使用本地選擇(Local selection)挑選育種個體，這種情況下個體僅與同一鄰域的個體相互作用。

同類群的DEAP實現(xiàn)：

toolbox.register("deme", tools.initRepeat, list, toolbox.individual)

DEME_SIZES = 10, 50, 100
population = [toolbox.deme(n=i) for i in DEME_SIZES]

粒子群：粒子群中的所有粒子共享全局最優(yōu)。在實現(xiàn)時需要額外傳入全局最優(yōu)位置與全局最優(yōu)適應(yīng)度給族群。

粒子群的DEAP實現(xiàn)：

creator.create("Swarm", list, gbest=None, gbestfit=creator.FitnessMax)
toolbox.register("swarm", tools.initRepeat, creator.Swarm, toolbox.particle)

在算法迭代時，需要更新該輪迭代中最優(yōu)的位置和最優(yōu)適應(yīng)度。

進化算法各元素的DEAP實現(xiàn)（二）：評價

評價部分是根據(jù)任務(wù)的特性高度定制的，DEAP庫中并沒有預(yù)置的評價函數(shù)模版。

在使用DEAP時，需要注意的是，無論是單目標還是多目標優(yōu)化，評價函數(shù)的返回值必須是一個tuple類型。

來做一個簡單的例子：

from deap import base, creator, tools
import numpy as np
# 定義問題
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #優(yōu)化目標：單變量，求最小值
creator.create('Individual', list, fitness = creator.FitnessMin) #創(chuàng)建Individual類，繼承l(wèi)ist

# 生成個體
IND_SIZE = 5
toolbox = base.Toolbox()
toolbox.register('Attr_float', np.random.rand)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)

# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
pop = toolbox.Population(n = N_POP)

# 定義評價函數(shù)
def evaluate(individual):
  return sum(individual), #注意這個逗號，即使是單變量優(yōu)化問題，也需要返回tuple

# 評價初始族群
toolbox.register('Evaluate', evaluate)
fitnesses = map(toolbox.Evaluate, pop)
for ind, fit in zip(pop, fitnesses):
  ind.fitness.values = fit
  print(ind.fitness.values)

# 結(jié)果：
# (2.593989197511478,)
# (1.1287944225903104,)
# (2.6030877077096717,)
# (3.304964061515382,)
# (2.534627558467466,)
# (2.4697149450205536,)
# (2.344837782191844,)
# (1.8959030773060852,)
# (2.5192475334239,)
# (3.5069764929866585,)

進化算法各元素的DEAP實現(xiàn)（三）：配種選擇

1.DEAP內(nèi)置的選擇操作

DEAP的tools模塊中內(nèi)置了13種選擇操作，對全部選擇算子的描述可以參考官方文檔。

2.常用選擇操作介紹

下面簡單介紹一些常用的配種選擇操作：

錦標賽選擇：deap.tools.selTournament(individuals, k, tournsize, fit_attr = 'fitness')

錦標賽選擇顧名思義，就是模擬錦標賽的方式，首先在族群中隨機抽取tournsize個個體，然后從中選取具有最佳適應(yīng)度的個體，將此過程重復k次，獲得育種族群。tournsize越大，選擇強度(selection intensity)越高，在選擇之后留下的育種族群的平均適應(yīng)度也就越高。比較常用的tournsize是2。

下圖給出了由5個個體構(gòu)成的族群中進行一次tournsize為3的錦標賽選擇的過程。

錦標賽選擇

錦標賽選擇相比于輪盤賭選擇，通常能夠有更快的收斂速度，在實際場景中應(yīng)用較多。

輪盤賭選擇: deap.tools.selRoulette(individuals, k, fit_attr = 'fitness')

輪盤賭選擇是最常見的選擇策略，它可以看作是有放回的隨機抽樣。

在輪盤賭選擇中，每個個體被選中的概率與其適應(yīng)度函數(shù)成正比：

下圖給出了與前文同樣例子的輪盤賭選擇：

輪盤賭選擇

注意在適應(yīng)度可能為負數(shù)時，不適合用輪盤賭選擇。

在實際應(yīng)用中，很多文章都指出輪盤賭選擇的性能較差，在通常情況下都不如隨機抽樣選擇和錦標賽選擇。

隨機普遍抽樣選擇：deap.tools.selStochasticUniversalSampling(individuals, k, fit_attr = 'fitness')

隨機普遍抽樣選擇是一種有多個指針的輪盤賭選擇，其優(yōu)點是能夠保存族群多樣性，而不會像輪盤賭一樣，有較大幾率對重復選擇最優(yōu)個體。

在與前文相同的例子中使用隨機普遍抽樣選擇，設(shè)定指針數(shù)k為3，那么指針間距即為，如下圖所示：

隨機普遍抽樣選擇

NSGA-II 選擇：deap.tools.selNSGA2(individuals, k, nd = 'standard')

NSGA-II全稱為 Nondominated sorting genetic algorithm II，是Kalyanmoy Deb于2002年提出的。該方法解決了前代NSGA的三個痛點：計算復雜度高；缺少精英選擇；需要給定額外參數(shù)值。

在使用該函數(shù)時，需要注意族群中個體數(shù)量必須要比k值大，因為在該算法中，每個個體在返回的選擇列表中至多出現(xiàn)一次。

由于本文意在工程應(yīng)用，解釋復雜的算法非我本意，需要詳細了解該算法的同學可以參見這里，Deb教授在實驗室網(wǎng)站上也給出了算法的C語言實現(xiàn)。

此外，一些基于排序的選擇算法，如Linear ranking selection, Exponential ranking selection等，在DEAP中都沒有給出直接的函數(shù)，需要自己實現(xiàn)。

3.選擇操作代碼示例

這里我們接著評價那一節(jié)使用的代碼，加上常見的選擇操作：

from deap import base, creator, tools
import numpy as np
# 定義問題
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #優(yōu)化目標：單變量，求最小值
creator.create('Individual', list, fitness = creator.FitnessMin) #創(chuàng)建Individual類，繼承l(wèi)ist

# 生成個體
IND_SIZE = 5
toolbox = base.Toolbox()
toolbox.register('Attr_float', np.random.rand)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)

# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
pop = toolbox.Population(n = N_POP)

# 定義評價函數(shù)
def evaluate(individual):
  return sum(individual), #注意這個逗號，即使是單變量優(yōu)化問題，也需要返回tuple

# 評價初始族群
toolbox.register('Evaluate', evaluate)
fitnesses = map(toolbox.Evaluate, pop)
for ind, fit in zip(pop, fitnesses):
  ind.fitness.values = fit

# 選擇方式1：錦標賽選擇
toolbox.register('TourSel', tools.selTournament, tournsize = 2) # 注冊Tournsize為2的錦標賽選擇
selectedTour = toolbox.TourSel(pop, 5) # 選擇5個個體
print('錦標賽選擇結(jié)果：')
for ind in selectedTour:
  print(ind)
  print(ind.fitness.values)

# 選擇方式2: 輪盤賭選擇
toolbox.register('RoulSel', tools.selRoulette)
selectedRoul = toolbox.RoulSel(pop, 5)
print('輪盤賭選擇結(jié)果：')
for ind in selectedRoul:
  print(ind)
  print(ind.fitness.values)

# 選擇方式3: 隨機普遍抽樣選擇
toolbox.register('StoSel', tools.selStochasticUniversalSampling)
selectedSto = toolbox.StoSel(pop, 5)
print('隨機普遍抽樣選擇結(jié)果：')
for ind in selectedSto:
  print(ind)
  print(ind.fitness.values)
  
#結(jié)果：
#錦標賽選擇結(jié)果：
#[0.2673058115582905, 0.8131397980144155, 0.13627430737326807, 0.10792026110464248, 0.4166962522797264]
#(1.741336430330343,)
#[0.5448284697291571, 0.9702727117158071, 0.03349947770537576, 0.7018813286570782, 0.3244029157717422]
#(2.5748849035791603,)
#[0.8525836387058023, 0.28064482205939634, 0.9235436615033125, 0.6429467684175085, 0.5965523553349544]
#(3.296271246020974,)
#[0.5243293164960845, 0.37883291328325286, 0.28423194217619596, 0.5005947374376103, 0.3017896612109636]
#(1.9897785706041071,)
#[0.4038211036464676, 0.841374996509095, 0.3555644512425019, 0.5849111474726337, 0.058759891556433574]
#(2.2444315904271317,)
#輪盤賭選擇結(jié)果：
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)
#[0.5448284697291571, 0.9702727117158071, 0.03349947770537576, 0.7018813286570782, 0.3244029157717422]
#(2.5748849035791603,)
#[0.630305953330188, 0.09565983206218687, 0.890691659939096, 0.8706091807317707, 0.19708949882847437]
#(2.684356124891716,)
#[0.5961060867498598, 0.4300051776616509, 0.4512760237511251, 0.047731561819711055, 0.009892120639829804]
#(1.5350109706221766,)
#隨機普遍抽樣選擇結(jié)果：
#[0.2673058115582905, 0.8131397980144155, 0.13627430737326807, 0.10792026110464248, 0.4166962522797264]
#(1.741336430330343,)
#[0.4038211036464676, 0.841374996509095, 0.3555644512425019, 0.5849111474726337, 0.058759891556433574]
#(2.2444315904271317,)
#[0.630305953330188, 0.09565983206218687, 0.890691659939096, 0.8706091807317707, 0.19708949882847437]
#(2.684356124891716,)
#[0.40659881466060876, 0.8387139101647804, 0.28504735705240236, 0.46171554118627334, 0.7843353275244066]
#(2.7764109505884718,)
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)

進化算法各元素的DEAP實現(xiàn)（四）：變異

變異過程就是從父代的基因出發(fā)，進行操作，最終得到子代基因的過程。通常包括交叉(Crossover)和突變(Mutation)兩種操作。

1.DEAP內(nèi)置的交叉(Crossover)操作

2.常用交叉操作介紹

單點交叉：deap.tools.cxOnePoint(ind1, ind2)

最簡單的交叉方式，選擇一個切口，將兩條基因切開之后，交換尾部基因段。盡管該方法非常簡單，但是多篇文章指出，該算法在各種實驗中性能都被其他交叉算法吊打，因此算是一種不建議使用的loser algorithm，參考這里。

單點交叉

兩點交叉：deap.tools.cxTwoPoint(ind1, ind2)

用兩個點切開基因之后，交換切出來的基因段。

兩點交叉

均勻交叉：deap.tools.cxUniform(ind1, ind2, indpb)

指定一個變異幾率，兩父代中的每個基因都以該幾率交叉。

均勻交叉

部分匹配交叉：deap.tools.cxPartialyMatched(ind1, ind2)

部分匹配交叉主要用于序列編碼的個體，進行部分匹配交叉包括3個步驟：首先，選擇父輩1的一段基因，復制到子代中；其次，查找父輩2中同位置的基因段，選擇沒有被復制的基因，建立一個映射關(guān)系；最后，進行沖突檢查，如果基因有沖突，則通過建立的映射變換為無沖突的基因，保證形成的一對子代基因無沖突。我盡力用語言描述了一個例子：

PMX

PMX用語言形容起來比較困難，更具體的闡述可以參考這里。

當解決路徑規(guī)劃問題時，如果最優(yōu)sub-subrouine越長，PMX交叉后就越難在子代中保留。

有序交叉：deap.tools.cxOrdered(ind1, ind2)

順序交叉

混合交叉：deap.tools.cxBlend(ind1, ind2, alpha)

混合交叉由Eshelman和Schaffer在1993年提出，常見的混合交叉算子有與兩種，DEAP中內(nèi)置的是前者。其具體算法如下：

• 選擇兩個父代和
• 對基因，計算
• 在區(qū)間之間取隨機數(shù)
• 將該隨機數(shù)作為子代的片段，即

對于任意，混合交叉會擴張搜索空間，因此應(yīng)用于受到約束的變量時需要注意。有些研究認為時，搜索效果優(yōu)于其他值。

模擬二值交叉：deap.tools.cxSimulatedBinary(ind1, ind2, eta)

SBX是在1995年由Deb和Agrawal提出來的。二進制編碼有只能進行離散搜索，Hamming cliff等問題，而實數(shù)編碼盡管能在連續(xù)域上操作，但是搜索能力較弱（此處搜索能力定義為給定一對父輩，產(chǎn)生任意子代的幾率，可以用擴散系數(shù)表征）。模擬二值交叉試圖綜合二者的優(yōu)勢，在實數(shù)編碼上模擬二進制編碼的搜索特點。

參數(shù)越大，產(chǎn)生的子代與父代越接近；該參數(shù)越小，產(chǎn)生的子代越可能與父代差距較大。

作者認為SBX在較難的測試中，表現(xiàn)比BLX-0.5要更優(yōu)，尤其在多局部最優(yōu)問題中表現(xiàn)出色。更具體的測試可以參見原文。

SBX

Deb教授在2007年又提出了改進型：Self-adaptive SBX，對學術(shù)部分感興趣的可以參見這篇文章。

混亂單點交叉：deap.tools.cxMessyOnePoint(ind1, ind2)

混亂單點交叉源自一篇挺有意思的文章（本人猜測，未得到開發(fā)人員證實）。作者質(zhì)疑為何遺傳算法中的基因都是如此有序：長短一致，編碼方式整整齊齊，反而在自然界中這樣的規(guī)律并不多見。因而作者提出了Messy GA，在這篇文章中，他將交叉操作拆分為cut與splice。Messy Crossover與一般的單點交叉最大的不同在于序列長度不會保持，如下圖所示：

混亂單點交叉

3.交叉操作代碼示例

Talk is cheap，還是代碼走起。官方提示最好不要直接用父代進行交叉，因為有些交叉算法是in-place運算的，因此最好先復制，再進行交叉。具體見代碼：

from deap import base, creator, tools
import random
# 創(chuàng)建兩個序列編碼個體
random.seed(42) # 保證結(jié)果可復現(xiàn)
IND_SIZE = 8
creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))
creator.create('Individual', list, fitness = creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register('Indices', random.sample, range(IND_SIZE), IND_SIZE)
toolbox.register('Individual', tools.initIterate, creator.Individual, toolbox.Indices)

ind1, ind2 = [toolbox.Individual() for _ in range(2)]
print(ind1, '\n', ind2)
# 結(jié)果：[1, 0, 5, 2, 7, 6, 4, 3] 
# [1, 4, 3, 0, 6, 5, 2, 7]

# 單點交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxOnePoint(child1, child2)
print(child1, '\n', child2)
#結(jié)果：[1, 4, 3, 0, 6, 5, 2, 7] 
# [1, 0, 5, 2, 7, 6, 4, 3]
# 可以看到從第四位開始被切開并交換了

# 兩點交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxTwoPoint(child1, child2)
print(child1, '\n', child2)
# 結(jié)果：[1, 0, 5, 2, 6, 5, 2, 3] 
# [1, 4, 3, 0, 7, 6, 4, 7]
# 基因段[6, 5, 2]與[7, 6, 4]互換了

# 均勻交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxUniform(child1, child2, 0.5)
print(child1, '\n', child2)
# 結(jié)果：[1, 0, 3, 2, 7, 5, 4, 3] 
# [1, 4, 5, 0, 6, 6, 2, 7]

# 部分匹配交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxPartialyMatched(child1, child2)
print(child1, '\n', child2)
# 結(jié)果：[1, 0, 5, 2, 6, 7, 4, 3] 
# [1, 4, 3, 0, 7, 5, 2, 6]
# 可以看到與之前交叉算子的明顯不同，這里的每個序列都沒有沖突

# 有序交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxOrdered(child1, child2)
print(child1, '\n', child2)
# 結(jié)果：[5, 4, 3, 2, 7, 6, 1, 0] 
# [3, 0, 5, 6, 2, 7, 1, 4]

# 混亂單點交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxMessyOnePoint(child1, child2)
print(child1, '\n', child2)
# 結(jié)果：[1, 0, 5, 2, 7, 4, 3, 0, 6, 5, 2, 7] 
# [1, 6, 4, 3]
# 注意個體序列長度的改變

4.DEAP內(nèi)置的突變(Mutation)操作

5.常用突變操作介紹

高斯突變：tools.mutGaussian(individual, mu, sigma, indpb)

對個體序列中的每一個基因按概率變異，變異后的值為按均值為，方差為的高斯分布選取的一個隨機數(shù)。如果不希望均值發(fā)生變化，則應(yīng)該將設(shè)為0。

亂序突變：tools.mutShuffleIndexes(individual, indpb)

將個體序列打亂順序，每個基因位置變動的幾率由indpb給出。

位翻轉(zhuǎn)突變：tools.mutFlipBit(individual, indpb)

對個體中的每一個基因按給定對變異概率取非。

有界多項式突變：tools.mutPolynomialBounded(individual, eta, low, up, indpb)

多項式突變一般在多目標優(yōu)化的NSGAII算法中配合使用。其具體算法如下：

若，突變后的個體由下式計算可得：

其中參數(shù)服從多項式分布：

在具體計算時，首先在中以均勻分布取一個隨機數(shù)再按下式計算：

Deb教授建議的參數(shù)取之間的數(shù)字，當參數(shù)取的越小，那么突變后的結(jié)果離突變前越近，影響大約為級。

均勻整數(shù)突變：tools.mutUniformInt(individual, low, up, indpb)

對序列中的每一位按概率變異，變異后的值為中按均勻分布隨機選取的一個整數(shù)。

6.突變操作代碼示例

上代碼，和交叉選擇相同，如果想要保留父代作為參照，那么最好先復制，然后再進行變異：

from deap import base, creator, tools
import random
# 創(chuàng)建一個實數(shù)編碼個體
random.seed(42) # 保證結(jié)果可復現(xiàn)
IND_SIZE = 5
creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))
creator.create('Individual', list, fitness = creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register('Attr_float', random.random)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, IND_SIZE)

ind1 = toolbox.Individual()
print(ind1)
# 結(jié)果：[0.6394267984578837, 0.025010755222666936, 0.27502931836911926, 0.22321073814882275, 0.7364712141640124]

# 高斯突變
mutant = toolbox.clone(ind1)
tools.mutGaussian(mutant, 3, 0.1, 1)
print(mutant)
# 結(jié)果：[3.672658632864655, 2.99827700737295, 3.2982590920597916, 3.339566606808737, 3.6626390539295306]
# 可以看到當均值給到3之后，變異形成的個體均值從0.5也增大到了3附近

# 亂序突變
mutant = toolbox.clone(ind1)
tools.mutShuffleIndexes(mutant, 0.5)
print(mutant)
# 結(jié)果：[0.22321073814882275, 0.7364712141640124, 0.025010755222666936, 0.6394267984578837, 0.27502931836911926]

# 有界多項式突變
mutant = toolbox.clone(ind1)
tools.mutPolynomialBounded(mutant, 20, 0, 1, 0.5)
print(mutant)
# 結(jié)果：[0.674443861742489, 0.020055418656044655, 0.2573977358171454, 0.11555018832942898, 0.6725269223692601]

# 均勻整數(shù)突變
mutant = toolbox.clone(ind1)
tools.mutUniformInt(mutant, 1, 5, 0.5)
print(mutant)
# 結(jié)果：[0.6394267984578837, 3, 0.27502931836911926, 0.22321073814882275, 0.7364712141640124]
# 可以看到在第二個位置生成了整數(shù)3

進化算法各元素的DEAP實現(xiàn)（五）：環(huán)境選擇

環(huán)境選擇也就是重插入(Reinsertion)，在選擇、交叉和突變之后，得到的育種后代族群規(guī)模與父代相比可能增加或減少。為保持族群規(guī)模，需要將育種后代插入到父代中，替換父代種群的一部分個體，或者丟棄一部分育種個體。

重插入分為全局重插入(Global reinsertion)和本地重插入(Local reinsertion)兩種，后者只有在使用含有本地鄰域的算法時使用。常見的全局重插入操作有以下四種：

• 完全重插入(Pure reinsertion)：產(chǎn)生與父代個體數(shù)量相當?shù)呐浞N個體，直接用配種個體生成新一代族群。
• 均勻重插入(Uniform reinsertion)：產(chǎn)生比父代個體少的配種個體，用配種個體隨機均勻地替換父代個體。
• 精英重插入(Elitist reinsertion)：產(chǎn)生比父代個體少的配種個體，選取配種后代中適應(yīng)度最好的一些個體，插入父代中，取代適應(yīng)度較低的父代個體。
• 精英保留重插入(Fitness-based reinsertion)：產(chǎn)生比父代個體多的配種個體，選取其中適應(yīng)度最大的配種個體形成新一代族群。

通常來說后兩種方式由于精英保留的緣故，收斂速度較快，因此比較推薦。

DEAP中沒有設(shè)定專門的reinsertion操作，可以用選擇操作選擇中的selBest, selWorst,selRandom來對育種族群和父代族群進行操作。