基于多策略差分進(jìn)化的元胞多目標(biāo)遺傳算法

詹 騰，張 屹，朱大林，劉 錚，鄭小東

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

0 引言

科學(xué)研究和工程實(shí)踐中存在大量的多目標(biāo)優(yōu)化問題，如生產(chǎn)調(diào)度、車間布局、自動(dòng)化控制、機(jī)械優(yōu)化設(shè)計(jì)、物流運(yùn)輸?shù)?，都需要同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化。在多目標(biāo)優(yōu)化問題中，通常各個(gè)目標(biāo)之間通過決策變量相互制約，對(duì)其中某一個(gè)目標(biāo)性能的優(yōu)化必然以其他目標(biāo)為代價(jià)，因此解的方案不是唯一的，而是存在一組非劣解（非支配解），稱為Pareto最優(yōu)解集。求解多目標(biāo)優(yōu)化問題的關(guān)鍵是使求得的近似Pareto最優(yōu)解與真實(shí)的Pareto最優(yōu)解集盡可能接近，并且具有較好的分布性。多目標(biāo)進(jìn)化算法已被證明是解決多目標(biāo)優(yōu)化問題的一類有效方法。迄今為止，國際上涌現(xiàn)出許多經(jīng)典的多目標(biāo)進(jìn)化算法，如非支 配 排 序 遺 傳 算 法［1］（Non－dominated Sorting genetic algorithm，NSGA－Ⅱ）、改進(jìn)的強(qiáng)度Pareto進(jìn) 化 算 法［2］（Strength Pareto Evolutionary Algorithm 2，SPEA2）和元胞多目標(biāo)遺傳算法［3］（Cellular Genetic Algorithm for Multi－objective Optimization，MOCell）等。

差分進(jìn)化（Differential Evolution，DE）算法［4］是一種隨機(jī)并行的全局搜索算法，具有簡單易用、穩(wěn)健性高和全局尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)，已在單目標(biāo)領(lǐng)域得到廣泛應(yīng)用。近年來，許多學(xué)者將DE算法引入多目標(biāo)問題領(lǐng)域，其中典型算法有非支配排序的差分進(jìn)化算法［5］（Non－dominated Sorting Differential Evolution，NSDE）、混合元胞遺傳算法［6］（Cell－DE）、差分元胞遺傳算法［7］（DECell）和基于分解機(jī)制的 多 目 標(biāo) 進(jìn) 化 算 法［8］（Multi－Objective Evolutionary Algorithm based on Decomposition，MOEA/D）等。NSDE算法利用DE進(jìn)化算子代替NSGA－Ⅱ中的交叉和變異算子，在解決旋轉(zhuǎn)多目標(biāo)問題時(shí)效果較好；CellDE和DECell算法都以MOCell算法為基礎(chǔ)，融入GDE3［9］中DE進(jìn)化的選擇算子，其中CellDE是用DE進(jìn)化的選擇算子替換交叉、變異算子，CellDE在解決3目標(biāo)問題時(shí)有不錯(cuò)的效果，DECell主要針對(duì)實(shí)際的車間布局優(yōu)化問題，使用DE進(jìn)化的選擇算子和換位變異算子，結(jié)果表明DECell在解決車間布局問題時(shí)有較好的效果。MOEA/D算法是基于一種分解機(jī)制的多目標(biāo)進(jìn)化算法，它使用一種混合DE進(jìn)化的變異作用于鄰居個(gè)體，該算法多樣性好、費(fèi)時(shí)少，但是必須已知問題的Pareto沿界面的形狀。

盡管上述MOEAs引用DE策略在解決多目標(biāo)優(yōu)化問題中取得了不同程度的效果，但是沒有具體分析DE策略對(duì)算法的實(shí)際影響和不同DE策略之間的優(yōu)劣，僅用DE策略來替換原始的交叉、變異算子。因此，本文提出一種基于多策略的差分進(jìn)化的元胞多目標(biāo)遺傳算法（Cellular genetic algorithm based on Multi－strategy Differential Evolution for multi－objective optimization，MDECell）。該算法結(jié)合元胞模型的特點(diǎn)，分析不同的DE進(jìn)化模式的優(yōu)劣，提出了使用三種不同的DE進(jìn)化模式協(xié)同進(jìn)化的選擇算子，而且在基于經(jīng)典的元胞多目標(biāo)遺傳算法MOCell的基礎(chǔ)上改進(jìn)了擁擠距離評(píng)估方法和替換策略。為驗(yàn)證該算法解決高維復(fù)雜多目標(biāo)優(yōu)化問題的多樣性和收斂性性能，使用ZDT和DTLZ系列的12個(gè)標(biāo)準(zhǔn)測試函數(shù)對(duì)算法進(jìn)行了全面的性能測試，并與目前性能優(yōu)異的NSGA－Ⅱ，MOCell和CellDE三個(gè)算法進(jìn)行了對(duì)比分析。

