基于三維元胞空間的多目標(biāo)元胞遺傳算法

祝勤友++許峰

摘 要：元胞遺傳算法是一種將元胞自動(dòng)機(jī)與遺傳算法相結(jié)合的進(jìn)化算法，這種算法具有遺傳算法的適用性、并行性和擴(kuò)展性，但是在后期的二維元胞空間擴(kuò)散速度過(guò)慢。提出了一種基于三維球形元胞空間的多目標(biāo)元胞遺傳算法，其基本思想是：取元胞空間為三維球，根據(jù)Pareto支配關(guān)系找出種群中的非支配解并保存到精英集，根據(jù)元胞自動(dòng)機(jī)中拓?fù)浣Y(jié)構(gòu)和鄰居等機(jī)制，使精英集中的Pareto非支配解在種群中擴(kuò)散。指標(biāo)分析和數(shù)值實(shí)驗(yàn)表明，新算法的解不僅多樣性和均勻性較好，而且在后期具有較快的擴(kuò)散速度。

關(guān)鍵詞：多目標(biāo)遺傳算法；元胞自動(dòng)機(jī)；三維元胞空間；均勻性

DOIDOI：10.11907/rjdk.151598

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）009005204

0 引言

20世紀(jì)80年代初，著名物理學(xué)家Wolfram開(kāi)始研究元胞自動(dòng)機(jī)，他先后研究了一系列一維和二維元胞自動(dòng)機(jī)，并根據(jù)研究成果，提出了著名的Wolfram規(guī)則。在此基礎(chǔ)上，Wolfram 2002年出版了專著《A New of Science》。1987年，Robertson提出世界上第一個(gè)元胞遺傳算法模型，該算法運(yùn)行在CMI計(jì)算機(jī)上。此模型的所有遺傳操作（父代個(gè)體的選擇、替換、交叉和變異操作）都是并行執(zhí)行。一年之后，Muhienbein等發(fā)表了一篇利用運(yùn)行在大規(guī)模并行機(jī)器上的元胞遺傳算法求解TSP問(wèn)題的文章，該算法添加了一個(gè)局部搜索，改善了由交叉和變異算子產(chǎn)生的解。因此，該算法被認(rèn)為是第一個(gè)混合元胞遺傳算法。之后，又出現(xiàn)了一些元胞遺傳算法。它們被稱為Pollination plants、Parallel individual、Diffusion、Fine grained、Massively parallelm模型。

鑒于元胞遺傳算法對(duì)于搜索空間能夠帶來(lái)全局搜索和局部尋優(yōu)的良好平衡，具有優(yōu)越的復(fù)雜問(wèn)題解決能力，許多學(xué)者將其用于解決實(shí)際工程問(wèn)題中，主要應(yīng)用領(lǐng)域有：神經(jīng)網(wǎng)絡(luò)訓(xùn)練、電子信息、機(jī)械設(shè)計(jì)制造、調(diào)度決策問(wèn)題數(shù)學(xué)優(yōu)化、交通控制、3D動(dòng)畫設(shè)計(jì)、圖像處理、經(jīng)濟(jì)學(xué)、生物學(xué)等。

本文根據(jù)元胞遺傳算法操作特點(diǎn)，對(duì)遺傳算法的元胞空間進(jìn)行分析，提出一種基于三維元胞空間的多目標(biāo)元胞遺傳算法，并對(duì)該算法進(jìn)行性能分析和數(shù)值實(shí)驗(yàn)。

1 元胞遺傳算法與元胞空間

1.1 元胞遺傳算法

