聲明：原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處。http://www.itdecent.cn/p/ebe0c98ddf0b
一、概述
遺傳算法(Genetic Algorithm)遵循自然界“適者生存、優(yōu)勝劣汰”的原則，是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。
二、算法流程
1、基因編碼
對(duì)一些個(gè)體的基因做一個(gè)編碼操作，描述出這些基因的結(jié)構(gòu)。
根據(jù)常識(shí)，在生物的每個(gè)細(xì)胞中，都存在相同的一套染色體（chromosome），即DNA組合的聚合體。
因此，我們可以將這些染色體由數(shù)字0和1組成的字符串來表達(dá)。
2、初始化種群
需要造出一個(gè)種群，這個(gè)種群有多個(gè)生物個(gè)體，但是其基因卻都不相同。
3、種群選擇（適應(yīng)度計(jì)算）
需要制造出一些苛刻的條件來淘汰一些不能適應(yīng)這些條件的個(gè)體，不讓其產(chǎn)生后代。
這是因?yàn)?，這些淘汰掉的個(gè)體和最終篩選出的個(gè)體差異很大，如果保留，他的后代只會(huì)讓計(jì)算量增大而距離目標(biāo)沒有顯著增近。
4、產(chǎn)生下一代
這個(gè)過程通常有三種方式：直接選擇、基因重組（種群交叉）、基因突變（種群變異）。
之后的過程，則會(huì)一直重復(fù)步驟3-4，直到找到最優(yōu)解。
三、背包問題
我們通過求解背包問題的最優(yōu)解來描述遺傳算法的步驟。
假設(shè)有這樣一個(gè)背包，可以放置30公斤的東西?，F(xiàn)在我們有以下物品，其<重量,價(jià)值>有如下關(guān)系：
| item | weight | value |
|---|---|---|
| 1 | 15 | 15 |
| 2 | 3 | 7 |
| 3 | 2 | 10 |
| 4 | 5 | 5 |
| 5 | 9 | 8 |
| 6 | 20 | 17 |
怎么能在不超過最大30公斤的限制，選取的物品價(jià)值最大呢？
1、基因編碼
這6種物品，我們可以采用bit位進(jìn)行編碼。
| item1 | item2 | item3 | item4 | item5 | item6 | chromosome |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 111111 |
共使用6位分別表示是否選取了此Item。1表示選取，0則表示未選取。
假設(shè)只有物品1,3,5,則染色體表示為101010。
2、初始化種群
我們隨機(jī)產(chǎn)生4個(gè)生物個(gè)體，其染色體如下：
100110：對(duì)應(yīng)物品1,4,5
001110：對(duì)應(yīng)物品3,4,5
010100：對(duì)應(yīng)物品2,4
011001：對(duì)應(yīng)物品2,3,6
3、種群選擇
從最初的這4個(gè)個(gè)體上，我們可以得到如下表格：
| 染色體 | 對(duì)應(yīng)物品 | 總質(zhì)量 | 總價(jià)值 |
|---|---|---|---|
| 100110 | 1,4,5 | 29 | 28 |
| 001110 | 3,4,5 | 16 | 23 |
| 010100 | 2,4 | 8 | 12 |
| 011001 | 2,3,6 | 25 | 34 |
這里我們將總價(jià)值這個(gè)指標(biāo)作為染色體的適應(yīng)度分?jǐn)?shù)，在不超過限制條件的條件下，
其值越大，他的適應(yīng)性也就越強(qiáng)。
除去苛刻條件的篩選過程（上例是重量超標(biāo)這個(gè)條件），我們還需要一次遴選的過程。即共分為篩選評(píng)估和遴選兩個(gè)過程
我們從總體中選擇適合的染色體，讓其基因重組，產(chǎn)生下一代。但是這樣將會(huì)導(dǎo)致染色體在數(shù)代之后差異減小，失去了基因的多樣性。
一般的，我們會(huì)通過輪盤賭這種方式進(jìn)行選擇。
輪盤賭（Roulette Wheel）：一種賭博游戲，如下圖，可進(jìn)行旋轉(zhuǎn)。輪盤上刻著很多小格子，輪盤開始旋轉(zhuǎn)后，放入一個(gè)小球，待輪盤靜止后，小球掉入的所對(duì)應(yīng)的號(hào)碼即為獲勝號(hào)碼。
想象一下，在一個(gè)分割了97（總適應(yīng)分?jǐn)?shù)）部分的輪盤，各個(gè)染色體的占有率如下：
| 染色體 | 適應(yīng)分?jǐn)?shù) | 占有率 |
|---|---|---|
| 100110 | 29 | 28.9% |
| 001110 | 16 | 23.7% |
| 010100 | 8 | 12.4% |
| 011001 | 25 | 35.1% |
我們轉(zhuǎn)動(dòng)4次，中獎(jiǎng)的染色體允許繁殖一次，通過計(jì)算染色體1和染色4進(jìn)入下一輪，各繁殖2次。
將這種方法稱為：隨機(jī)普遍選擇法（Stochastic Universal Selection method）。
4、產(chǎn)生下一代
4.1 基因重組
我們將上一步中的染色體1和染色體4進(jìn)行交叉重組，這里我們選擇單點(diǎn)交叉方式。
我們隨機(jī)選擇一個(gè)位置，將2個(gè)染色體分離并進(jìn)行重組。
| 個(gè)體 | 染色體 | 配對(duì) | 交叉點(diǎn)位置 | 重組結(jié)果 |
|---|---|---|---|---|
| 1 | 100 110 | 1-2 | 3 | 100 001 |
| 2 | 011 001 | 1-2 | 3 | 011 110 |
| 3 | 1001 10 | 3-4 | 4 | 1001 01 |
| 4 | 0110 01 | 3-4 | 4 | 0110 10 |
其基因重組過程為下表：
| 個(gè)體 | 染色體 | 配對(duì) | 交叉點(diǎn)位置 | 重組結(jié)果 |
|---|---|---|---|---|
| 1 | 100 110 | 1-2 | 3 | 100 001 |
| 2 | 011 001 | 1-2 | 3 | 011 110 |
| 3 | 1001 10 | 3-4 | 4 | 1001 01 |
| 4 | 0110 01 | 3-4 | 4 | 0110 10 |
4.2 基因變異
在后代的生長(zhǎng)過程中，它們體內(nèi)的基因會(huì)發(fā)生一些變化，使得它們與父母不同。這個(gè)過程我們稱為“變異”，它可以被定義為染色體上發(fā)生的隨機(jī)變化，正是因?yàn)樽儺?，種群中才會(huì)存在多樣性。
變異完成后，即得到了新為個(gè)體，進(jìn)化也就完成了，整個(gè)過程如下圖：
在生產(chǎn)完下一代之后，我們?nèi)匀恍枰獙?duì)這些后代進(jìn)行適應(yīng)度計(jì)算。如果發(fā)現(xiàn)出現(xiàn)了連續(xù)幾代適應(yīng)度幾乎不增加甚至反而減少的情況，
說明函數(shù)已經(jīng)收斂。
因此，一般的，有以下幾個(gè)終止條件：
- 在進(jìn)行N次迭代之后，總體適應(yīng)度沒有太大變化。
- 算法事先定義好了進(jìn)化的次數(shù)。
- 適應(yīng)度函數(shù)已經(jīng)達(dá)到了預(yù)先設(shè)定的值。
四、算法可調(diào)參數(shù)
1、初始群體
上面的背包問題，我們?cè)O(shè)定了初始群體個(gè)數(shù)為4個(gè)。當(dāng)然，針對(duì)這6個(gè)物品，最多有2^6個(gè)個(gè)體。一般情況下，我們可以設(shè)定初始群體數(shù)量為N個(gè)，N為當(dāng)前計(jì)算機(jī)最大可并行計(jì)算數(shù)量。
2、適應(yīng)度函數(shù)
上面例子中，我們使用輪盤賭算法。當(dāng)然也可以選擇其他方法。
3、基因重組
上面例子中，我們?cè)O(shè)定的交叉點(diǎn)為3和4，當(dāng)然可以選擇其他的交叉點(diǎn)。
4、終止條件
上面曾列舉了常見的3中終止條件，當(dāng)然還有其他，目的都是當(dāng)適應(yīng)函數(shù)收斂后終止。