1 多策略差分進(jìn)化的元胞多目標(biāo)遺傳算法

元胞遺傳算法是將元胞自動(dòng)機(jī)的作用機(jī)理和遺傳算法的基本理論有機(jī)結(jié)合的一種算法，其特點(diǎn)在于將種群中的每個(gè)個(gè)體分布于一個(gè)二維拓?fù)浣Y(jié)構(gòu)中，如圖1所示，每個(gè)個(gè)體擁有相同的鄰居數(shù)，且每個(gè)個(gè)體只能與其規(guī)定的鄰居個(gè)體進(jìn)行遺傳操作。遺傳操作限制在鄰域范圍內(nèi)進(jìn)行，在一定程度上降低了選擇壓力。

元胞多目標(biāo)遺傳算法MOCell（如圖2a）在基于元胞遺傳算法的大框架下，加入了多目標(biāo)進(jìn)化理論和策略。對(duì)于MOCell，總體而言，雖然其多樣性和收斂性均優(yōu)于NSGA－Ⅱ和SPEA2，但是仍存在改進(jìn)的空間，尤其在求解高維多目標(biāo)的情況下，當(dāng)目標(biāo)數(shù)大于等于3時(shí)，它在收斂性和多樣性測試上的求解效果仍不理想，會(huì)出現(xiàn)早熟收斂和解的分布性差等問題。對(duì)于CellDE［6］，由于加入了DE進(jìn)化的選擇算子，在解決三目標(biāo)問題時(shí)有較好的效果，這說明DE進(jìn)化策略能夠提高算法的性能，但CellDE在求解某些函數(shù)時(shí)效果仍然不佳。算法使用超體積（Hypervolume，HV）指標(biāo)來評(píng)估算法的多樣性，但由于HV指標(biāo)是一個(gè)綜合的性能指標(biāo)，不能完全描述算法的多樣性能優(yōu)劣?；诖耍琈DECell算法（如圖2b）針對(duì)DE進(jìn)化策略對(duì)多目標(biāo)求解的優(yōu)勢，分析不同差分進(jìn)化的特點(diǎn)，提出一種多進(jìn)化模式協(xié)同配合的選擇算子。對(duì)于算子中父代個(gè)體的選擇機(jī)制，根據(jù)不同策略的需求進(jìn)行動(dòng)態(tài)調(diào)整。同時(shí)，針對(duì)MOCell算法模型進(jìn)行相應(yīng)的改進(jìn)，提出一種新的擁擠距離評(píng)估方法和替換策略，從而在整體上提高了算法的求解性能。

1．1 多策略差分進(jìn)化的選擇算子

文獻(xiàn)［10－13］中應(yīng)用多策略對(duì)單目標(biāo)問題進(jìn)行求解的結(jié)果較好，但目前還未發(fā)現(xiàn)將該策略應(yīng)用到多目標(biāo)問題上的文獻(xiàn)，本文對(duì)此做了嘗試且獲得了較好的效果。DE存在多種進(jìn)化模式，其一般表示形式為DE/x/y/z。其中：x表示差分算子的基準(zhǔn)個(gè)體的選擇，一般有隨機(jī)選?。╮and）和當(dāng)前種群最優(yōu)個(gè)體選取（best）兩種；y表示參與重組的差異個(gè)體的選擇個(gè)數(shù)；z表示重組選擇的方式。下面給出5種常見的DE進(jìn)化模式及其重組公式：

（1）DE/rand/1/bin模式：Vi，G＝Xri1，G＋F（Xri2，G－Xri3，G）；

（2）DE/rand/2/bin模式：Vi，G＝Xri1，G＋F（Xri2，G－Xri3，G）＋F（Xri4，G－Xri5，G）；

（3）DE/best/1/bin 模 式：Vi，G＝ Xbest，G＋ F（Xri1，G－Xri2，G）；

（4）DE/best/2/bin 模 式：Vi，G＝ Xbest，G＋ F（Xri1，G－Xri2，G）＋F（Xri3，G－Xri4，G）；

（5）DE/rand－to－best/1/bin模式：Vi，G＝Xi，G＋F（Xbest，G－Xi，G）＋F（Xri1，G－Xri2，G）。

其中：Vi，G表示基準(zhǔn)個(gè)體i；G 表示進(jìn)化代數(shù)；Xbest，G表示當(dāng)代 最 優(yōu)個(gè)體；Xr1，G，Xr2，G，Xr3，G，Xr4，G，Xr5，G和Xi，G表示隨機(jī)選擇的個(gè)體；F表示差分控制參數(shù)。

