本文將會展示如何通過一個簡短的 python 教程實現遺傳演算法，並會附錄一些有關遺傳演算法的起源與理論目標。

你可以依據構建遺傳演算法的所有工具隨意修改以下實現。對於每一步，有很多種可能的方案，請採取最合適的那個。

這裡是全部代碼的 GitHub 項目（https://github.com/NicolleLouis/geneticAlgorithm/blob/master/algoGenetic），以及其 gist 版本（https://gist.github.com/NicolleLouis/d4f88d5bd566298d4279bcb69934f51d）。

想要更深入？

下面是訓練、理解以及參加人工智慧與遺傳演算法競賽的其他支持清單。

網頁應用

BoxCar 是遺傳演算法的在線實例，目標是創建最有效的兩輪汽車。

HTML5 遺傳演算法 2D Car Thingy - 推薦 Chrome 瀏覽器（http://rednuht.org/genetic_cars_2/）

移動應用

通過這一應用，你會比以前請求更多。你不得不創建一個帶有關節、骨架、肌肉的生物體，接著演算法將會優化其動作以執行跳躍、奔跑、攀爬臺階及其他任務。

進化 - Google Play 上的安卓應用（https://play.google.com/store/apps/details?id=com.keiwando.Evolution）

DIY

最後但同樣重要的：編碼遊戲。這是一個連接眾多開發者的平臺。每月中有為時一週的競賽，你必須打造出最佳的人工智慧。冠軍幾乎無一例外地使用遺傳演算法，如果你覺得已準備充足，那麼深吸一口氣然後開始吧。

編碼遊戲與為了更好地編碼的編程挑戰賽（https://www.codingame.com/home）

附錄

我們如何打造好的人工智慧？一個天真的解決方案就是創建有一系列規則構成的「經驗性演算法」：「如果你遇到這些條件，就這麼執行。」我可以想像到通過這樣的足夠多的規則，就能再現自然智能。但工作量會異常大，最終方案將永遠無法使創建者滿意。花大把時間創造什麼卻得知其不可能做到完美會不會令人感到很沮喪？

為了避免這一點，我有了一個新想法。如果我捨棄直接的方案而選擇再現進化會怎麼樣。我可以創造第一條史前魚，將其放入適合進化的條件內，自由地向人類進化。這個想法被稱為「遺傳演算法」，我們將在下文中親自創建一個。因此，首先讓我們刷新我們的記憶，並試著理解達爾文的自然選擇理論。

這個理論很簡單：如果一個種羣想要興盛，它必須不斷提升自己，這被稱為適者生存。種羣的最優秀品質遺傳給後代。但是為了保持一些多樣性以及適應自然環境變異的情況，其他個體不能被遺忘。

從一代到下一代

這一演算法尤其擅長解決優化問題。

實例：揹包問題

揹包優化是一個經典的演算法問題。你有兩樣東西：一個大小一定的揹包（其承載的重量固定）和一系列不同重量和價值的盒子。目標是裝滿這個揹包使其價值最大化卻又不超出其最大承載重量。自 1972 年以來，這一直是一個著名的數學問題。遺傳演算法可以很好地解決這一問題，因為它本質上是一個帶有大量可能答案的優化問題。

揹包問題

為了親自測試這一演算法的工作原理，我們將用它解決一個簡單問題：如何破解同事的密碼。

演算法用 Python 3 實現。你可以下載 Windows 版或者使用 brew install python3 , sudo apt-get install python3 or sudo yum install python3 進行安裝。我建議你在 Jupyter notebook 中運行這一代碼（http://jupyter.readthedocs.io/en/latest/install.html）。(http://jupyter.readthedocs.io/en/latest/install.html%EF%BC%89%E3%80%82)

選擇一個適應度函數

當你決定創建一個遺傳演算法時，要做的第一件事情就是創建評估函數，用來評估樣本的成功：它將允許我們把種羣劃分為醜小鴨和白天鵝。區分的目標在於成功的樣本稍後將有更多機會被挑選為下一代。這看起來很簡單，所以不要被愚弄了。

我們的目標是什麼？破解密碼。因此我們函數的目標是把連續標記中的二值結果「失敗或成功」從 0 提升到 100。

這裡有一個最簡單的方案：

fitness score = (number of char correct) / (total number of char)

如此，一個帶有更大適合度結果的個體將比其他樣本更接近於成功。因此我們的適合度函數將會精確分類種羣。

創建個體

因此現在我們知道如何評估個體，但是又如何對其定義呢？這一部分確實需要一點技巧：目標是知道什麼是固定不變的規格參數表以及什麼是變數。

這裡與遺傳的對比很有幫助。DNA 實際上是由基因組成，而基因又來自不同的等位基因（該基因的不同版本）。因此你不得不創建你的種羣的 DNA。

在我們的情況中，個體是單詞（密碼的長度當然是相同的），每個字母是一個基因，字母的值是等位基因。在單詞「banana」中，「b」是第一個字母的等位基因。

這一創建的要點是什麼？現在我們知道每一個體保持良好形狀（一個帶有正確長度的單詞），但是種羣將會覆蓋每一種可能性（每個可能帶有這一長度的單詞）。

創建第一個種羣

現在，我們知道個體的規格參數表，以及如何評估其表現。我們必須開始嚴格意義上的「進化」。

要記住的主要一點是我們必須不能把種羣導向一個明顯很好的方案。我們必須使種羣儘可能寬廣，覆蓋儘可能多的可能性。第一個完美的種羣應該覆蓋每一個現有的等位基因。

因此，在我們的案例中，我們將創建由隨機字母組成的單詞。

從一代到下一代

為此，我們有兩件事要做：選擇我們當前代中的一個特定部分，並且要整合育種者孕育下一代。

1.育種者選擇

我們有很多選擇，但是你必須牢記兩點：目標是選擇前一代的最佳方案並且不把其他方案徹底放在一邊。危害是：如果你在演算法開始時只選擇好的方案，你將會很快向局部最小值而不是可能的最佳方案收斂。

我的方案是一方面選擇 N 更好的樣本（在我的代碼中，N = best_sample），另一方面選擇無需區分適合度的 M 隨機個體（M = lucky_few）。

[Image: file:///-/blob/BWPAAAbzWVB/L2nVyfUFN_Pnlc7GnBJntQ]

2.繁衍

我們繼續繁衍的生物類比。有性繁殖的目的是混合兩個個體的 DNA，我們這裡也在做同樣的事情。我們有兩個個體「Tom」和「Jerry」，他們的 DNA 由其等位基因定義。因此為了混合其 DNA，我們不得不混合字母。我挑選了一種最簡單的解決方案：對於孩童的每一個字母，隨機選擇「Tom」或「Jerry」的字母。

很明顯，父母「Tom」和「Jerry」並不會只生一個孩子，為了確保種羣數量穩定，你必須確定每對父母所生孩子的數量（0 代中的個體數量等於下一代中的個體數量）。

突變

最後一步是個體的自然變異。繁衍之後，每一個個體必須有一定概率查看 DNA 的輕微變化。這一操作的目的是防止演算法在局部極小值中受限。

為了選擇變異率，我參考了這篇文章的建議（http://www.sciencedirect.com/science/article/pii/089571779500035Z）。

推薦閱讀：
相關文章