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

林志龍,魯宇明

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

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

林志龍,魯宇明

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

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

全局尋優/局部收斂平衡;鄰域結構;多樣性度量方式;種群多樣性

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

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

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

1.1 元胞遺傳算法原理

元胞遺傳算法種群多樣性的研究正是基于元胞自動機多變的演化規則,元胞空間能在復雜規則下情況下尋找函數進化過程的尋優[8]和收斂。其基本操作如圖1所示。不同于標準的遺傳算法,元胞遺傳算法中群體的個體分布在兩維網格中,每個個體分別占據網格中的一個節點,如圖2所示。

圖1 元胞遺傳算法圖

圖2 種群空間結構模型

1.2 多樣性分析

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

2 多樣性度量方式

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

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

表1 GDM測量參數定義

式(1)所示

(1)

(2)

(3)

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

3.1 算法的定義

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

變異算子通過基因座的二進制編碼進行判定,優秀個體繼續保留,不適應個體則進行變異,這樣就隨機產生一些新個體,算法在一定周期內對全局進行變異,從而保持多樣性。

3.2 DMCGA算法原理

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

4 算法性能測試及結果分析

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

4.1 測試函數

F1:Shubert函數

(4)

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

F2:Camel函數

(5)

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

F3:Schaffer函數

(6)

該函數全局最優解為0,分布在(0,0)。

F4:Griewangk函數

(7)

F5:Ackley函數

(8)

該函數為一多峰函數,具有大量局部最優點,全局最小值在xi=0處取得,最小值為0。

F6:Shifted Rosenbrock函數

(9)

該函數每個變量之間都具有關聯性,在xi=1時,函數取得全局最小值0。

4.2 參數設置及結果分析

測試中,將種群規模p設置為400,高維測試時,將2維設置進化最大代數為10代,在10維以上時設置為3 000代。函數優化均獨立運行50次,交叉率為0.8,變異率為0.15。

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

表2 DMCGA與CGAD算法測試結果對比

圖3 Shubert函數的GDM值結果

圖4 Camel函數的GDM值結果

為更好地驗證本文算法對高維函數的尋優能力,將本文算法對F4～F6這3個高維函數進行測試,其結果如圖5～圖7所示。從3個測試函數的結果來看,DMCGA算法對高維測試有較高的穩定性和收斂能力。

圖5 F4函數適應值迭代曲線

圖6 F5函數適應值迭代曲線

圖7 F6函數適應值迭代曲線

5 結束語

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

[1] 潘正君,康立山,陳毓屏.演化計算[M].北京:清華大學出版社,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].系統仿真學報,2005,17(5):1052-1057.

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

[7] 魯宇明.一種具有演化規則的元胞遺傳算法[J].電子學報,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

江西省自然科學基金資助項目(20114BAB201046)

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

10.16180/j.cnki.issn1007-7820.2015.04.003

TP

A