張　屹，萬(wàn)興余，鄭小東，孫莉莉

(三峽大學(xué)機(jī)械與動(dòng)力學(xué)院，湖北宜昌443002)

?

基于正交設(shè)計(jì)的元胞多目標(biāo)遺傳算法

張屹，萬(wàn)興余，鄭小東，孫莉莉

(三峽大學(xué)機(jī)械與動(dòng)力學(xué)院，湖北宜昌443002)

摘要：元胞多目標(biāo)遺傳算法在求解兩目標(biāo)優(yōu)化問(wèn)題時(shí)是比較高效的.但是，初步實(shí)驗(yàn)顯示其在求解三目標(biāo)優(yōu)化問(wèn)題(例如DTLZ系列)時(shí)，表現(xiàn)不是十分令人滿意.為了進(jìn)一步提高算法的性能，引入了正交設(shè)計(jì)的思想，提出了基于正交設(shè)計(jì)的多目標(biāo)元胞遺傳算法.在改進(jìn)算法的迭代過(guò)程中，先對(duì)父代個(gè)體進(jìn)行分段，之后按照正交表來(lái)對(duì)這些片段進(jìn)行重新組合產(chǎn)生多個(gè)子代個(gè)體，然后從這些子代個(gè)體中找出適應(yīng)度較優(yōu)的進(jìn)入下一代種群.實(shí)驗(yàn)結(jié)果表明，引入正交設(shè)計(jì)思想能夠提高算法性能，與其他優(yōu)秀算法進(jìn)行比較的結(jié)果說(shuō)明，改進(jìn)算法求解三目標(biāo)問(wèn)題(DTLZ系列)也是具有競(jìng)爭(zhēng)力的.

關(guān)鍵詞：多目標(biāo);元胞遺傳算法;正交設(shè)計(jì);函數(shù)優(yōu)化

1　引言

現(xiàn)實(shí)中很多優(yōu)化問(wèn)題常常同時(shí)涉及到相互沖突的多個(gè)目標(biāo)，稱之為多目標(biāo)優(yōu)化問(wèn)題.近年來(lái)，進(jìn)化算法在多目標(biāo)優(yōu)化中得到了廣泛應(yīng)用的同時(shí)也遇到了很多挑戰(zhàn)［1，2］.目前為止，這個(gè)領(lǐng)域中著名的算法有NSGAII［3］、PAES［4］、SPEA2［5］、MOEA/D［6］和MOCell［7］等.這些算法中，大部分的算法都是使用單一種群.與此相對(duì)應(yīng)的是，存在一些所謂的結(jié)構(gòu)化進(jìn)化算法，即在一定程度上對(duì)種群進(jìn)行分散處理.種群的分散處理大致包括兩種方式，一種是分布式，另一種是元胞式.元胞式遺傳算法已經(jīng)被證明在解決很多單目標(biāo)優(yōu)化問(wèn)題時(shí)非常高效［8］.Kirley M提出了一種集合種群進(jìn)化算法(MEA)［9］，這種算法是以在種群中偶爾發(fā)生災(zāi)變機(jī)制為特色的元胞模型，當(dāng)災(zāi)變發(fā)生的時(shí)候，災(zāi)變區(qū)域的所有個(gè)體都會(huì)滅絕同時(shí)這個(gè)空的區(qū)域也會(huì)被其他個(gè)體占據(jù).Alba提出了cMOGA［10］算法，這是當(dāng)時(shí)基于典型元胞遺傳算法(cGA)模型的一個(gè)元胞多目標(biāo)算法.在cMOGA的基礎(chǔ)上，為了更加適應(yīng)多目標(biāo)優(yōu)化領(lǐng)域的要求，Antonio J Nebro等提出了MOCell算法.MOCell與cMOGA相比的一個(gè)主要改進(jìn)就是引入了反饋機(jī)制，即在每次迭代完成后會(huì)將一定數(shù)量的解從外部文檔返回到種群中，隨機(jī)替換掉種群中相等數(shù)量的個(gè)體.

相關(guān)研究表明MOCell在解決大多數(shù)兩目標(biāo)優(yōu)化問(wèn)題時(shí)具有比較高的效率.但是，初步試驗(yàn)表明，MOCell算法在求解三目標(biāo)優(yōu)化問(wèn)題時(shí)有較大困難，這一點(diǎn)用MOCell求解DTLZ系列問(wèn)題可以看出.

