基于選擇壓力的全局優化元胞遺傳算法分析

汪穎，查代奉

九江學院電子工程學院，江西九江 332005

基于選擇壓力的全局優化元胞遺傳算法分析

汪穎，查代奉

九江學院電子工程學院，江西九江 332005

元胞遺傳算法將遺傳操作限制在鄰域內進行，減緩了優勢個體在群體中的擴散速度，具有更好的全局收斂性，在求解復雜優化問題中顯示出優越性。與傳統遺傳算法對比，以選擇壓力作為分析手段，對元胞遺傳算法進行定性分析。通過求解具有不同特征的函數，分析進化過程群體多樣性變化，從進化過程群體分布圖，直觀得出元胞遺傳算法具有較好的維持群體多樣性能力；從計算的統計結果，得出元胞遺傳算法能極大提高全局收斂率，并且求解穩定性更好。

元胞遺傳算法；選擇壓力；多樣性；精英策略

1 引言

元胞遺傳算法可以看作是一種新的優化算法模型，其思想基于：生物的進化不僅與個體的遺傳物質有關，而且還要受到個體周圍鄰居環境的影響。該算法借助元胞自動機，將構成群體的個體被分配在一個二維網格中（即所謂的元胞空間），而算法的遺傳操作不同于傳統遺傳算法[1]。傳統遺傳算法的選擇操作是在整個群體中隨機配對，而元胞遺傳算法的選擇操作是在個體及其有限鄰域內進行，這導致了個體的遺傳信息在整個群體中擴散速度減慢，從而有利于維持進化過程中群體的多樣性，為避免局部收斂以及對變化及時作出反應提供了條件。眾多實例研究發現，在處理多峰問題和動態問題時，群體多樣性的維持是一個關鍵問題，因此元胞遺傳算法也成為解決這類復雜問題的一種有效方法[2-4]。

文獻[5]針對七種不同的鄰域結構和三種群體規模組合，研究元胞遺傳算法的求解性能，實驗表明求解簡單問題時采用較大的鄰域結構，但問題復雜時，鄰域結構小比較好。通過具體函數優化問題，文獻[6]研究如何確定最合適選擇方法以及鄰域規模及形狀對算法性能的影響。

Alba[7-8]不僅分析了元胞遺傳算法的各種選擇壓力，而且在求解連續優化和組合優化問題時，從收斂率，平均收斂代數等性能方面，研究了群體的元胞個體更新方式以及Ratio這個新的算法參數對算法全局探索和局部探索平衡的影響。

生物個體的進化過程是適應選擇壓力的結果，同時選擇壓力又影響生物進化進程。作為模擬生物進化的進化算法，同樣存在選擇壓力影響優秀個體在整個種群中的生存及擴散能力。傳統認為：如果選擇壓力太低，優秀個體在種群中的擴散很慢，算法不能收斂，使搜索失去了方向，算法趨近于隨機搜索；當選擇壓力過高，優秀個體可以存活下來并得以繁殖的機率高，算法收斂快，但有可能會快速收斂于一個局部次優解從而找不到全局最優，選擇壓力直接影響了群體優化的收斂速度和群體多樣性，是進化算法中全局探索和局部尋優的一個關鍵問題[9]。

目前已有研究主要是就元胞遺傳算法自身涉及到的一些參數和因素展開，而與傳統遺傳算法的比較未有系統研究，本文將從選擇壓力和算法性能方面對傳統的遺傳算法和元胞遺傳算法進行比較分析，對不同特性的待優化問題，分析元胞遺傳算法維持進化過程中多樣性以及求解性能。

2 元胞遺傳算法有關描述

2.1 鄰域結構

在元胞遺傳算法中，一個重要特點就是借助了元胞自動機的鄰域結構，把個體嵌入規定好的元胞空間內，采用四邊形網格，每個個體都只與相鄰的個體產生聯系，這些相鄰個體的范圍被稱為鄰域，遺傳操作就在這個鄰域內進行。每個個體元胞都有自己的鄰域（圖1）。

圖1 二維元胞自動機的常見四種鄰居形式圖

2.2 更新策略（同步和異步）

元胞遺傳算法存在兩種更新機制：同步機制和異步機制。本文采用的是同步機制。

（1）同步機制

在算法進行的時候，網格中所有個體的狀態同時更新，即每個個體同時進行遺傳操作，這種更新方式叫做同步機制。同步機制的子代個體都是在同一時間產生的。

（2）異步機制

狀態的更新按照一定的順序進行，即網格中的每個個體按照時步逐個進行遺傳操作，這種更新方式就稱之為異步機制。一個時步只產生一個新個體。

2.3 算法步驟