元胞遺傳算法（Cellular Genetic Algorithms， CGA）是一種將遺傳算法和元胞自動(dòng)機(jī)原理相結(jié)合的進(jìn)化算法。在元胞遺傳算法中，元胞模型從初始個(gè)體出發(fā)對(duì)自然界的進(jìn)化過(guò)程進(jìn)行模擬，初始種群被分布在一個(gè)相互聯(lián)通的平面或空間拓?fù)浣Y(jié)構(gòu)中，在這種相互聯(lián)通的網(wǎng)狀結(jié)構(gòu)中，個(gè)體被安放在網(wǎng)格點(diǎn)上，每個(gè)個(gè)體只能與其鄰近的個(gè)體進(jìn)行信息交換，而且交叉操作也被嚴(yán)格限制在鄰近個(gè)體間進(jìn)行。這樣，可以使得種群中的個(gè)體產(chǎn)生一定的隔離，類似于自然界中的小生境，從而保持種群的多樣性。

CGA算法流程見(jiàn)圖1。

圖1 CGA算法流程

1.2 元胞空間

在元胞自動(dòng)機(jī)中，空間和時(shí)間都是離散的，物理量只取有限值集。元胞自動(dòng)機(jī)由元胞、元胞空間、鄰居和規(guī)則這4個(gè)基本部分組成。許多對(duì)元胞遺傳算法的改進(jìn)多集中于對(duì)元胞自動(dòng)機(jī)各組成部分的改進(jìn)，本文主要對(duì)元胞空間進(jìn)行改進(jìn)。

元胞所分布的空間網(wǎng)點(diǎn)的集合稱為元胞空間，可以按照幾何開(kāi)關(guān)、邊界條件對(duì)元胞空間進(jìn)行分類。目前，元胞遺傳算法多采用一維和二維元胞空間。對(duì)于一維元胞自動(dòng)機(jī)，元胞空間的劃分只有一種。而高維的元胞自動(dòng)機(jī)，元胞空間的劃分可有多種形式。在二維元胞自動(dòng)機(jī)中，三角形、四邊形和六邊形元胞空間最為常見(jiàn)，見(jiàn)圖2。

圖2 四邊形、三角形、六邊形元胞空間

三維元胞空間可以是多種形狀，考慮到網(wǎng)格點(diǎn)的均勻分布，本文采用三維球形元胞空間，見(jiàn)圖3。

圖3 三維球形元胞空間

2 多目標(biāo)元胞遺傳算法

考慮到元胞遺傳算法的優(yōu)良特性，Alba于2007年提出了第一個(gè)元胞多目標(biāo)遺傳算法cMOGA。之后，Alba又對(duì)其進(jìn)行了改進(jìn)，給出了改進(jìn)的cMOGA，即MOCell。Durillo將廣義差分算法引入MOCell算法，提出了一種混合元胞多目標(biāo)遺傳算法CellDE，大大提升了MOCell解決三目標(biāo)問(wèn)題的效果，此算法在解決三目標(biāo)問(wèn)題時(shí)明顯優(yōu)于NSGAII和MOCell。Li等提出了一種自適應(yīng)元胞多目標(biāo)遺傳算法，使得算法的收斂速度在一定程度上得到了提高。張屹等在CellDE中添加了一個(gè)變異算子，提出了新的差分進(jìn)化多目標(biāo)元胞算法 DECell，有效地保持了種群多樣性，增大了解集的覆蓋范圍。

2.1 多目標(biāo)遺傳算法

多目標(biāo)優(yōu)化問(wèn)題的數(shù)學(xué)模型為

雙目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)前沿通常是平面曲線，而三目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)前沿往往是空間曲面。

2.2 最優(yōu)解集評(píng)價(jià)標(biāo)準(zhǔn)

對(duì)多目標(biāo)優(yōu)化算法性能的評(píng)價(jià)包括算法的運(yùn)行效率和最優(yōu)解集的質(zhì)量。算法的運(yùn)行效率主要指算法的復(fù)雜性，可以用算法占用的CPU時(shí)間表示，最優(yōu)解集的質(zhì)量包括算法的全局、局部收斂性和最優(yōu)解集的均勻性、分布性。目前，評(píng)價(jià)多目標(biāo)優(yōu)化算法性能主要依靠典型測(cè)試問(wèn)題的數(shù)值實(shí)驗(yàn)和量化評(píng)價(jià)指標(biāo)值，本文采用的量化評(píng)價(jià)指標(biāo)值如下：

