一種改進操作算子的加速收斂遺傳算法

鄧洋春　梁昔明

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

關鍵詞：遺傳算法；變異；收斂速度；種群數

中圖分類號：TP391文獻標識碼：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)是一種宏觀意義下的仿生算法，它模仿的機制是一切生命與智能的產生與進化過程，從一個初始種群出發，不斷重復執行選擇，雜交和變異的過程，使種群進化越來越接近某一目標。它通過模擬達爾文“優勝劣汰，適者生存”的原理激勵好的結構；通過模擬孟德爾遺傳變異理論在迭代過程中保持已有的結構，同時尋找更好的結構。經典遺傳算法的求解步驟為：初始化種群；選擇；交叉；變異；判斷終止條件。由于它簡單有效，具有很強的魯棒性和通用性，所以被廣泛應用于模式識別、神經網絡、圖像處理、機器學習、工業優化控制、自適應控制、生物科學、社會科學等多種領域［1］。

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

1 改進操作算子的遺傳算法

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

1.1 初始化

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

1.2 選擇操作

經典遺傳算法根據適者生存原則選擇下一代個體。在選擇時，以適應度為選擇原則。適應度準則體現了適者生存，不適應者淘汰的自然法則。

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

如：X=100101，Y=011110

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

X=110101，Y=101110

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

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

1.3 交叉操作

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

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

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

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

1.4 變異操作

根據生物遺傳中基因變異的原理，以變異概率P璵對某些個體的某些位執行變異。在變異時，對執行變異的串的對應位求反，即把1變為0，把0變為1。

單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產生無法進化的單一群體。因為在所有的個體一樣時，交叉是無法產生新的個體的，這時只能靠變異產生新的個體。也就是說，變異增加了全局優化的特質。

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

2 算法描述

算法描述為：

(1) 采用二進制編碼，隨機產生一個體，通過逐位高頻精英變異，提高其適應度；

(2) 利用上述較優父染色體產生產生種群；

(3) 進行基于高頻精英變異的錦標賽選擇；

(4) 進行改進的交叉運算；

(5) 進行自適應變異運算；

(6) 是否到最大的遺傳代數，如果達到，結束；否則轉到步驟(3)。

3 仿真試驗及結果分析

3.1 試驗

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

(1) Camel函數

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

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

(2) Shubert函數

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］

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

(3) Schaffer函數

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

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

改進后算法的種群規模為20，進化代數為60。對兩種算法進行100次隨機仿真，試驗結果如表1所示。

表1 試驗結果

函數

SGA 最好解 最差解平均收斂代數 成功率%改進后遺傳算法最好解最差解平均收斂代數成功率%

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 結果分析

從以上結果可以看出，SGA容易早熟收斂，而改進后的算法能很好地擺脫早熟，并能以很高的成功概率快速搜索到最優值。從各參數也可以看出，改進后的遺傳算法在種群規模很小的情況下也具有很高的尋優效率。因此，這里提出的改進算子GA從全局收斂概率和平均進

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

4 結 語

通過對算法各算子的改進，較好地解決了一般遺傳算法收斂速度慢和全局尋優能力弱的缺點。實踐表明，改進GA和標準GA相比，在花費更少的情況下具有更快的收斂速度和精度。

參考文獻

［1］王小平,曹立明.遺傳算法——理論,應用與軟件實現.西安:西安交通大學出版社,2002.

［2］王忠,柴賀軍,劉浩吾.關于遺傳算法的幾點改進［J］.電子科技大學學報,2002,31(1):76－80.

［3］熊范倫,鄧超.退火遺傳算法及其應用［J］.生物數學學報,2000,15(2):150－154.

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

［5］金朝紅.一種基于自適應遺傳算法的神經網絡學習算法［J］.微計算機信息,2005,10(1):49－51.

［6］張文修,梁怡.遺傳算法的數學基礎［M］.西安:西安交通大學出版社,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］陶林波.一種解決早熟收斂的自適應遺傳算法設計［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］桂超,汪波.基于遺傳算法的最短路徑路由優化算法［J］.微計算機信息,2005,12(2):193－195.

作者簡介

鄧洋春 男，1983年出生，江西南昌人，碩士研究生。主要研究方向為智能算法，Java技術。

梁昔明 男，1967年出生，博士，教授，博士生導師。主要研究方向為過程控制與系統優化、進化計算與人工生命。