1、遺傳算法簡介
遺傳算法（Genetic Algorithm，GA）最早是由美國的 John holland于20世紀70年代提出，該算法是用于解決最優化問題的一種搜尋算法。它是模拟達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，通過數學的方式，利用計算機仿真運算，将問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。其本質是一種高效、并行、全局搜尋的方法，能在搜尋過程中自動擷取和積累有關搜尋空間的知識，并自适應地控制搜尋過程以求得最佳解。
2、問題引入
遺傳算法是用來解決最優化問題的，下面以求一個二進制函數在 x∈[−3,3]，y∈[−3,3] 範圍裡的最大值為例子來詳細講解遺傳算法的每一步。選取的二進制函數為：
def F(x,y):
return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)
将函數可視化，可視化代碼和運作結果如下：
%matplotlib notebook # 為使結果圖能旋轉，本次使用的編輯器為jupyter notebook
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams["axes.unicode_minus"] = False
def F(x,y):
return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)
x = np.arange(-3, 3, 0.01) # 可視化的 x 坐标範圍
y = np.arange(-3, 3, 0.01) # 可視化的 y 坐标範圍
# 生成 x-y 平面采樣網格點，友善可視化
X,Y = np.meshgrid(x,y)
Z = F(X,Y) # 計算網格點上的函數值
ax = plt.axes(projection='3d')
ax.plot_surface(X,Y,Z,cmap='rainbow') # 3D 曲面圖
ax.view_init(60, -30)
ax.set_xlabel('x')
ax.set_ylabel('y')
plt.show()
可以很容易發現函數在這個局部的最大值大概在當x ≈ 0 , y ≈ 1.5 時，函數值取得最大值，而這裡的 x , y 的取值就是我們最後想要得到的結果。
3、相關概念介紹以及實作代碼
為了更能友善了解遺傳算法，這裡需要引進幾組概念。
基因型(genotype)：性狀染色體的内部表現；
表現型(phenotype)：染色體決定的性狀的外部表現，或者說，根據基因型形成的個體的外部表現；
進化(evolution)：種群逐漸适應生存環境，品質不斷得到改良。生物的進化是以種群的形式進行的。
适應度(fitness)：度量某個物種對于生存環境的适應程度。
選擇(selection)： 以一定的機率從種群中選擇若幹個個體。一般，選擇過程是一種基于适應度的優勝劣汰的過程。
複制(reproduction)：細胞分裂時，遺傳物質DNA通過複制而轉移到新産生的細胞中，新細胞就繼承了舊細胞的基因。
交叉(crossover)：兩個染色體的某一相同位置處DNA被切斷，前後兩串分别交叉組合形成兩個新的染色體。也稱基因重組或雜交；
變異(mutation)：複制時可能（很小的機率）産生某些複制差錯，變異産生新的染色體，表現出新的性狀。
編碼(coding)：DNA中遺傳資訊在一個長鍊上按一定的模式排列。遺傳編碼可看作從表現型到基因型的映射。
解碼(decoding)：基因型到表現型的映射。
個體（individual）：指染色體帶有特征的實體；
種群（population）：個體的集合，該集合内個體數稱為種群的大小
3.1 種群和個體
遺傳算法是受進化理論啟發而形成的。進化是由種群為機關的，種群在生物學上是指在一定空間範圍内同時生活着的同種生物的全部個體。顯然要想了解種群的概念，又先得了解個體的概念。在遺傳算法裡，個體通常為某個問題的一個解，并且該解在計算機中被編碼為一個向量。例如，上面的例子中要求最大值，是以該問題的解為一組可能的 ( x , y ) 的取值。比如( x = 2.1 , y = 0.8 ) , ( x = − 1.5 , y = 2.3 ) . . . 就是求最大值問題的一個可能解，也就是遺傳算法裡的個體，把這樣的一組一組的可能解的集合就叫做種群。比如在這個問題中設定100個這樣的 x , y 的可能的取值對，那麼這100個個體就構成了種群。
3.2 編碼、解碼與染色體
在上面個體概念裡提到個體（也就是一組可能解）在計算機程式中被編碼為一個向量表示，而在我們這個問題中，個體是x , y 的取值，是兩個實數，是以問題就可以轉化為如何将實數編碼為一個向量表示，編碼是為了友善後續操作（交叉和變異）。在計算機中，将不同的實數用二進制串來表示就完成了編碼，解碼即為編碼的逆行為。将個體（可能解）編碼後的二進制串叫做染色體，染色體（或者有人叫DNA）就是個體（可能解）的二進制編碼表示。
遺傳算法中每一條染色體，對應着遺傳算法的一個解決方案，一般用适應性函數（fitness function）來衡量這個解決方案的優劣。是以從一個基因組到其解的适應度形成一個映射，可以把遺傳算法的過程看作是一個在多元函數裡面求最優解的過程。
3.3 适應度和選擇
遺傳算法是在得到一個種群後根據适者生存規則把優秀的個體儲存下來，同時淘汰掉那些不适應環境的個體。那麼，如何評價一個個體對環境的适應度？以求解上述函數最大值為例，這個衡量的标準比較容易制定：函數值的大小，即适應度函數直接傳回函數值就行了。即直接用可能解（個體）對應的函數的函數值的大小來評估，這樣可能解對應的函數值越大越有可能被保留下來。其求解函數最大值的python代碼如下：
def get_fitness(pop):
x,y = translateDNA(pop)
pred = F(x, y)
return (pred - np.min(pred)) + 1e-3 #減去最小的适應度是為了防止适應度出現負數，通過這一步fitness的範圍為[0, np.max(pred)-np.min(pred)],最後在加上一個很小的數防止出現為0的适應度
pred是将可能解帶入函數F中得到的預測值，因為後面的選擇過程需要根據個體适應度确定每個個體被保留下來的機率，而機率不能是負值，是以是以最後加上了一個很小的正數。有了求最大值的适應度函數，求最小值适應度函數也就容易了，python代碼如下:
def get_fitness(pop):
x,y = translateDNA(pop)
pred = F(x, y)
return (pred - np.max(pred)) + 1e-3
.
有了評估的适應度函數，則可以根據适者生存法則将優秀者保留下來了。選擇是根據新個體的适應度進行，但同時不意味着完全以适應度高低為導向（選擇 k 個适應度最高的個體，容易陷入局部最優解，因為單純選擇适應度高的個體将可能導緻算法快速收斂到局部最優解而非全局最優解，我們稱之為早熟）作為折中，遺傳算法依據原則：适應度越高，被選擇的機會越高，而适應度低的，被選擇的機會就低。常用的選擇方法――輪盤賭（Roulette Wheel Selection）選擇法。比如有5條染色體，他們所對應的适應度評分分别為：5，7，10，13，15，是以是以累計總适應度為：
則各個個體被選中的機率分别為：
可以想象一下，轉動輪盤，輪盤停下來的時候，指針會随機地指向某一個個體所代表的區域，很明顯，适應度評分越高的個體被選中的機率越大。
遺傳算法的選擇在python中使用choice實作，np.random.choice函數是numpy庫中用于生成随機樣本的函數。它可以從一個給定的數組中随機抽取樣本。該函數有三個必選參數: a、Size、p。其中a為數組，size為抽取樣本的個數，p為每個元素被抽到的機率。還有其他可選參數如replace、weights、random_state等。代碼如下：
def select(pop, fitness): # nature selection wrt pop's fitness
idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
p=(fitness)/(fitness.sum()) )
return pop[idx]
其中，參數p描述了從np.arange(POP_SIZE)裡選擇每一個元素的機率，機率越高約有可能被選中，最後傳回被選中的個體即可。
3.4 交叉、變異
通過選擇得到了目前看來“還不錯的基因”，但是這并不是最好的基因，需要通過繁殖後代（包含有交叉+變異過程）來産生比目前更好的基因，但是繁殖後代并不能保證每個後代個體的基因都比上一代優秀，這時需要繼續通過選擇過程來讓試應環境的個體保留下來，進而完成進化，不斷疊代上面這個過程種群中的個體就會一步一步地進化。具體地繁殖後代過程包括交叉和變異兩步。
交叉： 二進制編碼的基因交換過程非常類似高中生物中所講的同源染色體的聯會過程――随機把其中幾個位于同一位置的編碼進行交換，産生新的個體。每一個個體是由父親和母親兩個個體繁殖産生，子代個體的DNA（二進制串）獲得了一半父親的DNA，一半母親的DNA，但是這裡的一半并不是真正的一半，這個位置叫做交配點，是随機産生的，可以是染色體的任意位置。
變異： 通過交叉子代獲得了一半來自父親一半來自母親的DNA，但是子代自身可能發生變異，使得其DNA即不來自父親，也不來自母親，在某個位置上發生随機改變，通常就是改變DNA的一個二進制位（0變到1，或者1變到0）。例如下面這串二進制編碼：
101101001011001
經過基因突變後，可能變成以下這串新的編碼：
001101011011001
需要說明的是交叉和變異不是必然發生，而是有一定機率發生。先考慮交叉，最壞情況，交叉産生的子代的DNA都比父代要差（這樣算法有可能朝着優化的反方向進行，不收斂），如果交叉是有一定機率不發生，那麼就能保證子代有一部分基因和目前這一代基因水準一樣；而變異本質上是讓算法跳出局部最優解，如果變異時常發生，或發生機率太大，那麼算法到了最優解時還會不穩定。交叉機率，範圍一般是0.6~1，突變常數（又稱為變異機率），通常是0.1或者更小。對于這兩個機率，我們一般管叫“步長”。一般來說步長越大，開始時進化的速度會比較快，但是後來比較難收斂到精确的點上。而小步長卻能較精确的收斂到一個點上。是以很多時候為了加快遺傳算法的進化速度，而又能保證後期能夠比較精确地收斂到最優解上面，會采取動态改變步長的方法。這個過程與前面介紹的模拟退火過程比較相類似。
交叉和變異的實作代碼如下：
def crossover_and_mutation(pop, CROSSOVER_RATE = 0.8):
new_pop = []
for father in pop: #周遊種群中的每一個個體，将該個體作為父親
child = father #孩子先得到父親的全部基因（這裡我把一串二進制串的那些0，1稱為基因）
if np.random.rand() < CROSSOVER_RATE: #産生子代時不是必然發生交叉，而是以一定的機率發生交叉
mother = pop[np.random.randint(POP_SIZE)] #再種群中選擇另一個個體，并将該個體作為母親
cross_points = np.random.randint(low=0, high=DNA_SIZE*2) #随機産生交叉的點
child[cross_points:] = mother[cross_points:] #孩子得到位于交叉點後的母親的基因
mutation(child) #每個後代有一定的機率發生變異
new_pop.append(child)
return new_pop
def mutation(child, MUTATION_RATE=0.003):
if np.random.rand() < MUTATION_RATE: #以MUTATION_RATE的機率進行變異
mutate_point = np.random.randint(0, DNA_SIZE) #随機産生一個實數，代表要變異基因的位置
child[mutate_point] = child[mutate_point]^1 #将變異點的二進制為反轉
3.5 群體進化
上述步驟即為遺傳算法的核心子產品，将這些子產品在主函數中疊代起來，即實作種群進化，實作代碼如下：
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE*2)) #生成種群 matrix (POP_SIZE, DNA_SIZE)
for _ in range(N_GENERATIONS): #種群疊代進化N_GENERATIONS代
crossover_and_mutation(pop, CROSSOVER_RATE) #種群通過交叉變異産生後代
fitness = get_fitness(pop) #對種群中的每個個體進行評估
pop = select(pop, fitness) #選擇生成新的種群
4、遺傳算法流程
4.1 算法步驟
1.評估每條染色體所對應個體的适應度。
2.遵照适應度越高，選擇機率越大的原則，從種群中選擇兩個個體作為父方和母方。
3.抽取父母雙方的染色體，進行交叉，産生子代。
4.對子代的染色體進行變異。
5.重複2，3，4步驟，直到新種群的産生。
選擇的作用：優勝劣汰，适者生存；
交叉的作用：保證種群的穩定性，朝着最優解的方向進化；
變異的作用：保證種群的多樣性，避免交叉可能産生的局部收斂。
4.2 遺傳算法流程圖
。
5、完整代碼
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D
DNA_SIZE = 24
POP_SIZE = 200
CROSSOVER_RATE = 0.8
MUTATION_RATE = 0.005
N_GENERATIONS = 50
X_BOUND = [-3, 3]
Y_BOUND = [-3, 3]
def F(x, y):
return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)
def plot_3d(ax):
X = np.linspace(*X_BOUND, 100)
Y = np.linspace(*Y_BOUND, 100)
X,Y = np.meshgrid(X, Y)
Z = F(X, Y)
ax.plot_surface(X,Y,Z,rstride=1,cstride=1,cmap=cm.coolwarm)
ax.set_zlim(-10,10)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('z')
plt.pause(3)
plt.show()
def get_fitness(pop):
x,y = translateDNA(pop)
pred = F(x, y)
return (pred - np.min(pred)) + 1e-3 #減去最小的适應度是為了防止适應度出現負數，通過這一步fitness的範圍為[0, np.max(pred)-np.min(pred)],最後在加上一個很小的數防止出現為0的适應度
def translateDNA(pop): #pop表示種群矩陣，一行表示一個二進制編碼表示的DNA，矩陣的行數為種群數目
x_pop = pop[:,1::2]#奇數清單示X
y_pop = pop[:,::2] #偶數清單示y
#pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)
x = x_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(X_BOUND[1]-X_BOUND[0])+X_BOUND[0]
y = y_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(Y_BOUND[1]-Y_BOUND[0])+Y_BOUND[0]
return x,y
def crossover_and_mutation(pop, CROSSOVER_RATE = 0.8):
new_pop = []
for father in pop: #周遊種群中的每一個個體，将該個體作為父親
child = father #孩子先得到父親的全部基因（這裡我把一串二進制串的那些0，1稱為基因）
if np.random.rand() < CROSSOVER_RATE: #産生子代時不是必然發生交叉，而是以一定的機率發生交叉
mother = pop[np.random.randint(POP_SIZE)] #再種群中選擇另一個個體，并将該個體作為母親
cross_points = np.random.randint(low=0, high=DNA_SIZE*2) #随機産生交叉的點
child[cross_points:] = mother[cross_points:] #孩子得到位于交叉點後的母親的基因
mutation(child) #每個後代有一定的機率發生變異
new_pop.append(child)
return new_pop
def mutation(child, MUTATION_RATE=0.003):
if np.random.rand() < MUTATION_RATE: #以MUTATION_RATE的機率進行變異
mutate_point = np.random.randint(0, DNA_SIZE*2) #随機産生一個實數，代表要變異基因的位置
child[mutate_point] = child[mutate_point]^1 #将變異點的二進制為反轉
def select(pop, fitness): # nature selection wrt pop's fitness
idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
p=(fitness)/(fitness.sum()) )
return pop[idx]
def print_info(pop):
fitness = get_fitness(pop)
max_fitness_index = np.argmax(fitness)
print("max_fitness:", fitness[max_fitness_index])
x,y = translateDNA(pop)
print("最優的基因型：", pop[max_fitness_index])
print("(x, y):", (x[max_fitness_index], y[max_fitness_index]))
if __name__ == "__main__":
fig = plt.figure()
ax = Axes3D(fig)
plt.ion()#将畫圖模式改為互動模式，程式遇到plt.show不會暫停，而是繼續執行
plot_3d(ax)
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE*2)) #matrix (POP_SIZE, DNA_SIZE)
for _ in range(N_GENERATIONS):#疊代N代
x,y = translateDNA(pop)
if 'sca' in locals():
sca.remove()
sca = ax.scatter(x, y, F(x,y), c='black', marker='o');plt.show();plt.pause(0.1)
pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE))
#F_values = F(translateDNA(pop)[0], translateDNA(pop)[1])#x, y --> Z matrix
fitness = get_fitness(pop)
pop = select(pop, fitness) #選擇生成新的種群
print_info(pop)
plt.ioff()
plot_3d(ax)