林志龍,魯宇明

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

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

林志龍,魯宇明

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

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

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

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

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

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

1.1 元胞遺傳算法原理

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

圖1 元胞遺傳算法圖

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

1.2 多樣性分析

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

2 多樣性度量方式

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

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

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

式(1)所示

(1)

(2)

(3)

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

3.1 算法的定義

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

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

3.2 DMCGA算法原理

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

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

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

4.1 測試函數(shù)

F1:Shubert函數(shù)

(4)

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

F2:Camel函數(shù)

(5)

該函數(shù)有6個局部極小值點,其中(-0.089 8,0.712 6)和(0.089 8,-0.712 6)為兩個全局最小點,最小值為-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)點,全局最小值在xi=0處取得,最小值為0。

F6:Shifted Rosenbrock函數(shù)

(9)

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[1] 潘正君,康立山,陳毓屏.演化計算[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é)報,2005,17(5):1052-1057.

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

[7] 魯宇明.一種具有演化規(guī)則的元胞遺傳算法[J].電子學(xué)報,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é)基金資助項目(20114BAB201046)

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

10.16180/j.cnki.issn1007-7820.2015.04.003

TP

A