實數自適應并行遺傳算法的研究

摘要：針對遺傳算法中的早收斂現象，提出了一種實數自適應并行遺傳算法（real adaptive parallel genetic algorithm，RAPGA）。該算法采用了一種并行遺傳進化結構，并將自適應交叉、變異算子引入到本算法中，增強和保持了種群的多樣性。最后，通過與其他經典優(yōu)化遺傳算法進行比較顯示，RAPGA對多個標準測試函數均表現出較好的搜索性能。

關鍵詞：并行; 遺傳算法; 實數; 自適應

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001－3695(2008)06－1687－03

0引言

遺傳算法是一類借鑒自然選擇和自然遺傳機制的隨機優(yōu)化搜索算法。它以進化論和基因遺傳學說為基礎，模擬了生物進化過程，通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的個體，使種群中的優(yōu)質個體比例逐漸增加，最終使整個種群收斂到最優(yōu)解。該算法因其在解決各類非線性問題時表現出的魯棒性、全局最優(yōu)性、可并行性及高效率受到眾多學者的關注，已被廣泛應用于機器學習、人工智能、復雜組合優(yōu)化、自適應控制、人工神經網絡權值的訓練等各種智能領域。然而遺傳算法容易出現早收斂和收斂速度慢的缺點。為此許多學者對遺傳算法進行了改進。改進的方式有傳統(tǒng)遺傳算子的改進和引入混合遺傳算子。

改進傳統(tǒng)遺傳算子主要是通過改善選擇算子、交叉算子或變異算子增強遺傳算法的性能。最早研究的遺傳算法是簡單遺傳算法（SGA）。其算法思路直觀、操作簡單，但其收斂速度慢且受參數選擇的影響。針對SGA的缺點，文獻[1] 改進了選擇算子，提出種群替換法，在父代中挑選出一個與新個體最相似的個體進行替換，保持了種群的多樣性。文獻[2]提出了自適應遺傳算法（AGA），對交叉算子和變異算子進行了改進。AGA將交叉概率、變異概率和適應度值聯系起來，隨著種群平均適應度的改變而自適應調節(jié)交叉突變概率，能更好地保持種群的多樣性，保存優(yōu)良個體，但沒有考慮到更好地增加種群的多樣性。

另一種方式是將遺傳算子與其他一些優(yōu)秀的算法結合，稱為混合遺傳算子。例如，將貪婪算法和遺傳算法相結合用于旅行商問題；將模擬退火算法和遺傳算法相結合用于避免遺傳算法早熟等。

本文提出了一種新的實數并行自適應遺傳算法（RAPGA），獨特的并行結構和改進（μ+λ）選擇算子能夠有效地防止局部早收斂，增強全局搜索能力。實驗結果表明，RAPGA對各種復雜基準函數都可以保證以很快的速度收斂到全局最優(yōu)值，優(yōu)化效果明顯優(yōu)于其他遺傳算法。

1實數自適應并行遺傳算法(RAPGA)

1．1算法描述

為了提高算法的運算速度，RAPGA采用實數的表示方式，避免了二進制表示方式開銷太大的缺點。

算法在結構上采用了一種新型的并行遺傳結構，不同于以往的異步遺傳結構。如果采用先交叉后變異的異步遺傳結構，進化初期交叉作用產生的優(yōu)質個體在變異中可能被破壞，從而影響種群的進化速度；進化末期也可能因此影響搜索結果的精度。為此本文提出并行遺傳結構，同代中交叉運算和變異運算互不相關，兩個算子并行處理。這種并行操作結構的優(yōu)點在于能夠讓交叉、變異作用產生的優(yōu)質個體無損壞地進入下一代，避免了種群在進化過程中受到不當因素的干擾而丟失。同時，RAPGA也對遺傳算子進行了改進，選擇采用改進（μ+λ）選擇算子。計算交叉概率時引入海明距離，變異時根據種群的進化程度不斷收縮算子的擾動范圍，提高了全局搜索的效率。

1．2改進的遺傳算子

1．2．1改進（μ+λ）選擇算子

