一種新的種群數自適應遺傳算法

摘 要：針對簡單遺傳算法存在早收斂和在進化后期搜索效率較低的缺點，提出了一種新的種群數自適應遺傳算法。該算法在對進化種群數進行宏觀調控的同時，再用個體壽命限制個體的生存期，實現對種群數的微觀調控。實驗數據表明，該算法具有比簡單遺傳算法好的收斂性能。

關鍵詞：遺傳算法； 早收斂； 自適應種群

中圖法分類號：TP18 文獻標識碼：A 文章編號：1001-3695(2006)10-0030-03

New Genetic Algorithm with Adaptive Population Size

HE Hong1，2， QIAN Feng1

(1.Automation Institute， East China University of Science Technology， Shanghai 200237， China; 2.College of Mechanical Electronic Engineering， Shanghai Normal University， Shanghai 201418， China)

Abstract:A New Genetic Algorithm with Adaptive Population Size(NGAAPS) is proposed to overcome premature convergence and slow convergent speed in the later evolution process of simple genetic algorithm. NGAAPS uses both macroscopic control and microscopic control based on lifetimes of the chromosomes to realize population size adaptation. The experiments show NGAAPS has prominently better convergent performance than simple genetic algorithm.

Key words:Genetic Algorithms; Premature Convergence; Adaptive Population Size

1 引言

遺傳算法是根據達爾文自然進化論中“物競天擇、適者生存”的思想發展起來的全局優化算法。它具有簡單通用、魯棒性強、適于并行處理以及應用范圍廣等顯著特點，并已廣泛用于各個領域。但是簡單遺傳算法(Simple Genetic Algorithm，SGA)本身存在兩個突出的缺陷，即易發生過早收斂和在進化后期搜索效率較低，這使得最終搜索得到的結果往往不是全局最優解，而是局部最優解，這些不足阻礙了遺傳算法的推廣應用。

遺傳算法在進化中發生早收斂的主要原因是由于遺傳算法中選擇及交叉變異等算子的作用，這使得一些優秀的基因片段過早丟失，造成種群中個體之間的差異較小，減少了種群內個體之間的信息交換量，從而失去了產生更優個體的能力。同時由于選擇壓力的存在，有可能造成個別優秀個體的基因在進化過程中很快占據種群的統治地位，導致種群中由于缺乏新鮮的基因而不能找到全局最優值。簡單遺傳算法中種群數始終保持一定，因此算法收斂性與初始種群中個體的分布情況有很大關系。種群中個體的多樣性較強時，種群就越有可能產生出更優子代；而一旦種群喪失多樣性，種群個體間越相互趨同，則早收斂現象就很容易發生[1]。

一般地，選擇較大數目的初始種群可以同時處理更多的解，保持種群的多樣性也容易找到全局最優解，但種群數目過大會增加計算時間，使進化過程變得異常緩慢；而種群數目太小則會使得算法收斂速度過快，以至于找不到全局最優解[2]。可見種群數的大小對算法的收斂性影響很大，本文就將針對SGA存在的不足提出一種新的種群數控制方法。該方法除將種群數分為三個等級進行宏觀調控以外，還同時對每個個體賦予用適應度表示的壽命，用個體壽命再對種群的大小進行微觀調控，從而形成一種種群數目隨進化過程解的搜索情況自適應調整的遺傳算

法，進一步提高了算法的搜索性能。

2 遺傳算法種群控制策略

為解決遺傳算法的早收斂問題，從控制種群數量的角度出發，Arabas在文獻[3]中引入了壽命的概念。每個個體在出生時刻就具有自身壽命，并在壽命期內存活，同時每個個體的年齡隨進化代數的增加而增加，當個體年齡超出其壽命時，個體將從種群中除去，標志個體的死亡。Arabas用年齡的概念代替了選擇的概念，因此算法中沒有選擇操作，選擇壓是通過用個體適應度計算個體壽命來保證的。該算法比簡單遺傳算法的收斂性能好，但是該算法最大的缺點就是種群大小受種群最大復制比的影響很大，經過幾代進化后，種群數目往往可達幾千，使得算法的實際運行變得很困難，計算時間很長，限制了算法的可行性[4]。為了提高算法的收斂速度，本文提出一種新的基于個體壽命的種群數自適應控制方法。

2．1 種群數的微觀控制

種群數的微觀控制是通過對種群中的每個個體賦予壽命來實現的。為避免優秀的基因片段過早丟失，個體壽命并不是如文獻[3]中在個體出生后一直保持不變，而是在每代進化過程中重新計算個體的壽命，保證了優秀個體基因片段能充分遺傳給后代，減少遺傳操作對它的影響，并加速了不良基因的淘汰。文獻[3]中分別用了比例分配法、線性分配法和雙線性分配法計算壽命，結果表明雙線性分配法計算量最小，并具有與其他方法同樣的效果。因此在本文中采用雙線性計算公式計算種群中個體壽命Lifetime[i]，并加以修正如下。