鑒于MOCell算法的優(yōu)點(diǎn)，很多學(xué)者對(duì)此進(jìn)行了研究，主要涉及鄰居結(jié)構(gòu)［11］、選擇機(jī)制、交叉機(jī)制以及與其他算法混合等.Juan J Durillo等將MOCell與差分進(jìn)化算法相結(jié)合［12］，使用差分算子替換掉MOCell中的交叉和變異算子，試驗(yàn)結(jié)果表明這種改進(jìn)能夠較好的解決DTLZ系列問(wèn)題.Asmaa Al-Naqi等將自適應(yīng)三維拓?fù)浣Y(jié)構(gòu)引入元胞遺傳算法［13］，種群被放置在三維空間中并且動(dòng)態(tài)調(diào)整遺傳參數(shù)，試驗(yàn)結(jié)果表明這種改進(jìn)方法在搜索效率方面得到了較大提高.

本文借鑒正交設(shè)計(jì)的思想，以MOCell為基礎(chǔ)提出了基于正交交叉的多目標(biāo)元胞遺傳算法(Cellular Genetic Algorithm for Multiobjective Optimization Based on Orthogonal Design，ODMOCell).正交交叉在一次操作中就可以產(chǎn)生多個(gè)子代個(gè)體，而根據(jù)正交表均衡分散的特點(diǎn)，這些個(gè)體都是在父代個(gè)體周圍均衡分布的，能夠加強(qiáng)算法的局部搜索能力.實(shí)驗(yàn)結(jié)果表明，ODMOCell算法與其他幾種典型的算法相比，有一定的競(jìng)爭(zhēng)力.

2　典型元胞遺傳算法(cGA)

典型cGA的基本思想如算法1所示，在這個(gè)基本cGA中，種群被放置在一維、二維或者三維的網(wǎng)格中，然后對(duì)個(gè)體的鄰居進(jìn)行定義.算法在執(zhí)行過(guò)程中，逐一對(duì)種群中的每個(gè)個(gè)體進(jìn)行操作(第3行)，每個(gè)個(gè)體只能與它周圍的鄰居進(jìn)行交流(第4、5行).對(duì)選出的父代個(gè)體進(jìn)行交叉操作(第6行)和變異操作(第7行)，然后對(duì)得到的子代個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)(第8行)，如果產(chǎn)生的子代個(gè)體符合一定條件，就將其插入輔助種群中(第9行).每一次迭代完成后，新產(chǎn)生的輔助種群被當(dāng)作下一次循環(huán)的新種群(第11行)，如此循環(huán)直到滿足循環(huán)終止條件為止(第2行).

3　基于正交設(shè)計(jì)的多目標(biāo)元胞遺傳算法(ODMOCell)

不少學(xué)者對(duì)正交設(shè)計(jì)在算法中的應(yīng)用進(jìn)行了相關(guān)研究，取得了較好的效果［14～20］.受到這種啟示，為了進(jìn)一步提高多目標(biāo)元胞遺傳算法的性能，使得在求解DTLZ系列問(wèn)題時(shí)也能具有較好的效果，將正交設(shè)計(jì)技術(shù)引入到MOCell算法中.

ODMOCell算法的流程如算法2所示，首先，配置算法中需要用到的參數(shù)(第1行)，例如交叉概率，變異概率，鄰居大小等;其次，創(chuàng)建一個(gè)空的Pareto前端文件用來(lái)存放算法在運(yùn)行過(guò)程中找到的非支配解(第2行);然后，依次對(duì)種群中的每個(gè)個(gè)體進(jìn)行取鄰居、選父代個(gè)體、設(shè)計(jì)正交交叉、交叉操作和變異操作等(第5-9行);緊接著對(duì)得到的子代個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)(第10行);然后將子代個(gè)體按照一定的規(guī)則插入到輔助種群和Pareto前端文件中(第11，12行);接下來(lái)將輔助種群作為下一代進(jìn)化的新種群(第14行);最后，調(diào)用反饋機(jī)制將Pareto前端文件中的部分個(gè)體隨機(jī)替換掉種群中的等量的個(gè)體，形成下一次迭代開始的初始種群.如此循環(huán)直到滿足終止條件為止(第3行).

正交交叉算子主要用于指導(dǎo)父代個(gè)體的結(jié)合方式.按照正交表的規(guī)則構(gòu)造出的交叉算子稱為“正交交叉”算子(OXC).在此，以L8(27)為例進(jìn)行說(shuō)明.

圖1中，P1，P2是兩個(gè)父代個(gè)體，O1、O2至O8都是按照7因素2水平正交表生成的子代個(gè)體，其中O1與P1完全相同，因此父代個(gè)體中的P1被保留到了子代，然后所有的子代個(gè)體之間進(jìn)行競(jìng)爭(zhēng)，選出最好的一個(gè)個(gè)體進(jìn)行下一步的遺傳操作，這種方式在一定程度上保護(hù)了好的父代個(gè)體免遭交叉操作的破壞.

