元胞遺傳算法的多樣性研究

林志龍,魯宇明

(南昌航空大學(xué) 信息工程學(xué)院,江西 南昌 330063)

元胞遺傳算法的多樣性研究

林志龍,魯宇明

(南昌航空大學(xué) 信息工程學(xué)院,江西 南昌 330063)

探討了元胞遺傳算法中種群多樣性對(duì)全局尋優(yōu)/局部收斂平衡的意義,提出了基于鄰域結(jié)構(gòu)內(nèi)元胞遺傳算法的多樣性度量方式,并提出了改變遺傳算子的元胞遺傳算法來維持進(jìn)化過程種群的多樣性,算法將元胞空間網(wǎng)格嵌入到種群空間中,模擬遺傳操作在相鄰個(gè)體之間進(jìn)行。該算法不僅提高了全局搜索能力,且在維持種群多樣性方面有一定優(yōu)勢(shì)。

全局尋優(yōu)/局部收斂平衡;鄰域結(jié)構(gòu);多樣性度量方式;種群多樣性

在進(jìn)化算法[1]研究中,全局尋優(yōu)/局部收斂平衡是一個(gè)重要因素,全局尋優(yōu)與種群個(gè)體的分布有較大關(guān)系。進(jìn)化算法的主要問題就是存在過早收斂[2]。過早收斂的起因就是全局尋優(yōu)/局部收斂平衡問(Exploration/Exploitation Balance,EEB)[3]。生物學(xué)的多樣性往往與種群個(gè)體的外在特征有關(guān),即表現(xiàn)型多樣性,遺傳算法則更多從基因型多樣性來討論多樣性特征。

關(guān)于元胞遺傳算法種群多樣性的研究中,Alba[4]等人運(yùn)用算術(shù)交叉,均勻變異并提出了一種新方法,處理具有元胞遺傳算法的連續(xù)搜索空間來解決實(shí)際編碼問題,并在此基礎(chǔ)上采用非均勻變異的方法在初始空間進(jìn)行均勻搜索,采用適應(yīng)度高的個(gè)體代替當(dāng)前個(gè)體的精英替代策略。申元霞[5]等人提出一種新型保持群體多樣性的遺傳算法,并從種群的熵和個(gè)體基因座的多樣性來進(jìn)化種群的多樣性。李軍華[6]等人提出一種對(duì)遺傳算法多樣性的檢測(cè)方法,通過計(jì)算連接種群個(gè)體的連接矩陣的熵來反映種群的多樣性。魯宇明[7]等人提出了一種具有演化規(guī)則的元胞遺傳算法,并采取算法元胞演化選取規(guī)則,比較了元胞遺傳算法和遺傳算法對(duì)多樣性的維持能力。因此,元胞遺傳算法可以降低高適應(yīng)度個(gè)體的基因傳播速度,在一定程度上保持種群多樣性,改善遺傳性能具有較大的優(yōu)勢(shì)。

1 元胞遺傳算法多樣性分析

1.1 元胞遺傳算法原理

元胞遺傳算法種群多樣性的研究正是基于元胞自動(dòng)機(jī)多變的演化規(guī)則,元胞空間能在復(fù)雜規(guī)則下情況下尋找函數(shù)進(jìn)化過程的尋優(yōu)[8]和收斂。其基本操作如圖1所示。不同于標(biāo)準(zhǔn)的遺傳算法,元胞遺傳算法中群體的個(gè)體分布在兩維網(wǎng)格中,每個(gè)個(gè)體分別占據(jù)網(wǎng)格中的一個(gè)節(jié)點(diǎn),如圖2所示。

圖1 元胞遺傳算法圖

圖2 種群空間結(jié)構(gòu)模型

1.2 多樣性分析