RAPGA采用改進（μ+λ）選擇算子進行選擇運算，增強了種群的多樣性。先復制父代，將父代備份分別進行交叉和變異，然后在父代和得到的新種群中選擇適應度最好的個體組成新的父代。

 常見的依概率選擇法（如輪盤選擇法、期望值法）由于模仿了適者生存，不適應者淘汰的自然法則被普遍應用于遺傳算法中。然而，種群規(guī)模的有限性使得依概率選擇法在算法初期容易出現局部頂端優(yōu)勢，即種群中的超級個體會因為適應度遠大于其他個體而被大量選擇。這樣造成了下一代大多來源于同一個體，種群的多樣性遭到了破壞，所謂高度并行性的優(yōu)勢也就不存在了。

改進（μ+λ）選擇算子采取了父代和子代共同參與競爭的方式 。父代和兩個子代經過選擇后，優(yōu)質個體每代繁殖的次數不超過3，不少于1，降低了選擇壓力，有效地防止了初期局部頂端優(yōu)勢現象的發(fā)生。

1．2．2自適應交叉算子

RAPGA在交叉過程中采用了離散位交叉方式，并在AGA[3]的交叉概率公式的基礎上引入海明距離參數，使交叉概率根據交叉?zhèn)€體的不同而變化。此算子避免了近親繁殖，提高了交叉算子的效率，有利于種群的多樣性。實現步驟如下：

a)將chromosome按位離散裝在預先分配好的基因位池中，如個體4586：

4586

b)根據變異概率pm進行實數非均勻變異，設變異個體的編碼是x，新個體x′=x+yλ(1-g/G)γ 。為防止新個體超出區(qū)域邊界，設置y=min(x，b′-x)，b′為定義域的最大值，λ=U(-1，1)。G是最大進化代數。如果超過G代算法沒有自適應停止，就視做算法搜索失敗，算法停止。g是當前進化代數，γ代表非均勻性程度，范圍為[0，1]。

非均勻變異實現了最初在g很小的時候，算子在空間中均勻搜索。隨著g的增長，搜索范圍逐漸減小，滿足了初期大范圍搜索、后期小范圍搜索的要求，有利于收斂于全局最優(yōu)值和提高搜索精度。

1．3停止條件

綜合考慮種群適應度平均值和方差。平均適應度越大，說明種群中的個體越好；方差越小，說明種群中個體分布越集中。測定公式為Stop= E(fit)-VAR(fit)，fit為種群的適應度矩陣。如果新種群的Stop值小于父種群，算法停止。

上面的條件由于考慮了二階矩，準確性高，但計算時間長，在實時性要求高的條件下，可以只考慮種群適應度的平均值，即Stop=E(fit)，如果Stop的值連續(xù)超過閾值次數不發(fā)生變化。閾值的取值與種群大小和要求結果的可靠性成正比。在RAPGA中，閾值一般為種群大小的1/3。

1．4算法的實現

實數自適應并行遺傳算法（RAPGA）的方案和流程圖如圖1所示。

1．5收斂性分析

遺傳算法中，種群多樣性和選擇壓力是影響收斂效果的主要因素。RAPGA采用的并行結構和改進(μ+λ)選擇算子在初期階段降低了選擇壓力，有利于種群多樣性，保證了算法的并行搜索能力。自適應交叉和變異算子根據個體適應度調整pc、pm，既保留了進化過程中的優(yōu)質個體，也增大了種群的搜索空間。在終止階段變異算子更傾向于局部搜索，提高了搜索精度。

2測試實驗

為了驗證本算法的有效性和穩(wěn)定性，筆者參考了一些論文中采用的標準測試函數。測試所用的函數列于表1。分別對RAPGA和SGA[5]、AGA[2]、GAVaPS[6]進行測試比較。為了便于性能比較，除GAVaPS，所有遺傳算法初始種群的大小都固定為30。RAPGA、AGA、GAVaPS為自適應停止，RAPGA、AGA、SGA最大進化代數為100。表2記錄了RAPGA和AGA、SGA的實驗結果，比較的性能指標包括平均優(yōu)化結果（50次）、結果偏離度、平均進化代數（最大代數100）、計算時間四個參數。結果偏離度=（最大值-搜索結果中的最小值）/最大值×100%，它反映了最終結果的收斂程度。

從平均優(yōu)化結果和結果偏離度兩個指標綜合比較，RAPGA除F5函數不能每次收斂于全局最優(yōu)，其余的函數都能收斂到全局最優(yōu)域。F1、F2、F3、F4、F7中RAPGA的平均優(yōu)化結果和標準極值偏差最大為3．65%；AGA為27．97%；SGA為20．14%，說明了RAPGA比AGA、SGA具有更優(yōu)越的全局搜索能力。這主要是因為RAPGA獨特的并行結構和改進(μ+λ)選擇算子在初期保留了種群的多樣性，使搜索空間能夠收斂到全局最優(yōu)域，在后期自適應變異算子使得搜索空間自適應縮小，提高了搜索精度，達到了滿意的結果。