上述5種進(jìn)化模式各具特點(diǎn)，對(duì)各種不同進(jìn)化模式分析如下：

DE/rand/1/bin模式和DE/rand/2/bin模式具有很好的全局探索能力，容易跳出局部最優(yōu)解，但是收斂速度較慢。根據(jù)這兩種進(jìn)化模式，在算法初期，種群分布的區(qū)域較為寬廣，個(gè)體之間的差異大，則個(gè)體之間的差分向量值較大，對(duì)個(gè)體Xri1，G的擾動(dòng)也較大，從而實(shí)現(xiàn)算法的全局搜索；而在進(jìn)化后期，種群中的個(gè)體大多分布于最優(yōu)個(gè)體附近，差分向量之間的差值較小，對(duì)個(gè)體Xri1，G有微調(diào)作用，可實(shí)現(xiàn)算法的局部尋優(yōu)，但是進(jìn)化過程中沒有很好地引導(dǎo)進(jìn)化的收斂方向，從而導(dǎo)致收斂速度較慢。

DE/best/1/bin模式和 DE/best/2/bin模式的主要特點(diǎn)是收斂速度快，但是其全局探索能力相對(duì)較弱，易陷入局部收斂。根據(jù)這兩種進(jìn)化模式，在進(jìn)化初期以Xbest，G為基準(zhǔn)個(gè)體，對(duì)算法的收斂方向有很好的導(dǎo)向作用，從而有利于算法向Pareto的前端靠近，但會(huì)導(dǎo)致全局搜索能力下降；而在進(jìn)化后期，由于個(gè)體之間的差異變小，使得算法局部尋優(yōu)效果不佳，易陷入局部收斂。

DE/rand－to－best/1/bin模 式 的 全 局 探 索 和 局部尋優(yōu)相對(duì)保持平衡，但是其魯棒性相對(duì)較差。這種進(jìn)化模式是前兩類進(jìn)化模式的綜合體，可在一定程度上維持算法多樣性和收斂性之間的平衡，但是進(jìn)化模式不夠穩(wěn)定。

鑒于上述各種DE進(jìn)化策略各自的優(yōu)勢和不足，不能一概而論地說哪種進(jìn)化模式更優(yōu)秀，哪種進(jìn)化模式相對(duì)較弱，但是各類進(jìn)化模式存在共同的特性，即采取的重組方式都是基準(zhǔn)個(gè)體與其差異個(gè)體之間的線性組合。本文將 DE/rand/1/bin，DE/best/1/bin和 DE/rand－to－best/1/bin三種進(jìn)化策略引入交叉算子中，讓三種進(jìn)化策略相互配合、相互促進(jìn)、協(xié)同進(jìn)化。

結(jié)合元胞空間結(jié)構(gòu)的特點(diǎn)和元胞遺傳算法的特性，在選擇進(jìn)化個(gè)體時(shí)也有其特點(diǎn)。本文采用八鄰居結(jié)構(gòu)，分別對(duì)三種模式所需個(gè)體進(jìn)行選擇（如圖2b）。對(duì)于 DE/rand/1/bin進(jìn)化模式，必須選擇三個(gè)個(gè)體，分別為一個(gè)中心元胞個(gè)體和兩個(gè)鄰居個(gè)體；對(duì)于DE/best/1/bin進(jìn)化模式，三個(gè)個(gè)體的來源分別為：兩個(gè)差分個(gè)體來自鄰居個(gè)體，對(duì)于Xbest，G，如果外部存檔為0，則從當(dāng)前種群中隨機(jī)選擇一個(gè)Pareto等級(jí)為0的個(gè)體，否則從外部存檔中隨機(jī)選擇一個(gè)個(gè)體；對(duì)于 DE/rand－to－best/1/bin進(jìn)化模式，四個(gè)個(gè)體分別為：一個(gè)中心個(gè)體、兩個(gè)鄰居個(gè)體和最優(yōu)個(gè)體，其選擇同DE/best/1/bin。

這種多策略進(jìn)化差分的選擇算子，使每種進(jìn)化策略都有相同的概率產(chǎn)生子代個(gè)體，而且在執(zhí)行某一進(jìn)化策略時(shí)必然存在其他進(jìn)化策略生成的個(gè)體參與進(jìn)化，因此MDECell具有隱式的多種群特性。再者，由于每種進(jìn)化策略參與進(jìn)化的概率相同，MDECell算法在時(shí)間復(fù)雜度上與一般的DE算法相同。

MDECell采用的多策略差分進(jìn)化的交叉算子的偽代碼如下：

