快速遺傳算法

1、快速遺傳算法研究吳斌吳堅(jiān)涂序彥【摘要】提出了一種稱為廣義自適應(yīng)遺傳算法的快速遺傳算法，它首先產(chǎn)生均勻分布的初始種群，其次根據(jù)種群模式的狀況決定是否引入“高品質(zhì)”移民， 最后自適應(yīng)地進(jìn)行交換和變異運(yùn)算。其搜索性和全局收斂性比現(xiàn)有的許多遺傳算 法都有明顯的改善，并通過仿真說明了該改進(jìn)遺傳算法的有效性。關(guān)鍵詞 廣義自適應(yīng)；遺傳算法；初始種群；移民；適應(yīng)度函數(shù)中圖分類號(hào)TP301.6Research of Fast Genetic AlgorithmWu Bin Wu Jian(Dept. of Information and Control Engineering , SWIT Mianyang 6

2、21002)Tu Xuyan(Information Engineering School, UST Beijing Beijing 100083)Abstract A fast genetic algorithmGSAGA(generalized self-adaptivegenetic algorithm) is presented in this paper. First, evenly distributed initial population is generated. Then, high quality immigrants are introduced according t

3、o the condition of the population schema. Finally, crossover and mutation are operated on self-adaptively. In GSAGA, the searching performance and global convergence are greatly improved compared with many existing genetic algorithms. Through emulation, the validity of this modified genetic algorith

4、m is proved.Key words generalized self-adaptive; genetic algorithm; initial population; immigration; fitness function在遺傳算法中，算法的收斂性主要通過復(fù)制實(shí)現(xiàn)，而搜索性主要通過交換和 變異實(shí)現(xiàn)。由于復(fù)制和交換的作用，適應(yīng)度高于種群平均適應(yīng)度的優(yōu)良個(gè)體得到 保留，并且其數(shù)量隨著進(jìn)化而不斷增加，最后成為種群中的超級(jí)個(gè)體，產(chǎn)生封閉 競(jìng)爭(zhēng)，即出現(xiàn)“近親繁殖”，減慢甚至導(dǎo)致進(jìn)化地停滯，過早地收斂于局部極值 解;而變異操作可以增加新的搜索空間，擴(kuò)大搜索范圍，以利于找到全局最優(yōu)解， 但增加變

5、異會(huì)影響收斂的速度。現(xiàn)有的各種改進(jìn)遺傳算法有助于解決算法搜索性 與收斂性間的矛盾，但許多算法只有在迭代步數(shù)很多時(shí)才有可能搜索到全局極值 點(diǎn)附近，給算法的實(shí)際應(yīng)用造成了困難。為此，本文提出了一種快速遺傳算法 廣義自適應(yīng)遺傳算法(GSAGA)。1廣義自適應(yīng)遺傳算法的原理1.1初始種群的產(chǎn)生在許多改進(jìn)的遺傳算法中，初始種群的產(chǎn)生依然采用完全的隨機(jī)方式，而沒 有解決初始種群中各個(gè)體在解空間中的分布情況。這有可能讓許多個(gè)體都集中在某一局部區(qū)域內(nèi)，不利于擴(kuò)大搜索空間和收斂到全局最優(yōu)解。廣義自適應(yīng)遺傳算 法首先在初始種群的產(chǎn)生上要求各個(gè)體之間保持一定的距離，使各個(gè)體盡可能均 勻地分布在整個(gè)解空間上。定義相同