從平均進化代數來看，RAPGA較其他算法更加穩(wěn)定，收斂代數一般在20~30次左右。因為改進(μ+λ)進化選擇避免了局部頂端優(yōu)勢現象的發(fā)生，保證了平穩(wěn)的進化過程，使種群不會過早收斂。

2．1RAPGA和GAVaPS的性能對比

表4用RAPGA測試了文獻[6]中的標準函數，并與GAVaPS、SGA的優(yōu)化結果進行了比較。標準函數如表3所示。

以上函數都是含有許多局部次優(yōu)解的多峰函數。G2不能通過任何梯度求解的方法優(yōu)化，因為不存在可用的梯度信息；G3是帶有欺騙性的問題。在表4中， RAPGA種群固定為30，其余算法種群固定為75。其中：P為平均優(yōu)化結果 ； E為平均進化代數。

2．2性能曲線比較

圖2(a)(b)分別描繪了SGA、AGA、RAPGA算法測試f6、f7的進化曲線。

從圖2的比較中可以看出，三種算法的初始種群是一致的。從相同起點開始搜索，RAPGA搜尋到的最優(yōu)值接近全局最優(yōu)，而且收斂的速度也最快，反映了較好的全局搜索能力和收斂速度。另外，相對于階梯狀的進化曲線，RAPGA的曲線平滑，說明整個進化過程中種群整體逐漸向全局最優(yōu)值進化，有效地防止了局部頂端優(yōu)勢的發(fā)生，表現出必然收斂的趨勢。

3結束語

RAPGA針對傳統(tǒng)異步遺傳結構的缺點，引入了自適應并行遺傳算子的進化策略，在進化初期降低了選擇壓力，增強了種群多樣性，有效地防止了早收斂。

測試實驗結果表明，RAPGA具有很強的魯棒性和較高的收斂性。該算法中絕大部分參數都實現了自適應調整，不需要太多的先驗知識，可操作性強，具有很強的通用性。下一步要研究的方向是如何將該算法應用到其他問題中，如機器學習、特征選擇。

參考文獻：

［1］GOLDBERG D E．Genetic algorithms in search，optimization， and machine learning[M].Massachusetts:Addison－Wesley，1989:735－749.

[2]SRINIVAS M，PATNAIK M．Adaptive probabilities of crossover and mutation in genetic algorithms[J]．IEEE Trans on Systems，Man and Cybernetics，1994，24(4):656－659.

[3]MICHALEWICZ Z．Genetic algorithms+datastructures=evolution programs[M]．New York:Springer－Verlag，1996.

[4]張文修，梁怡.遺傳算法的數學基礎[M]．西安:西安交通大學出版社，2000:256－289.

[5]HOLLAND J H．Adaptation natural and artificial systems[M].Ann Arbor:University of Michigan Press，1975:30－134.

[6]GEN M，CHENG Run－wei.Genetic algorithm and project design [M].[S.l.]: Wiley，2001.

[7]ARABAS J，MICHALEWICZ Z， MULAWKA J. GAVaPS:a genetic algorithm with varying population size[C]//Proc of the 1st Confe－rence on Evolutionary， IEEE World Congress on Computational Intelligence. Orlando:[s.n.]，1994:73－78.

[8]MAC F，BHRIDE G，McGINNITV T M， et al．Landscape classification and problem specific reasoning for genetic algorithms[J].Krbernetes ，2005，34(9/10):1469－1495.

[9]徐宗本，高勇. 遺傳算法過早收斂現象的特征分析及其預防[J]．中國科學（E輯），1996，26 (4): 364－375．

[10]馬鈞水，劉貴忠，賈玉蘭.改進遺傳算法搜索性能的大變異操作[J]．控制理論與應用，1998，15(3): 404－408．

[11]De JDNE K． An analysis of the behavior of a class of genetic adaptive system[D].San Mateo:[s.n.]，1975:103－156.

[12]De JDNE，K. A genetic algorithms: a 10 year perspective[C]//Proc of the 1st International Conference on Genetic Algorithms and Their Applications.1985:169－177.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文