Number＝rand［0，3］ //三種進(jìn)化模式的代號(hào)

jrand＝floor（randi［0，1］＊D）＋1

for j＝＝1to D //每個(gè)個(gè)體中的決策變量進(jìn)行差分進(jìn)化

if（randj［0，1］＜CRVj＝j(luò)rand）then

if（Number＝1）then

Vi［j］，G＝Xr1［j］，G＋F（Xr2［j］，G－Xr3［j］，G） //DE/rand/1/bin模式

else if（Number＝2）then

Vi［j］，G ＝Xbest［j］，G ＋F（Xr1［j］，G －Xr2［j］，G）//DE/best /1/bin模式

else if（Number＝3）then

根據(jù)本次紅外相機(jī)的調(diào)查數(shù)據(jù)，初步獲得廣東省青云山森林動(dòng)態(tài)監(jiān)測樣地地面活動(dòng)獸類和林下活動(dòng)鳥類的物種名錄，對(duì)部分鳥獸(如白鷴、野豬等)種類的種群狀況也有所了解，為調(diào)查廣東省青云山自然保護(hù)區(qū)現(xiàn)有的陸生脊椎動(dòng)物多樣性資源積累了基礎(chǔ)數(shù)據(jù)。目前，已確認(rèn)的鳥類和獸類共計(jì)18種，隸屬于5目9科。

Vi［j］，G＝Xi［j］，G ＋F（Xbest［j］，G －Xi，G）＋F（Xr1［j］G －Xr2［j］，G）//DE/best－to－rand/1/bin模式

end if

else

Vi［j］，G＝Xi［j］，G

end if

end for

1．2 基于熵的擁擠距離評(píng)估方法

在不斷進(jìn)化的過程中，為了維持外部檔案的非支配解的多樣性，合理的精英個(gè)體修剪策略尤為重要。一些學(xué)者對(duì)修剪策略進(jìn)行了探討。對(duì)于SPEA2，采用密度評(píng)估策略；對(duì)于具有相同適應(yīng)度值的個(gè)體，采用第k個(gè)最近個(gè)體的密度來進(jìn)行區(qū)分，該策略耗時(shí)相對(duì)較大。PEAS2采用自適應(yīng)網(wǎng)格法對(duì)外部種群進(jìn)行維護(hù)，在基于區(qū)域的選擇中，選擇單元是一個(gè)超級(jí)盒（hyperbox）而不是個(gè)體，這種方法減少了計(jì)算費(fèi)用，但是需要對(duì)超級(jí)盒的大小進(jìn)行控制。MOCell采用的是Pareto非支配等級(jí)排序和局部擁擠距離密度估計(jì)的精英策略，該方法不能完全真實(shí)地反映個(gè)體的擁擠程度。例如使用MOCell的擁擠距離密度評(píng)估策略，如圖3所示，令a為單位長度，dm1和dn1為A點(diǎn)相鄰兩個(gè)個(gè)體之間在f1目標(biāo)值的差值，dn2和dm2為A點(diǎn)相鄰兩個(gè)個(gè)體之間在f2目標(biāo)值的差值，則A點(diǎn)的擁擠距離為13a，同理B點(diǎn)為10a，即A點(diǎn)的擁擠距離比B點(diǎn)大。但是由圖3可知B點(diǎn)的分布性比A點(diǎn)好。

針對(duì)上述問題，本文采用基于熵的擁擠距離評(píng)估策略［14］。其定義如下：

根據(jù)式（5）計(jì)算A、B和C點(diǎn)的擁擠距離分別為：CEA＝8．041 9、CEB＝10和CEC＝3。結(jié)果表明，式（5）改進(jìn)的擁擠距離計(jì)算方法符合實(shí)際情況，能夠更真實(shí)地反映Pareto解集中每個(gè)個(gè)體的擁擠距離，該方法能在修剪外部存檔和選擇個(gè)體時(shí)提供更加準(zhǔn)確的信息，同時(shí)有利于Pareto解集保持良好的分布性。

1．3 替換策略的改進(jìn)

元胞遺傳算法中的替換策略有利于種群沿著好的方向進(jìn)化，特別是在使用異步更新策略時(shí)，對(duì)算法的收斂性有一定程度的影響［15］。為了進(jìn)一步加強(qiáng)算法的收斂性，MDECell算法對(duì)子代產(chǎn)生的優(yōu)良個(gè)體的替換策略做了進(jìn)一步改良，基本內(nèi)容如下：