如果算法中的個(gè)體編碼方法用的是實(shí)數(shù)編碼，則可以對(duì)父代個(gè)體的每個(gè)基因位進(jìn)行離散操作，具體方法如下:

(1)取出兩個(gè)父代個(gè)體，

(2)取出每個(gè)基因位上的最大值和最小值，min(e1i，e2i)，max(e1i，e2i).

(3)將每個(gè)基因位離散化為Q個(gè)水平，

(4)選擇與Q個(gè)水平相對(duì)應(yīng)的正交表生成下一代個(gè)體.

盡管可以將因素較少的試驗(yàn)安排在因素較多的正交表中，但是這樣做并不是非常好.還是希望盡可能的將試驗(yàn)安排在因素大小剛好合適的正交表中.而且，有些時(shí)候個(gè)體的編碼串會(huì)很長(zhǎng)，要構(gòu)造出這樣的正交表并且按照這種正交表進(jìn)行子代個(gè)體的組合，計(jì)算開銷會(huì)特別大.我們的目標(biāo)是無(wú)論編碼串有多長(zhǎng)，都可以使用正交交叉.為了達(dá)到這個(gè)目的，采取的方法是將代碼串進(jìn)行分解，將分解后得到的每個(gè)小段當(dāng)做一個(gè)整體作為一個(gè)因素.如果想要使用L8(27)正交表，則需要將父代個(gè)體的編碼串分割為7小段，如果想要使用L9(34)正交表，則需要將父代個(gè)體的編碼串分割為4小段，同時(shí)將兩個(gè)父代個(gè)體的對(duì)應(yīng)基因位離散化為3水平.

對(duì)基因串進(jìn)行分割的具體方法是這樣的.首先，隨機(jī)產(chǎn)生m個(gè)正整數(shù)(m個(gè)數(shù)將基因串隨機(jī)分割為m +1段，也就是m + 1水平)，1≤H1＜H2＜…＜Hm＜n;其次，將分割后的子串處理為新的因素:

4　實(shí)驗(yàn)與結(jié)果分析

下面主要是對(duì)改進(jìn)算法(ODMOCell)的性能進(jìn)行評(píng)估.首先，介紹了文中要用到的測(cè)試函數(shù);其次，對(duì)需要用到的性能指標(biāo)進(jìn)行了說(shuō)明;再次，將改進(jìn)算法與它的初始算法(MOCell)以及MOCell的改進(jìn)算法CellDE的性能進(jìn)行了比較，以便判斷引進(jìn)正交設(shè)計(jì)是否能夠提高算法的性能;最后，將改進(jìn)算法與多目標(biāo)優(yōu)化領(lǐng)域幾個(gè)經(jīng)典算法(NSGA-II、SPEA2等)進(jìn)行比較.

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

本文選用多目標(biāo)優(yōu)化領(lǐng)域經(jīng)常采用的測(cè)試函數(shù)作為測(cè)試基準(zhǔn)函數(shù)，包括ZDT［21］系列，WFG［22］系列和DTLZ［23］系列，其中ZDT系列是兩目標(biāo)測(cè)試函數(shù)，DTLZ系列是三目標(biāo)測(cè)試函數(shù).WFG系列可以按照需要進(jìn)行配置，使其具有不同的特性(凸、非凸、離散等).在本文中，使用的WFG系列都配置成為三目標(biāo)優(yōu)化函數(shù).

4.2性能指標(biāo)

本文選取HV與IGD兩個(gè)評(píng)價(jià)指標(biāo)對(duì)算法性能進(jìn)行綜合評(píng)價(jià)［24］，另外還選取GD指標(biāo)對(duì)收斂性進(jìn)行評(píng)價(jià).

(1)超體積(Hypervolume，HV［25］)

超體積是用來(lái)計(jì)算獲得的Pareto解集個(gè)體在目標(biāo)域所覆蓋的體積.這個(gè)指標(biāo)可以對(duì)收斂性和多樣性進(jìn)行綜合評(píng)價(jià)，其計(jì)算公式如式(2):

式中Q為所獲得的Pareto前端的個(gè)數(shù).對(duì)于這個(gè)Pareto前端中的每一個(gè)個(gè)體i，vi是由參考點(diǎn)W =(0，…，0)和成員i所形成的超體積，此指標(biāo)越大表明所得的Pareto解集越能寬廣地分布在其前端上.因此，其取值越大越好.

(2)反轉(zhuǎn)世代距離(Inverted Generational Distance，IGD)

IGD是收斂性評(píng)價(jià)方法GD的反轉(zhuǎn)，它計(jì)算Pareto面上均勻點(diǎn)到非支配解集上最小距離的平均值，其表達(dá)式如式(3)