6、長(zhǎng)度的以a為基的兩個(gè)字符串中對(duì)應(yīng)位不相同的數(shù)量稱為兩者間 的廣義海明距離，記為GH。設(shè)個(gè)體是以為基的字符串，個(gè)體的長(zhǎng)度為k，種群的規(guī)模大小為N，則要求 入選種群的所有個(gè)體之間的廣義海明距離GH必須滿足砂* 7)E (1)式中i、j為兩個(gè)個(gè)體，一 ；b為一常數(shù)，視不同的編碼形式而定。一般若為二進(jìn)制編碼，則b=int(k/2)；若為十進(jìn)制編碼，則可取J/。種群的大小N影響著算法的有效性，當(dāng)N太小時(shí)，算法會(huì)很差或找不出問題 的解；而N太大時(shí)，則會(huì)使收斂時(shí)間增長(zhǎng)，因此設(shè)定N=3K(K4)。對(duì)于一個(gè)以a為基，長(zhǎng)度為k的字符串，共有ak個(gè)編碼串。在這ak個(gè)編碼 串中，相互間廣義海明距離大于或等于(k-b)

7、的字符串編碼總共有ak-(k-b)+i個(gè)。所 以在廣義自適應(yīng)遺傳算法中，種群的大小N=3k遠(yuǎn)小于 ak-(k-b)+1， 即要求初始種群 中所有個(gè)體間的廣義海明距離大于或等于(k-b)是完全能滿足要求的。設(shè)兩個(gè)長(zhǎng)度為l的字符串個(gè)體間的廣義海明距離是GH，則這兩個(gè)字符串中 所包含的相同模式的數(shù)量為2i-gh，而長(zhǎng)度為l的字符串個(gè)體所含的模式數(shù)為2】， 故這兩個(gè)字符串中所包含的不相同模式的數(shù)量就是(2-2】-gh)。廣義海明距離GH 越大，字符串間所包含的不相同模式的數(shù)量就越多，種群中的模式也越多。能。1.2適應(yīng)度函數(shù)f在遺傳算法中，適應(yīng)度函數(shù)用來評(píng)價(jià)各個(gè)解的優(yōu)劣。適應(yīng)度計(jì)算的簡(jiǎn)單或復(fù) 取決于問題

8、本身。對(duì)有些問題，只需要一個(gè)數(shù)學(xué)解析公式計(jì)算出來；有些問初始種群采取這種方式產(chǎn)生就能保證隨機(jī)產(chǎn)生的各個(gè)體間有較明顯的差別， 使它們能比較均勻地分布在解空間上，保證初始種群含有較豐富的模式，從而增 加搜索收斂于全局最優(yōu)解的可雜，題本生不存在這樣的解析式，需通過一系列基于規(guī)則的步驟才能求得；還有些問題的計(jì)算，是上述兩種方法的結(jié)合。在廣義自適應(yīng)遺傳算法中，我們采用解析公式計(jì)算適應(yīng)度。設(shè)實(shí)際問題的目 標(biāo)函數(shù)為J(x)，適應(yīng)度函數(shù)為f(x)，則有(2)J-iNII=min Wh Z = max ，式中N為種群大??；-1.3復(fù)制算子為了保證搜索到的最優(yōu)個(gè)體不會(huì)因?yàn)檫x擇、變異、交換算子的操作而被破壞， 我們

9、將父代種群中適應(yīng)度最大的0.1N個(gè)（10%）優(yōu)良個(gè)體直接傳遞到子代種群中， 成為子代種群中的個(gè)體。對(duì)父代種群中剩下的0.9N個(gè)（90%）個(gè)體，按各自的適應(yīng) 度進(jìn)行從小到大排序。設(shè)各個(gè)體相應(yīng)的排序序號(hào)為I； 12，。-9&），則每個(gè)個(gè) 體按如下的數(shù)量復(fù)制到匹配池中（3）1.4 “高品質(zhì)”移民在廣義自適應(yīng)遺傳算法中，為了避免出現(xiàn)超級(jí)個(gè)體，防止發(fā)生封閉競(jìng)爭(zhēng)，將 根據(jù)匹配池中各個(gè)體間的差異來決定是否引入移民和移民的數(shù)量，并且要求被引 入的移民具有較高的“品質(zhì)”，即移民個(gè)體的適應(yīng)度應(yīng)該大于或等于當(dāng)前匹配池 中個(gè)體的平均適應(yīng)度。當(dāng)匹配池中各個(gè)體間的廣義海明距離小于一特定值/時(shí)， 就不斷地引入“高品質(zhì)”移民