對(duì)于MDECell產(chǎn)生的最新子代個(gè)體，如果其支配父代中心元胞個(gè)體或者子代個(gè)體與父代個(gè)體都處于非支配關(guān)系，且子代個(gè)體的熵?fù)頂D距離大于父代中心元胞個(gè)體，則用子代替換父代個(gè)體，并將子代加入外部存檔。如果子代個(gè)體不滿足替換父代中心元胞個(gè)體的條件，則將子代加入父代鄰居中，組成一個(gè)小種群。小種群按照支配關(guān)系和熵?fù)頂D距離進(jìn)行排列，如果最差個(gè)體為子代個(gè)體，則子代個(gè)體替換掉種群中的最差個(gè)體并加入外部存檔中進(jìn)行篩選，否則用最優(yōu)個(gè)體替換掉鄰居中的最差個(gè)體，并將最優(yōu)個(gè)體加入外部存檔。

該替換策略增加了優(yōu)秀個(gè)體在整個(gè)種群中的擴(kuò)散，有利于提高算法的收斂性。由于差分策略和基于熵的擁擠距離評(píng)估方法有利于提高算法的多樣性，而替換策略在一定程度上增強(qiáng)了算法的收斂性，使算法的選擇壓力保持在一個(gè)相對(duì)合理的水平，從而提高了算法的整體性能。

1．4 MDECell算法流程

綜合1．1節(jié)～1．3節(jié)在經(jīng)典的元胞遺傳算法上的三方面改進(jìn)，MDECell算法流程如下：

步驟1 在決策變量空間隨機(jī)生成初始化種群P，將種群分布于一個(gè)二維的網(wǎng)格結(jié)構(gòu)中，每個(gè)個(gè)體都有對(duì)應(yīng)的鄰居（本文選用Moore型八鄰居結(jié)構(gòu)）。

步驟2 根據(jù)不同的DE進(jìn)化模式，選擇不同的個(gè)體進(jìn)行交叉操作，最后執(zhí)行多項(xiàng)式變異操作，產(chǎn)生子代。對(duì)子代個(gè)體執(zhí)行改進(jìn)的替換策略。對(duì)于外部存檔中的個(gè)體按熵?fù)頂D距離進(jìn)行排序，若其非支配個(gè)體超過了規(guī)定的容量，則刪除其中熵?fù)頂D距離最小的個(gè)體。

步驟3 隨機(jī)選取外部存檔中的一部分個(gè)體，替換掉原始種群中的個(gè)體。

步驟4 判斷是否滿足終止條件，若滿足則輸出非支配解集，否則轉(zhuǎn)步驟2。

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

為驗(yàn)證MDECell算法在多目標(biāo)優(yōu)化問題上的求解性能，將它與 NSGA－Ⅱ［1］，MOCell［3］和 Cell－DE［6］三種目前比較優(yōu)異的 MOEAs算法在求解二目標(biāo)和三目標(biāo)優(yōu)化問題上進(jìn)行對(duì)比實(shí)驗(yàn)。本文選用二目標(biāo)ZDT［16］和三目標(biāo) DTLZ［17］基準(zhǔn)函數(shù)進(jìn)行性能測試。所有實(shí)驗(yàn)在硬件配置為AMD CPU 3．00 GHz、內(nèi)存2．00GB的計(jì)算機(jī)上進(jìn)行，程序采用Java語言編寫，其中對(duì)比的算法NSGA－Ⅱ、MOCell和CellDE的源程序來自文獻(xiàn)［18］。

ZDT系列測試函數(shù)是二目標(biāo)優(yōu)化問題，其Pareto前端已知。其中ZDT1的Pareto前端為凸曲面；ZDT2為非凸曲面；ZDT3為非連續(xù)函數(shù)；ZDT4含有219個(gè)局部Pareto前端，可以測試算法解決多峰問題的能力，跳出局部最優(yōu)解的能力；ZDT6的整個(gè)搜索空間具有非均勻的分布，可以用來衡量算法維持群體多樣性的能力。DTLZ系列測試函數(shù)為維數(shù)可擴(kuò)展的高維多目標(biāo)優(yōu)化問題，且求解難度隨著維數(shù)的增加而增大，在此將其維數(shù)擴(kuò)展為三。

2．1 算法性能評(píng)價(jià)標(biāo)準(zhǔn)

采用覆蓋性指標(biāo) HV、分布指標(biāo)（Spread）和收斂性指標(biāo)（Inverted Generational Distance，IGD）三個(gè)性能指標(biāo)進(jìn)行度量。

（1）覆蓋性指標(biāo)HV

超體積用來計(jì)算獲得的Pareto解集個(gè)體在目標(biāo)域所覆蓋的體積。其計(jì)算公式如下：式中Q為所獲得的Pareto前端的個(gè)數(shù)。對(duì)于這個(gè)Pareto前端中的每一個(gè)體i，vi是由參考點(diǎn)w＝（0，…，0）和成員i所形成的超體積，該指標(biāo)越大，表明所得的Pareto解集越能寬廣地覆蓋在其前端上。

