遺傳算法中種群維護(hù)策略的比較

譚 陽(yáng)，方 頌

(湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院，湖南長(zhǎng)沙 410004)

遺傳算法中種群維護(hù)策略的比較

譚 陽(yáng)，方 頌*

(湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院，湖南長(zhǎng)沙 410004)

遺傳算法在許多優(yōu)化問(wèn)題中都有成功的應(yīng)用，但其本身也存在一些不足。如何改善遺傳算法的搜索能力，使其兼顧收斂速度和搜索范圍，能更好地解決實(shí)際問(wèn)題，一直是智能計(jì)算領(lǐng)域主要的課題之一。本文就3種常見(jiàn)的種群維護(hù)策略進(jìn)行了比較與討論，并分析了不同策略的優(yōu)劣之處。

遺傳算法;選擇策略;適應(yīng)度排序;歐氏距離;海明距離

一、引言

遺傳算法(Genetic Algorithm ，GA)［1］是一種模擬生物進(jìn)化中遺傳選擇和自然淘汰過(guò)程的計(jì)算模型。其算法思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，通過(guò)采用“生存+檢測(cè)”的迭代過(guò)程進(jìn)行尋優(yōu)搜索。由于遺傳算法具有不依賴于問(wèn)題模型的特點(diǎn)，且還具有全局最優(yōu)性、隱含并行性、高效率以及解決非線性問(wèn)題穩(wěn)定等特點(diǎn)，被廣泛地應(yīng)用于各個(gè)領(lǐng)域。尤其在數(shù)值優(yōu)化領(lǐng)域，遺傳算法以其對(duì)求解問(wèn)題限制少，不要求目標(biāo)函數(shù)連續(xù)可微等特性而倍受關(guān)注。但是遺傳算法同樣也存在局部搜索能力較差，全局優(yōu)化速度緩慢，易出現(xiàn)早熟收斂等問(wèn)題。

不失一般性，考慮如下全局優(yōu)化問(wèn)題:

式中，x=(x1，x2，…，xm)∈D，D?Rm為搜索空間，f:Rm→R 為目標(biāo)函數(shù)，L=(l1，l2，…，lm)，U=(u1，u2，…，um)，［L，U］={(x1，x2，…，xm)=|li≤xi≤ui，i=1，2，…，m|}表示可行解空間，［L，U］= ?D，Q=D［L，U］為不可行解空間。

定義 1:向量 u=(u1，u2，…，um)稱為非劣于(Dominated)向量 v=(v1，v2，…，vm)，當(dāng)且僅當(dāng)對(duì)于?i∈{1，2，…，m}，ui≤vi∧?i∈{1，2，…，m}，使得ui＜vi。

基本遺傳算法中采用單點(diǎn)交叉算子和簡(jiǎn)單的變異算子，優(yōu)點(diǎn)是操作簡(jiǎn)單、計(jì)算開(kāi)銷小，但是在使用過(guò)程存在很大的局限性［2］，由于單點(diǎn)交叉破壞模式的概率較小，導(dǎo)致搜索到的模式數(shù)目也較少，從而算法具有的搜索能力較低，難以對(duì)多維連續(xù)空間的問(wèn)題進(jìn)行有效搜索。

二、GA種群的維護(hù)策略

為了能保留GA在整個(gè)迭代搜索過(guò)程中偶然發(fā)現(xiàn)的“最優(yōu)個(gè)體”，并使種群進(jìn)化方向具備導(dǎo)向性，通常GA都會(huì)采用精英保留機(jī)制。在精英保留及指導(dǎo)機(jī)制的作用下會(huì)使得GA搜索效率得到很大的提高，但是帶來(lái)的負(fù)面效應(yīng)是對(duì)目標(biāo)函數(shù)的搜索不夠全面，容易使得算法陷入局部極值區(qū)，產(chǎn)生早熟現(xiàn)象，從而無(wú)法搜索到全局最優(yōu)解。為此當(dāng)前GA研究的重點(diǎn)在如何合理地維護(hù)種群的多樣性。