10、隨機(jī)地替代匹配池中的某些個(gè)體，直到匹配池中個(gè) 體間的廣義海明距離大于或等于為止。其中工為一常數(shù)，一般取為0.01。1.5自適應(yīng)交換算子交換是對(duì)被選擇到匹配池中的0.9N個(gè)個(gè)體進(jìn)行的。對(duì)于隨機(jī)選擇的交換匹 配對(duì)的兩個(gè)個(gè)體來說，當(dāng)兩者之間的廣義海明距離很小時(shí)（即兩者非常相似）， 交換的作用變得不明顯，因此應(yīng)減少交換操作，甚至不進(jìn)行交換操作，亦即交換 的概率pc應(yīng)較小或?yàn)榱?；而?dāng)兩者間的距離較大時(shí)，交換后產(chǎn)生新個(gè)體的機(jī)會(huì) 也較大，有助于提高搜索效率，因而應(yīng)有較大的交換概率pc。在廣義自適應(yīng)遺傳算法中，交換概率Pc具有如下形式式中i，j分別為匹配對(duì)中的兩個(gè)個(gè)體；G%它們間的廣義海明距離；為匹配池中所有

11、個(gè)體間的平均廣義海明距離；a為一個(gè)常數(shù)，取值范圍為0.20.8。這樣確定的交換概率Pc將依據(jù)匹配對(duì)個(gè)體間的情況而變化，距離大的交換 可能性大；反之，交換的可能性就小。1.6自適應(yīng)變異算子變異算子保證算法能搜索到問題解空間的每一點(diǎn)，使算法具有全局收斂性。當(dāng)種群的平均廣義海明距離G很小時(shí)，說明種群中的各個(gè)體基本上趨于一致， 種群的基因模式單一性增強(qiáng)，因而可能導(dǎo)致進(jìn)化停滯，過早地收斂于局部的極值 解，為此必須通過變異操作來改變這種情況。在交換操作前，用廣義海明距離來評(píng)價(jià)要交換的雙親個(gè)體的差異，根據(jù)這個(gè) 差異，以及當(dāng)前匹配池中個(gè)體間的平均廣義海明距離和適應(yīng)度的情況來確定交換 后的后代變異概率P。在廣義

12、自適應(yīng)遭傳算法中，經(jīng)交換后的各個(gè)體按如下變異概率Pm進(jìn)行變異 操作 m式中5。門分別為匹配池中交換前所有個(gè)體的最大適應(yīng)度、平均 適應(yīng)度和平均廣義海明距離和配對(duì)個(gè)體間的廣義海明距離；仃為常數(shù)，一般取 為0.005。 一 一和亓體現(xiàn)了群體的收斂程度，當(dāng)它們較小時(shí)，說明群體已趨 向收斂，P應(yīng)加大。匹配池中的0.9N個(gè)個(gè)體經(jīng)移民、交換、變異操作后進(jìn)入新一代種群。1.7停止條件在廣義自適應(yīng)遺傳算法中，算法停止條件為M代內(nèi)最優(yōu)適應(yīng)度值無顯著提高。M太大則收斂時(shí)間太長(zhǎng)，而太小則所求得的最優(yōu)結(jié)果與實(shí)際最優(yōu)解相差太大。我們根據(jù)種群規(guī)模N來確定，取上。2廣義自適應(yīng)遺傳算法仿真文獻(xiàn)3比較了幾種遺傳算法，我們也用其中

