文章目錄
-
-
- 一、簡介
- 二、算法流程
- 三、參數
- 四、代碼
- 五、參考資料
-
一、簡介
遺傳算法（Genetic Algorithm, GA）是模拟達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模拟自然進化過程搜尋最優解的方法。
遺傳算法以一種群體中的所有個體為對象，并利用随機化技術指導對一個被編碼的參數空間進行高效搜尋。其中，選擇、交叉和變異構成了遺傳算法的遺傳操作；參數編碼、初始群體的設定、适應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳算法的核心内容。
二、算法流程
遺傳算法和自然選擇的過程類似，在種群裡面進行繁衍，産生的下一代加入種群，并根據一定的條件淘汰掉部分個體，保持種群個數一定，然後繼續下一個循環，當循環次數達到界限或者種群中出現滿足要求的個體，停止循環。
遺傳算法的過程如下：
我們以資料集的特征選擇為例，講一下裡面的一些專有名詞。
- 參數編碼：一般二進制編碼用的稍微多一些，0表示特征沒有被選擇，1表示特征被選擇，一個解決方案會形成一個 1 ∗ n 1*n 1∗n的數組，其中n是資料集的特征數；
Genetic Algorithm遺傳算法整理 - 适應度函數（fitness function）：用于評價目前個體（特征選擇的方案）對環境的适應度（性能），用于在繁殖之後淘汰掉部分個體；
- 選擇操作：從種群中選擇用于繁衍的雙親，選擇的方法是輪盤賭(Roulette Wheel Selection)或者輪盤賭的變體。
- 交叉（crossover）操作：類似于染色體交換基因，如果使用二進制編碼，會有三種操作模式：（1）單點交叉（single）：比如用于繁衍的雙親是A和B，并且資料集有20個特征，那麼在數組裡随機選擇一個斷點，A的前半段和B的後半段組成下一代C，A的後半段和B的前半段組成下一代D；（2）多點交叉：和單點交叉類似，多個斷點；（3）均勻交叉（也稱一緻交叉，uniform）：兩個配對個體的每個基因座上的基因都以相同的交叉機率進行交換，進而形成兩個新個體；
- 變異（mutation）操作：以特征選擇為例，20個特征會形成一個 1 ∗ n 1*n 1∗n的數組，部分1的突變為0，部分0的突變為1；
百度百科對輪盤賭(Roulette Wheel Selection)的解釋比較清晰，示例如下：
若産生随機數為0.81，則6号個體被選中。
之前給同學講這個算法的時候，講了一個故事輔助了解。羊群共有30隻羊（初始化個體數pop_size），40隻羊交配産生20隻羊（40*0.5， c r o s s − r a t e ∗ p o p − s i z e cross_-rate*pop_-size cross−rate∗pop−size），新産生的20隻羊，每個都有可能突變（突變率），最後的60隻羊根據适者生存，保留40隻，重複這個過程就能選出40隻适應能力特别強的羊。
三、參數
遺傳算法裡面一般有以下參數：
- 疊代次數：算法結束的标準；
- 初始種群個體個數：有多少個方案可供選擇。如果太多，算法運作時間比較長；太少不一定能選出最好的結果；
- 交叉率：用于确定下一代的個數， c r o s s − r a t e ∗ p o p − s i z e = n u m − n e w − s o l u t i o n cross_-rate*pop_-size=num_-new_-solution cross−rate∗pop−size=num−new−solution；
- 突變率：主要是确定下一代個體是否産生突變，一般随機産生一個0-1之間的數和突變率比較，決定是否突變；
總結：遺傳算法好壞初始種群的選擇有很大關系，不一定能夠找到最佳方案。
四、代碼
代碼可以看這篇部落格遺傳算法詳解 附python代碼實作
這篇部落格在産生後代後，篩選種群并不是完全按照适應度大小選擇的，為了陷入局部最優，按照“适應度越高，被選擇的機會越高，而适應度低的，被選擇的機會就低”的原則進行了折中處理：
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]
這個對我的啟發比較大。
五、參考資料
【算法】超詳細的遺傳算法(Genetic Algorithm)解析
百度百科–Roulette Wheel Selection
百度百科–遺傳算法
利用 Python 實作 遺傳算法（GeneticAlgorithm）