其中，P*是覆蓋整個(gè)Pareto最優(yōu)面的均勻點(diǎn)，d(v，D)表示點(diǎn)v到非支配解集NDS中個(gè)體的最小歐氏距離，IGD能綜合評(píng)價(jià)解集的收斂性和多樣性.

(3)世代距離(Generational Distance，GD)

Van Veldhuizen和Lamont［26］提出這個(gè)指標(biāo)，用來(lái)評(píng)估得到的非支配解集與真實(shí)Pareto最優(yōu)解集之間的距離，是一種評(píng)價(jià)收斂性的指標(biāo).定義如式(4)

其中，n是非支配解集中非支配解的個(gè)數(shù)，di是在目標(biāo)空間中每個(gè)非支配解與離它最近的真實(shí)解的歐氏距離.當(dāng)GD =0時(shí)，說(shuō)明得到的所有非支配解都屬于真實(shí)Pareto最優(yōu)解集.為了得到可靠的結(jié)果，這些得到的非支配解在計(jì)算歐氏距離之前都進(jìn)行了歸一化處理.這個(gè)指標(biāo)的取值越小越好.

4.3改進(jìn)算法(ODMOCell)與MOCell、CellDE進(jìn)行比較

首先將改進(jìn)算法與MOCell以及CellDE進(jìn)行比較，以便確定引入正交設(shè)計(jì)可以提高算法的性能.選用的測(cè)試函數(shù)由ZDT系列、DTLZ系列和WFG系列組成，這些問(wèn)題的特征已經(jīng)足夠支持其得到的結(jié)論.算法的參數(shù)配置如表1所示.

按照表1中的參數(shù)配置好算法后，開始執(zhí)行算法.由于進(jìn)化算法在執(zhí)行后得到的結(jié)果有一定的概率性(多次運(yùn)行得到的結(jié)果可能不一樣)，因此，所有算法都獨(dú)立運(yùn)行50次，并對(duì)得到的結(jié)果進(jìn)行統(tǒng)計(jì)學(xué)分析.

實(shí)驗(yàn)結(jié)果如表2～4所示，為了方便查看，表中每個(gè)問(wèn)題的最優(yōu)值都用波浪線標(biāo)出，次優(yōu)值都用點(diǎn)劃線標(biāo)出.

表1　算法參數(shù)配置

表2　HV的平均值和標(biāo)準(zhǔn)差

表2是HV指標(biāo)的平均值和標(biāo)準(zhǔn)差，這個(gè)指標(biāo)是對(duì)算法的多樣性和收斂性進(jìn)行綜合評(píng)判，其取值越大越好.從表2中可以直觀的看出，在21個(gè)測(cè)試問(wèn)題中，ODMOCell得到了12個(gè)問(wèn)題的最優(yōu)值，CellDE得到了6個(gè)問(wèn)題的最優(yōu)值而MOCell只得到了3個(gè)問(wèn)題的最優(yōu)值.在這個(gè)指標(biāo)中，ODMOCell具有明顯的優(yōu)勢(shì).對(duì)表2的結(jié)果做更細(xì)致的分析，在兩目標(biāo)測(cè)試問(wèn)題ZDT系列上，ODMOCell得到了4個(gè)最優(yōu)值，MOCell得到了1個(gè)最優(yōu)值而CellDE一個(gè)最優(yōu)值也沒(méi)有得到，表明在ZDT系列問(wèn)題上，ODMOCell具有顯著優(yōu)勢(shì);在三目標(biāo)測(cè)試問(wèn)題WFG系列上，ODMOCell得到了4個(gè)問(wèn)題的最優(yōu)值，CellDE得到了4個(gè)問(wèn)題的最優(yōu)值而MOCell只得到了1個(gè)最優(yōu)值，這說(shuō)明在WFG系列問(wèn)題上，改進(jìn)的算法性能與CellDE差別不大，但是與MOCell相比，有顯著優(yōu)勢(shì);在三目標(biāo)測(cè)試問(wèn)題DTLZ系列上，ODMOCell得到了4個(gè)最優(yōu)值和3個(gè)次優(yōu)值，CellDE得到了2個(gè)最優(yōu)值和2個(gè)次優(yōu)值而MOCell只得到了1個(gè)最優(yōu)值和2個(gè)次優(yōu)值，說(shuō)明在解決DTLZ系列問(wèn)題時(shí)，ODMOCell算法優(yōu)勢(shì)較明顯.

表3　GD的平均值和標(biāo)準(zhǔn)差