若fitness[i]≤AvgFit，

Lifetime[i]=MinLT+ηfitness[i]-WorstFitAvgFit-WorstFit

若fitness[i]＞AvgFit，

Lifetime[i]=12(MinLT+MaxLT)+ηfitness[i]-AvgFitBestFit-AvgFit（1）

其中，η=12(MaxLT-MinLT);MaxLT，MinLT分別為允許的個體最大壽命和最小壽命；BestFit，AvgFit，WorstFit分別為當前代最優、平均和最差適應度函數值。

由式（1）可以看出，適應度高的解個體將具有更長的壽命，將在更多的進化代數中存活，具有更多的機會將優秀的基因片段遺傳給后代。同時種群中的個體年齡隨進化代數增加而增加，并都只在其壽命期限內存活，這樣防止了超級個體和早熟現象的出現。

2．2 種群數的宏觀控制

為避免種群數目過大而使得算法可行性變差，根據實際計算速度，通常種群數達到1 000時進化速度明顯減慢。限定最大種群數為1 000，并將種群數目分成初始種群數、500和1 000三個級別，每個級別具有不同的種群復制比。這樣種群數不僅根據算法對解的搜索情況有了較大的變化空間，也不會因種群數過大影響算法的收斂速度。在個體賦予壽命以后，種群數目不再是常數，而是受個體壽命控制的一個可變參數。t+1代種群的數量為

PS(t+1)=NPS(t)-D(t)當NPS(t)≤PS0時

PS(t)×(1+R1)-D(t)當PS0＜NPS(t)≤500時

PS(t)×(1+R2)-D(t)當500＜NPS(t)≤1000時

1000-D(t)當NPS(t)＞1000時(2)

其中，R1，R2分別為0．2和0．1，均是種群數增長的最大復制比；D(t)為t代年齡超過壽命的死亡個體數；PS(t)和PS(t+1)分別為t代和t+1的種群數；NPS(t)為經過交叉變異操作后的新種群數；PS0為初始種群數。

式（2）表示當NPS(t)比初始種群還小時，不進行種群最大增長幅度的運算，以保證種群具有一定的規模，防止過快收斂于局部最優解；當NPS(t)在初始種群與最大種群數之間變化時，種群數受最大復制比控制，種群數變大，最大復制比取小，以防止種群數增加過快；當NPS(t)＞1000時，種群數為種群數上限1 000減去自然死亡個體。這種方法可以看作是在進化過程中由于資源的限制對種群數進行的宏觀調控。而種群數的大小則是在宏觀調控的作用下，根據個體的自然死亡數再發生自適應的微觀調控，使其始終朝著有利于進化的方向變化。

3 種群數自適應遺傳算法的基本流程

在保證了進化種群的多樣性后，為進一步加快算法收斂的速度，算法保留SGA中的選擇操作，并采用較大的變異率。新型種群數自適應遺傳算法(New Genetic Algorithm with Adaptive Population Size，NGAAPS)的基本流程如下：

（1）對個體進行二進制編碼，隨機生成初始種群PS0；

（2）計算個體適應度值，并根據式（1）計算個體的壽命；

（3）對種群數進行宏觀調控，即根據式（2）給出參與進化的種群最大限制數量；

（4）個體年齡增長1，并對種群數進行微觀調控，即除去種群中年齡大于壽命的個體；

（5）對新種群進行選擇、交叉和變異操作，并將進化產生的新個體插入到種群中，重新計算種群數NPS(t)；

（6）判斷是否滿足算法終止條件，即判斷是否已達到最大進化代數，或算法搜索到的最優解函數值與理想極值的誤差是否滿足進化要求；否則轉入步驟（2），是則輸出最終結果。

4 算法測試

4．1 測試函數選擇

為了驗證NGAAPS的算法性能，本文將其與SGA一起進行算法測試。同時選用了四個常見的用于優化算法測試的函數。

（1）f1 Sphere函數

f(x)=∑3i=1x2i， -5．12≤xi≤5．12

（2）f2 Rosenbrock函數

f(x1，x2)=100×(x21-x2)2+(1-x1)2， -2．048≤x1，x2≤2．048

（3）f3 Rastrigin 函數

f(x)=∑2i=1(x2i-10cos(2πxi)+10)，-5．12≤xi≤5．12

（4）f4 Schaffer函數

f(x，y)=0．5-（sinx2+y2)2-0．5(1+0．001(x2+y2))2，-100≤x，y≤100