（1）代間距離（Generation Distance， GD）：

其中，n和di與（1）中相同。實(shí)際上，SP就是di的標(biāo)準(zhǔn)差。根據(jù)標(biāo)準(zhǔn)差的意義，SP描述的是最優(yōu)解集的均勻性。

2.3 多目標(biāo)三維元胞空間遺傳算法

在CGA中，遺傳算法將初始種群均勻地分布在元胞空間拓?fù)浣Y(jié)構(gòu)中。在這種元胞空間的網(wǎng)狀結(jié)構(gòu)中，每個(gè)個(gè)體被置于網(wǎng)格點(diǎn)上，每個(gè)個(gè)體只能與其鄰近個(gè)體交叉操作。元胞遺傳算法最主要的優(yōu)點(diǎn)在于，在對(duì)解空間進(jìn)行搜索時(shí)，能保持全局搜索和局部尋優(yōu)平衡。但是在這種平衡下，后期的最優(yōu)解在種群中擴(kuò)散的速度比較緩慢，效率不高，這時(shí)候算法的繁殖周期較大，即最優(yōu)個(gè)體占據(jù)元胞空間所需要的周期比較長(zhǎng)。

為了改善后期效率，可以對(duì)元胞空間進(jìn)行改進(jìn)，將初始種群中的個(gè)體安置于三維元胞空間中。類似于二維元胞空間，將初始種群均勻分布在球體的表面網(wǎng)格中，這種網(wǎng)狀結(jié)構(gòu)的邊界是同心球球面，一個(gè)個(gè)體的鄰居是根據(jù)它在種群網(wǎng)格中與其它個(gè)體之間的距離（二個(gè)同心球的半徑距離）來(lái)定義的。對(duì)于二維元胞空間遺傳算法，個(gè)體與自己的鄰居進(jìn)行進(jìn)化產(chǎn)生的新個(gè)體，繁殖的周期一致，但是當(dāng)繁殖周期到一定程度時(shí)，原先的元胞遺傳算法會(huì)出現(xiàn)種群中最優(yōu)個(gè)體擴(kuò)散到窄邊界的情況，這時(shí)候最優(yōu)個(gè)體擴(kuò)散速度明顯下降。但是在三維元胞空間中，種群分布在球的表面，不會(huì)出現(xiàn)上述情況，這時(shí)最優(yōu)個(gè)體所占比例增長(zhǎng)速度不會(huì)出現(xiàn)變慢的現(xiàn)象。

算法流程如下：①將初始種群分布在三維元胞空間中；②在相鄰的元胞中選擇一個(gè)個(gè)體作為父代；③將選擇出來(lái)的鄰居元胞與中心元胞進(jìn)行交叉，變異操作；④根據(jù)Pareto支配關(guān)系找出種群中的非支配解并保存到精英集中，產(chǎn)生新的個(gè)體；⑤如果產(chǎn)生的新個(gè)體優(yōu)于中心元胞，則將中心元胞替換，否則，不替換；⑥如果代數(shù)小于最大進(jìn)化代數(shù)，則返回到步驟②；⑦將當(dāng)前最優(yōu)解輸出。

3 數(shù)值實(shí)驗(yàn)

為了檢驗(yàn)算法性能，下面對(duì)兩個(gè)多目標(biāo)進(jìn)化算法標(biāo)準(zhǔn)測(cè)試函數(shù)DTLZ1和DTLZ2進(jìn)行數(shù)值計(jì)算，并將優(yōu)化結(jié)果與普通多目標(biāo)元胞遺傳算法的優(yōu)化結(jié)果進(jìn)行比較。

數(shù)值實(shí)驗(yàn)參數(shù)是：群體規(guī)模為200，進(jìn)化代數(shù)為200，交叉概率為0.85，變異概率為0.1。