將元胞自動機與遺傳算法相結合，元胞模式從個體的角度出發模擬自然進化，在元胞遺傳算法中，構成群體的個體分布于一個二維四邊形網格里，這個網格代表了搜索空間。

算法具體步驟：

步驟2設定終止條件。

步驟3評價群體個體的適應度f(Qpij)。

步驟4采用同步機制對分布于元胞空間的所有個體進行相關遺傳操作：

選擇：以確定的元胞空間位置的個體為中心元胞Qpcenter=Qpij，此中心元胞鄰域內個體集QpNij（式（1），以摩爾鄰居結構為例）選擇其中一個體QpNij=max(f(QpNij))；對中心元胞個體處于元胞空間邊緣情況，若中心元胞的鄰居個體不在元胞空間內，則以另一側邊緣個體作為鄰居個體，如中心元胞為Qp11，其鄰域個體集為QpN11（式（2））。

交叉：以中心元胞個體Qpcenter和鄰域內選中的個體QpNij進行交叉操作，對于實數編碼可采用下式產生新個體QpNew：

變異：以某一概率p對交叉操作中產生的新個體QpNew進行變異，產生新個體QpNew'；

替代：若f(QpNew')＞f(Qpcenter)，則產生的新個體QpNew'優于原中心元胞個體Qpcenter，則Qpij=QpNew'，否則Qpij= Qpcenter。

步驟5判定是否滿足終止條件，不滿足，轉步驟4。

步驟6結束。

3 選擇壓力的定義

所謂選擇壓力[10-12]是指自然選擇作用于某一種群效果的衡量標準。在進化算法中，選擇壓力影響算法進行全局搜索和局部探索的能力，選擇壓力大可提高收斂速度，而選擇壓力小維持群體多樣性性能好，為進化提供了可能。Goldberg提出了取代時間概念，用它作為衡量一個進化過程選擇壓力的一個重要指標，從操作來看，即是：在只有選擇操作情況下，一個好的個體占據整個群體的時間[13]。取代時間越短意味著選擇壓力越高，選擇壓力與取代時間成反比。

目前文獻[14]中，給出取代時間的定義如下：在群體規模為n，初始群體P(0)包含一個最優個體X，這個最優個體經過t次選擇操作后，占據整個P(t)的最短時間t*。即

t*=min{t|P(t)=n(X*＜P(0))}（4）

由于選擇算子是一個隨機算子，上述定義中的取代時間實際上是一個隨機變量，而并不是一個確定的值。在文獻[15]中對取代時間的分布進行了實驗，并使用了最大熵原理對其作出了理論上的解釋。

4 元胞遺傳算法的優化分析

4.1 選擇壓力比較

下面通過計算機模擬來得到只進行選擇操作情況下，優秀個體在群體中的擴散。通過成長曲線將抽象的取代時間概念具體化，以優勢個體在群體中的占有率隨進化代數變化曲線衡量，占有率增長趨勢快說明進化過程中選擇壓力大，反之說明進化過程中選擇壓力小。

假設群體規模64×64，引入一個優秀個體，置為“1”，其余則為“0”，只進行單純的選擇操作而不涉及到交叉和變異，如此迭代進行，以占有率作為成長曲線縱坐標，以進化代數為橫坐標。通過成長曲線的趨勢可反映出算法選擇壓力的強弱，模擬結果如圖2。

圖2 占有率隨代數變化曲線

由圖2可知，在初期，GA算法優勢個體占有率低于CGA算法，并且增長趨勢也略緩于CGA算法，這是由于群體中優秀個體數量很少，GA算法中個體的隨機配對選擇與CGA算法個體的基于鄰域選擇比較而言，但隨著進化的深入，標準遺傳算法的優勢個體占有率曲線呈急劇增長，而元胞遺傳算法的優勢個體占有率曲線要緩慢得多，這主要是因為元胞的操作是在有限鄰域內進行，優秀個體信息擴散只能通過鄰域擴散，因此要緩慢些，而標準遺傳算法中優秀個體達到一定數量后，由于其遺傳操作是在整個群體內進行，則優秀個體信息迅速擴散。

4.2 算法性能比較

4.2.1 測試函數

為了對比分析，這里引入以下幾個測試函數：

F1（圖3）有兩個極值點，分布在（2.048，-2.048）、（-2.048，-2.048），對應的值為3 897.734 2和3 905.926 2。后者為全局極大值點，一般遺傳算法極易陷入第一個極值點。

F2（圖4）有5個極值點，其全局極大值為3 600，分布在(0，0)；其余4個為局部極大值，值為2 748.8，分布在(+5.12，+5.12)，(-5.12，-5.12)，(+5.12，-5.12)，(-5.12，+5.12)。一般算法容易陷入這4個局部極值點處。

4.2.2 進化過程個體分布分析

圖3 函數F1的圖像

圖4 函數F2的圖像

傳統遺傳算法采用最優保留策略，選擇為聯賽方式，交叉概率0.9，變異概率0.05；元胞遺傳算法的鄰居結構采用圖1（b），交叉概率0.9，變異概率0.05，群體規模均為400，指定最大進化代數為2 000。在此記錄了算法其中1次迭代過程的不同時刻群體分布變化情況（圖5～8）。

圖5 CGA-F1進化過程

圖6 GA-F1進化過程

圖7 GA-F2進化過程

圖8 CGA-F2進化過程

F1有兩個極值點，其中一個為全局最優點（圖3），在第5代和第10代圖中，GA算法中個體向兩個極值點均勻靠攏，到第50代后，個體集中分布在少數幾個點，而且這些個體基本上分布在2個極值點之一，只有少數幾個個體在另一極值點（圖7），所以一旦大多數個體趨向的那個極值點是局部極值點，就跳不出來了。而CGA算法中在整個進化過程初期，個體也是分別向兩個極值靠攏，在后期個體也趨向集中，但個體分別集中在兩個極值點周圍，它們呈現區域范圍內集中現象（圖8），這樣即使到進化后期在每個極值點附近都會有一定數量個體存在，保證了進一步進化的可能。

F2全局最優值在中心，而4個角點處有4個局部極值點（圖4），由于此問題向全局極值點的過渡是在很小突變區域內，而向其他4個局部極值點過渡是緩慢漸近的過程，因此在第5代和第10代圖中（圖8），GA算法中個體比較容易會從任何方向趨向于某個局部極值點，到第50代后，GA算法的個體同樣集中在少數幾個點，一旦個體落入的是局部極值點，GA算法就很難逃逸。而CGA算法中個體從進化開始就向各個極值點移動，隨著種群進化，個體仍向各個極值點區域性集中，在每個極值點處都有一定數量個體（圖7），因此CGA算法中個體收斂于全局最優和次優解處。

表1 F1計算結果

表2 F2計算結果

4.2.3 計算結果分析

有關參數如4.2.2節所設，運行100次，考慮最大進化代數分別為1 000和2 000的情況。在作統計分析時采用的統計量如下：

F1在設定的最大進化代數內以最優值的平均值、最優值的標準差、收斂率、其求解最優值在局部極值點3 897.734 2±1的百分比（P）等指標來分析算法的計算性能，結果如表1。

F2在設定最大進化代數內以最優值的平均值、最優值的標準差、收斂率、其求解最優值在局部極值點2 748.8±1的百分比（P）等指標來分析算法的計算性能，結果如表2。

由表1來看，除兩種算法獲得的最優解是相似的，其他方面差異較大：采用CGA算法時，F1雖然在指定最大進化代數1 000時，收斂率為0，但是其在2 000代時，優化結果得到提高，全局收斂率為10%，優化結果的質量總體是好于1 000代的，在進化代數為1 000和2 000時均未有解在次優解處，而采用GA算法時，求解結果在次優解附近的次數較多，并且進化代數從1 000到2 000時，解的質量雖然有所提高，但在次優解附近的個體只是從89%降到79%，其全局收斂率仍未得到提高，其標準差較CGA算法大得多，也既是優化結果有少數收斂到全局最優附近，但大部分收斂到次優解附近。

由表2來看，采用CGA算法時，F2在指定最大進化代數可以收斂到最優解，其在2 000代時的收斂率較1 000代時有明顯提高，并且其均值與最優解偏差分別為0.1和0.2，沒有落入次優解的個體，并且標準差很小，而采用GA算法時，在指定最大進化代數內收斂率均為0，其在次優解附近的個體隨著進化代數從1 000到2 000，從75%下降到71%，加大進化代數并不能使個體跳出次優解，并且由于其最優解和次優解相差很大，其標準差相當大。

5 結論

由以上分析可知，進化過程中，元胞遺傳算法的選擇壓力要低于傳統遺傳算法，CGA算法維持種群多樣性能力好于GA算法，這也就為優化過程的進行提供了條件。當優化問題存在多個極值點時，即使初始種群個體是均勻分布在搜索空間，但隨著種群進化，個體在搜索空間的分布會發生變化，趨勢是有差異的。GA算法中大多數個體是向某個局部極值點靠近，因此GA算法在求解上述存在局部最優解問題時，由于變異存在，有少數機會可以跳出次優解，但大多數時候都落入次優解而無法跳出；而CGA算法中個體是向不同極值點呈區域范圍內靠近，因此可尋優得到全局極值點，適當增加進化代數，可以促進其全局收斂。總體而言，元胞遺傳算法無論是在優化結果還是在優化穩定性方面都優于傳統遺傳算法，并且具有更好的全局探索能力。在處理具有多個極值點的優化問題時，元胞遺傳算法的性能具有特別明顯的優勢，尤其當最優極值點處于極小區域內時（如F2），遺傳算法幾乎無法尋找到全局最優，通常在未收斂到全局最優之前就停滯局部優處。

[1]Whitley D.Cellular genetic algorithms[C]//Proc of the Fifth International Conference on Genetic Algorithms（ICGA）.[S.l.]：Morgan Kaufmann，1993：658-659.

[2]Rudolph G，Sprave J.A cellular genetic algorithm with self-adjusting acceptance threshold[C]//Genetic Algorithms in Engineering Systems：Innovations and Applications，1995：365-372.

[3]Folino G，Pizzuti C，Spezzano G.A cellular genetic programming approach to classification[C]//Proc of the Genetic and Evolutionary Computation Conference（GECCO-99）.[S.l.]：Morgan Kaufmann，1999：1015-1020.

[4]Kim W，Man W，Chi S.Adding learning to cellular genetic algorithms for training recurrent neural networks[J].IEEE Transactions on Neural Networks，1999，10（2）：239-252.

[5]Bernabe D，Enrique A.A simple cellular genetic algorithm for continuous optimization[C]//IEEE Congress on Evolutionary Computation，2006：2838-2844.

[6]Gordon V，Mathias K，Whitley D.Cellular genetic algorithms as function optimizers：locality effects[C]//ACM Symposium on Applied Computing，1994：237-241.

[7]Alba E，Dorronsoro B.The exploration/exploitation trade off in dynamic cellular genetic algorithms[J].IEEE Trans on Evolutionary Computation，2005，9（2）：126-142.

[8]Alba E，Troya J.Cellular evolutionary algorithms：evaluating the influence of ratio[C]//Proceedings of the 6th International Conference on Parallel Problem Solving from Nature，2000：29-38.

[9]Enrique A，Gabriel L.Theoretical models of selection pressure for dEAs：topology influence[C]//The 2005 IEEE Congress on Evolutionary Computation，2005：214-221.

[10]魯宇明，陳殊，黎明，等.自適應調整選擇壓力的災變元胞遺傳算法[J].系統仿真學報，2013，25（3）：436-444.

[11]Zu Qiaohong，Cao Mengmeng，Guo Fang，et al.Slotting optimization of warehouse based on hybrid genetic algorithm[C]//Proceedings-2011 6th International Conference on Pervasive Computing and Applications 2011.United States：IEEE Computer Society，2011：19-21.

[12]Didier L I，López D E.Redundancy allocation problems considering systems with imperfect repairs using multi objective genetic algorithms and discrete event simulation[J].Simulation Modelling Practice and Theory，2011，19（1）：362-381.

[13]Alba E，Luque G.Theoretical models of selection pressure for dEAs：topology influence[C]//The 2005 IEEE Congress on Evolutionary Computation.USA：IEEE，2005：214-221.

[14]郭東偉，周春光，劉大有.遺傳算法取代時間的分析[J].計算機研究與發展，2001，38（10）：1211-1216.

[15]孫瑞祥，屈梁生.遺傳算法進化截止代數分布規律的研究[J].計算機研究與發展，2000，37（2）：188-193.

WANG Ying,ZHA Daifeng

School of Electronic Engineering,Jiujiang University,Jiujiang,Jiangxi 332005,China

Cellular genetic algorithm is an algorithm model that combines cellular automata with genetic algorithm.In this algorithm,the genetic operate of a certain individuals is restricted within neighborhood,so it slows down the diffusion speed of the good individual.So the cellular genetic algorithm can offer us an overall exploitation in solving problems struck into local optimum,thus increases the global convergence,and shows great superiority in coping complex problem. Compared with traditional genetic algorithm,selective pressure is chosen to analytical tool,and cellular genetic algorithm is done qualitative analysis.By solving function with different characteristics,the population diversity of evolution process is analyzed.From evolution group distribution,intuitive cellular genetic algorithm has better ability to maintain population diversity.According to statistical results,the calculation of cellular genetic algorithm can greatly improve the rate of global convergence,and solve the stability.

cellular genetic algorithms;selective pressure;diversity;elitist strategy

A

TP301

10.3778/j.issn.1002-8331.1308-0311

WANG Ying,ZHA Daifeng.Analysis on global optimum of cellular genetic algorithm based on selective pressure. Computer Engineering and Applications,2014,50（6）：40-45.

汪穎（1983—），女，講師，主要研究方向：計算機通信網。

2013-08-24

2013-10-22

1002-8331（2014）06-0040-06

CNKI網絡優先出版：2013-12-11，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1308-0311.html