一種改進(jìn)操作算子的加速收斂遺傳算法

鄧洋春　梁昔明

摘 要：針對基本遺傳算法效率低和易早熟的缺陷，提出了一種改進(jìn)操作算子的遺傳算法。該算法在種群初始化、選擇、交叉、變異等基本算子的基礎(chǔ)上加以改進(jìn)，使算法具有更好的適應(yīng)性。對3組不同函數(shù)的測試表明，改進(jìn)算法較傳統(tǒng)的遺傳算法具有在種群很小的情況下收斂速度快穩(wěn)定性高的優(yōu)點(diǎn)，同時(shí)能有效地避免早熟現(xiàn)象。

關(guān)鍵詞：遺傳算法；變異；收斂速度；種群數(shù)

中圖分類號：TP391文獻(xiàn)標(biāo)識碼：B

文章編號：1004 373X(2009)02 139 03

Accelerating Convergency Genetic Algorithm of Improved Operator

DENG Yangchun,LIANG Ximing

(College of Information Science and Engineering,Central South University,Changsha,410083,China)

Abstract：To overcome low performance and premature convergence of simple Genetic Algorithm(GA),an improved operator genetic algotithm is proposed.It improves the operators such as initialization,selection,crossover and mutation,which make the algorithm more adaptive.The 3 groups of experiments show that improved algorithm has a quick speed convergence and more stable than simple GA,and also can efficiently avoid premature convergence.

Keywords：genetic algorithm;mutation;convergence speed;population size

0 引 言

遺傳算法(Genetic Algorithm,GA)是一種宏觀意義下的仿生算法，它模仿的機(jī)制是一切生命與智能的產(chǎn)生與進(jìn)化過程，從一個(gè)初始種群出發(fā)，不斷重復(fù)執(zhí)行選擇，雜交和變異的過程，使種群進(jìn)化越來越接近某一目標(biāo)。它通過模擬達(dá)爾文“優(yōu)勝劣汰，適者生存”的原理激勵好的結(jié)構(gòu)；通過模擬孟德爾遺傳變異理論在迭代過程中保持已有的結(jié)構(gòu)，同時(shí)尋找更好的結(jié)構(gòu)。經(jīng)典遺傳算法的求解步驟為：初始化種群；選擇；交叉；變異；判斷終止條件。由于它簡單有效，具有很強(qiáng)的魯棒性和通用性，所以被廣泛應(yīng)用于模式識別、神經(jīng)網(wǎng)絡(luò)、圖像處理、機(jī)器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)控制、生物科學(xué)、社會科學(xué)等多種領(lǐng)域［1］。

早熟和收斂時(shí)間過長是影響遺傳算法效率的兩個(gè)主要因素，而選擇壓力過大是導(dǎo)致早熟收斂的一個(gè)重要原因［2］，為此不少學(xué)者對遺傳算法做了改進(jìn)［3－5］，但仍存在一定局限性。在此對遺傳算法個(gè)操作算子加以改進(jìn)，通過對經(jīng)典多極值測試函數(shù)的仿真研究表明，改進(jìn)后的算法能夠有效避免早熟且在種群規(guī)模較小的情況下具有較快的收斂速度。

1 改進(jìn)操作算子的遺傳算法

經(jīng)典遺傳算法的把變異作為一種輔助手段，認(rèn)為變異只是一個(gè)背景機(jī)制，這一觀點(diǎn)與生物學(xué)中的實(shí)際觀察是相符的，但作為設(shè)計(jì)人工求解問題方法的思想，他正受到理論與實(shí)踐兩方面的挑戰(zhàn)［6］。另外，從微觀角度來講，變異隨時(shí)都有可能發(fā)生，如果突變向不好的方向進(jìn)行，其“修復(fù)系統(tǒng)”立刻就能對其進(jìn)行修復(fù)。基于以上兩點(diǎn)，這里在選擇與交叉算子中滲入不同的變異行為，且動態(tài)改進(jìn)變異算子，使算法能快速達(dá)到全局最優(yōu)。

1.1 初始化