（2）分布指標(biāo)Δ（Spread）

Deb提出的分布指標(biāo)用來衡量所得的Pareto前端解集的分布情況。其計(jì)算公式如下：式中：di為所得Pareto前端上每兩個(gè)連續(xù)解的歐氏距離為這些歐氏距離的平均距離，df和dl分別為所得Pareto前端的邊界點(diǎn)與Pareto最優(yōu)邊界點(diǎn)的歐氏距離，n為所得Pareto前端個(gè)體的數(shù)目。對(duì)于分布均勻的解來說，該指標(biāo)取0。因此，該指標(biāo)的值越小，說明分布程度越均勻。

（3）收斂性指標(biāo)（IGD）

IGD為收斂性評(píng)價(jià)方法GD的反轉(zhuǎn)，用來計(jì)算Pareto面上的均勻點(diǎn)到非支配解集上最小距離的平均值，其評(píng)價(jià)函數(shù)為式中di為真實(shí)Pareto前端中的向量與目標(biāo)空間中每個(gè)向量之間的最短距離。IGD不僅能評(píng)價(jià)解集的收斂性，也能評(píng)價(jià)其均勻性和廣泛性。IGD越小，說明收斂性越好。

2．2 算法性能測試、對(duì)比與分析

MDECell，NSGA－Ⅱ［1］和 MOCell［3］算 法 的 參數(shù)設(shè)置均采用實(shí)數(shù)制進(jìn)行編碼、多項(xiàng)式變異。NSGA－Ⅱ和MOCell采用模擬二進(jìn)制交叉（Simulated Binary Crossover，SBX）［19］算子；CellDE［6］算法采用DE選擇算子，其CR＝0．1，F(xiàn)＝0．5；MDECell采用多策略差分進(jìn)化的選擇算子，DE進(jìn)化參數(shù)設(shè)置為：CR＝0．5，F(xiàn)＝0．5。種群規(guī)模均為100，最大進(jìn)化代數(shù)為25 000，交叉概率為0．9，變異概率為1/len，len為變量維數(shù)。外部存檔大小設(shè)置為100，反饋個(gè)體數(shù)目設(shè)置為20。將這四種算法分布對(duì)測試函數(shù)進(jìn)行50次獨(dú)立運(yùn)行計(jì)算，統(tǒng)計(jì)HV、Δ和IGD的平均值（括號(hào)外）及標(biāo)準(zhǔn)差（括號(hào)內(nèi)）。對(duì)于計(jì)算的結(jié)果，最優(yōu)值使用深灰色標(biāo)識(shí)，次優(yōu)值使用淺灰色標(biāo)識(shí)。

從表1中的HV性能指標(biāo)可以看出：12個(gè)測試函數(shù)中MDECell共求得6個(gè)最優(yōu)值、4個(gè)次優(yōu)值；NSGA－Ⅱ獲得6個(gè)最優(yōu)值、3個(gè)次優(yōu)值；CellDE獲得3個(gè)次優(yōu)值；MOCell表現(xiàn)最差，僅獲得1個(gè)次優(yōu)值。實(shí)驗(yàn)數(shù)據(jù)說明，MDECell與NSGA－Ⅱ在解的覆蓋率方面性能相當(dāng)，但是遠(yuǎn)勝于MOCell和Cell－DE算法。NSGA－Ⅱ算法在求解ZDT系列類函數(shù)時(shí)較有優(yōu)勢，而MDECell在求解DTLZ系列類函數(shù)時(shí)相對(duì)更有優(yōu)勢。

從表2中的Δ性能指標(biāo)可知，MDECell獲得最優(yōu)值的比例為9/12，次優(yōu)值為3/12，相對(duì)應(yīng)的Cell－DE獲得3個(gè)最優(yōu)值、3個(gè)次優(yōu)值，MOCell獲得5個(gè)次優(yōu)值，NSGA－Ⅱ僅得到一個(gè)次優(yōu)值。MOCell在ZDT系列函數(shù)上的多樣性表現(xiàn)較好，CellDE則在DTLZ系列函數(shù)上更有優(yōu)勢，而MDECell整體的多樣性最優(yōu)。促使MDECell算法多樣性較好的主要原因有：①含有具有元胞種群結(jié)構(gòu)的算法［20］，存在一種隱性遷移機(jī)制，而且算法的選擇壓力相對(duì)較低，有利于提高其多樣性。由計(jì)算結(jié)果可知，含有元胞拓?fù)浣Y(jié)構(gòu)的算法，其多樣性性能整體優(yōu)于隨機(jī)交配種群的算法。②大量研究和實(shí)驗(yàn)發(fā)現(xiàn)，差分進(jìn)化算法在維護(hù)種群多樣性和搜索能力方面功能較強(qiáng)［21］。由數(shù)據(jù)可知在三目標(biāo)函數(shù)上，加入差分策略的Cell－DE明顯存在優(yōu)勢，說明在解決高維問題上差分策略能夠提高種群的多樣性，采用三差分協(xié)同進(jìn)化策略的MDECell在多樣性方面更有優(yōu)勢。③使用基于熵的擁擠距離評(píng)估方法MDECell，相對(duì)于使用擁擠距離評(píng)估方法MOCell和NSGA－Ⅱ在保持種群多樣性上效果更好。由此說明，MDECell算法中種群的元胞拓?fù)浣Y(jié)構(gòu)、差分策略和基于熵的擁擠距離評(píng)估方法有助于提高算法的多樣性。

