最近在看遺傳算法,查了很多資料,所以做了如下一些總結(jié),也希望對(duì)后面研究的人有些幫助.因?yàn)槌鯇W(xué)GA,文中自己的見(jiàn)解,不一定全對(duì),感興趣的可以一起探討.
I 簡(jiǎn)介
基本概念
遺傳算法(Genetic Algorithms, GA)是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。
它模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。
GA的組成:
（1）編碼（產(chǎn)生初始種群）
（2）適應(yīng)度函數(shù)
（3）遺傳算子（選擇、交叉、變異）
（4）運(yùn)行參數(shù)
編碼
基因在一定能夠意義上包含了它所代表的問(wèn)題的解?；虻木幋a方式有很多，這也取決于要解決的問(wèn)題本身。常見(jiàn)的編碼方式有：
（1） 二進(jìn)制編碼，基因用0或1表示（常用于解決01背包問(wèn)題）
如：基因A：00100011010 (代表一個(gè)個(gè)體的染色體)
（2） 互換編碼（用于解決排序問(wèn)題，如旅行商問(wèn)題和調(diào)度問(wèn)題）
如旅行商問(wèn)題中，一串基因編碼用來(lái)表示遍歷的城市順序，如：234517986，表示九個(gè)城市中，先經(jīng)過(guò)城市2，再經(jīng)過(guò)城市3，依此類推。
（3） 樹(shù)形編碼（用于遺傳規(guī)劃中的演化編程或者表示）
如,問(wèn)題：給定了很多組輸入和輸出。請(qǐng)你為這些輸入輸出選擇一個(gè)函數(shù)，使得這個(gè)函數(shù)把每個(gè)輸入盡可能近地映射為輸出。
編碼方法：基因就是樹(shù)形結(jié)構(gòu)中的一些函數(shù)。
（4） 值編碼 （二進(jìn)制編碼不好用時(shí)，解決復(fù)雜的數(shù)值問(wèn)題）
在值編碼中，每個(gè)基因就是一串取值。這些取值可以是與問(wèn)題有關(guān)任何值：整數(shù)，實(shí)數(shù)，字符或者其他一些更復(fù)雜的東西。
適應(yīng)度函數(shù)
遺傳算法對(duì)一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來(lái)評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過(guò)程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問(wèn)題本身的要求而定。
如TSP問(wèn)題，遍歷各城市路徑之和越小越好，這樣可以用可能的最大路徑長(zhǎng)度減去實(shí)際經(jīng)過(guò)的路徑長(zhǎng)度，作為該問(wèn)題的適應(yīng)度函數(shù)。
遺傳算子——選擇
遺傳算法使用選擇運(yùn)算來(lái)實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個(gè)體，遺傳到下一代群體。
SGA（基本遺傳算法）中采用輪盤賭選擇方法。
輪盤賭選擇又稱比例選擇算子，基本思想：各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n ，個(gè)體i 的適應(yīng)度為 Fi，則個(gè)體i 被選中遺傳到下一代群體的概率為：
遺傳算子——交叉
所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算在GA中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。
1. 單交叉點(diǎn)法 （用于二進(jìn)制編碼）
選擇一個(gè)交叉點(diǎn),子代在交叉點(diǎn)前面的基因從一個(gè)父代基因那里得到,后面的部分從另外一個(gè)父代基因那里得到。
如：交叉前：
00000|01110000000010000
11100|00000111111000101
交叉后：
00000|00000111111000101
11100|01110000000010000
2. 雙交叉點(diǎn)法 （用于二進(jìn)制編碼）
選擇兩個(gè)交叉點(diǎn),子代基因在兩個(gè)交叉點(diǎn)間部分來(lái)自一個(gè)父代基因,其余部分來(lái)自于另外一個(gè)父代基因.
如：交叉前：
01 |0010| 11
11 |0111| 01
交叉后：
11 |0010| 01
01 |0111| 11
3. 基于“ 與/或 ”交叉法 （用于二進(jìn)制編碼）
對(duì)父代按位"與”邏輯運(yùn)算產(chǎn)生一子代A;按位”或”邏輯運(yùn)算產(chǎn)生另一子代B。該交叉策略在解背包問(wèn)題中效果較好 .
如：交叉前：
01001011
11011101
交叉后：
01001001
11011111
4. 單交叉點(diǎn)法 （用于互換編碼）
選擇一個(gè)交叉點(diǎn)，子代的從初始位置出發(fā)的部分從一個(gè)基因復(fù)制，然后在另一個(gè)基因中掃描，如果某個(gè)位點(diǎn)在子代中沒(méi)有，就把它添加進(jìn)去。
如：交叉前：
87213 | 09546
98356 | 71420
交叉后：
87213 | 95640
98356 | 72104
5. 部分匹配交叉（PMX）法（用于互換編碼）
先隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，定義這兩點(diǎn)間的區(qū)域?yàn)槠ヅ鋮^(qū)域，并用交換兩個(gè)父代的匹配區(qū)域。
父代A：872 | 130 | 9546
父代B：983 | 567 | 1420 變?yōu)椋?/p>
TEMP A: 872 | 567 | 9546
TEMP B: 983 | 130 | 1420
對(duì)于 TEMP A、TEMP Ｂ中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進(jìn)行替換。匹配關(guān)系：1<——>５?。?lt;——>６?。?lt;——>０
子代Ａ：802 | 567 | 9143
子代Ｂ：986 | 130 | 5427
6. 順序交叉法(OX) （用于互換編碼）
從父代Ａ隨機(jī)選一個(gè)編碼子串，放到子代Ａ的對(duì)應(yīng)位置；子代Ａ空余的位置從父代Ｂ中按Ｂ的順序選?。ㄅc己有編碼不重復(fù)）。同理可得子代Ｂ。
父代A: 872 | 139 | 0546
父代B: 983 | 567 | 1420
交叉后：
子代A: 856 | 139 | 7420
子代B: 821 | 567 | 3904
7. 循環(huán)交叉（CX）法（用于互換編碼）
CX同OX交叉都是從一個(gè)親代中取一些城市，而其它城市來(lái)自另外一個(gè)親代，但是二者不同之處在于：OX中來(lái)自第一個(gè)親代的編碼子串是隨機(jī)產(chǎn)生的，而CX卻不是，它是根據(jù)兩個(gè)雙親相應(yīng)位置的編碼而確定的。
父代Ａ：1 2 3 4 5 6 7 8 9
| | | | |
父代Ａ：5 4 6 9 2 3 7 8 1
可得循環(huán)基因：1->5->2->4->9->1
用循環(huán)的基因構(gòu)成子代Ａ，順序與父代Ａ一樣
1 2 4 5 9
用父代Ｂ剩余的基因填滿子代Ａ：
1 2 6 4 5 3 7 8 9
子代Ｂ的編碼同理。（循環(huán)基因 5->1->9->4->2->5）
遺傳算子——變異
變異是指依據(jù)變異概率將個(gè)體編碼串中的某些基因值用其它基因值來(lái)替換，從而形成一個(gè)新的個(gè)體。GA中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了GA的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。
注：變異概率Pm不能太小，這樣降低全局搜索能力；也不能太大，Pm > 0.5，這時(shí)GA退化為隨機(jī)搜索。
1. 基本位變異算子 （用于二進(jìn)制編碼）
基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。
如：變異前：
000001110000000010000
變異后：
000001110001000010000
2. 逆轉(zhuǎn)變異算子（用于互換編碼）
在個(gè)體中隨機(jī)挑選兩個(gè)逆轉(zhuǎn)點(diǎn)，再將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因交換。
如：變異前：
1346798205
變異后：
1246798305
運(yùn)行參數(shù)
GA運(yùn)行時(shí)選擇的參數(shù)應(yīng)該視解決的具體問(wèn)題而定，到目前為止，還沒(méi)有一個(gè)適用于GA所有應(yīng)用領(lǐng)域的關(guān)于算法參數(shù)的理論。下面是一般情況下使用GA時(shí)推薦的參數(shù)：
1) 交叉率
交叉率一般來(lái)說(shuō)應(yīng)該比較大，推薦使用80％-95％。
2) 變異率
變異率一般來(lái)說(shuō)應(yīng)該比較小，一般使用0.5％-1％最好。
3) 種群的規(guī)模
種群規(guī)模指的是群體中個(gè)體的個(gè)數(shù)。實(shí)驗(yàn)發(fā)現(xiàn)，比較大的種群的規(guī)模并不能優(yōu)化遺傳算法的結(jié)果。種群的大小推薦使用20-30，一些研究表明，種群規(guī)模的大小取決于編碼的方法，具體的說(shuō)就是編碼串（EncodedString）的大小。也就是說(shuō)，如果說(shuō)采用32位為基因編碼的時(shí)候種群的規(guī)模大小最好為32的話，那么當(dāng)采用16位為基因編碼時(shí)種群的規(guī)模相應(yīng)應(yīng)變?yōu)樵瓉?lái)的兩倍。
4) 遺傳運(yùn)算的終止進(jìn)化代數(shù)
個(gè)人的想法是，設(shè)定一個(gè)計(jì)數(shù)器，如果連續(xù)N代出現(xiàn)的最優(yōu)個(gè)體的適應(yīng)度都一樣時(shí)，（嚴(yán)格的說(shuō)應(yīng)該是，連續(xù)N代子代種群的最優(yōu)個(gè)體適應(yīng)度都<=父代最優(yōu)個(gè)性的適應(yīng)度）可以終止運(yùn)算。
也可以簡(jiǎn)單的根據(jù)經(jīng)驗(yàn)固定進(jìn)化的代數(shù)。
II 運(yùn)算流程
圖中的“是否滿足停止準(zhǔn)則”便可參照上節(jié)中“遺傳運(yùn)算的終止進(jìn)化代數(shù)”
III 災(zāi)變與精英主義
災(zāi)變
遺傳算法的局部搜索能力較強(qiáng)，但是很容易陷入局部極值。引用網(wǎng)上的一段原話:
“那么如何解決遺傳算法容易陷入局部極值的問(wèn)題呢？讓我們來(lái)看看大自然提供的方案。六千五百萬(wàn)年以前，恐龍和靈長(zhǎng)類動(dòng)物并存，恐龍?jiān)诘厍蛏险冀^對(duì)統(tǒng)治地位，如果恐龍沒(méi)有滅絕靈長(zhǎng)類動(dòng)物是絕沒(méi)有可能統(tǒng)治地球的。正是恐龍的滅絕才使靈長(zhǎng)類動(dòng)物有了充分進(jìn)化的余地，事實(shí)上地球至少經(jīng)歷了5次物種大滅絕，每次物種滅絕都給更加高級(jí)的生物提供了充分進(jìn)化的余地。所以要跳出局部極值就必須殺死當(dāng)前所有的優(yōu)秀個(gè)體，從而讓遠(yuǎn)離當(dāng)前極值的點(diǎn)有充分的進(jìn)化余地。這就是災(zāi)變的思想。”
災(zāi)變就是殺掉最優(yōu)秀的個(gè)體，這樣才可能產(chǎn)生更優(yōu)秀的物種。那何時(shí)進(jìn)行災(zāi)變，災(zāi)變次數(shù)又如何設(shè)定？
何時(shí)進(jìn)行災(zāi)變，可以采用災(zāi)變倒計(jì)數(shù)的方式。如果n代還沒(méi)有出現(xiàn)比之前更優(yōu)秀的個(gè)體時(shí)，可以發(fā)生災(zāi)變。災(zāi)變次數(shù)可以這樣來(lái)確定，如果若干次災(zāi)變后產(chǎn)生的個(gè)體的適應(yīng)度與沒(méi)災(zāi)變前的一樣，可停止災(zāi)變。
精英主義
當(dāng)利用交叉和變異產(chǎn)生新的一代時(shí)，我們有很大的可能把在某個(gè)中間步驟中得到的最優(yōu)解丟失。
精英主義的思想是,在每一次產(chǎn)生新的一代時(shí)，首先把當(dāng)前最優(yōu)解原封不動(dòng)的復(fù)制到新的一代中。然后按照前面所說(shuō)的那樣做就行。精英主義方法可以大幅提高運(yùn)算速度，因?yàn)樗梢苑乐箒G失掉找到的最好的解。
矛盾
由上面看來(lái),災(zāi)變與精英主義之間似乎存在著矛盾.前者是將產(chǎn)生的最優(yōu)個(gè)體殺掉,而后者是將最優(yōu)秀個(gè)體基因直接保存到下一代.
應(yīng)該辯證地看待它們之間的矛盾,兩者其實(shí)是可以共存的.我們?cè)诿恳淮M(jìn)行交叉運(yùn)算時(shí),均直接把最優(yōu)秀的個(gè)體復(fù)制到下一代;但當(dāng)連續(xù)N代,都沒(méi)有更優(yōu)秀的個(gè)體出現(xiàn)時(shí),便可以猜想可能陷入局部最優(yōu)解了,這樣可以采用災(zāi)變的手段.可以說(shuō),精英主義是伴隨的每一代的,但災(zāi)變卻不需要經(jīng)常發(fā)生,否則算法可能下降為隨機(jī)搜索了.
當(dāng)然,每個(gè)算法中不一定要用精英主義和災(zāi)變的手段,應(yīng)該根據(jù)具體的問(wèn)題而定.
IV GA的特點(diǎn)
遺傳算法的優(yōu)點(diǎn):
（1）群體搜索，易于并行化處理；
（2）不是盲目窮舉，而是啟發(fā)式搜索；
（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。
（4）容易實(shí)現(xiàn)。一旦有了一個(gè)遺傳算法的程序，如果想解決一個(gè)新的問(wèn)題，只需針對(duì)新的問(wèn)題重新進(jìn)行基因編碼就行；如果編碼方法也相同，那只需要改變一下適應(yīng)度函數(shù)就可以了。
遺傳算法的缺點(diǎn):
（1）全局搜索能力不強(qiáng),很容易陷入局部最優(yōu)解跳不出來(lái)；(可結(jié)合SA進(jìn)行改進(jìn),因?yàn)镾A在理率上是100%得到全局最優(yōu)的,但搜索代價(jià)高)
聯(lián)系客服