為了改善初始群體的效能，提高模式的優(yōu)良度，采取如下方法：先隨機(jī)產(chǎn)生一個(gè)父染色體，對其進(jìn)行一定次數(shù)(20次左右)的逐位精英選擇高頻變異，方法如下：例如染色體為01001，先把第一位變異為1，成為11001，若適應(yīng)度提高，則此位以很大的概率p(如0.98)轉(zhuǎn)換為1，否則以很小的概率(如0.01)轉(zhuǎn)換為1，以此類推。接著產(chǎn)生具有一定規(guī)模的染色體種群，隨機(jī)使其中每個(gè)染色體的某段基因與之前父染色體相應(yīng)基因段保持一致。如：假設(shè)父染色體為00110，隨機(jī)產(chǎn)生個(gè)體10101，若以第一和第二位基因與父染色體一致，則該個(gè)體變?yōu)椋?0101。該方法把較優(yōu)秀的模式分散到各個(gè)染色體中，使它一開始就具有一定概率的優(yōu)秀短模式，從而有效提高算法的尋優(yōu)效率。

1.2 選擇操作

經(jīng)典遺傳算法根據(jù)適者生存原則選擇下一代個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。

然而基于適應(yīng)度的概率選擇機(jī)制如輪盤賭選擇法在種群中出現(xiàn)個(gè)別或極少數(shù)適應(yīng)度相當(dāng)高的個(gè)體時(shí)，就可能導(dǎo)致這些個(gè)體在群體中迅速繁殖，經(jīng)過少數(shù)迭代后占滿了種群的位置。這樣，遺傳算法的求解過程就結(jié)束了，也即收斂了。但這樣很有可能使收斂到局部最優(yōu)解，即出現(xiàn)早熟現(xiàn)象［1］。為了從根本上避免早熟現(xiàn)象且加快收斂速度，采用基于高頻精英變異的錦標(biāo)賽選擇法。其操作如下：假設(shè)競賽規(guī)模為2，首先選取種群中第1和第2個(gè)個(gè)體X和Y

如：X=100101，Y=011110

從第1位開始比較適應(yīng)值的大小，即當(dāng)個(gè)體X與Y的第1位分別是1和0時(shí)，假設(shè)fitness(X)＞ fitness(Y)，于是把Y的第1位由0高頻變異為1，此時(shí)：

X=110101，Y=101110

此時(shí)，若fitness(X)＜ fitness(Y)，則把Y的第1位由1高頻變異為0。如此下去，最終得到的為選擇出的個(gè)體，其中較高位(如第1至L/3位，其中L為染色體長度)變異率為0.8，其他位變異率為0.95，理由是較高位的個(gè)體即使適應(yīng)度低也有可能在附近變異成適應(yīng)度更高的個(gè)體。

然后選取種群中第2和第3個(gè)個(gè)體應(yīng)用上法選擇出第2個(gè)個(gè)體，這個(gè)過程重復(fù)進(jìn)行，完成剩余個(gè)體的選擇。這種算子在選擇個(gè)體上就可以有方向性且極大地加快算法的收斂速度。

1.3 交叉操作

交叉是把兩個(gè)父個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作，從而在下一代產(chǎn)生新的個(gè)體。它的目的是開發(fā)問題解空間中新的區(qū)域，尋找父個(gè)體已有的但未能合理組合的基因，盡量保證具有優(yōu)良模式的個(gè)體不被交叉操作所完全破壞，同時(shí)增大種群的離散程度，產(chǎn)生新的搜索空間。所有交叉操作的一個(gè)共同特征是，不破壞兩個(gè)父個(gè)體之間的公共串模式，允許繼續(xù)搜索空間時(shí)保留好的模式［2］。

對于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇2個(gè)個(gè)體的相同位置，按交叉概率P在選中的位置實(shí)行交換。在選中的位置實(shí)行交換［1］。這個(gè)過程反映了隨機(jī)信息交換，目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。在交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。

一點(diǎn)交叉是經(jīng)典的交叉方法，它是對于給定的兩個(gè)父個(gè)體，隨機(jī)地選取1個(gè)交叉位置，然后相互交換兩個(gè)個(gè)體交叉位置右邊部分基因，形成2個(gè)子代，一點(diǎn)交叉能夠搜索到的空間十分有限。多點(diǎn)交叉的破壞性可以促進(jìn)解空間的搜索，而不是促進(jìn)過早地收斂，因此搜索更加健壯［1］。這里在采取多點(diǎn)交叉的同時(shí)考慮父個(gè)體間的多樣度。

