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