元胞遺傳算法以元胞自動(dòng)機(jī)的主要理論為基礎(chǔ),交叉變異在鄰域之間進(jìn)行的一種遺傳算法。該算法核心思想是,選擇和交叉都只在一個(gè)鄰域內(nèi)完成,然后保留子代和父代中較優(yōu)秀個(gè)體,這樣就有效防止了過早收斂的發(fā)生。同時(shí),由于鄰域的重疊,保證基因不能越過鄰域傳遞,僅可在網(wǎng)格之間相互傳遞,最優(yōu)個(gè)體擴(kuò)散速度減慢,這樣大幅維持了種群的多樣性。

2 多樣性度量方式

盡管目前還沒有統(tǒng)一的概念來定義種群多樣性[9],但影響多樣性主要由種群個(gè)體之間的距離[10]和種群基因頻率兩種因素。本文提出了遺傳多樣性度量方式[11](Genotypic Diversity Measures,GDM),是一種專門衡量進(jìn)化過程中種群的多樣性值,其能較好地控制EEB平衡。為了更好的測(cè)量GDM值,在此處提出GDM的規(guī)范化,當(dāng)然一個(gè)好的GDM要能準(zhǔn)確測(cè)量迭代過程中種群多樣性值,為整個(gè)種群進(jìn)化提供依據(jù)。

GDM值與種群個(gè)體之間的距離是相關(guān)的,同時(shí)也跟個(gè)體基因位出現(xiàn)的頻率有較大關(guān)聯(lián)。GDM值在評(píng)價(jià)種群多樣性具有重要的參考性,表1是GDM規(guī)范條件下參數(shù)的設(shè)計(jì)。

表1 GDM測(cè)量參數(shù)定義

式(1)所示

(1)

(2)

(3)

3 基于提高變異算子概率的算法

3.1 算法的定義

簡(jiǎn)單的元胞遺傳算法CGA能反映元胞空間最初的個(gè)體生死狀態(tài),在進(jìn)化過程中,選擇和交叉算子通常正比于種群多樣性,但選擇與交叉算子并不能完全反映種群的多樣性發(fā)展。因此,在元胞遺傳算法的基礎(chǔ)上提出了加強(qiáng)變異概率的模擬機(jī)制,其本質(zhì)就是在二進(jìn)制編碼方式的基礎(chǔ)上提升概率來促進(jìn)個(gè)體適應(yīng)度。為達(dá)到效果,本文提出了一種新的遺傳算法(Diversity Maintaining Cellular Genetic Algorithm,DMCGA),該算法的精髓就是在選擇,交叉操作后,種群會(huì)造成一部分優(yōu)秀個(gè)體的損失,采取對(duì)個(gè)體進(jìn)行基因變異,提高競(jìng)爭(zhēng)壓力,促進(jìn)多樣性的保持。

變異算子通過基因座的二進(jìn)制編碼進(jìn)行判定,優(yōu)秀個(gè)體繼續(xù)保留,不適應(yīng)個(gè)體則進(jìn)行變異,這樣就隨機(jī)產(chǎn)生一些新個(gè)體,算法在一定周期內(nèi)對(duì)全局進(jìn)行變異,從而保持多樣性。

3.2 DMCGA算法原理

推導(dǎo):設(shè)xi,j為元胞空間種群個(gè)體,且xi,j采用基因座的二進(jìn)制編碼表示。初始下基因座是平衡的,也就是基因座“1”和“0”恰好各占1/2,用P(xij)=M/R公式來表示,其中M和R,分別代表種群個(gè)體xi,j“1”和“0”的總個(gè)數(shù)。在選擇交叉操作后會(huì)有大量?jī)?yōu)秀個(gè)體的缺失,優(yōu)秀個(gè)體的基因型特征用Φ表示,其Φ0和Φ1分別對(duì)應(yīng)其兩邊臨界點(diǎn),即Φ0≤P(xij)≤Φ1,在這里取Φ0=2/3,Φ1=1。當(dāng)P(xij)超出這個(gè)范圍就進(jìn)行變異操作,在這里用T表示,當(dāng)M?R時(shí),則有“M-R”個(gè)數(shù)目進(jìn)行變異;反之當(dāng)R?M時(shí),則有“R-M”進(jìn)行變異。