表3是GD指標(biāo)的平均值和標(biāo)準(zhǔn)差，從表中可以直觀的看出，在21個(gè)測(cè)試問(wèn)題中，ODMOCell得到了15個(gè)問(wèn)題的最優(yōu)值，MOCell和CellDE各得到了3個(gè)問(wèn)題的最優(yōu)值.在這個(gè)指標(biāo)上，改進(jìn)算法的優(yōu)勢(shì)較為明顯.對(duì)表3的結(jié)果做更細(xì)致的分析，在兩目標(biāo)測(cè)試問(wèn)題ZDT系列上，ODMOCell得到了4個(gè)最優(yōu)值，MOCell只得到了1個(gè)最優(yōu)值而CellDE一個(gè)問(wèn)題的最優(yōu)值都沒(méi)有得到，在這個(gè)問(wèn)題上，ODMOCell顯著勝出;在三目標(biāo)測(cè)試問(wèn)題WFG系列上，ODMOCell得到了5個(gè)最優(yōu)值和4個(gè)次優(yōu)值，CellDE得到了2個(gè)最優(yōu)值和0個(gè)次優(yōu)值而MOCell得到了2個(gè)最優(yōu)值和5個(gè)次優(yōu)值，這說(shuō)明在WFG系列問(wèn)題上，改進(jìn)的算法有顯著優(yōu)勢(shì);在三目標(biāo)測(cè)試問(wèn)題DTLZ系列上，ODMOCell得到了6個(gè)最優(yōu)值和1個(gè)次優(yōu)值，CellDE得到了1個(gè)最優(yōu)值和1個(gè)次優(yōu)值而MOCell得到了0個(gè)最優(yōu)值和5個(gè)次優(yōu)值，說(shuō)明在解決DTLZ系列問(wèn)題時(shí)，ODMOCell算法優(yōu)勢(shì)依然較顯著.

表4　IGD的平均值/標(biāo)準(zhǔn)差

表4是IGD指標(biāo)的平均值和標(biāo)準(zhǔn)差，從表中可以直觀的看出，在21個(gè)測(cè)試問(wèn)題中，ODMOCell得到了7個(gè)問(wèn)題的最優(yōu)值，MOCell和CellDE各得到了6個(gè)和8個(gè)問(wèn)題的最優(yōu)值.在這個(gè)指標(biāo)上，改進(jìn)算法的整體優(yōu)勢(shì)不是很明顯.但是，在三目標(biāo)測(cè)試問(wèn)題DTLZ系列上，ODMOCell得到了4個(gè)最優(yōu)值，CellDE得到了2個(gè)最優(yōu)值而MOCell得到了1個(gè)最優(yōu)值，說(shuō)明在解決DTLZ系列問(wèn)題時(shí)，ODMOCell算法優(yōu)勢(shì)依然較顯著.

綜合以上分析，我們可以得出結(jié)論，從總體上來(lái)看，改進(jìn)算法較其他兩個(gè)算法性能明顯得到了提高.雖然在解決WFG系列時(shí)，改進(jìn)算法的性能與CellDE相比，優(yōu)勢(shì)不是十分明顯.但是，在解決ZDT系列和三目標(biāo)優(yōu)化問(wèn)題DTLZ系列時(shí)，改進(jìn)算法的優(yōu)勢(shì)都比較顯著.這也說(shuō)明，本文引入正交設(shè)計(jì)思想，能夠在一定程度上提高算法性能.

4.4改進(jìn)算法(ODMOCell)與其他算法比較

為了清楚改進(jìn)算法與其他算法相比的競(jìng)爭(zhēng)性，將改進(jìn)算法與多目標(biāo)優(yōu)化領(lǐng)域的兩個(gè)經(jīng)典算法進(jìn)行比較，即與NSGA-II和SPEA2算法進(jìn)行比較.

NSGA-II算法是由Deb等提出來(lái)的，它是以個(gè)體的Pareto秩與擁擠距離作為密度評(píng)估指標(biāo).本文中，NSGA-II算法的參數(shù)配置如下，交叉概率為0.9，變異概率為1/n(n是決策變量的個(gè)數(shù))，交叉算子用的是SBX交叉，變異算子用的是多項(xiàng)式變異.種群大小設(shè)置為100，算法終止條件是35000次函數(shù)評(píng)價(jià).

SPEA2算法是由Zitler等人提出的，它是對(duì)SPEA的改進(jìn)版.SPEA算法存在如下缺陷:一是根據(jù)SPEA的適應(yīng)度賦值過(guò)程，被相同文檔個(gè)體支配的種群個(gè)體適應(yīng)度相同，這意味著當(dāng)外部文檔只包含一個(gè)成員時(shí)，無(wú)論種群個(gè)體之間是否存在支配關(guān)系，所有種群個(gè)體都具有相同的適應(yīng)度值，這種情況下SPEA與隨機(jī)搜索類似;二是聚類分析能夠減少非劣解集的大小，但它可能錯(cuò)誤的刪掉一些必須保存在非劣解集中的個(gè)體，影響算法的多樣性.針對(duì)SPEA的上述缺點(diǎn)，Zitler等在適應(yīng)度賦值、個(gè)體密度值計(jì)算方法和外部文檔維護(hù)三個(gè)方面對(duì)SPEA進(jìn)行了改進(jìn)，提出了SPEA2算法.本文中，SPEA2算法的參數(shù)配置如下，種群大小和外部文檔的大小都設(shè)置為100，其他參數(shù)與NSGA-II算法的參數(shù)相同.每種算法獨(dú)立運(yùn)行50次，實(shí)驗(yàn)結(jié)果如表5和表6所示，表格中每個(gè)問(wèn)題的最優(yōu)解都用波浪線標(biāo)出.