其中，f1是三參數、單極值的二次函數，在（0，0，0）處有最小值0，容易搜索到最優解；f2是二參數、單極值的非二次函數，但它是病態的，在x2＝x21處有一狹長深谷，且極難極小化，尋優中可能陷入局部解，其在（1，1）處有全局最小值0；f3是一個具有多個局部最優點的多峰函數，局部極小點成正弦坡度分布，其在（0，0）處有全局最小值為0；f4在（0，0）處有最大值為1，該函數最大值峰周圍有一圈脊，其取值均為0．990 283，因此很容易陷入在此的局部最大點。

4．2 算法收斂性對比分析

在優化函數測試中，本文對文獻[3]中的方法也進行了測試，發現該方法種群增長過快，除f1外，對于其他函數種群數可達幾千甚至上萬，嚴重影響了算法的收斂速度，因此本文僅對NGAAPS和SGA進行收斂性能比較。SGA與NGAAPS均采用輪盤賭選擇和單點交叉，交叉率均為0．7。設置初始種群數為30，最大進化代數為1 000，當搜索得到的最優解的函數值與理想極值的誤差小于10-3時，則認為算法收斂并停止進化。將兩種算法分別各運行20次，每個函數的每種算法變異率依次取0．01，0．05，0．1進行運算，并記錄為A，B，C三種情況。SGA和NGAAPS運行后的收斂次數如表1所示。

從表1中可知，在相同的進化條件下，NGAAPS比SGA的收斂性能明顯要好。對于較為簡單的單峰f1和多峰函數f3，NGAAPS每次運行均能收斂于最優解，而對特殊的單峰函數f2和多峰函數f4，NGAAPS的收斂次數比SGA多。根據兩種算法收斂情況，對f1，f2，f3，f4的變異率分別取為0．01，0．05，0．01，0．01，其他條件不變，每種算法對不同函數再運行100次，記錄算法停止搜索時找到最優解的平均進化代數AvgGN和最優解函數值與理想極值的平均誤差AvgfE，結果如表2所示。

表1 SGA和NGAAPS的收斂次數函數

函數算法f1f2f3f4AvgGNAvgfEAvgGNAvgfEAvgGNAvgfEAvgGNAvgfESGA5720.014 310 944230.001 016 335760.231 577 205000.007 435 12NGAAPS300.000 590 981680.000 587 62500.000 342 821020.002 066 51根據表2的數據結果可知，NGAAPS與SGA相比，不僅收斂速度明顯加快，而且搜索到的最優解更精確。在搜索過程中，除f2外，其他函數NGAAPS在進化過程中，種群的數量始終在100之內變動。而當函數存在局部最優點時，如對于f2和f4，NGAAPS在函數的局部最優點處種群的數量增加較為迅速，說明個體之間差距不大，個體壽命大的較多。但由于最大壽命的限制，算法不會在局部最優點處長期徘徊不前，同時由交叉和變異操作引入的新個體將使算法具有更大的幾率跨越局部收斂區，最后找到全局最優值。

5 結束語

本文針對簡單遺傳算法存在早收斂和在進化后期搜索效率較低的缺點，提出了對進化種群數進行宏觀調控的同時，再用個體壽命限制個體的生存期，實現對種群數的微觀調控，使種群數能夠根據算法對解的搜索情況發生自適應調整，保證了進化過程中種群的多樣性，避免了算法陷入局部最優點，并提高了算法的收斂速度。實驗數據表明這種新的變種群數遺傳算法與簡單遺傳算法相比，不論在尋優性能上還是在收斂性能上均有極大的提高。

參考文獻：

[1]吳浩揚，朱長純，常炳國，等.基于種群過早收斂程度定量分析的改進自適應遺傳算法[J].西安交通大學學報，1999，33(11):27-31.

[2]C Fernandes， A Rosa. A Study on Nonrandom Mating and Varying Population Size in Genetic Algorithms Using Royal Road Function[C]. Seoul: Proc. of the Congress on Evolutionary Computation， IEEE Press Piscataway， 2001.60-66.

[3]J Arabas， Z Michalewicz， J Mulawka. GAVaPS: A Genetic Algorithm with Varying Population Size[C].Proc.of the 1st IEEE Conf.on Evolutionary Computation， Piscataway:IEEE Press，1994.73-78.

[4]T Back， A E Eiben， N A L Van der Vaart. An Empirical Study on GAs \"without Parameters\"[C]. Proceedings of the 6th Conference on Parallel Problem Solving from Nature， Number 1917 in Lecture Notes in Computer Science， Berlin: Springer， 2000.315-324.

作者簡介：

何宏（1973-），女，博士研究生，主要研究方向為智能計算、智能控制理論及應用技術；錢鋒（1961-），男，教授，博導，主要研究方向為工業過程先進控制、優化與故障診斷、人工智能在流程工業過程建模、控制和優化中的應用。

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