基因遺傳算法是一種靈感源於達爾文自然進化理論的啟發式搜索算法。該算法反映瞭自然選擇的過程，即最適者被選定繁殖，並產生下一代。本文簡要地介紹瞭遺傳算法的基本概念和實現，希望能為讀者展示啟發式搜索的魅力。

如上圖（左）所示，遺傳算法的個體由多條染色體組成，每條染色體由多個基因組成。上圖（右）展示瞭染色體分割和組合的方式。

遺傳算法的概念

自然選擇的過程從選擇群體中最適應環境的個體開始。後代繼承瞭父母的特性，並且這些特性將添加到下一代中。如果父母具有更好的適應性，那麼它們的後代將更易於存活。迭代地進行該自然選擇的過程，最終，我們將得到由最適應環境的個體組成的一代。

這一概念可以被應用於搜索問題中。我們考慮一個問題的諸多解決方案，並從中搜尋出最佳方案。

遺傳算法含以下五步：

1. 初始化
2. 個體評價（計算適應度函數）
3. 選擇運算
4. 交叉運算
5. 變異運算

初始化

該過程從種群的一組個體開始，且每一個體都是待解決問題的一個候選解。

個體以一組參數（變量）為特征，這些特征被稱為基因，串聯這些基因就可以組成染色體（問題的解）。

在遺傳算法中，單個個體的基因組以字符串的方式呈現，通常我們可以使用二進制（1 和 0 的字符串）編碼，即一個二進制串代表一條染色體串。因此可以說我們將基因串或候選解的特征編碼在染色體中。

種群、染色體和基因

個體評價（計算適應度函數）

個體評價利用適應度函數評估瞭該個體對環境的適應度（與其它個體競爭的能力）。每一個體都有適應度評分，個體被選中進行繁殖的可能性取決於其適應度評分。適應度函數值越大，解的質量就越高。適應度函數是遺傳算法進化的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。

選擇運算

選擇運算的目的是選出適應性最好的個體，並使它們將基因傳到下一代中。基於其適應度評分，我們選擇多對較優個體（父母）。適應度高的個體更易被選中繁殖，即將較優父母的基因傳遞到下一代。

交叉運算

交叉運算是遺傳算法中最重要的階段。對每一對配對的父母，基因都存在隨機選中的交叉點。

舉個例子，下圖的交叉點為 3：

1ef76cb476d6de3351c49d75bd3cae15

父母間在交叉點之前交換基因，從而產生瞭後代。

8fd4d5e84900405dd6840af9feba38fe

父母間交換基因，然後產生的新後代被添加到種群中。

965a03b3cc75e212846bed879f54774e

變異運算

在某些形成的新後代中，它們的某些基因可能受到低概率變異因子的作用。這意味著二進制位串中的某些位可能會翻轉。

變異運算前後

變異運算可用於保持種群內的多樣性，並防止過早收斂。

終止

在群體收斂的情況下（群體內不產生與前一代差異較大的後代）該算法終止。也就是說遺傳算法提供瞭一組問題的解。

案例實現

種群的規模恒定。新一代形成時，適應度最差的個體凋亡，為後代留出空間。這些階段的序列被不斷重復，以產生優於先前的新一代。

這一迭代過程的偽代碼：