在GA優(yōu)化搜索過(guò)程中，對(duì)于種群的選擇策略主要采用懲罰函數(shù)法［3］－［8］，但優(yōu)化搜索的效率對(duì)懲罰函數(shù)的選擇有明顯的依賴性。同時(shí)，各種懲罰函數(shù)特性各異，其參數(shù)因子沒(méi)有統(tǒng)一的選擇標(biāo)準(zhǔn)，使得選擇策略的取舍非常困難。若對(duì)不可行解直接采用簡(jiǎn)單的拒絕策略，種群中只保留可行解，則會(huì)大大減少搜索范圍，以致GA很難收斂到最優(yōu)解。通常采用的策略是:先基于某一懲罰函數(shù)的方法，選擇出可行解和不可行解，并按照一定的比例或要求對(duì)可行解和不可行解進(jìn)行種群混合。就國(guó)內(nèi)外的研究情況而言，對(duì)于GA種群維護(hù)的策略主要可以歸納為3大類型:

1.目標(biāo)函數(shù)指導(dǎo)

這類方法以目標(biāo)函數(shù)的優(yōu)化要求為基準(zhǔn)，以篩選出種群中的最優(yōu)個(gè)體為目標(biāo)，并以適應(yīng)度高低為評(píng)價(jià)體系對(duì)種群中所有個(gè)體以進(jìn)行分級(jí)排序。某個(gè)體被篩選的依據(jù)是種群存在多少個(gè)個(gè)體優(yōu)勝于該個(gè)體，并以此作為下次進(jìn)化過(guò)程的選擇的依據(jù)。目標(biāo)函數(shù)指導(dǎo)方法操作簡(jiǎn)單，是一種完全按照“優(yōu)勝劣汰”模式選擇的策略，其典型代表為:適應(yīng)度排序算法，該算法以適應(yīng)度為主要關(guān)鍵字對(duì)種群個(gè)體進(jìn)行排序，基本方法以快速排序?yàn)橹鳎灿猩倭渴褂猛芭判蚝陀?jì)數(shù)排序［9］。

2.目標(biāo)空間距離

空間距離是目前應(yīng)用得較多的一種策略，也是現(xiàn)在研究的熱點(diǎn)之一。該策略以某些特定個(gè)體為依據(jù)，并通過(guò)這些特定個(gè)體映射在目標(biāo)函數(shù)空間之上，使之形成一些特定點(diǎn)(基點(diǎn))其他個(gè)體也以點(diǎn)的形式在函數(shù)空間中投射，但其與基點(diǎn)的距離有特定要求，當(dāng)小于某一值時(shí)則被GA舍棄。這是一種能夠在相當(dāng)程度維護(hù)種群多樣性的策略，其特點(diǎn)是使某些特定點(diǎn)具有一定的“排異”半徑，能夠在多個(gè)維度上“排擠”距離過(guò)于接近的其他個(gè)體，從而使得種群以較少量的個(gè)體維持在解空間中的有效分布，其典型的代表為:歐氏(歐幾里得，Euclid)距離算法，式(2)為a、b兩點(diǎn)在空間中歐氏距離e(a，b)的計(jì)算公式［10］。

其中 x、y、z分別為 a、b 兩點(diǎn)的坐標(biāo)值，n 為 a、b兩點(diǎn)所處空間的維度。

3.種群個(gè)體結(jié)構(gòu)

此類策略應(yīng)用較為少見(jiàn)，該策略的核心思想是以種群中個(gè)體的基因代碼結(jié)構(gòu)為依據(jù)來(lái)進(jìn)行選擇，目的是使具有類似基因結(jié)構(gòu)的個(gè)體能夠聚集，形成小生境環(huán)境并協(xié)同進(jìn)行進(jìn)化;或是以基因結(jié)構(gòu)差異的大小來(lái)作為種群維護(hù)的依據(jù)。可以看出此策略和目標(biāo)空間距離策略具有類似之處，前者以超平面空間為衡量依據(jù)，后者以幾何空間為衡量依據(jù)。其典型的代表為:海明距離(Hamming Distance)算法，若a、b為算法種群中兩個(gè)采用2進(jìn)制編碼的個(gè)體，那么a、b 間的海明距離 h(a，b)由下式(3)計(jì)算得出［11］。

