汪穎，查代奉

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

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

汪穎，查代奉

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

（1）同步機(jī)制

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

（2）異步機(jī)制

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

2.3 算法步驟

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

算法具體步驟：

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

步驟3評(píng)價(jià)群體個(gè)體的適應(yīng)度f(wàn)(Qpij)。

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

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

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

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

替代：若f(QpNew')＞f(Qpcenter)，則產(chǎn)生的新個(gè)體QpNew'優(yōu)于原中心元胞個(gè)體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提出了取代時(shí)間概念，用它作為衡量一個(gè)進(jìn)化過(guò)程選擇壓力的一個(gè)重要指標(biāo)，從操作來(lái)看，即是：在只有選擇操作情況下，一個(gè)好的個(gè)體占據(jù)整個(gè)群體的時(shí)間[13]。取代時(shí)間越短意味著選擇壓力越高，選擇壓力與取代時(shí)間成反比。

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

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

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

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

4.1 選擇壓力比較

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

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

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

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

4.2 算法性能比較

4.2.1 測(cè)試函數(shù)

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

F1（圖3）有兩個(gè)極值點(diǎn)，分布在（2.048，-2.048）、（-2.048，-2.048），對(duì)應(yīng)的值為3 897.734 2和3 905.926 2。后者為全局極大值點(diǎn)，一般遺傳算法極易陷入第一個(gè)極值點(diǎn)。

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

4.2.2 進(jìn)化過(guò)程個(gè)體分布分析

圖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次迭代過(guò)程的不同時(shí)刻群體分布變化情況（圖5～8）。

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

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

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

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

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

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

表1 F1計(jì)算結(jié)果

表2 F2計(jì)算結(jié)果

4.2.3 計(jì)算結(jié)果分析

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

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

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

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

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

5 結(jié)論

由以上分析可知，進(jìn)化過(guò)程中，元胞遺傳算法的選擇壓力要低于傳統(tǒng)遺傳算法，CGA算法維持種群多樣性能力好于GA算法，這也就為優(yōu)化過(guò)程的進(jìn)行提供了條件。當(dāng)優(yōu)化問(wèn)題存在多個(gè)極值點(diǎn)時(shí)，即使初始種群個(gè)體是均勻分布在搜索空間，但隨著種群進(jìn)化，個(gè)體在搜索空間的分布會(huì)發(fā)生變化，趨勢(shì)是有差異的。GA算法中大多數(shù)個(gè)體是向某個(gè)局部極值點(diǎn)靠近，因此GA算法在求解上述存在局部最優(yōu)解問(wèn)題時(shí)，由于變異存在，有少數(shù)機(jī)會(huì)可以跳出次優(yōu)解，但大多數(shù)時(shí)候都落入次優(yōu)解而無(wú)法跳出；而CGA算法中個(gè)體是向不同極值點(diǎn)呈區(qū)域范圍內(nèi)靠近，因此可尋優(yōu)得到全局極值點(diǎn)，適當(dāng)增加進(jìn)化代數(shù)，可以促進(jìn)其全局收斂。總體而言，元胞遺傳算法無(wú)論是在優(yōu)化結(jié)果還是在優(yōu)化穩(wěn)定性方面都優(yōu)于傳統(tǒng)遺傳算法，并且具有更好的全局探索能力。在處理具有多個(gè)極值點(diǎn)的優(yōu)化問(wèn)題時(shí)，元胞遺傳算法的性能具有特別明顯的優(yōu)勢(shì)，尤其當(dāng)最優(yōu)極值點(diǎn)處于極小區(qū)域內(nèi)時(shí)（如F2），遺傳算法幾乎無(wú)法尋找到全局最優(yōu)，通常在未收斂到全局最優(yōu)之前就停滯局部?jī)?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)變?cè)z傳算法[J].系統(tǒng)仿真學(xué)報(bào)，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]郭東偉，周春光，劉大有.遺傳算法取代時(shí)間的分析[J].計(jì)算機(jī)研究與發(fā)展，2001，38（10）：1211-1216.

[15]孫瑞祥，屈梁生.遺傳算法進(jìn)化截止代數(shù)分布規(guī)律的研究[J].計(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ì)算機(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