祝勤友++許峰

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

關鍵詞：多目標遺傳算法；元胞自動機；三維元胞空間；均勻性

DOIDOI：10.11907/rjdk.151598

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：16727800（2015）009005204

0 引言

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

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

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

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

1.1 元胞遺傳算法

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

CGA算法流程見圖1。

圖1 CGA算法流程

1.2 元胞空間

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

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

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

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

圖3 三維球形元胞空間

2 多目標元胞遺傳算法

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

2.1 多目標遺傳算法

多目標優(yōu)化問題的數(shù)學模型為

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

2.2 最優(yōu)解集評價標準

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

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

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

2.3 多目標三維元胞空間遺傳算法

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

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

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

3 數(shù)值實驗

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

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

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

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

4 結(jié)語

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

目前，遺傳算法、多目標進化算法、元胞遺傳算法的理論基礎還很薄弱，性能研究只能依賴于對測試問題的對比實驗。元胞遺傳算法的收斂性及解的性能等有待進一步研究。

參考文獻參考文獻：

[ 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 ] 張屹，盧超，張虎.基于差分元胞多目標遺傳算法的車間布局優(yōu)化[ J ].計算機集成制造系統(tǒng)， 2013， 19（4）： 727734.

責任編輯（責任編輯：杜能鋼）