其中L為個(gè)體的2進(jìn)制編碼長(zhǎng)度，l為相同位置的編碼位。

圖1 3種類型的種群維護(hù)策略

圖1中為3種維護(hù)策略對(duì)于基礎(chǔ)點(diǎn)(0，0)在2維空間上的選擇示意圖。可以看出適應(yīng)度排序?qū)τ谒阉骺臻g的覆蓋是基于隨機(jī)分布的，并以其獨(dú)立個(gè)體作為指導(dǎo)，若需要較為有效地覆蓋搜索空間則需要大量的個(gè)體進(jìn)行隨機(jī)嘗試;但通常為了合理控制計(jì)算開(kāi)銷，GA在使用中會(huì)限制種群規(guī)模，這使得適應(yīng)度排序策略對(duì)搜索空間的覆蓋存在較大的隨機(jī)性。歐氏距離策略則能夠很好的解決有效覆蓋需要個(gè)體過(guò)多的問(wèn)題，圖1(b)中可以看出只需很少量的個(gè)體即可較為有效地覆蓋搜索空間，但是可行解的分布卻與適應(yīng)度排序一樣呈現(xiàn)隨機(jī)性和無(wú)序性。海明距離的個(gè)體分布具有明顯的規(guī)律性，并呈現(xiàn)出“內(nèi)緊外松”的分布特性，這種分布可以很好地兼顧算法搜索的效率和分布問(wèn)題，但是海明距離是一種針對(duì)2進(jìn)制代碼的維護(hù)策略，對(duì)于采用實(shí)數(shù)編碼的問(wèn)題則無(wú)法運(yùn)用，同時(shí)也可以看出為了保證海明距離策略的有效性，種群個(gè)體的數(shù)目遠(yuǎn)比歐氏距離策略的要高。

三、仿真測(cè)試

為了對(duì)分別采用3種維護(hù)策略的GA進(jìn)行評(píng)價(jià)，本文在基本GA的基礎(chǔ)上，建立了一個(gè)外部精英種群用于保存GA在迭代搜索過(guò)程搜索到的精英個(gè)體，并使用外部精英種群作為交叉操作的參照對(duì)象。對(duì)種群維護(hù)的策略分別采用適應(yīng)度排序(Fitness－GA，F(xiàn)GA)、歐氏距離(Euclid －GA，EGA)和海明距離(Hamming－GA，HGA)3種方法進(jìn)行維護(hù)。函數(shù)優(yōu)化實(shí)驗(yàn)是測(cè)試迭代搜索算法性能的必備實(shí)驗(yàn)［12］［13］，測(cè)試所用的4個(gè)基準(zhǔn)函數(shù)具有較強(qiáng)的代表性，通過(guò)尋找這些函數(shù)的最小值可以評(píng)價(jià)尋優(yōu)算法的尋優(yōu)性能及收斂速度，并可判斷算法是否具有較好的健壯性和穩(wěn)定性。

選取的測(cè)試函數(shù)f1為單峰函數(shù);函數(shù)f2、f3和f4為多峰函數(shù)，存在多個(gè)局部極值，并且其局部最優(yōu)解的個(gè)數(shù)隨著維數(shù)的增加成幾何級(jí)增加，這四個(gè)函數(shù)均在(0，0，…，0)處取得全局最優(yōu)解。3種對(duì)比策略的給定維數(shù)分別為5維和10維，種群規(guī)模為50，最大迭代次數(shù)為500，算法的終止條件為:達(dá)到最大迭代次數(shù)或者N＞20，其中N表示連續(xù)的第Ti+1代和第Ti代種群最優(yōu)值之間的差為0的次數(shù)。為了進(jìn)行有效對(duì)比3種策略，對(duì)4個(gè)測(cè)試函數(shù)均使用相同的初始種群并獨(dú)立按不同維數(shù)進(jìn)行20次實(shí)驗(yàn)。

