利用達爾文的理論學習遺傳演算法

選自sicara

機器之心編譯

參與：黃小天、路雪

本文藉助生物學中達爾文的進化理論來介紹遺傳演算法，並展示了通過簡短的 Python 教程實現遺傳演算法的案例。

在本文中，我將會解釋遺傳演算法的概念。首先，我會介紹它的起源與目標。接著，我會展示如何通過一個簡短的 Python 教程實現它。

所以，問題就是：我們如何打造好的人工智慧？

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

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

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

從一代到下一代

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

實例：背包問題

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

背包問題

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

該演算法用 Python 3 實現。你可以下載 Windows 版或者使用 brew install python3 、sudo apt-get install python3 或 sudo yum install python3 進行安裝。我建議你在 Jupyter notebook 中運行這一代碼。

選擇一個適應度函數

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

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

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

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

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

創建個體

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

此處，將其比作遺傳會有一定幫助。DNA 實際上是由基因組成，而基因又來自不同的等位基因（該基因的不同版本）。因此你不得不創建你的種群的 DNA。

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

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

創建第一個種群

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

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

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

從一代到下一代

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

育種者選擇

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

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

繁衍

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

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

突變

最後一步是個體的自然突變。繁衍之後，每一個個體都存在一定的概率：DNA 發生輕微改變。這一操作的目的是防止演算法在局部極小值中受限。

現在，你有了構建遺傳演算法的所有工具。請隨意修改我的實現。每一步都有很多種可能的方案，請採取最合適的那個。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！