基于選擇壓力的全局優(yōu)化元胞遺傳算法分析

汪穎，查代奉

九江學(xué)院電子工程學(xué)院，江西九江 332005

基于選擇壓力的全局優(yōu)化元胞遺傳算法分析

汪穎，查代奉

九江學(xué)院電子工程學(xué)院，江西九江 332005

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

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

1 引言

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

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

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

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

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

2 元胞遺傳算法有關(guān)描述

2.1 鄰域結(jié)構(gòu)

在元胞遺傳算法中，一個重要特點就是借助了元胞自動機(jī)的鄰域結(jié)構(gòu)，把個體嵌入規(guī)定好的元胞空間內(nèi)，采用四邊形網(wǎng)格，每個個體都只與相鄰的個體產(chǎn)生聯(lián)系，這些相鄰個體的范圍被稱為鄰域，遺傳操作就在這個鄰域內(nèi)進(jìn)行。每個個體元胞都有自己的鄰域（圖1）。

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

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

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

（1）同步機(jī)制

在算法進(jìn)行的時候，網(wǎng)格中所有個體的狀態(tài)同時更新，即每個個體同時進(jìn)行遺傳操作，這種更新方式叫做同步機(jī)制。同步機(jī)制的子代個體都是在同一時間產(chǎn)生的。

（2）異步機(jī)制

狀態(tài)的更新按照一定的順序進(jìn)行，即網(wǎng)格中的每個個體按照時步逐個進(jìn)行遺傳操作，這種更新方式就稱之為異步機(jī)制。一個時步只產(chǎn)生一個新個體。

2.3 算法步驟

將元胞自動機(jī)與遺傳算法相結(jié)合，元胞模式從個體的角度出發(fā)模擬自然進(jìn)化，在元胞遺傳算法中，構(gòu)成群體的個體分布于一個二維四邊形網(wǎng)格里，這個網(wǎng)格代表了搜索空間。

算法具體步驟：

步驟2設(shè)定終止條件。

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

步驟4采用同步機(jī)制對分布于元胞空間的所有個體進(jìn)行相關(guān)遺傳操作：

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

交叉：以中心元胞個體Qpcenter和鄰域內(nèi)選中的個體QpNij進(jìn)行交叉操作，對于實數(shù)編碼可采用下式產(chǎn)生新個體QpNew：

變異：以某一概率p對交叉操作中產(chǎn)生的新個體QpNew進(jìn)行變異，產(chǎn)生新個體QpNew'；

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

步驟5判定是否滿足終止條件，不滿足，轉(zhuǎn)步驟4。

步驟6結(jié)束。

3 選擇壓力的定義

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

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

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

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

4 元胞遺傳算法的優(yōu)化分析

4.1 選擇壓力比較

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

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

圖2 占有率隨代數(shù)變化曲線

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

4.2 算法性能比較

4.2.1 測試函數(shù)

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

F1（圖3）有兩個極值點，分布在（2.048，-2.048）、（-2.048，-2.048），對應(yīng)的值為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 進(jìn)化過程個體分布分析

圖3 函數(shù)F1的圖像

圖4 函數(shù)F2的圖像

傳統(tǒng)遺傳算法采用最優(yōu)保留策略，選擇為聯(lián)賽方式，交叉概率0.9，變異概率0.05；元胞遺傳算法的鄰居結(jié)構(gòu)采用圖1（b），交叉概率0.9，變異概率0.05，群體規(guī)模均為400，指定最大進(jìn)化代數(shù)為2 000。在此記錄了算法其中1次迭代過程的不同時刻群體分布變化情況（圖5～8）。

圖5 CGA-F1進(jìn)化過程

圖6 GA-F1進(jìn)化過程

圖7 GA-F2進(jìn)化過程

圖8 CGA-F2進(jìn)化過程

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

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

表1 F1計算結(jié)果

表2 F2計算結(jié)果

4.2.3 計算結(jié)果分析

有關(guān)參數(shù)如4.2.2節(jié)所設(shè)，運行100次，考慮最大進(jìn)化代數(shù)分別為1 000和2 000的情況。在作統(tǒng)計分析時采用的統(tǒng)計量如下：

F1在設(shè)定的最大進(jìn)化代數(shù)內(nèi)以最優(yōu)值的平均值、最優(yōu)值的標(biāo)準(zhǔn)差、收斂率、其求解最優(yōu)值在局部極值點3 897.734 2±1的百分比（P）等指標(biāo)來分析算法的計算性能，結(jié)果如表1。

F2在設(shè)定最大進(jìn)化代數(shù)內(nèi)以最優(yōu)值的平均值、最優(yōu)值的標(biāo)準(zhǔn)差、收斂率、其求解最優(yōu)值在局部極值點2 748.8±1的百分比（P）等指標(biāo)來分析算法的計算性能，結(jié)果如表2。

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

由表2來看，采用CGA算法時，F(xiàn)2在指定最大進(jìn)化代數(shù)可以收斂到最優(yōu)解，其在2 000代時的收斂率較1 000代時有明顯提高，并且其均值與最優(yōu)解偏差分別為0.1和0.2，沒有落入次優(yōu)解的個體，并且標(biāo)準(zhǔn)差很小，而采用GA算法時，在指定最大進(jìn)化代數(shù)內(nèi)收斂率均為0，其在次優(yōu)解附近的個體隨著進(jìn)化代數(shù)從1 000到2 000，從75%下降到71%，加大進(jìn)化代數(shù)并不能使個體跳出次優(yōu)解，并且由于其最優(yōu)解和次優(yōu)解相差很大，其標(biāo)準(zhǔn)差相當(dāng)大。

5 結(jié)論

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

[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]魯宇明，陳殊，黎明，等.自適應(yīng)調(diào)整選擇壓力的災(zāi)變元胞遺傳算法[J].系統(tǒng)仿真學(xué)報，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].計算機(jī)研究與發(fā)展，2001，38（10）：1211-1216.

[15]孫瑞祥，屈梁生.遺傳算法進(jìn)化截止代數(shù)分布規(guī)律的研究[J].計算機(jī)研究與發(fā)展，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—），女，講師，主要研究方向：計算機(jī)通信網(wǎng)。

2013-08-24

2013-10-22

1002-8331（2014）06-0040-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-12-11，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1308-0311.html