表1中為3種對(duì)比策略對(duì)函數(shù)f1～f4的測(cè)試結(jié)果，為了體現(xiàn)各種維護(hù)策略GA的性能，這里選取了3個(gè)指標(biāo)作為對(duì)算法評(píng)價(jià)的衡量依據(jù)，分別為:平均全局最優(yōu)解出現(xiàn)的代數(shù)，記為NGO;出現(xiàn)全局最優(yōu)解的平均執(zhí)行時(shí)間s，記為ART;平均種群最優(yōu)解，記為AGO。

表1中的尋優(yōu)數(shù)據(jù)表明，在對(duì)函數(shù)f1、f3和f4平均尋優(yōu)結(jié)果而言HGA的結(jié)果較其他算法更為精確。對(duì)函數(shù)f2優(yōu)化中HGA在平均精度上略遜于EGA，經(jīng)分析f2函數(shù)為U型結(jié)構(gòu)最優(yōu)值呈線性分布，相對(duì)來(lái)說(shuō)以“面”進(jìn)行尋優(yōu)的算法要好于以“點(diǎn)”進(jìn)行尋優(yōu)的算法;但是就全局最優(yōu)解的平均迭代次數(shù)和平

表1 對(duì)函數(shù)f1～f4優(yōu)化性能的比較

函數(shù)f5(Needle－in－a－Haystack)的參數(shù) a，b取 a=3.0，b=0.05，該函數(shù)為典型的欺騙函數(shù)。圖2(a)為該函數(shù)在MATLAB中的模擬圖像，該函數(shù)的最優(yōu)點(diǎn)分布在(0，0)處;4個(gè)局部極值點(diǎn)對(duì)稱分布在4個(gè)角上，這些局部極值點(diǎn)距離全局最優(yōu)點(diǎn)的距離很大，且函數(shù)在相當(dāng)?shù)娜≈捣秶鷥?nèi)單調(diào)，通常優(yōu)化算法難以獲得全局最優(yōu)解。測(cè)試中，3種對(duì)比策略的給定維數(shù)為2，種群規(guī)模為20，最大迭代次數(shù)為500，算法的終止條件為N＞20;每種算法獨(dú)立運(yùn)行10次并記錄種群最優(yōu)解。均搜索時(shí)間上FGA則領(lǐng)先于這兩個(gè)對(duì)比策略。也可以看出FGA較為簡(jiǎn)單的維護(hù)策略并沒(méi)有使得GA在迭代搜索過(guò)程中的計(jì)算開(kāi)銷明顯增加，因此搜索速度較快。EGA則是3種策略中耗時(shí)最大的，這主要是因?yàn)樾枰獙?duì)所有搜索的結(jié)果進(jìn)行映射計(jì)算和取舍，計(jì)算量較大。

圖2 對(duì)函數(shù)的優(yōu)化情況

在對(duì)函數(shù)f5的優(yōu)化中HGA和EGA都能搜索到全局最優(yōu)解，F(xiàn)GA則陷入了局部極值始終未能搜索到全局最優(yōu)。圖2(b)反映出因?yàn)楹瘮?shù)f5中有大范圍單調(diào)區(qū)域的存在，這使得HGA和EGA都曾短暫陷入局部極值;HGA在進(jìn)化到150代以后才進(jìn)行了有效的收斂，EGA則進(jìn)化至400代以后才進(jìn)行了有效收斂，圖2(b)中也可看出HGA雖然收斂的整體代數(shù)較為提前但是收斂速度卻遠(yuǎn)不及EGA。就3種策略的整體情況來(lái)看HGA和EGA種群的多樣性優(yōu)勢(shì)得以較好的體現(xiàn)，通過(guò)較少的迭代周期即能逃逸出局部極值的陷阱，并較快地搜尋到全局最優(yōu)值，體現(xiàn)出較好的全局搜索能力。

四、結(jié)論

