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