簡單介紹
遺傳算法，模擬達(dá)爾文進(jìn)化論的自然選擇和遺產(chǎn)學(xué)機(jī)理的生物進(jìn)化構(gòu)成的計算模型，一種不斷選擇優(yōu)良個體的算法。在不斷進(jìn)行多輪的染色體交叉、變異、選擇后，得到的個體基本上是最優(yōu)的，再繼續(xù)下去，就一直保持最優(yōu)。
應(yīng)用場景
解決優(yōu)化類問題，尤其是不能直接解出來的問題，通常可以用遺傳算法來做。比如，對于下面這個函數(shù)
要求這個函數(shù)的最大值，一種方法是等間距地在的區(qū)間中去100萬個點(diǎn)，求出100萬個
的值，然后比大小，很蠢很樸素。遺傳算法其實(shí)也是一個個地搜索，只不過人為地給了一些方向和策略。
一些術(shù)語及其在算法中的對應(yīng)關(guān)系
建議結(jié)合算法詳解食用
- 基因型：將十進(jìn)制取值
經(jīng)過二進(jìn)制編碼后的二進(jìn)制數(shù)
- 表現(xiàn)型：十進(jìn)制的取值
- 變異：隨機(jī)改變基因中某個位置的值，如將0101 1001變?yōu)?111 1001，即是改變了第三位的數(shù)
- 交叉：將兩個二進(jìn)制編碼某一段相同長度的子串進(jìn)行交換
- 適應(yīng)度：代入
- 種群：所有
算法詳解
編碼
遺傳算法中應(yīng)用的編碼方式有很多種，不同的編碼方式可以應(yīng)對在不同的場景中。常見的有二進(jìn)制編碼，浮點(diǎn)編碼（高精度，復(fù)雜度高的問題），符號編碼等。
下面我們只介紹二進(jìn)制編碼
二進(jìn)制編碼其實(shí)就是為了將十進(jìn)制的的值轉(zhuǎn)化為用‘0’和‘1’表示的二進(jìn)制數(shù)字。為什么要表示成二進(jìn)制？原因有以下幾點(diǎn)：
- 發(fā)揮你的想象力，二進(jìn)制數(shù)字的0101形式像不像基因中的簡化的堿基序列？
- 編碼、解碼簡單易行
- 變成二進(jìn)制形式后更容易進(jìn)行所謂的“交叉”和“變異” 等遺傳操作
- 可以利用模式定理對算法進(jìn)行理論分析
二進(jìn)制編碼的缺點(diǎn)是：對于一些連續(xù)函數(shù)的優(yōu)化問題，由于其隨機(jī)性使得其局部搜索能力較差，如對于一些高精度的問題，當(dāng)解迫近于最優(yōu)解后，由于其變異后表現(xiàn)型變化很大，不連續(xù)，所以會遠(yuǎn)離最優(yōu)解，達(dá)不到穩(wěn)定。
舉一個簡單的例子，對于8位數(shù)字的二進(jìn)制編碼:
1 -------> 0000 0001
255-----> 1111 1111
或者
------> 0000 0001
1-----------> 1111 1111
不同的編碼方式對應(yīng)的精度和范圍都不同，也可以通過增加位數(shù)來提高精度，可以根據(jù)應(yīng)用場景選擇。
交叉和變異
變異其實(shí)就是將編碼后的 中的某一位或多位的值發(fā)生變化，將變化后得到的
變成十進(jìn)制的
，將這個
代入函數(shù)得到
將現(xiàn)有的
進(jìn)行比較，判斷是好的變異，還是不好的變異。變異也有基本位變異（Simple Mutation）、均勻變異（Uniform Mutation）、邊界變異（Boundary Mutation）、非均勻變異等等，看情況選取
交叉也是一樣，隨機(jī)將種群中兩個 中的某一連續(xù)的幾個位置交換，大概率得到兩個新的個體。比如，將0010 1110與1101 1100中第2、3、4位進(jìn)行交換，得到兩個新的個體就是0101 1110和1010 1100。當(dāng)然交叉方法也有很多種，目的都是一致的，即產(chǎn)生隨機(jī)個體。
說白了，上面這兩中遺傳操作都是為了產(chǎn)生隨機(jī)性的新個體，好讓解不陷入一個局部最優(yōu)解.
選擇
好了，現(xiàn)在經(jīng)過上面一定次數(shù)的交叉和變異，多出來一堆的新的個體，一個種群中吃不消有這么多個體呀，怎么辦？優(yōu)勝劣汰！
那要用什么樣的選擇方法比較好呢？常見的選擇算子有以下幾種：
- 輪盤賭選擇（Roulette Wheel Selection）：是一種回放式隨機(jī)采樣方法。每個個體進(jìn)入下一代的概率等于它的適應(yīng)度值與整個種群中個體適應(yīng)度值和的比例。選擇誤差較大。
- 隨機(jī)競爭選擇（Stochastic Tournament）：每次按輪盤賭選擇一對個體，然后讓這兩個個體進(jìn)行競爭，適應(yīng)度高的被選中，如此反復(fù)，直到選滿為止。
- 最佳保留選擇：首先按輪盤賭選擇方法執(zhí)行遺傳算法的選擇操作，然后將當(dāng)前群體中適應(yīng)度最高的個體結(jié)構(gòu)完整地復(fù)制到下一代群體中。
- ……還有很多
用輪盤賭來做例子解釋一下
假如有５條染色體，他們的適應(yīng)度分別為５、８、３、７、２。
那么總的適應(yīng)度為：F = 5 + 8 + 3 + 7 + 2 = 25。
那么各個個體的被選中的概率為：
α1 = ( 5 / 25 ) * 100% = 20%
α2 = ( 8 / 25 ) * 100% = 32%
α3 = ( 3 / 25 ) * 100% = 12%
α4 = ( 7 / 25 ) * 100% = 28%
α5 = ( 2 / 25 ) * 100% = 8%
當(dāng)指針在這個轉(zhuǎn)盤上轉(zhuǎn)動，停止下來時指向的個體就是天選之人啦?？梢钥闯?，適應(yīng)性越高的個體被選中的概率就越大。
參考資料：
【算法】超詳細(xì)的遺傳算法(Genetic Algorithm)解析
通俗解釋遺傳算法及其MATLAB實(shí)現(xiàn)
