遺傳算法中種群維護策略的比較

譚 陽，方 頌

(湖南網絡工程職業學院，湖南長沙 410004)

遺傳算法中種群維護策略的比較

譚 陽，方 頌*

(湖南網絡工程職業學院，湖南長沙 410004)

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

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

一、引言

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

不失一般性，考慮如下全局優化問題:

式中，x=(x1，x2，…，xm)∈D，D?Rm為搜索空間，f:Rm→R 為目標函數，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)，當且僅當對于?i∈{1，2，…，m}，ui≤vi∧?i∈{1，2，…，m}，使得ui＜vi。

基本遺傳算法中采用單點交叉算子和簡單的變異算子，優點是操作簡單、計算開銷小，但是在使用過程存在很大的局限性［2］，由于單點交叉破壞模式的概率較小，導致搜索到的模式數目也較少，從而算法具有的搜索能力較低，難以對多維連續空間的問題進行有效搜索。

二、GA種群的維護策略

為了能保留GA在整個迭代搜索過程中偶然發現的“最優個體”，并使種群進化方向具備導向性，通常GA都會采用精英保留機制。在精英保留及指導機制的作用下會使得GA搜索效率得到很大的提高，但是帶來的負面效應是對目標函數的搜索不夠全面，容易使得算法陷入局部極值區，產生早熟現象，從而無法搜索到全局最優解。為此當前GA研究的重點在如何合理地維護種群的多樣性。

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

1.目標函數指導

這類方法以目標函數的優化要求為基準，以篩選出種群中的最優個體為目標，并以適應度高低為評價體系對種群中所有個體以進行分級排序。某個體被篩選的依據是種群存在多少個個體優勝于該個體，并以此作為下次進化過程的選擇的依據。目標函數指導方法操作簡單，是一種完全按照“優勝劣汰”模式選擇的策略，其典型代表為:適應度排序算法，該算法以適應度為主要關鍵字對種群個體進行排序，基本方法以快速排序為主，也有少量使用桶排序和計數排序［9］。

2.目標空間距離

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

其中 x、y、z分別為 a、b 兩點的坐標值，n 為 a、b兩點所處空間的維度。

3.種群個體結構

此類策略應用較為少見，該策略的核心思想是以種群中個體的基因代碼結構為依據來進行選擇，目的是使具有類似基因結構的個體能夠聚集，形成小生境環境并協同進行進化;或是以基因結構差異的大小來作為種群維護的依據?？梢钥闯龃瞬呗院湍繕丝臻g距離策略具有類似之處，前者以超平面空間為衡量依據，后者以幾何空間為衡量依據。其典型的代表為:海明距離(Hamming Distance)算法，若a、b為算法種群中兩個采用2進制編碼的個體，那么a、b 間的海明距離 h(a，b)由下式(3)計算得出［11］。

其中L為個體的2進制編碼長度，l為相同位置的編碼位。

圖1 3種類型的種群維護策略

圖1中為3種維護策略對于基礎點(0，0)在2維空間上的選擇示意圖?？梢钥闯鲞m應度排序對于搜索空間的覆蓋是基于隨機分布的，并以其獨立個體作為指導，若需要較為有效地覆蓋搜索空間則需要大量的個體進行隨機嘗試;但通常為了合理控制計算開銷，GA在使用中會限制種群規模，這使得適應度排序策略對搜索空間的覆蓋存在較大的隨機性。歐氏距離策略則能夠很好的解決有效覆蓋需要個體過多的問題，圖1(b)中可以看出只需很少量的個體即可較為有效地覆蓋搜索空間，但是可行解的分布卻與適應度排序一樣呈現隨機性和無序性。海明距離的個體分布具有明顯的規律性，并呈現出“內緊外松”的分布特性，這種分布可以很好地兼顧算法搜索的效率和分布問題，但是海明距離是一種針對2進制代碼的維護策略，對于采用實數編碼的問題則無法運用，同時也可以看出為了保證海明距離策略的有效性，種群個體的數目遠比歐氏距離策略的要高。

三、仿真測試

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

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

表1中為3種對比策略對函數f1～f4的測試結果，為了體現各種維護策略GA的性能，這里選取了3個指標作為對算法評價的衡量依據，分別為:平均全局最優解出現的代數，記為NGO;出現全局最優解的平均執行時間s，記為ART;平均種群最優解，記為AGO。

表1中的尋優數據表明，在對函數f1、f3和f4平均尋優結果而言HGA的結果較其他算法更為精確。對函數f2優化中HGA在平均精度上略遜于EGA，經分析f2函數為U型結構最優值呈線性分布，相對來說以“面”進行尋優的算法要好于以“點”進行尋優的算法;但是就全局最優解的平均迭代次數和平

表1 對函數f1～f4優化性能的比較

函數f5(Needle－in－a－Haystack)的參數 a，b取 a=3.0，b=0.05，該函數為典型的欺騙函數。圖2(a)為該函數在MATLAB中的模擬圖像，該函數的最優點分布在(0，0)處;4個局部極值點對稱分布在4個角上，這些局部極值點距離全局最優點的距離很大，且函數在相當的取值范圍內單調，通常優化算法難以獲得全局最優解。測試中，3種對比策略的給定維數為2，種群規模為20，最大迭代次數為500，算法的終止條件為N＞20;每種算法獨立運行10次并記錄種群最優解。均搜索時間上FGA則領先于這兩個對比策略。也可以看出FGA較為簡單的維護策略并沒有使得GA在迭代搜索過程中的計算開銷明顯增加，因此搜索速度較快。EGA則是3種策略中耗時最大的，這主要是因為需要對所有搜索的結果進行映射計算和取舍，計算量較大。

圖2 對函數的優化情況

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

四、結論

在實際運用中為了提高GA性能，通常會采用各種策略對GA的種群進行維護。本文討論了3種類型的種群維護策略，并進行了分析和比較。本文認為對于較為簡單的問題宜采用較為簡單的維護策略以期獲得較高計算速度;對于精度要求較高的問題則應該采用較為復雜的維護策略，相比較之下種群個體結構的策略雖然整體性能較好，但是其對于問題的通用性較差;就總體性能和使用的便利性考慮，我們推薦采用目標空間距離的策略來對GA的種群進行維護。

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

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

［3］李士勇，李浩.一種基于相位比較的量子遺傳算法［J］.系統工程與電子技術，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］杜海峰，公茂果，劉若辰等.自適應混沌克隆進化規劃算法［J］.中國科學(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］魯宇明，黎明，李凌.一種具有演化規則的元胞遺傳算法［J］.電子學報，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］嚴蔚敏，吳偉民.數據結構(第2版)［M］.北京:清華大學出版社，2009:96－106.

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

［11］李敏強，寇紀淞，林丹等.遺傳算法的基本理論與應用［M］.北京:科學出版社，2002:163－253.

［12］李敏強，寇紀淞，林丹等.遺傳算法的基本理論與應用［M］.北京:科學出版社，2002:163－253.

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

A Comparison of Population Maintenance Strategies in Genetic Algorithm

TAN Yang，FANG 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

湖南省自然科學基金項目“無線傳感器網絡容錯技術研究”(06JJ50107);湖南省教育廳重點項目“多復變函數空間上算子理論”(10A074)。

譚陽(1979－ )，男，湖南網絡工程職業學院講師，工程師，計算數學碩士;方頌(1978－ )，男，湖南網絡工程職業學院工程師。