從表3的收斂性指標(biāo)可知：MDECell有很好的收斂性，其中最優(yōu)值數(shù)目達(dá)到9個(gè)、次優(yōu)值為1個(gè)；NSGA－Ⅱ最優(yōu)值為1個(gè)、次優(yōu)值為7個(gè)；MOCell和CellDE的最優(yōu)值和次優(yōu)值分別都為1個(gè)和2個(gè)。MDECell采用了三差分協(xié)同進(jìn)化策略，其中如第2、3策略“DE/best/1/bin”，“DE/rand－to－best/1/bin”有利于提高算法的收斂性，且改進(jìn)的替換原則更能在一定程度上加快優(yōu)秀解在種群的擴(kuò)散速度，提高算法的收斂性。

表1 HV性能指標(biāo)對(duì)比

續(xù)表1

表2 Δ性能指標(biāo)對(duì)比

表3 IGD性能指標(biāo)對(duì)比

由圖4可知，在解決ZDT3問題時(shí)，NSGA－Ⅱ和MDECell具有較好的收斂性和均勻性保持能力，而MOCell和CellDE則表現(xiàn)出相對(duì)較差的性能，NSGA－Ⅱ和MDECell表現(xiàn)出相近的實(shí)驗(yàn)結(jié)果。由圖5和圖6可知，在解決ZDT6和DTLZ6時(shí)，Cell－DE和MDECell的收斂性和均勻性保持較好，NS－GA－Ⅱ和MOCell在相同的評(píng)價(jià)次數(shù)下不能很好地收斂到最優(yōu)Pareto前沿附近，說明含有差分進(jìn)化策略的算法的收斂性和多樣性更好，且對(duì)比CellDE和MDECell的Pareto解集的分布性發(fā)現(xiàn)，MDECell的分布性更均勻。

由表1～表3以及圖4～圖6的結(jié)果對(duì)比可知，在二目標(biāo)測試函數(shù)ZDT和三目標(biāo)測試函數(shù)DTLZ的求解效果上，MDECell相對(duì)于NSGA－Ⅱ、MOCell和CellDE算法均具有明顯的優(yōu)勢，不僅能達(dá)到最好的收斂性和多樣性，還能獲得分布更均勻、覆蓋范圍更廣的近似Pareto最優(yōu)解集。

3 結(jié)束語

本文提出一種多策略差分進(jìn)化的元胞多目標(biāo)遺傳算法（MDECell）來求解高維復(fù)雜的多目標(biāo)優(yōu)化問題。該算法結(jié)合元胞模型定義了一種多策略差分協(xié)同進(jìn)化的選擇算子，并改進(jìn)了原有的擁擠距離評(píng)估方法和替換策略。通過與NSGA－Ⅱ、MOCell和CellDE的測試對(duì)比，該算法比上述算法在覆蓋性指標(biāo)（HV）方面有優(yōu)勢，尤其在收斂性指標(biāo)（IGD）、分布性指標(biāo)（Spread）上表現(xiàn)更優(yōu)異，是求解高維多目標(biāo)算法的有效方法。對(duì)于MDECell算法能否實(shí)現(xiàn)自適應(yīng)地分配各差分進(jìn)化模式，以及如何將其運(yùn)用至實(shí)際工程應(yīng)用中，將是下一步研究的方向。

［1］ DEB K，PRATAP A，MEYARIVAN T．A fast and elitist

multi－objective genetic algorithm：NSGA－Ⅱ［J］．IEEE Trans

actions on Evolutionary Computation，2002，6（2）：182－197．［2］ ZITZLER E，THIELE L．Multi－objective evolutionary algorithms：a comparative case study and the strength Pareto approach［J］．IEEE Transactions on Evolutionary Computation，1999，3（4）：257－271．