當(dāng)兩個(gè)父個(gè)體的漢明距離較低，可能導(dǎo)致交叉操作無效。另外，由于交叉點(diǎn)隨機(jī)產(chǎn)生，可能會導(dǎo)致交叉后新個(gè)體無變化，例如，兩父個(gè)體分別為01100101和01011010，如果交叉點(diǎn)取值為第2位，則交叉后的兩個(gè)新個(gè)體與父個(gè)體相同，交叉操作無效。在此采取交叉概率與漢明距離成正比的策略：兩父體相似度高時(shí)交叉概率減小以避免無效操作，一旦在這種情況下進(jìn)行交叉，首先保持具有高適應(yīng)度的父個(gè)體不變，然后對低適應(yīng)度個(gè)體或者交叉點(diǎn)左右具有相同子串的個(gè)體采取變異操作以增大它們之間的漢明距離，從而提高交叉操作的有效性。

1.4 變異操作

根據(jù)生物遺傳中基因變異的原理，以變異概率P璵對某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對執(zhí)行變異的串的對應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。

單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說，變異增加了全局優(yōu)化的特質(zhì)。

這里提出一種自適應(yīng)快速收斂變異法：對每一個(gè)體采取從高位到低位逐位變異的策略。在尋優(yōu)的早期主要是全局搜索，此時(shí)各變量二進(jìn)制的高位應(yīng)采用高變異率，低位采用低變異率。在尋優(yōu)過程中不斷調(diào)整各位的變異率，即高位變異率逐漸降低，低位變異率逐漸增加。到尋優(yōu)后期，主要是局部優(yōu)化，全局優(yōu)化次之，此時(shí)各位變異率與早期相反，即低位變異率要比高位變異率大。在變異過程中采用概率精英保留策略，也就是每位變異后若適應(yīng)值增加，則以高概率保留，否則放棄此位變異。實(shí)驗(yàn)證明，這種變異策略在種群規(guī)模較小的情況下能獲得較滿意的進(jìn)化能力。

2 算法描述

算法描述為：

(1) 采用二進(jìn)制編碼，隨機(jī)產(chǎn)生一個(gè)體，通過逐位高頻精英變異，提高其適應(yīng)度；

(2) 利用上述較優(yōu)父染色體產(chǎn)生產(chǎn)生種群；

(3) 進(jìn)行基于高頻精英變異的錦標(biāo)賽選擇；

(4) 進(jìn)行改進(jìn)的交叉運(yùn)算；

(5) 進(jìn)行自適應(yīng)變異運(yùn)算；

(6) 是否到最大的遺傳代數(shù)，如果達(dá)到，結(jié)束；否則轉(zhuǎn)到步驟(3)。

3 仿真試驗(yàn)及結(jié)果分析

3.1 試驗(yàn)

為驗(yàn)證改進(jìn)算法的效率，用經(jīng)典遺傳算法SGA和文中的加速收斂改進(jìn)遺傳算法相比較，其中SGA采用的遺傳操作及相應(yīng)參數(shù)為比例選擇、單點(diǎn)交叉(交叉概率0.85)及基本位變異(變異概率0.05)，種群規(guī)模為100，進(jìn)化代數(shù)為100。兩者都采用保留個(gè)體精英的方法。選擇如下3個(gè)算例進(jìn)行仿真計(jì)算。

(1) Camel函數(shù)

f1(x,y)=(4-2.1x2+x4/3)x2+xy+(4y2-4)y2

此函數(shù)有6個(gè)極小點(diǎn)，其中有2個(gè)(-0.089 8,0.712 6)和(0.089 8,-0.712 6)為全局最小點(diǎn)，最小值為-1.031 628，自變量的取值范圍為 -100＜x,y＜100。

(2) Shubert函數(shù)

f2(x,y)=∑5i=1icos［(i+1)x+1·

∑5i=1icos［(i+1)y+1+

0.5［(x+1.425 13)2+(y+0.800 32)2］

該函數(shù)有760個(gè)局部極小點(diǎn)，其中只有1個(gè)(-1.425 13,-0.800 32)為全局最小，最小值為186.730 9。自變量取值范圍 -10＜x,y＜10。此函數(shù)極易陷入局部極小值186.34。

