科學計算之遺傳算法python實作☞1
- 遺傳算法
-
- 染色體編碼和種群初始化
- 适應度和選擇
- 選擇交配
- 選擇變異
- 代碼主體
- 目标函數
- 運作效果
版權聲明：本文為威哥哥帶你寫代碼原創文章，有錯請評論，轉載請注明，謝謝
遺傳算法
遺傳算法是一種随機自适應的随機搜尋算法，從一定程度上反應了達爾文的進化理論"自然選擇"和“優勝劣汰”，算法流程并不複雜，大緻分為6個部分，分别是染色體編碼，種群初始化，适應度評價，選擇種群，交配，變異。其中染色體編碼相對來說比較複雜，需要将十進制轉化為相應的二進制，其中針對不同的精确度需要分析不同的二進制位數，本文主要針對次元為1的函數進行優化，針對高維函數的代碼将在下一篇文章中展示。
染色體編碼和種群初始化
部落客這裡的精确度取的0.001，定義域【0，5】，是以需要10個二進制位，種群數量取的100，是以需要生成100個長度為10的二進制編碼。
初始化：
def initialize():
pop=np.random.randint(2,size=(100,10))
return pop
這裡我們可以看看種群（部分）
array([[0, 1, 1, 0, 1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 0, 1, 0, 0, 0, 1],
[0, 1, 1, 1, 1, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 1, 0, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 1, 0, 1, 0, 1],
[0, 1, 0, 0, 0, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 1, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 1, 0, 1, 1, 0],
[1, 1, 1, 0, 0, 1, 1, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 1, 0, 1, 0],
[1, 1, 1, 1, 0, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 0],
[1, 1, 0, 0, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1, 1],
........
如果相應的個體不再定義域内部怎麼辦？這裡就需要用等分的思想稍微轉化一下
pop.dot(2**np.arange(10)[::-1])/float(2**10-1)*5
其中5是定義域的長度，等分成2^10-1分，然後乘對應的大小就完成了轉換。
适應度和選擇
适應度的評估函數用于評估每個染色體的适應值，用于進行優勝劣汰的自然選擇，每個染色體的适應度為F（xi）/sum（F（xi））；對應的适應度越大則在自然選擇過程中的機率也越大。
def fitness(pop):
for i in range(100):
pop[i]=F(pop[i])
if pop[i]<0:
pop[i]=0
return pop
def selection(pop,fit,sum_fitness):
i = np.random.choice(np.arange(100), size=100, replace=True, p=fit/sum_fitness)
其中np.random.choice()的用法在這裡不做解釋，請自行百度。
關于
if pop[i]<0: pop[i]=0
這裡是因為後面要算适應度，适應度也即個體被選擇的機率，不應該小于0，是以将小于0的元素全部換成0代替。
選擇交配
首先這裡需要設定一個種群交配機率，部落客設定的為0.8，被選擇的種群還需要選擇交換的DNA片段，這裡關于DNA的交換片段可以根據1/2原則進行設定，這裡用的是生成0 1随機數然後轉化成bool型實作的。
def crossover(parent,pop):
if np.random.rand()<0.8:
i= np.random.randint(0, 100, size=1) #選擇母體進行交配
point=np.random.randint(0,2,size=10).astype(np.bool)
parent[point]=pop[i,point]
return parent
選擇變異
和交配一樣，首先設定一個變異的機率，然後針對不同的個體進行每一個染色體中DNA片段的等機率變異，這裡的變異機率設定為0.03
def mutation(m):
for i in range(10):
if np.random.rand()<0.003:
if m[i]==1:
[i]=0
else:
[i]=1
return m
代碼主體
代碼總體部分非常簡單，設定一個循環即可搞定。流程圖為
pop=selection(pop,fit,sum(fit))
pop_copy = pop.copy()
for parent in pop:
m = crossover(parent,pop_copy)
m = mutation(m)
目标函數
def F(x):
y=5*x+5*np.sin(5*x)+2*np.cos(3*x)
return y
運作效果
可以看見是逐漸向最大值移動的，雖然效率有待提高，不是最終可以針對多為函數的代碼版本，這裡就不放完整代碼了，需要的可以評論留郵箱。