在實(shí)際運(yùn)用中為了提高GA性能，通常會(huì)采用各種策略對(duì)GA的種群進(jìn)行維護(hù)。本文討論了3種類型的種群維護(hù)策略，并進(jìn)行了分析和比較。本文認(rèn)為對(duì)于較為簡(jiǎn)單的問(wèn)題宜采用較為簡(jiǎn)單的維護(hù)策略以期獲得較高計(jì)算速度;對(duì)于精度要求較高的問(wèn)題則應(yīng)該采用較為復(fù)雜的維護(hù)策略，相比較之下種群個(gè)體結(jié)構(gòu)的策略雖然整體性能較好，但是其對(duì)于問(wèn)題的通用性較差;就總體性能和使用的便利性考慮，我們推薦采用目標(biāo)空間距離的策略來(lái)對(duì)GA的種群進(jìn)行維護(hù)。

［1］Schraudolph N N，Belew R K.Dynamo is Parameter Encoding for Genetic Algorithms［J］.Machine learning，1992，9(1):9－21.

［2］李敏強(qiáng)，寇紀(jì)淞.遺傳算法的模式欺騙性分析［J］.中國(guó)科學(xué)(E 輯)，2002，32(1):95 －102.

［3］李士勇，李浩.一種基于相位比較的量子遺傳算法［J］.系統(tǒng)工程與電子技術(shù)，2010，32(10):2219－2222.

［4］Powell M.An efficient method for finding the minimum of a function of several variables without calculating derivatives［J］.Evolutionary Computation，2008，12(4):303 －307.

［5］杜海峰，公茂果，劉若辰等.自適應(yīng)混沌克隆進(jìn)化規(guī)劃算法［J］.中國(guó)科學(xué)(E 輯)2005，35(8):817－830.

［6］Kumanan S，Jegan G，Jose K Raja.Multi－project scheduling using a heuristic and a genetic algorithm［J］.Inter J of Advanced Manu－fracturing Technology，2006，31(3－4):360－366.

［7］魯宇明，黎明，李凌.一種具有演化規(guī)則的元胞遺傳算法［J］.電子學(xué)報(bào)，2010，38(7):1603 －1607.

［8］Wei－ cai Zhong，Jing Liu，et al.A Multivalent Genetic Algorithm for Global Numerical Optimization［J］.IEEE transactions on systems，man，and cybernetics－ part B:cybernetics(S1083－4419)，2004，34(2):1128－1141.

［9］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(第2版)［M］.北京:清華大學(xué)出版社，2009:96－106.

［10］李密青，鄭金華，肖桂霞，謝炯亮.基于空間距離的多目標(biāo)進(jìn)化算法［J］.模式識(shí)別與人工智能，2009，22(4):589～596.

［11］李敏強(qiáng)，寇紀(jì)淞，林丹等.遺傳算法的基本理論與應(yīng)用［M］.北京:科學(xué)出版社，2002:163－253.

［12］李敏強(qiáng)，寇紀(jì)淞，林丹等.遺傳算法的基本理論與應(yīng)用［M］.北京:科學(xué)出版社，2002:163－253.

［13］袁曉輝，袁艷斌，王乘等.一種新型的自適應(yīng)混沌遺傳算法［J］.電子學(xué)報(bào)，2006，34(4):708 －712.

A Comparison of Population Maintenance Strategies in Genetic Algorithm

TAN Yang，F(xiàn)ANG Song

Genetic algorithms are successfully applied in many optimization procedures，but there are also some drawbacks of its own.How to improve the search capabilities of genetic algorithms to take into account the convergence speed and search range，and solve practical problems better，has been one of the main topics of intelligent computing field.In this paper，three common populations maintenance strategy are compared together，with the discussion and analysis of the strengths and weaknesses of different strategies.

Genetic algorithm(GA);selection strategy;fitness sorting;Euclidean distance;hamming distance

TP301.6

A

1009－5152(2011)04－0049－05

2011－11－18

湖南省自然科學(xué)基金項(xiàng)目“無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)技術(shù)研究”(06JJ50107);湖南省教育廳重點(diǎn)項(xiàng)目“多復(fù)變函數(shù)空間上算子理論”(10A074)。

譚陽(yáng)(1979－ )，男，湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院講師，工程師，計(jì)算數(shù)學(xué)碩士;方頌(1978－ )，男，湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院工程師。