【優化】遺傳演算法介紹
編者按:遺傳演算法是計算數學中用於解決最優化的搜索演算法，也是最為經典的智能演算法之一。日本新幹線N700系列車「氣動雙翼」的獨特空氣動力造型車鼻就是遺傳演算法運算結果。通過閱讀這篇文章，你將了解遺傳演算法的發展，優缺點以及實例求解過程。
文章作者：蘇向陽
責任編輯：張浩然文章發表於微信公眾號【運籌OR帷幄】：【優化】遺傳演算法介紹歡迎原鏈接轉發，轉載請私信@留德華叫獸獲取信息，盜版必究。敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：『運籌OR帷幄』大數據人工智慧時代的運籌學
1簡介
遺傳演算法（Genetic Algorithm, GA）來源於進化論和群體遺傳學，由美國的 Holland 教授於 1975 年在他的專著《自然界和人工系統的適應性》[1]中首先提出。遺傳演算法作為一種非確定性的擬自然演算法，為複雜系統的優化提供了一種新思路，對於諸多NP-Hard問題，遺傳演算法都有不錯的表現。相對於傳統演算法而言，遺傳演算法有以下突出優點[2,3]：
1. 可適用於灰箱甚至黑箱問題；
2. 搜索從群體出發，具有潛在的並行性；
3. 搜索使用評價函數（適應度函數）啟發，過程簡單；
4. 收斂性較強。
5. 具有可擴展性，容易與其他演算法（粒子群、模擬退火等）結合。
遺傳演算法的不足[4]:
1. 演算法參數的選擇嚴重影響解的品質,而目前這些參數的選擇大部分是依靠經驗；
2. 遺傳演算法的本質是隨機性搜索，不能保證所得解為全局最優解；
3.遺傳演算法常見的編碼方法有二進位編碼、Gray編碼等。二進位編碼比較常見，但是二進位編碼容易產生漢明距離注1（Hamming Distance），可能會產生漢明懸崖注2(Hamming Cliff），Gray可以克服漢明懸崖的問題，但是往往由於實際問題的複雜度過大導致Gray編碼難以精確地描述問題。
4.在處理具有多個最優解的多峰問題時容易陷入局部最小值而停止搜索，造成早熟問題，無法達到全局最優。
注1：將一個字元串變換成另外一個字元串所需要替換的字元個數
注2：相鄰整數的二進位編碼之間存在漢明距離，交叉和遺傳難以跨越
2演算法的發展與重心
經過多年的發展，遺傳演算法的研究熱點及發展方向可以由圖1進行展示[5]：
遺傳演算法的搜索核心是遺傳運算元的選擇，因此對於遺傳演算法的研究，其中最常見的內容與方向是遺傳運算元，遺傳運算元的選擇多樣性也導致了演算法表現的多樣性，常見的選擇方式如圖2所示：
遺傳演算法作為一種搜索演算法，在諸多領域均有很好的表現[6]，如函數優化、組合優化、生產調度、自動控制、機器學習、圖像處理、人工生命、遺傳編程、機器學習、數據挖掘等。
3實例說明
為了更通俗地理解遺傳演算法，下面將通過一些實例進行描述：
如果想在一座連綿的大山上找到其最高點，正常情況下你需要爬遍整座山才可以找到最高峰，但大多數的智能演算法並不需要搜索整個山峰，不同的智能演算法有不同的求解思路，舉幾個簡單例子：
1. 爬山演算法（也稱為貪心演算法）。假設有一隻猴子從山的任意一點出發，當它爬到第一個高峰值點的時候便停止前進，並認為當前的山峰為整座山最高的點。這種情況下，運氣好可能會到達最高點，但是大概率情況下都不會是最高點。
2. 模擬退火演算法。假設有一隻神志不清的猴子，當它爬到山峰的時候，它有一定的概率繼續出發，也有概率停止前進。這種情況下它也有可能通過有限的時間找到整座山的最高點。
3. 遺傳演算法。假設山上有一群猴子，猴子生存的食物只有在山峰處才有，而且山峰越高食物量越充裕。那麼這些猴子為了生存，會不斷聚集在各個山頭上進行生存繁衍，而這些山峰可以理解為各種局部最優解（圖3中類似綠色和藍色的地方），如果種群規模足夠大，勢必會有一群猴子聚集在了整座山的最高點，也就是全局最優解（圖3中紅色位置）。
基於以上三種演算法的描述，我們可以對智能演算法有一個簡單的了解：無論是哪種演算法，都具有一定的隨機性，都不能保證最終選擇的山峰為整座山的最高點。但是在實際生活中，有諸多類似的問題，如果要考慮所有的情況可能會花費大量的時間，而恰巧我們並不需要一個最好的結果，我們只需要快速找到一個相對較好的結果便可以滿足要求的時候，智能演算法的意義便得到了體現。
通俗了解後，雖然心裡有大概思路，但還是雲里霧裡，這個時候我們可以考慮結合一些實際的例子來理解遺傳演算法。
3.1經典問題（0-1背包問題）
問題描述：假設一個你有一個可以裝五公斤重的背包，現在地上有三塊重金屬A、B、C供你挑選，重量分別為1公斤、2公斤、3公斤，價值分別為1萬元、5萬元、10萬元。為了使得總體收益最大，應該選擇哪些金屬塊裝入背包。
問題分析：這種規模的問題我們可以直觀看出最優解為，選擇B、C帶走可以獲得最大收益。但當問題規模擴大十倍百倍的時候，我們就必須要藉助計算機來進行求解了。
下面分別以三種演算法為例進行說明：
1. 爬山演算法。初始點不確定，背包放不下就放手。
假設第一步選擇A金屬，有如下情況：A→B→C（保留AB），A→C→B（保留AC）；假設第一步選擇B金屬，有如下情況：B→A→C（保留BA），B→C→A（保留BC）；假設第一步選擇C金屬，有如下情況：C→A→B（保留CA），C→B→A（保留CB）；
可以看出，一共六種情況下，只有兩種情況（選擇BC）是可以得到最好結果的。側面說明了爬山演算法具有很大的不確定性。
2. 模擬退火演算法。 模擬退火與爬山最大的不同就是，每次拿到金屬塊的時候我們有一定的概率來決定是否將這塊金屬放入背包。我們假設這個概率為0.5（幾乎所有的智能演算法都需要提前設定初始參數，而不同的初始參數對求解結果及求解效率的影響非常大。）每次拿到金屬塊都有0.5的概率保留或者選擇下一塊，當執行足夠多的次數後總能得到結果，結果雖然不一定是最好的，但整體隨機性更大，當問題規模較大的時候更有可能選出最優解。
3. 種群遺傳演算法。初始隨機產生100個15位2進位變數（每3位分別對應A、B、C，0為不取，1為取）。其中111為不可能的情況，設定這種基因片段不能繁衍下一代。
總生存力為五個基因片段之和，設定第一個位置出現1則生存力加0.01，第二個位置出現1則生存力加0.05，第三個位置出現1則生存力加0.1。則a為0；b1、b2和b3分別為0.1、0.05和0.01。c1、c2和c3分別為0.06、0.11和0.15。
生存力越高則生存率越高，依據輪盤賭選擇策略（生成隨機數，落在生存率區間選擇相應的個體），選擇遺傳下一代的個體。
生存率=個體生存力/總生存力。
選擇方法：隨機生成6個0-1的數，根據落在哪裡選對應的個體。
表1表2分別表示了種群的選擇和遺傳。
由於問題簡單，規模較小，一次遺傳之後便可以得出很明顯的結果：種群中留有大量的011基因，即選擇BC的結果。但是當問題規模擴大十倍百倍的時候往往需要多次迭代才會有明顯的區分度。
另一方面，如果種群陷入了100與100的配對循環，那麼這種情況下，永遠不可能得出最好的情況011，這個時候需要對基因的某一段進行變異，將100變異為101或110，種群就會出現更優的基因型。但是在實際問題中變異不一定是向好的方向發展，也有可能會出現更壞的結果。
總的來說，遺傳演算法的選擇充滿了不確定性。但是當你設定無窮大的種群規模，足夠長的繁衍時間後，最終總會達到最優，但是時間也會成倍上升。
適應度的概念在遺傳演算法中表示為個體趨近於最優解的程度，適應度越高遺傳到下一代的概率就越大。上述的例子中，我們自己選擇了適應度函數（生存力），在日常建模的時候，生存力函數可以是目標函數，也可以自己選擇。在演化計算中，某些特殊運算元的選擇方式（例如這裡的輪盤賭選擇）要注意兩點[7,8]：1.適應度必須非負;2.優化過程中目標函數的變化方嚮應與群體進化過程中適應度函數變化方向一致。
但在諸多大規模非凸非線性問題的求解時，上述觀點不再適用。
結語
雖然遺傳演算法有著一定的弊端和不足，但是遺傳演算法在諸多領域還是有著很不錯的表現並已經運用到實際生活中。為了不斷適應各種問題，近年來不斷有學者提出改進策略，以使遺傳演算法有更廣泛的應用領域。
參考文獻：
[1] HOLLAND J H． Adaptation in natural and artificial systems: an introductory analysis with applications to biology，control，and artificial intelligence［M］．2nd ed．Cambridge: MIT Press，1992．
[2]葛繼科,邱玉輝,吳春明,蒲國林.遺傳演算法研究綜述[J].計算機應用研究,2008(10):2911-2916.
[3]雷德明.多維實數編碼遺傳演算法[J].控制與決策,2000(02):239-241.
[4]臧文科. DNA遺傳演算法的集成研究與應用[D].山東師範大學,2018.
[5]馬永傑,雲文霞.遺傳演算法研究進展[J].計算機應用研究,2012,29(04):1201-1206+1210.
[6]吉根林.遺傳演算法研究綜述[J].計算機應用與軟體,2004(02):69-73.
[7] Nix A E , Vose M D . Modeling genetic algorithms with Markov chains[J]. Annals of Mathematics & Artificial Intelligence, 1992, 5(1):79-88.
[8]楊新武,楊麗軍.基於交叉模型的改進遺傳演算法[J].控制與決策,2016,31(10):1837-1844.
文章由『運籌OR帷幄』原創發布
如需轉載請在公眾號後台獲取轉載須知
掃二維碼關注『運籌OR帷幄』公眾號：
點擊查看『運籌OR帷幄』志願者招募介紹及加入方式：
推薦閱讀：