從表5可以看出，在HV指標(biāo)上改進(jìn)算法ODMOCell得到了12個(gè)問(wèn)題中的8個(gè)最優(yōu)值，SPEA2得到了12個(gè)問(wèn)題中的3個(gè)最優(yōu)值而NSGA-II只得到了1個(gè)最優(yōu)值.所以，就HV指標(biāo)而言，與其他兩個(gè)算法相比ODMOCell具有明顯優(yōu)勢(shì).在求解DTLZ系列問(wèn)題時(shí)，ODMOCell得到了7個(gè)問(wèn)題中的3個(gè)最優(yōu)值，SPEA2也得到了7個(gè)問(wèn)題中的3個(gè)最優(yōu)值，所以在求解DTLZ系列問(wèn)題時(shí)，這兩個(gè)算法的性能沒(méi)有顯著差異，但都比NSGA-II的性能要強(qiáng)，因?yàn)镹SGA-II只得到了7個(gè)問(wèn)題中的1個(gè)最優(yōu)值.

表5　HV的平均值/標(biāo)準(zhǔn)差

表6　GD的平均值/標(biāo)準(zhǔn)差

從表6可以看出，在GD指標(biāo)上ODMOCell得到了12個(gè)問(wèn)題中的11個(gè)最優(yōu)值，SPEA2得到了12個(gè)問(wèn)題中的1個(gè)最優(yōu)值，而NSGA-II一個(gè)最優(yōu)值都沒(méi)有得到.因此，ODMOCell在GD指標(biāo)上比其他兩個(gè)算法具有顯著優(yōu)勢(shì).

綜合以上分析我們可以得出結(jié)論，ODMOCell與NSGA-II、SPEA2相比，還是有較強(qiáng)的競(jìng)爭(zhēng)力.為了直觀的顯示出ODMOCell算法的性能，從50次運(yùn)行結(jié)果中挑出每個(gè)算法得到的較好結(jié)果，將其與問(wèn)題的真實(shí)Pareto前端畫在一個(gè)圖形中.由于數(shù)據(jù)量較大，這里只作出差異最為顯著的DTLZ6問(wèn)題的圖形.

圖2，圖3，圖4和圖5都是在50次運(yùn)行結(jié)果中找出的每個(gè)算法效果較好的數(shù)據(jù)作出的圖形，從圖中可以很直觀的看出MOCell、NSGA-II、SPEA2都收斂不到DTLZ6問(wèn)題的真實(shí)前端，只有ODMOCell收斂到了DTLZ6的真實(shí)前端，從圖形上還可以看出，改進(jìn)算法ODMOCell求出的非支配解沿著真實(shí)前端的分布非常均勻.其他問(wèn)題的圖形，在收斂性和均勻性上也存在一些差異，但是由于不是十分明顯，列出之后不易看出(從性能指標(biāo)的數(shù)值中可以看出)，另外限于篇幅，也不再一一列舉.

5　結(jié)語(yǔ)

MOCell在求解三目標(biāo)優(yōu)化問(wèn)題時(shí)存在一定的困難，即在求解DTLZ系列問(wèn)題時(shí)表現(xiàn)不是非常令人滿意.針對(duì)這一點(diǎn)，同時(shí)也為了進(jìn)一步提高算法的性能，本文引入正交設(shè)計(jì)的思想，利用正交表均衡分散的特點(diǎn)從父代個(gè)體構(gòu)造出多個(gè)子代個(gè)體，然后選取其中最優(yōu)的個(gè)體進(jìn)入下一代種群.在改進(jìn)的算法中，也使用了MOCell中鄰居的概念，這樣每個(gè)個(gè)體鄰居的重疊部分既使得算法能夠?qū)φ麄€(gè)解空間進(jìn)行全局搜索，又能控制住種群中較優(yōu)個(gè)體的擴(kuò)散速度，可以在一定程度上避免早熟問(wèn)題.用多目標(biāo)領(lǐng)域內(nèi)流行的測(cè)試問(wèn)題對(duì)算法性能進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在HV和GD指標(biāo)上都比文中的對(duì)比算法有較明顯的優(yōu)勢(shì)，說(shuō)明從收斂性和均勻性上綜合考察，改進(jìn)算法具有一定的競(jìng)爭(zhēng)力.特別的，從DTLZ系列問(wèn)題上來(lái)看，改進(jìn)算法也是有較好的性能表現(xiàn).后續(xù)工作將考慮把算法與實(shí)際問(wèn)題結(jié)合起來(lái)，擴(kuò)大其適用范圍，在實(shí)際問(wèn)題中對(duì)算法進(jìn)行應(yīng)用并改進(jìn).

