首先參考下上篇博客：遺傳算法求解背包問題

1. 極大值問題

假設有一個函數z=ysin(x)+xcos(y)，圖形如下：

這時要求這個函數在x位于[-10,10]和y位于[-10,10]之間的最大值。

這時想象這是個地形圖，且這個地區無規律的放置很多人，有的在谷底，有的在半山腰，下面讓他們一代代生生不息的繁殖下去，凡是能爬的更高的就留下，按照這個思路走下去就有了遺傳算法的應用。

2. 應用遺傳算法

• 基因編碼：
  這里和背包問題的基因編碼不同，背包問題的基因編碼是離散的，而這里是連續的，但是在精度可允許的范圍內是可以使其離散化的。這里的[-10,10]范圍內如果取到小數點后三位的精度的話，就要把上述范圍分割成20001種取值。如果用二進制進行基因編碼應選用15位，即214=16384,215=32768，這里用第一位作為正負數的標志，剩下的14位作為具體數字的標識符，這樣15位的數字就成為了[-16383，0]，[0，16383]。最后，表示二進制的到實數值的函數H(x)定義如下：
  

  H(x)=?????????10?F(x)+11638410?F(x)?116384F(x)?0F(x)?0
  其中F(x)表示二進制到十進制的轉換。

• 設計初始群體：
  這里設計的初始群體每個染色體有兩條基因，分別是x和y，這兩條基因各有15個基因點，也就是有215個可能，隨機產生8組基因。

• 適應度計算：
  適應度在這個場景里用 z=ysin(x)+xcos(y) 即可。

• 產生下一代：
  這里用的是對應兩條染色體的x基因交叉組合，y基因交叉組合，還有就是一條基因的x和另一條染色體的y基因交叉組合，然后翻過來。這樣8組作為初始種群的大小就有C28=28種組合方式，而每種組合產生2個后代，那么實際上就產生56個染色體。

這里允許基因突變，對56個個體的適應度進行排序，只取出排名前8的個體。然后在8個個體中隨機找到2個個體，讓2個個體其中一個染色體x發生變異，而讓另一個個體y染色體發生變異。之后再兩兩重組，產生下一代。

這里要注意：染色體的斷開點的位置，理論上是隨機的，但是斷開點靠左對數值影響變化大，自變量的變化范圍也就大。反之亦然。還有就是基因變異的位置和斷開點的位置影響是一樣的，同樣是靠左影響大。

2. 代碼

