由 chrisname 釋出

2013年6月21日 (最後更新: 2013年6月23日)

評分: 3.6/5 (210票)

什麼是遺傳演算法？

遺傳演算法是進化演算法的一個子集；它們是受生物學啟發的搜尋啟發式演算法，用於尋找已知預期結果的問題的解決方案。遺傳演算法試圖為問題找到最佳的候選解決方案。該解決方案通常是正確解決方案的近似值，尤其是在無法獲得精確解、難以處理（需要無限時間或資源）或根本不需要精確解的問題中。這些演算法透過“進化”解決方案來工作。

遺傳演算法如何工作？

遺傳演算法透過構建一組初始的隨機潛在解決方案來工作。從中選擇一部分用於“繁殖”，以產生新的潛在解決方案，這些新解決方案隨後成為新種群。此過程一直持續，直到滿足某些終止條件。這些條件可能包括找到一個“足夠好”（即使不是精確）的解決方案、種群沒有改進（收斂）、達到設定的最大代數（即新種群）或達到設定的計算時間和資源限制。

由此，我們可以提取三個步驟

1. 初始化 - 建立 N 個隨機候選解決方案的初始種群（其他更生物學的術語是“個體”、“生物體”或“染色體”）
2. 再生 - 從上一個種群中建立一個新種群
3. 退出（滿足終止條件後）- 返回迄今為止找到的最佳解決方案，演算法停止執行

再生有三個子步驟

1. 選擇 - 從種群中透過演算法選擇一部分種群
2. 重組（也稱為“交叉”）- 將選定的個體組合起來以產生新的個體
3. 變異 - 對新的個體（“後代”）進行變異以增加遺傳多樣性

初始化

隨機建立 N 個解決方案的初始種群。通常，解決方案被編碼為一系列位元（二進位制數字）。這些可以被認為是類似於構成真實 DNA 基因的基本配對，儘管真實基因由基本配對的三聯體組成，每個三聯體有四種可能的“值”（核苷酸 - 腺嘌呤、胞嘧啶、鳥嘌呤和胸腺嘧啶（在 RNA 中，胸腺嘧啶被尿嘧啶取代））而我們的位元只有兩種——0 或 1。此外，在生物學中，染色體是 DNA 的纏繞鏈，包含許多基因；然而，在我們的術語中，染色體將僅指一系列位元。解決方案的“DNA”稍後可以解碼。通常 N 的值在幾百到幾千之間。初始值 1,000 是可以接受的，之後可以進行調整。

再生

選擇

在選擇過程中，使用選擇演算法從種群中選擇一部分種群——通常是兩個解決方案，當然也可以使用更多（一些研究表明使用兩個以上的父代可以產生更高質量的後代）。一個例子稱為適應度比例選擇，或輪盤賭選擇。在此演算法中，個體以基於其適應度的機率隨機選擇，適應度是一個值，表示該個體距離成為有效解決方案有多近（通常，該值介於 0 和 1 之間）。適應度函式將在稍後詳細討論。每次 FPS 迭代返回一個單獨的個體，因此該演算法可以應用多次以獲得所需的父代數量。更簡單的選擇演算法包括截斷選擇，即選擇種群的最佳一半、三分之一或其他分數，以及錦標賽選擇，即從種群的隨機子集中選擇最佳個體。另一種更復雜但更公平的演算法稱為隨機通用取樣，它是 RWS 的修改版本，其中解決方案均勻分佈，因此較弱的解決方案（即適應度函式值較低的解決方案）有公平的機會被選中（儘管演算法仍然普遍選擇更高的適應度）。允許選擇較弱解決方案的好處是，較弱的解決方案可能只是對更強的解決方案進行微小修改，而只允許選擇最適合的解決方案可能會導致解決方案遺傳多樣性不足。

重組

在重組中，選擇的解決方案進行交叉以建立新的解決方案，儘管通常存在發生的機率；例如，70%。這種交叉的概念也取自生物學：在減數分裂（導致四個基因不同的細胞的細胞分裂）過程中，相應的父（來自父親）和母（來自母親）染色體會聚集在一起，並可能交換基因（交叉）。在遺傳演算法中，這個過程透過多種方式進行模擬。最簡單的方法是單點交叉，即選擇染色體中的一個隨機位置，然後將該點之後的所有內容與另一條染色體交換。其他方法更復雜，但可能產生更高質量的後代和更多的遺傳多樣性。

變異

交叉發生後，變異可能以非常小的機率（每個位元約 0.1%）發生。在變異中，遍歷染色體，每個位元都可能根據小機率被翻轉。這類似於細胞分裂過程中偶爾發生的替換突變。除了簡單地翻轉位元，還可以前置、插入、追加和/或刪除它們，這相當於生物學中的插入和刪除突變。透過這種方式，進一步增加了遺傳多樣性。

關於編碼和解碼

如前所述，遺傳演算法中的染色體通常被編碼為一系列位元。一組位元——一個基因——可以代表字串中的一個字元，例如，如果要生成字串“hello world”，字母 h 可能由二進位制數 000 表示，e 由 001 表示，l 由 010 表示，o 由 011 表示，空格由 100 表示，w 由 101 表示，r 由 110 表示，d 由 111 表示。最終，人們會希望偶然發現序列 000,001,010,010,011,100,101,011,110,010,111，這對應於字串“hello world”。像這樣編碼資料的絕妙之處在於，遺傳演算法可以非常通用地編寫——任何具有適應度函式、交叉函式和變異函式的物件都可以使用，並且演算法永遠不需要知道實現細節。通常解碼會在兩個階段進行：一次在需要計算適應度函式時，一次在想要顯示遺傳演算法輸出時。

到底什麼是適應度函式？

我多次提到了適應度函式，但沒有真正解釋它們是什麼。簡單來說，它們衡量個體的適應度，即它接近解決所需問題的程度。產生此結果的計算是高度領域特定的，儘管通常需要一個介於 0 和 1 之間的值。在我們“hello world”的例子中，適應度函式可能會將二進位制序列解碼為 ASCII 字串，然後將其與作為所需輸出提供的 ASCII 字串進行比較。兩者之間的差異然後轉換為 0 到 1 之間的數字，如下所示：1/(y - x) – 其中 y 是期望的解決方案，x 是解碼結果。

待辦事項

• 選擇演算法的虛擬碼實現
• 交叉演算法的虛擬碼實現
• 變異演算法的虛擬碼實現
• 通用遺傳演算法類的骨架結構