參考文獻(xiàn)

［1］鞏敦衛(wèi)，季新芳，孫曉燕.基于集合的高維多目標(biāo)優(yōu)化問(wèn)題的進(jìn)化算法［J］.電子學(xué)報(bào)，2014，42(1):77 -83.Gong Dun-wei，Ji Xin-fang，Sun Xiao-yan.Solving many-objective optimization problems using set-based evolutionary algorithms［J］.Acta Electronica Sinica，2014，42(1):77 -83.(in Chinese)

［2］李坤，黎明，陳昊.進(jìn)化算法的困難性理論研究進(jìn)展［J］.電子學(xué)報(bào)，2014，42(2):383 -390.Li Kun，Li Ming，Chen Hao.Research progress of hardness theories on evolutionary algorithm［J］.Acta Electronica Sinica，2014，42(2):383 -390.(in Chinese)

［3］Deb K，Pratap A，Agarwal S，et al.A fast and elitist multiobjective genetic algorithm: NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6(2):182 -197.

［4］Knowles J，Corne D.The pareto archived evolution strategy: A newbaseline algorithmfor pareto multiobjective optimization ［A］.Proceedings of the 1999 Congress on Evolutionary Computation［C］.USA: IEEE，1999，98 -105.

［5］Bleuler S，Brack M，Thiele L，et al.Multiobjective genetic programming: Reducing bloat using SPEA2［A］.Proceedings of the 2001 Congress on Evolutionary Computation［C］.USA: IEEE，2001.536 -543.

［6］Zhang Q，Li H.MOEA/D: A multiobjective evolutionary algorithm based on decomposition［J］.IEEE Transactions on Evolutionary Computation，2007，11(6):712 -731.

［7］Nebro A J，Durillo J J，Luna F，et al.Mocell: A cellular genetic algorithm for multiobjective optimization［J］.International Journal of Intelligent Systems，2009，24(7):726 -746.

［8］Alba E，Dorronsoro B.The exploration/exploitation tradeoff indynamic cellular genetic algorithms［J］.IEEE Transactions on Evolutionary Computation，2005，9(2):126 -142.

［9］Kirley M.MEA: A metapopulation evolutionary algorithm for multi-objective optimisation problems［A］.Proceedings of the 2001 Congress on Evolutionary Computation［C］.USA: IEEE，2001.949 -956.

［10］Alba E，Dorronsoro B，Luna F，et al.A cellular multi-objective genetic algorithm for optimal broadcasting strategy in metropolitan MANETs［J］.Computer Communications，2007，30(4):685 -697.

［11］Dorronsoro B，Alba E，Giacobini M，et al.The influence of grid shape and asynchronicity on cellular evolutionary algorithms［A］.Proceedings of the Congress on Evolutionary Computation［C］.USA: IEEE，2004.2152 -2158.

［12］Durillo J J，Nebro A J，Luna F，et al.Solving three-objective optimization problems using a new hybrid cellular genetic algorithm［A］.Parallel Problem Solving from Nature PPSN X ［M］.Berlin Heidelberg: Springer，2008.661 -670.

［13］Al-Naqi A，Erdogan A T，Arslan T，et al.Balancing exploration and exploitation in an adaptive three-dimensional cellular genetic algorithm via a probabilistic selection operator［A］.Proceedings of the Conference on Adaptive Hardware and Systems(AHS)［C］.USA: IEEE，2010.258 -264.

［14］Gong W，Cai Z，Jiang L.Enhancing the performance of differential evolution using orthogonal design method［J］.Applied Mathematics and Computation，2008，206(1):56 -69.

［15］Leung Y W，Wang Y.An orthogonal genetic algorithm with quantization for global numerical optimization［J］.IEEE Transactions on Evolutionary Computation，2001，5(1): 41 -53.

［16］Zeng S Y，Kang L S，Ding L X.An orthogonal multi-objective evolutionary algorithmfor multi-objective optimization problems with constraints［J］.Evolutionary Computation，2004，12(1):77 -98.

［17］Zhang Q，Leung Y W.An orthogonal genetic algorithm for multimedia multicast routing［J］.IEEE Transactions on Evolutionary Computation，1999，3(1):53 -62.