# coding=utf-8 import random import math import numpy as np#極大值問題 #染色體 基因X 基因Y X = [[1, 000000100101001, 101010101010101],[2, 011000100101100, 001100110011001],[3, 001000100100101, 101010101010101],[4, 000110100100100, 110011001100110],[5, 100000100100101, 101010101010101],[6, 101000100100100, 111100001111000],[7, 101010100110100, 101010101010101],[8, 100110101101000, 000011110000111]]#染色體長度 CHROMOSOME_SIZE = 15#判斷退出(判斷最近3代的最大值如何變化) def is_finished(last_three):s = sorted(last_three)if s[0] and s[2] - s[0] < 0.01 * s[0]:return Trueelse:return False#初始染色體樣態 def init():chromosome_state1 = ['000000100101001', '101010101010101']chromosome_state2 = ['011000100101100', '001100110011001']chromosome_state3 = ['001000100100101', '101010101010101']chromosome_state4 = ['000110100100100', '110011001100110']chromosome_state5 = ['100000100100101', '101010101010101']chromosome_state6 = ['101000100100100', '111100001111000']chromosome_state7 = ['101010100110100', '101010101010101']chromosome_state8 = ['100110101101000', '000011110000111']chromosome_states = [chromosome_state1,chromosome_state2,chromosome_state3,chromosome_state4,chromosome_state5,chromosome_state6,chromosome_state7,chromosome_state8]return chromosome_states# 計算適應度 def fitness(chromosome_states):fitnesses = []for chromosome_state in chromosome_states:if chromosome_state[0][0] == '1': # 判斷正負號# 其中的int()函數把二進制表示成十進制x = 10 * (-float(int(chromosome_state[0][1:], 2) - 1)/16384) else:x = 10 * (float(int(chromosome_state[0], 2) + 1)/16384)if chromosome_state[1][0] == '1':y = 10 * (-float(int(chromosome_state[1][1:], 2) - 1)/16384)else:y = 10 * (float(int(chromosome_state[1], 2) + 1)/16384)z = y * math.sin(x) + x * math.cos(y) # 計算適應度#print x, y, zfitnesses.append(z)return fitnesses# 篩選 def filter(chromosome_states, fitnesses):# top 8 對應的索引值chromosome_states_new = []top1_fitness_index = 0for i in np.argsort(fitnesses)[::-1][:8].tolist():chromosome_states_new.append(chromosome_states[i])top1_fitness_index = ireturn chromosome_states_new, top1_fitness_index# 產生下一代 def crossover(chromosome_states):chromosome_states_new = []while chromosome_states:chromosome_state = chromosome_states.pop(0) # 彈出首個染色體，也就是遍歷所有的組合#print 'chromosome_state:',chromosome_statefor v in chromosome_states:pos = random.choice(range(8, CHROMOSOME_SIZE - 1))# 先是對應的交叉，再是相互交叉，得到的是兩條新的染色體chromosome_states_new.append([chromosome_state[0][:pos] + v[0][pos:], chromosome_state[1][:pos] + v[1][pos:]])chromosome_states_new.append([v[0][:pos] + chromosome_state[1][pos:], v[0][:pos] + chromosome_state[1][pos:]])return chromosome_states_new# 基因突變 def mutation(chromosome_states):n = int(5.0 / 100 * len(chromosome_states)) # 隨機找到群體里的2個個體進行變異處理print 'n:',nwhile n > 0:n -= 1chromosome_state = random.choice(chromosome_states)index = chromosome_states.index(chromosome_state)print 'index:',indexpos = random.choice(range(len(chromosome_state))) #print 'pos:',pos# 選擇基因斷開點的位置，也就是基因變異的位置，這里固定選擇0,1是為了加大數值變化范圍x = chromosome_state[0][:pos] + str(int(not int(chromosome_state[0][pos]))) + chromosome_state[0][pos+1:]y = chromosome_state[1][:pos] + str(int(not int(chromosome_state[1][pos]))) + chromosome_state[1][pos+1:]chromosome_states[index] = [x, y] # 得到新的染色體if __name__ == '__main__':chromosome_states = init() # 設計初始群體，每條染色體有x,y兩條基因，每個基因有15基因信息點last_three = [0] * 3 # 得到[0,0,0]last_num = 0n = 100while n > 0: # 循環100次n -= 1chromosome_states = crossover(chromosome_states)print 'len of crossover():',len(chromosome_states)mutation(chromosome_states) # 加入變異后的染色體組fitnesses = fitness(chromosome_states) # 適應度計算#print 'fitnesses:',fitnesseschromosome_states, top1_fitness_index = filter(chromosome_states, fitnesses)#print chromosome_states, top1_fitness_index#print chromosome_stateslast_three[last_num] = fitnesses[top1_fitness_index]print 'last_three:',last_threeprint fitnesses[top1_fitness_index]if is_finished(last_three):breakif last_num >= 2:last_num = 0else:last_num += 1print '---------%d-----------' % n

運行結果：

len of crossover(): 56 n: 2 index: 51 index: 18 last_three: [3.5925181502851835, 0, 0] 3.59251815029 ---------99----------- len of crossover(): 56 n: 2 index: 16 index: 1 last_three: [3.5925181502851835, 6.127668819486251, 0] 6.12766881949 ---------98----------- len of crossover(): 56 n: 2 index: 10 index: 35 last_three: [3.5925181502851835, 6.127668819486251, 8.896330026626941] 8.89633002663 ---------97----------- len of crossover(): 56 n: 2 index: 5 index: 4 last_three: [8.974057864608891, 6.127668819486251, 8.896330026626941] 8.97405786461 ---------96----------- len of crossover(): 56 n: 2 index: 12 index: 4 last_three: [8.974057864608891, 8.993358420730987, 8.896330026626941] 8.99335842073 ---------95----------- len of crossover(): 56 n: 2 index: 5 index: 6 last_three: [8.974057864608891, 8.993358420730987, 9.02454209561596] 9.02454209562

注意這里的收斂條件是：計算每一代的適應函數最大值，并判斷最近3代的最大值如何變化。如果最近3代的適應度函數比較，第一大（最大）的比第三大（最小）的增益小于1%，也即是增長很慢了，就判斷為收斂，這種收斂速度是很快的。當然這里可以采用其他的額參數和方法，可以繼續考究。。

3. 補充

多運行幾次可以發現有時得到的最大值不同，當然最大的才是正確的，其實這里是在繁殖下一代的時候又出現一次播散的情況，但是播散不均勻，導致趨向于錯誤峰值的種群表現良好，反而趨向于正確峰值的種群，這時可以采取的措施有：

• 初始種群擴大化
• 每一代的遴選增加名額

這兩種方法都可以讓找到最優解的概率大大增加

4. 筆記

Python int() 函數

int() 函數用于將一個字符串會數字轉換為整型。
用法：class int(x, base=10)

• x – 字符串或數字。
• base – 進制數，默認十進制。
• 返回整型數據

即是：如果base參數有說明，則x對應相應的進制，而輸出對應的是其十進制的整數。

參考：《白話大數據與機器學習》

總結

以上是生活随笔為你收集整理的遗传算法求解极大值问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。