今天介紹另外一種樸素仿生學算法，遺傳算法。聽上去好像好高大上的樣子，與生物、基因相關，其實思想非常簡單，就是參考生物進化過程，模擬染色體DNA的交叉（染色體段的交換）和變異（基因突變就是在基因複製的時候某個鹼基的密碼發生變化如應該是A結果變成了T或者其他類型的鹼基，鹼基有ATCG四種）來生成不同的種群，用適應性函數（模擬環境篩選作用）來篩選出較好的子代，然後不斷重複迭代這個過程直至達到最優。
遺傳算法核心就是要確定適應函數如何設計、子代如何選擇。適應性函數往往是從問題中綜合而來，可以假設為已知。而子代的選擇規則可以用樸素的概率論的思想表達。即適應性越強的子代，存活的概率越高（子代生存概率=子代適應性/所有子代適應性之和），求作為概率最大的子代進化（適應性函數是根據問題設計的，可以視為已知）。
但只考慮用適用性作為篩選標準會遇到陷入局部最大的問題，引入多樣性評價可以解決這個問題（多樣性評價，就是在適應性選擇後用子代之間的差異最優為標準選擇下一個子代。
不少問題都可以用上述思想來建模，例如一個計劃包括了N個環節，求最優的計劃。每個環節都可以看成為一個鹼基（ATCG），通過遺傳算法來求最優計劃，變異意味著鹼基序列發生變化如A-T/C/G，象徵著基因位點的突變，而環節的交換可以看作染色體交換，適應性函數可以看作計劃性能，通過進化（迭代若干次）得到最優計劃。
分享到:
閱讀更多 老郭講算法 的文章
