遺傳算法（Genetic Algorithm, GA）是一種進化計算（Evolutionary Computing）算法，屬于人工智能技術(shù)的一部分稿械。遺傳算法最早是由John Holland和他的學(xué)生發(fā)明并改進的浙芙，源于對達芬奇物種進化理論的模仿。在物種進化過程中，為了適應(yīng)環(huán)境断国，好的基因得到保留撕彤，不好的基因被淘汰鱼鸠，這樣經(jīng)過很多代基因的變化，物種的基因就是當前自然環(huán)境下適應(yīng)度最好的基因羹铅。該算法被廣泛應(yīng)用于優(yōu)化和搜索中蚀狰，用于尋求最優(yōu)解（或最優(yōu)解的近似），其最主要的步驟包括交叉（crossover）和突變（mutation）职员。

所有的生物體都由細胞組成麻蹋，每個細胞中都包含了同樣的染色體（chromosome）。染色體由一串DNA組成焊切，我們可以簡單地把一個生物個體表示為一條染色體扮授。每條染色體上都包含著基因，而基因又是由多個DNA組成的专肪。每個基因都控制著個體某個性狀的表達刹勃，例如眼睛的顏色、眼皮的單雙等嚎尤。在物種繁衍的過程中荔仁，首先發(fā)生交叉，來自于父母的染色體經(jīng)過分裂和重組，形成后代的染色體乏梁。之后次洼，后代有一定概率發(fā)生基因突變，即染色體上某個位置處的基因以一定概率發(fā)生變化遇骑。之后滓玖，對每一代都重復(fù)進行交叉和突變兩個步驟。對于每一個后代质蕉，我們可以通過一定的方式測量其適應(yīng)度势篡。適應(yīng)度越好的個體，在下一次交叉中被選中的概率越大模暗，它的基因越容易傳給下一代禁悠。這樣，后代的適應(yīng)度就會越來越好兑宇，直到收斂到一個穩(wěn)定值碍侦。

在優(yōu)化問題中，可行解總是有很多個隶糕，我們希望尋找一個最優(yōu)解瓷产，它相對于其他可行解來說具有更好的適應(yīng)度（即目標函數(shù)值更大或更小）枚驻。每個可行解就是一個“生物個體”濒旦，可以表示為狀態(tài)空間中的一個點和適應(yīng)度。每個解都是一個經(jīng)過編碼的序列再登，已二進制編碼為例尔邓，每個解都是一個二進制序列。這樣每個染色體就是一個二進制序列锉矢。遺傳算法從從一組可行解開始梯嗽，稱為population，從population中隨機選擇染色體進行交叉產(chǎn)生下一代沽损。這一做法的基于下一代的適應(yīng)度會好于上一代灯节。遺傳算法的過程如下：

1. 初始化，隨機生成n個染色體绵估；
2. 根據(jù)目標函數(shù)炎疆，計算每個染色體的函數(shù)值，即適應(yīng)度壹士；
3. 產(chǎn)生下一代：
   • 隨機選擇兩個染色體磷雇，且適應(yīng)度越好的染色體被選中的概率越大偿警；
   • 按照一定的交叉概率使兩個染色體發(fā)生交叉躏救，產(chǎn)生兩個新后代；如果沒有發(fā)生交叉，則后代即為這兩個染色體本身盒使；
   • 按照一定的突變概率使后代發(fā)生基因突變崩掘；
   • 把后代放入新的population中；
4. 使用新的population少办，重復(fù)步驟2和3苞慢，直到達到終止條件。

終止條件可以是達到了最大迭代次數(shù)英妓，或者是前后連續(xù)幾代的最優(yōu)染色體的適應(yīng)度差值小于一個閾值挽放。以上算法描述也許還不夠直觀，我們舉例說明蔓纠。假設(shè)解可以用二進制編碼表示辑畦，則每個染色體都是一個二進制序列。假設(shè)序列長度為16腿倚，則每個染色體都是一個16位的二進制序列：

染色體

首先纯出，我們隨機生成一個population，假設(shè)population size為20敷燎，則有20個長度為16的二進制序列暂筝。計算每個染色體的適應(yīng)度，然后選取兩個染色體進行交叉硬贯，如下圖所示焕襟。下圖在第6為上將染色體斷開再重組，斷開的位置是可以隨機選擇的饭豹。當然胧洒，斷裂位置也可以不止一個∧矗可以根據(jù)具體問題選擇具體的交叉方式來提升算法性能卫漫。

交叉

之后，隨機選取后代染色體上某個基因發(fā)生基因突變肾砂，突變的位置是隨機選取的列赎。并且，基因突變并不是在每個后代上都會發(fā)生镐确，只是有一定的概率包吝。對于二進制編碼，基因突變的方式是按位取反：

基因突變

上述例子是關(guān)于二進制編碼的源葫，像求解一元函數(shù)在某個區(qū)間內(nèi)的最大最小值就可以使用二進制編碼诗越。例如，求解函數(shù)f(x)=x+sin(3x)+cos(3x)在區(qū)間[0,6]內(nèi)的最小值息堂。假設(shè)我們需要最小值點x保留4位小數(shù)嚷狞，那么求解區(qū)間被離散成60000個數(shù)块促。因為2^{15}<60000<2{16}，所以床未，需要16位二進制數(shù)來表示這60000個可能的解竭翠。其中0x0000表示0，0x0001表示0.0001薇搁，以此類推斋扰。針對這個例子，文末給出了demo code．

然而啃洋，在排序問題中無法使用二進制編碼传货，應(yīng)該采用排列編碼（permutation encoding）。例如有下面兩個染色體：

排列編碼

交叉：隨機選取一個交叉點宏娄，從該出將兩個染色體斷開损离。染色體A的前部分組成后代1的前部分，然后掃描染色體B绝编，如果出現(xiàn)了后代1中不包含的基因僻澎，則將其順序加入后代1中。同理十饥，染色體B的前部分組成了后代2的前部分窟勃，掃描染色體A獲得后代2的后部分。注意逗堵，交叉的方式多種多樣秉氧，此處只是舉出其中一種方式。

(1 5 3 2 6 | 4 7 9 8) + (8 5 6 7 2 | 3 1 4 9) => (1 5 3 2 6 8 7 4 9) + (8 5 6 7 2 1 3 4 9)

突變：對于一個染色體蜒秤，隨機選中兩個基因互換位置汁咏。例如第3個基因和倒數(shù)第2個基因互換：

(1 5 3 2 6 8 7 4 9) => (1 5 4 2 6 8 7 3 9)

此外還有值編碼（value encoding）和樹編碼（tree encoding）等，具體例子可以參考這個鏈接：http://obitko.com/tutorials/genetic-algorithms/encoding.php

在實際的遺傳算法中作媚，往往會保留上一代中的少數(shù)幾個精英（elite）攘滩，即將上一代population中適應(yīng)度最好的幾個染色體加入到后代的poulation中，同時去除后代population中適應(yīng)度最差的幾個染色體纸泡。通過這個策略漂问，如果在某次迭代中產(chǎn)生了最優(yōu)解，則最優(yōu)解能夠一直保留到迭代結(jié)束女揭。

用GA求函數(shù)最小值的demo code：https://github.com/JiaxYau/GA_test

參考資料：

[1] Introduction to Genetic Algorithm,http://obitko.com/tutorials/genetic-algorithms/index.php

[2] Holland J H. Adaption in natural and artificial systems