［18］Wang Y，Liu H，Cai Z，et al.An orthogonal design based constrained evolutionary optimization algorithm［J］.Engineering Optimization，2007，39(6):715 -736.

［19］Wang Y，Dang C.An evolutionary algorithm for global optimization based on level-set evolution and Latin squares［J］.IEEE Transactions on Evolutionary Computation，2007，11(5):579 -595.

［20］Wang Y，Cai Z，Zhang Q.Enhancing the search ability of differential evolution through orthogonal crossover［J］.Information Sciences，2012，185(1):153 -177.

［21］Zitzler E，Deb K，Thiele L.Comparison of multiobjective evolutionary algorithms: Empirical results［J］.Evolutionary Computation，2000，8(2):173 -195.

［22］Huband S，Barone L，While L，et al.A scalable multi-objective test problem toolkit［A］.Evolutionary Multi-Criterion Optimization［M］.Berlin Heidelberg: Springer，2005.280 -295.

［23］Deb K，Thiele L，Laumanns M，et al.Scalable multi-objective optimization test problems［A］.Proceedings of the Congress on Evolutionary Computation［C］.Honolulu，USA: IEEE，2002.825 -830.

［24］李密青，鄭金華.一種多目標(biāo)進(jìn)化算法解集分布廣度評(píng)價(jià)方法［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34(4):647 -663.Li Mi-qing，Zheng Jin-hua.An indicator for assessing the spread of solutions inmulti-objective evolutionary algorithm ［J］.Chinese Journal of Computers，2011，34(4): 647 -663.(in Chinese)

［25］Zitzler E，Thiele L.Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach［J］.Evolutionary Computation，1999，3(4):257 -271.

［26］Van Veldhuizen D A，Lamont G B.Multiobjective Evolutionary Algorithm Research: A History and Analysis(Technical Report TR-98-03，Department of Electrical and Computer Engineering)［R］.Wright-Patterson AFB，Ohio: Graduate School of Engineering，Air Force Institute of Technology，1998.

張屹男，1976年12月出生，甘肅蘭州人，博士、副教授、碩士生導(dǎo)師、國(guó)家自然科學(xué)基金委機(jī)械學(xué)科評(píng)審專家.分別于2000年、2005年在中國(guó)科學(xué)技術(shù)大學(xué)獲工學(xué)學(xué)士學(xué)位和工學(xué)博士學(xué)位; 2006年至2008年在中國(guó)科學(xué)技術(shù)大學(xué)工程學(xué)院力學(xué)博士后流動(dòng)站從事博士后研究，主要研究方向?yàn)闄C(jī)電系統(tǒng)現(xiàn)代設(shè)計(jì)方法、智能計(jì)算等.E-mail: jxzhangyi1976@126.com

萬(wàn)興余男，1988年12月出生，湖北黃岡人，2012年獲三峽大學(xué)工學(xué)學(xué)士學(xué)位，現(xiàn)為三峽大學(xué)機(jī)械電子工程碩士研究生，主要從事多目標(biāo)優(yōu)化方面的研究.

E-mail: wanxingyuhui@163.com

Cellular Genetic Algorithm for Multiobjective Optimization Based on Orthogonal Design

ZHANG Yi，WAN Xing-yu，ZHENG Xiao-dong，SUN Li-li
(College of Mechanical and Power Engineering，China Three Gorges University，Yichang，Hubei 443002，China)

Abstract:Multi-objective cellular genetic algorithm has proven to be effective in solving bi-objective MOPs.However，preliminary experiments have revealed that it has difficulties when dealing with three-objective MOPs(the DTLZ problem family).In order to enhance the performance，the orthogonal design idea is introduced and a new cellular genetic algorithm called cellular genetic algorithm for multi-objective optimization based on orthogonal design is proposed.In the progress of iteration of improved algorithm，the parent individuals are divided into many segments，and then several offsprings are produced by recombining the segments according to the orthogonal table，finally，choose the individuals which have better fitness value from the offsprings to the next population.The experiments show that the performance is improved after introducing the orthogonal design.Compared with several state-of-the-art multi-objective metaheuristics，the obtained results show that the improved algorithm is competitive for DTLZ problem family，too.

Key words:multi-objective; cellular genetic algorithm; orthogonal design; function optimization

作者簡(jiǎn)介

基金項(xiàng)目:國(guó)家自然科學(xué)基金(No.51275274);三峽大學(xué)研究生科研創(chuàng)新基金(No.2013CX029)

收稿日期:2014-04-23;修回日期: 2014-07-21;責(zé)任編輯:孫瑤

DOI:電子學(xué)報(bào)URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.013

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

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：0372-2112(2016)01-0087-08