(3) Schaffer函數(shù)

f3(x,y) = 0.5-sin2x2+y2-0.52

該函數(shù)有無限個(gè)局部極大點(diǎn)，其中只有一個(gè)(0,0)為全局最大，最大值為1。自變量的取值范圍為-100＜x,y＜100。該函數(shù)最大值峰周圍有一個(gè)圈脊，它們的取值均為0.990 283，因此很容易停滯在局部極大值。

改進(jìn)后算法的種群規(guī)模為20，進(jìn)化代數(shù)為60。對兩種算法進(jìn)行100次隨機(jī)仿真，試驗(yàn)結(jié)果如表1所示。

表1 試驗(yàn)結(jié)果

函數(shù)

SGA 最好解 最差解平均收斂代數(shù) 成功率%改進(jìn)后遺傳算法最好解最差解平均收斂代數(shù)成功率%

f1-1.031 628-1.031 6278177-1.031 628-1.031 62848100

f2186.730 9186.725 88773186.730 9186.730 75291

f311.000 02636871111100

3.2 結(jié)果分析

從以上結(jié)果可以看出，SGA容易早熟收斂，而改進(jìn)后的算法能很好地?cái)[脫早熟，并能以很高的成功概率快速搜索到最優(yōu)值。從各參數(shù)也可以看出，改進(jìn)后的遺傳算法在種群規(guī)模很小的情況下也具有很高的尋優(yōu)效率。因此，這里提出的改進(jìn)算子GA從全局收斂概率和平均進(jìn)

化代數(shù)來看，是成功的，它具有高效的全局以及局部搜索能力。

4 結(jié) 語

通過對算法各算子的改進(jìn)，較好地解決了一般遺傳算法收斂速度慢和全局尋優(yōu)能力弱的缺點(diǎn)。實(shí)踐表明，改進(jìn)GA和標(biāo)準(zhǔn)GA相比，在花費(fèi)更少的情況下具有更快的收斂速度和精度。

參考文獻(xiàn)

［1］王小平,曹立明.遺傳算法——理論,應(yīng)用與軟件實(shí)現(xiàn).西安:西安交通大學(xué)出版社,2002.

［2］王忠,柴賀軍,劉浩吾.關(guān)于遺傳算法的幾點(diǎn)改進(jìn)［J］.電子科技大學(xué)學(xué)報(bào),2002,31(1):76－80.

［3］熊范倫,鄧超.退火遺傳算法及其應(yīng)用［J］.生物數(shù)學(xué)學(xué)報(bào),2000,15(2):150－154.

［4］張毅,楊秀霞.一種基于能量熵的快速遺傳算法研究［J］.系統(tǒng)工程理論與實(shí)踐,2005(2):123－128.

［5］金朝紅.一種基于自適應(yīng)遺傳算法的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法［J］.微計(jì)算機(jī)信息,2005,10(1):49－51.

［6］張文修,梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)［M］.西安:西安交通大學(xué)出版社,2003.

［7］Qi Xiaofeng.Theoretical Analysis of Evolutionary Algorithms With an Infinite Population Size in Continuous Space Part II:Analysis of the Diversification Role of Crossover［J］.IEEE Transactions on Neural Networks,1994,5(1):120－129.

［8］陶林波.一種解決早熟收斂的自適應(yīng)遺傳算法設(shè)計(jì)［J］.微計(jì)算機(jī)信息,2006,12(1):268－270.

［9］Introduction to Genetic Algorithms.http://www.rennard.org/alife/english/gavintrgb.html.

［10］Genetic Algorithm－Traveller in Space.http://arc.net.cn/wiki/pmwiki.php/R/GeneticAlgorithm.

［11］桂超,汪波.基于遺傳算法的最短路徑路由優(yōu)化算法［J］.微計(jì)算機(jī)信息,2005,12(2):193－195.

作者簡介

鄧洋春 男，1983年出生，江西南昌人，碩士研究生。主要研究方向?yàn)橹悄芩惴?，Java技術(shù)。

梁昔明 男，1967年出生，博士，教授，博士生導(dǎo)師。主要研究方向?yàn)檫^程控制與系統(tǒng)優(yōu)化、進(jìn)化計(jì)算與人工生命。