［3］ NEBRO A J，DURILLO J J，LUNA F，et al．MOCell：a cellu

lar genetic algorithm for multi－objective optimization［J］．Inter

national Journal of Intelligent Systems，2009，24（7）：726－746．［4］ BALDUZZI F，GIUA A，MENGA G．First－order hybrid petri nets：a model for optimization and control［J］．IEEE Transactions on Robotics and Automation，2000，16（4）：382－399．

［5］ IORIOA W，LI X．Solving rotated multi－objective optimization problems using differential evolution［J］．Lecture Notes in Computer Science，2005，3339：861－872．

［6］ DURILLO J J，NEBRO A J，LUNA F，et al．Solving threeobjective optimization problems using a new hybrid cellular genetic algorithm［J］．Lecture Notes in Computer Science，2008，5199：661－670．

［7］ ZHANG Yi，LU Chao，ZHANG Hu，et al．Workshop layout optimization based on differential cellular multi－objective genetic algorithm［J］Computer Integrated Manufacturing Systems，2013，19（4）：727－733（in Chinese）．［張 屹，盧 超，張

虎，等．基于差分元胞多目標(biāo)遺傳算法的車間布局優(yōu)化［J］．計(jì)算機(jī)集成制造系統(tǒng)，2013，19（4）：727－733．］

［8］ ZHANG Qingfu，LIU Wudong，TSAND E，et al．Expensive multi－objective optimization by MOEA/D with gaussian process model［J］．IEEE Transactions on Evolutionary Computation，2010，14（3）：456－474．

［9］ KUKKONEN S，LAMPINEN J．GDE3：the third evolution step of generalized differential evolution［C］//Proceedings of IEEE Congress on Evolutionary Computation（CEC 2005）．Washington，D．C．，USA：IEEE，2005：443－450．

［10］ QIN A K，SUGANTHAN P N．Self－adaptive differential evolution algorithm for numerical optimization［C］//Proceedings of IEEE Congress on Evolutionary Computation（CEC 2005）．Washington，D．C．，USA：IEEE，2005：1785－1791．

［11］ QIN A K，HUANG V L，SUSANTHAN P N．Self－adaptive differential evolution algorithm for constrained real－parameter optimization［C］//Proceedings of 2006IEEE Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE，2006：17－24．

［12］ QIN A K，HUANG V L，SUSANTHAN P N．Differential evolution algorithm with strategy adaptation for global numerical optimization［J］．IEEE Transactions on Evolutionary Computation，2009，13（2）：398－417．

［13］ HE Yichao，WANG Xizhao，LIU Kunqi，et al．Convergent analysis and algorithmic improvement of differential evolution［J］．Journal of Software，2010，21（5）：875－885（in Chinese）．［賀毅朝，王熙照，劉坤起，等．差分演化的收斂性分析與算法改進(jìn)［J］．軟件學(xué)報(bào)，2010，21（5）：875－885．］

［14］ WANG Yaonan，WU Lianghong，YUAN Xiaofeng．Multi－objective self－adaptive differential evolution with elitist archive and crowding entropy－based diversity measure［J］．Soft Compute，2010，14（3）：193－209．

［15］ NEBRO A J，DURILLO J J，LUNA F，et al．Design issues in a multi－objective cellular genetic algorithm［J］．Lecture Notes in Computer Science，2007，4403：126－140．

［16］ ZITZLER E，DEB K，THIELE L．Comparison of multi－objective evolutionary algorithms：empirical results［J］．Evolutionary Computation，2000，8（2）：173－195．

［17］ DEB K，THIELE L，LAUMANNS M．Scalable test problems for evolutionary multi－objective optimization［J］．Evolutionary Multi－objective Optimization，2005，5（2）：105－145．

［18］ DURILLO J J，NEBRO A J．jMetal：ajava framework for developing multi－objective optimization［J］．Advances in Engineering Software，2011，42（10）：760－771．

［19］ DEB K，AGRAWAL R B．Simulated binary crossover for continuous search space［J］．Complex Systems，1995，9（2）：115－148．

［20］ ALBA E，DORRONSORO B．Cellular genetic algorithms［M］．Berlin，Germany：Springer－Verlag，2008．

［21］ MENG Hongyun，ZHANG Xiaohua，LIU Sanyang．A differential evolution based on double population for constrained multi－objective optimization problem［J］．Chinese Journal of Computers，2008，31（2）：228－235（in Chinese）．［孟紅云，張小華，劉三陽．用于約束多目標(biāo)優(yōu)化問題的雙群體差分進(jìn)化算法［J］．計(jì)算機(jī)學(xué)報(bào)，2008，31（2）：228－235．］