從表1和表2可以看出，基于三維元胞空間的多目標(biāo)元胞遺傳算法的GD指標(biāo)明顯優(yōu)于常規(guī)CGA算法，表明引入三維元胞空間的確明顯改善了CGA的全局收斂性。三維CGA的ER和SP指標(biāo)較常規(guī)CGA算法也顯著占優(yōu)，表明三維CGA解的分布性和均勻性也有明顯提高。

由此得出明確結(jié)論：基于三維元胞空間的多目標(biāo)元胞遺傳算法與二維多目標(biāo)遺傳算法相比，在解的分布性、均勻性和收斂性方面有明顯改善。

4 結(jié)語(yǔ)

針對(duì)二維元胞遺傳算法后期解的擴(kuò)散速度較慢這個(gè)缺陷，將三維球形元胞空間引入多目標(biāo)元胞遺傳算法。指標(biāo)分析與數(shù)值實(shí)驗(yàn)結(jié)果表明：三維多目標(biāo)元胞遺產(chǎn)算法在后期的擴(kuò)散速度較快，解的分布性、均勻性、收斂性均明顯優(yōu)于二維多目標(biāo)元胞遺傳算法。

目前，遺傳算法、多目標(biāo)進(jìn)化算法、元胞遺傳算法的理論基礎(chǔ)還很薄弱，性能研究只能依賴于對(duì)測(cè)試問(wèn)題的對(duì)比實(shí)驗(yàn)。元胞遺傳算法的收斂性及解的性能等有待進(jìn)一步研究。

參考文獻(xiàn)參考文獻(xiàn)：

[ 1 ] WOLFRAM S. A new kind of science[ M ].Champsign： Wolfram Media， 2002.

[ 2 ] ROBERTSON G. Parallel implementation of genetic algorithms in a classifier system[ C ].Proceedings of the Second International Conference on Genetic Algorithms， New Jersey， 1987： 140147.

[ 3 ] MUHLENBEIN H，GORGES SCHLEUTR M，KRAMER O.Evolution algorithms in combinatorial optimization[ J ].Parallel Computing， 1988（7）： 6588.

[ 4 ] GOLDBERG D E.Genetic algorithms in search，optimization and machine learning[ M ].Reading：AddisonWesley，1989.

[ 5 ] HOFFNEISTER F.Applied parallel and distributed optimization[ M ].Heidelberg：SpringerVerlag，1991.

[ 6 ] BACKT，F(xiàn)OGEL D B，MICHALEWICZ Z.Handbook of evolutionary computation[ M ].London：Oxford university press， 1997.

[ 7 ] MANDERICK B，SPIESSENS P.Finegrained parallel genetic algorithms[ C ].Proceedings of the Third International Conference on Genetic Algorithms，Richmond，1989：428433.

[ 8 ] HILIS D.Coevolving parasites improve simulated evolution ad an optimizing procedure[ J ].Physical D，1990（42）：228234.

[ 9 ] ALBA E，DORRONSORO B，LUNA F.A cellular multiobjective genetic altorithm for optimal broadcasting strategy in metrolitan MANETs[ J ]. Computer Communications， 2007， 30（4）： 685697.

[ 10 ] NEBRO A J，DURILLO J J，LUNA F.MOCell：a celluar genetic algorithm for multiobjective optimization[ J ].International journal of Intelligent Syetems， 2009， 24（7）： 726746.

[ 11 ] DURILLO J J，NEBRO A J，LUNA F.Solving threeobjective optimization problems using a new hybrid cellular genetic algorithm[ C ].Proceedings of the International Conference on Parallel problem Solving from Nature. Heidellberg： SpringerVerlag， 2008： 661670.

[ 12 ] LI X Y，SUN Y F，LIU C Y.The adaptive cellular genetic algorithm and analysis of stock prices[ J ].Journal of Wuyi University，2011，25（4）：5765.

[ 13 ] 張屹，盧超，張虎.基于差分元胞多目標(biāo)遺傳算法的車間布局優(yōu)化[ J ].計(jì)算機(jī)集成制造系統(tǒng)， 2013， 19（4）： 727734.

責(zé)任編輯（責(zé)任編輯：杜能鋼）