實(shí)數(shù)自適應(yīng)并行遺傳算法的研究

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

關(guān)鍵詞：并行; 遺傳算法; 實(shí)數(shù); 自適應(yīng)

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

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

0引言

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

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

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

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

1實(shí)數(shù)自適應(yīng)并行遺傳算法(RAPGA)

1．1算法描述

為了提高算法的運(yùn)算速度，RAPGA采用實(shí)數(shù)的表示方式，避免了二進(jìn)制表示方式開銷太大的缺點(diǎn)。

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

1．2改進(jìn)的遺傳算子

1．2．1改進(jìn)（μ+λ）選擇算子

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

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

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

1．2．2自適應(yīng)交叉算子

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

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

4586

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

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

1．3停止條件

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

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

1．4算法的實(shí)現(xiàn)

實(shí)數(shù)自適應(yīng)并行遺傳算法（RAPGA）的方案和流程圖如圖1所示。

1．5收斂性分析

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

2測(cè)試實(shí)驗(yàn)

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

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

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

2．1RAPGA和GAVaPS的性能對(duì)比

表4用RAPGA測(cè)試了文獻(xiàn)[6]中的標(biāo)準(zhǔn)函數(shù)，并與GAVaPS、SGA的優(yōu)化結(jié)果進(jìn)行了比較。標(biāo)準(zhǔn)函數(shù)如表3所示。

以上函數(shù)都是含有許多局部次優(yōu)解的多峰函數(shù)。G2不能通過任何梯度求解的方法優(yōu)化，因?yàn)椴淮嬖诳捎玫奶荻刃畔ⅲ籊3是帶有欺騙性的問題。在表4中， RAPGA種群固定為30，其余算法種群固定為75。其中：P為平均優(yōu)化結(jié)果 ； E為平均進(jìn)化代數(shù)。

2．2性能曲線比較

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

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

3結(jié)束語

RAPGA針對(duì)傳統(tǒng)異步遺傳結(jié)構(gòu)的缺點(diǎn)，引入了自適應(yīng)并行遺傳算子的進(jìn)化策略，在進(jìn)化初期降低了選擇壓力，增強(qiáng)了種群多樣性，有效地防止了早收斂。

測(cè)試實(shí)驗(yàn)結(jié)果表明，RAPGA具有很強(qiáng)的魯棒性和較高的收斂性。該算法中絕大部分參數(shù)都實(shí)現(xiàn)了自適應(yīng)調(diào)整，不需要太多的先驗(yàn)知識(shí)，可操作性強(qiáng)，具有很強(qiáng)的通用性。下一步要研究的方向是如何將該算法應(yīng)用到其他問題中，如機(jī)器學(xué)習(xí)、特征選擇。

參考文獻(xiàn)：

［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]張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M]．西安:西安交通大學(xué)出版社，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]徐宗本，高勇. 遺傳算法過早收斂現(xiàn)象的特征分析及其預(yù)防[J]．中國科學(xué)（E輯），1996，26 (4): 364－375．

[10]馬鈞水，劉貴忠，賈玉蘭.改進(jìn)遺傳算法搜索性能的大變異操作[J]．控制理論與應(yīng)用，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.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文