13、的函數(shù)來檢驗(yàn)廣義自適應(yīng)遺傳 算法，并與它的結(jié)果進(jìn)行了比較。2.1實(shí)際問題待優(yōu)化函數(shù)為式中xi(i=1,2,3)的取值范圍均為：呵土卜5一飛5屈，求函數(shù)的最大值。函數(shù) 的最大值在(0,0,0)處取得，為100。2.2算法實(shí)現(xiàn)每個(gè)變量用8位十進(jìn)制數(shù)表示，把三個(gè)變量的十進(jìn)制碼串接構(gòu)成一個(gè)個(gè)體，于是編碼長(zhǎng)度K=24，種群大小N=3K=72,結(jié)束迭代次數(shù) 3。適應(yīng)度函數(shù)定義為式中i代表種群中第i個(gè)個(gè)體；J.和J分別為種群中最小和最大的目標(biāo)函數(shù) 值。maX算法流程圖如圖1所示，程序用VB編寫。2.3結(jié)果分析為消除隨機(jī)性帶來的干擾，算法重復(fù)執(zhí)行了 30次，將仿真實(shí)驗(yàn)數(shù)據(jù)取平均 值記錄于表1中。從表1可以看出

14、，當(dāng)指定的目標(biāo)函數(shù)值小于99.99時(shí)，廣義自 適應(yīng)遺傳算法能迅速地收斂到指定極值點(diǎn)，并且在實(shí)驗(yàn)中發(fā)現(xiàn)如果沒有移民，則 對(duì)于搜索大于或等于99.99的目標(biāo)函數(shù)值將要進(jìn)化很多代才能搜索到，甚至有時(shí) 在指定的進(jìn)化代數(shù)內(nèi)搜索不到指定的極值。與文獻(xiàn)3的結(jié)果相比較，廣義自適應(yīng)遺傳算法不僅收斂速度快，而且能夠 搜索到更優(yōu)越的解，其搜索性和收斂性比許多遺傳算法都有很大的改善。圖1廣義自適應(yīng)遺傳算法實(shí)現(xiàn)流程圖表1不同遺傳算法達(dá)到指定函數(shù)值的進(jìn)化代數(shù)目標(biāo)函靈敏值9999.599.999.9599.9999.99599.99999.999 5簡(jiǎn)單遺傳算法383045185均勻交換遺傳算法385490157引入普通移

15、民的算法474078179文獻(xiàn)3的遺傳算法372658134163廣義自適應(yīng)遺傳算法2.634.478.411.6338.8346.151.2752.87注：“一”表示在進(jìn)化200代后該算法的最大目標(biāo)函數(shù)值仍不能達(dá)到指定值。3結(jié)論從上面的分析和仿真實(shí)驗(yàn)結(jié)果可以看出，由于廣義自適應(yīng)遺傳算法首先通過 產(chǎn)生能適應(yīng)問題解空間分布狀況的初始種群，保證了初始種群中個(gè)體模式的合理 分布；其次是通過保護(hù)優(yōu)秀個(gè)體直接進(jìn)入下一代種群，避免了交換、變異操作破 壞優(yōu)良個(gè)體，同時(shí)，有條件地引入“高品質(zhì)”移民，有效地解決了種群中個(gè)體的 多樣性；最后，對(duì)匹配池中的個(gè)體用自適應(yīng)的方式確定各個(gè)體的交換概率P和 變異概率P,從而

16、較好地解決了算法收斂性和搜索性之間的協(xié)調(diào)問題。在廣義自 適應(yīng)遺傳算法的整個(gè)過程中，無論是初始種群的產(chǎn)生，還是外來移民的引入，以 及交換和變異概率的確定都是根據(jù)種群中各個(gè)體的具體情況而定的，并且自適應(yīng) 地隨著進(jìn)化而不斷地改變。所有這一切使得廣義自適應(yīng)遺傳算法具有良好的搜索 性和收斂性，其性能明顯優(yōu)于現(xiàn)存的許多遺傳算法。四川省應(yīng)用基礎(chǔ)研究基金資助項(xiàng)目作者簡(jiǎn)介：吳斌男，33歲，博士生，講師作者單位：吳斌吳堅(jiān)（西南工學(xué)院信息與控制工程系綿陽621002）涂序彥（北京科技大學(xué)信息工程學(xué)院北京100083）參考文獻(xiàn)Holland John H. Adaptation in natural and artificial