4 算法性能測(cè)試及結(jié)果分析

在測(cè)試中,選用6個(gè)測(cè)試函數(shù)對(duì)帶演化規(guī)則的元胞遺傳算法災(zāi)變機(jī)制下的元胞遺傳算法(Celluar Genetic Algotithm With Disaster,CGAD)和本文算法DMCGA兩種算法進(jìn)行測(cè)試。在優(yōu)化算法的全局收斂性,群體多樣性以及穩(wěn)定性進(jìn)行分析和比較,并采用式(3)來測(cè)試新算法對(duì)GDM值保持的效果。

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

F1:Shubert函數(shù)

(4)

該函數(shù)有760個(gè)局部最小值,其中18個(gè)是全局最小,其值為-186.73。

F2:Camel函數(shù)

(5)

該函數(shù)有6個(gè)局部極小值點(diǎn),其中(-0.089 8,0.712 6)和(0.089 8,-0.712 6)為兩個(gè)全局最小點(diǎn),最小值為-1.031 628。

F3:Schaffer函數(shù)

(6)

該函數(shù)全局最優(yōu)解為0,分布在(0,0)。

F4:Griewangk函數(shù)

(7)

F5:Ackley函數(shù)

(8)

該函數(shù)為一多峰函數(shù),具有大量局部最優(yōu)點(diǎn),全局最小值在xi=0處取得,最小值為0。

F6:Shifted Rosenbrock函數(shù)

(9)

該函數(shù)每個(gè)變量之間都具有關(guān)聯(lián)性,在xi=1時(shí),函數(shù)取得全局最小值0。

4.2 參數(shù)設(shè)置及結(jié)果分析

測(cè)試中,將種群規(guī)模p設(shè)置為400,高維測(cè)試時(shí),將2維設(shè)置進(jìn)化最大代數(shù)為10代,在10維以上時(shí)設(shè)置為3 000代。函數(shù)優(yōu)化均獨(dú)立運(yùn)行50次,交叉率為0.8,變異率為0.15。

統(tǒng)計(jì)結(jié)果如表2所示,其中,OP代表平均尋優(yōu)值,CV代表平均收斂代數(shù),GL全局收斂率,“—”表示不符合收斂條件。圖3和圖4是對(duì)Shubert函數(shù)和Camel函數(shù)在2維測(cè)試下的GDM值對(duì)比圖。圖3中DMCGA算法GDM值下降速率明顯低于CGAD算法,CGAD算法在進(jìn)化代數(shù)到達(dá)50代后GDM值基本就降到最低點(diǎn)。而從圖4Camel函數(shù)的測(cè)試結(jié)果來看,雖然最初DMCGA算法對(duì)種群多樣性損失較大,但迭代次數(shù)到70代左右時(shí),發(fā)生逆轉(zhuǎn)。長(zhǎng)期進(jìn)化來看,DMCGA算法對(duì)多樣性的維持好于CGAD算法。

表2 DMCGA與CGAD算法測(cè)試結(jié)果對(duì)比

圖3 Shubert函數(shù)的GDM值結(jié)果

圖4 Camel函數(shù)的GDM值結(jié)果

為更好地驗(yàn)證本文算法對(duì)高維函數(shù)的尋優(yōu)能力,將本文算法對(duì)F4～F6這3個(gè)高維函數(shù)進(jìn)行測(cè)試,其結(jié)果如圖5～圖7所示。從3個(gè)測(cè)試函數(shù)的結(jié)果來看,DMCGA算法對(duì)高維測(cè)試有較高的穩(wěn)定性和收斂能力。

圖5 F4函數(shù)適應(yīng)值迭代曲線

圖6 F5函數(shù)適應(yīng)值迭代曲線

圖7 F6函數(shù)適應(yīng)值迭代曲線

5 結(jié)束語

本文首先闡述了種群多樣性的研究現(xiàn)狀,提出了種群多樣性的3種度量方式,并選擇GF測(cè)量方式測(cè)試GDM值。最終,通過測(cè)試函數(shù)對(duì)本文算法性能進(jìn)行測(cè)試,從試驗(yàn)結(jié)果看,DMCGA算法在函數(shù)尋優(yōu)和收斂率方面取得了較好的效果,雖在高維函數(shù)測(cè)試時(shí),仍存在一定不足,但在一定程度上可以解決函數(shù)收斂問題,提高了搜索效率。

[1] 潘正君,康立山,陳毓屏.演化計(jì)算[M].北京:清華大學(xué)出版社,1998.

[2] Eiben A E,Schippers C A.On evolutionary exploration and exploitation[J].Fundamenta Informaticae,1998,2(1-4):35-50.

[3] Wh Tlev D.Cellular genetic algorithms[C].Morgan Kaufflnann:Proceeding Softhes International Conferrenee on Genetic Algorithms,1993:658-662.

[4] Bernabe Dorronsoro,Enrique Alba.A simple cellular genetic algorithm for continuous optimization[C].IEEE Congress on Evolutionary Computation,2009.

[5] 申元霞,張翠芳.一種新型保持種群多樣性的遺傳算法[J].系統(tǒng)仿真學(xué)報(bào),2005,17(5):1052-1057.

[6] 李軍華,黎明.元胞遺傳算法的收斂性分析和收斂速度估計(jì)[J].系統(tǒng)仿真學(xué)報(bào),2012,25(5):874-879.

[7] 魯宇明.一種具有演化規(guī)則的元胞遺傳算法[J].電子學(xué)報(bào),2010,38(7):1603-1607.

[8] James A Foster.Evolutionary computation[J].Nature,2001,4(2):428-436.

[9] Lieberson S.Measuring population diversity[J].America Sociol Review,1969,34(6):50-862.

[10]Olorunda O,Engelbrecht A P.Measuring exploration/exploitation in particle swarms using swarm diversity[C].In Proceeding of IEEE Congress Evolution Computer,2008:1128-1134.

[11]Guillaume Corriveau,Raynald Guilbault.Review and study of genotypic diversity measures for real-coded representations[J].IEEE Transactions On Evolutionary Computation,2012,16(5):695-709.

[12]Ursem R K.Diversity-guided evolutionary algorithms[C].In Proceeding 7thConference Parallel Problem Solving Nat.,2002,2439:462-471.

[13]Rosca J P.Entropy-driven adaptive representation.in Proc[C].Workshop Genet Program,1995,23-32.

Diversity of Cellular Genetic Algorithm

LIN Zhilong,LU Yuming

(School of Information Engineering,Nanchang Hangkong University,Nanchang 330063,China)

This paper discusses the significance of cellular genetic algorithms population diversity for exploration/exploitation balance (EEB),proposes diversity measures based on the neighborhood structure of the cellular genetic algorithm.By changing the genetic operators of the cellular genetic algorithm,the diversity of the population of the evolutionary process is maintained.The algorithm is to embed grid population space into the cellular space to simulate genetic operation between neighboring individuals.The algorithm not only improves the exploration/exploitation search ability,but it also has certain advantages in terms of maintaining the diversity of the population.

exploration/exploitation balance;neighborhood structure;genotypic diversity measures;population diversity

2014- 09- 01

江西省自然科學(xué)基金資助項(xiàng)目(20114BAB201046)

林志龍(1989—),男,碩士研究生。研究方向:智能優(yōu)化算法。E-mail:291587960@qq.com

10.16180/j.cnki.issn1007-7820.2015.04.003

TP

A