王福才，周魯蘋

(魯東大學(xué)信息與電氣工程學(xué)院,山東煙臺(tái) 264001)

?

混合精英策略的元胞多目標(biāo)遺傳算法及其應(yīng)用

王福才，周魯蘋

(魯東大學(xué)信息與電氣工程學(xué)院,山東煙臺(tái) 264001)

摘要：為了提高Pareto解集的收斂性,平衡多目標(biāo)優(yōu)化的全局搜索和局部尋優(yōu)的能力，提出一種混合精英策略的元胞多目標(biāo)遺傳算法.該算法在分析元胞種群結(jié)構(gòu)的特點(diǎn)基礎(chǔ)上，融入一種混合精英策略，提高算法的收斂性能.為了更好的平衡算法的全局搜索和局部尋優(yōu)的能力，加入一種差分進(jìn)化交叉算子.通過與同類算法在21個(gè)基準(zhǔn)函數(shù)上對(duì)比實(shí)驗(yàn)，結(jié)果表明，引入混合精英策略和差分進(jìn)化策略能夠提高算法的性能，與其他優(yōu)秀算法進(jìn)行比較的結(jié)果說明，新算法有更好的收斂性和多樣性.工程實(shí)例求解結(jié)果表明了算法的工程可行性.

關(guān)鍵詞:多目標(biāo)；元胞遺傳算法；混合精英；差分進(jìn)化；函數(shù)優(yōu)化；桁架結(jié)構(gòu)

1引言

科學(xué)研究與工程領(lǐng)域中的優(yōu)化問題大都是多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problems,MOPs).為有效求解這類問題,人們提出了多目標(biāo)進(jìn)化算法(Multi-objective Evolutionary Algorithm,MOEA).過去的20年中，多目標(biāo)進(jìn)化算法在解決多目標(biāo)優(yōu)化問題上取得了長足發(fā)展，也涌現(xiàn)出了許多優(yōu)秀算法，主要有NSGA-II[1]、PAES[2]、SPEA2[3]、MOEA/D[4]和MOCell[5]等.西班牙學(xué)者Enrique Alba[6]將進(jìn)化算法按照種群結(jié)構(gòu)的分布方式，可以分為兩類，分別為單種群進(jìn)化算法和結(jié)構(gòu)化種群進(jìn)化算法，而上述優(yōu)秀算法中絕大多數(shù)屬于單種群進(jìn)化算法.

元胞遺傳算法是一種結(jié)構(gòu)化種群進(jìn)化算法，且已經(jīng)被證明在解決很多單目標(biāo)優(yōu)化問題時(shí)非常高效[7].Kirley M[8]提出了一種集合種群進(jìn)化算法(Metapopulation Evolutionary Algorithm,MEA)，該算法是以在種群中偶爾發(fā)生災(zāi)變機(jī)制為特色的元胞模型，當(dāng)災(zāi)變發(fā)生的時(shí)候，災(zāi)變區(qū)域的所有個(gè)體都會(huì)滅絕同時(shí)這個(gè)空的區(qū)域也會(huì)被其他個(gè)體占據(jù).魯宇明等人[9]將元胞自動(dòng)機(jī)的演化規(guī)則融合到元胞遺傳算法中，提出了一種具有演化規(guī)則的元胞遺傳算法.Enrique Alba等人[10]在解決城市移動(dòng)自組網(wǎng)廣播策略問題的過程中，提出了一種新型的多目標(biāo)元胞遺傳算法cMOGA，該算法一般被認(rèn)為是基于經(jīng)典元胞遺傳算法模型的第一個(gè)多目標(biāo)元胞遺傳算法.在cMOGA的基礎(chǔ)上，為了更加適應(yīng)多目標(biāo)優(yōu)化領(lǐng)域的要求，Antonio J.Nebro等[5]提出了MOCell算法，MOCell與cMOGA相比的一個(gè)主要改進(jìn)就是引入了反饋機(jī)制，即在每次迭代完成后會(huì)將一定數(shù)量的解從外部文檔返回到種群中，隨機(jī)替換掉種群中相等數(shù)量的個(gè)體，測試對(duì)比表明MOCell算法性能遠(yuǎn)優(yōu)于cMOGA算法，說明精英策略對(duì)算法性能影響較大.

根據(jù)相關(guān)研究，元胞多目標(biāo)遺傳算法在求解多目標(biāo)優(yōu)化問題時(shí)，算法的多樣性較好.鑒于元胞多目標(biāo)遺傳算法的特點(diǎn)，如何提高算法的收斂性并更好的平衡全局搜索和局部尋優(yōu)能力？這是個(gè)值得研究的問題.為了解決這兩個(gè)問題，在MOCell基礎(chǔ)上，提出一種混合精英策略的元胞多目標(biāo)遺傳算法(Cellular Multi-Objective Genetic Algorithm based Hybrid Elite Strategy,CMOGA-HES).該算法首先研究元胞鄰居結(jié)構(gòu)對(duì)算法性能的基礎(chǔ)上，提出一種混合精英策略，從而更加有效的提高收斂性能.基于元胞種群結(jié)構(gòu)的特點(diǎn)，每個(gè)個(gè)體只能與其鄰居個(gè)體進(jìn)行進(jìn)化操作，在一定程度上有利于算法的局部尋優(yōu)，為了增強(qiáng)算法的全局搜索能力，引入一種差分進(jìn)化策略，從而更好的平衡算法的全局搜索和局部尋優(yōu)性能.實(shí)驗(yàn)結(jié)果表明，CMOGA-HES算法與其他幾種典型的算法相比，有一定的競爭力.

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

Enrique Alba等人[6]根據(jù)種群的分布情況，將進(jìn)化算法分為兩類，一類是隨機(jī)交配種群結(jié)構(gòu)，如圖1(a)所示；一類是結(jié)構(gòu)化種群，而結(jié)構(gòu)化種群又分為分布式式種群結(jié)構(gòu)(圖1(b)所示)和元胞種群結(jié)構(gòu).

元胞遺傳算法[6]是將元胞自動(dòng)機(jī)的拓?fù)涮匦酝z傳算法的基本理論相結(jié)合而發(fā)展起來的一種優(yōu)化算法，因此該算法不僅繼承了遺傳算法的優(yōu)良品質(zhì)，而且擁有元胞自動(dòng)機(jī)的部分特性.其特點(diǎn)在于將種群中的每個(gè)個(gè)體分布于一個(gè)二維拓?fù)浣Y(jié)構(gòu)中(圖1(c)所示)，每個(gè)個(gè)體擁有相同的鄰居數(shù)，且每個(gè)個(gè)體只能與其規(guī)定的鄰居個(gè)體進(jìn)行遺傳操作.遺傳操作限制在鄰域范圍內(nèi)進(jìn)行，在一定程度上降低了選擇壓力.

元胞多目標(biāo)遺傳算法[5]MOCell(如圖2所示)，是基于元胞遺傳算法的大框架下，加入了多目標(biāo)進(jìn)化理論和策略.MOCell算法也是基于cMOGA算法的基礎(chǔ)上加入外部存檔精英保留策略，結(jié)果表明MOCell算法相對(duì)于cMOGA有較好的收斂性和多樣性，也說明精英保留策略有利于提高算法的性能.

MOCell算法的基本思想如表1所示，首先生產(chǎn)一個(gè)空的外部存檔，用于存儲(chǔ)進(jìn)化過程中的非支配(第2行).將初始種群分布于一個(gè)二維的網(wǎng)格結(jié)構(gòu)中，每個(gè)個(gè)體都有對(duì)應(yīng)的鄰居(第4、5行).從鄰居中選擇父代個(gè)體進(jìn)行交叉變異操作(第6～8行).對(duì)產(chǎn)生的子代個(gè)體進(jìn)行評(píng)估，并進(jìn)行替換策略(第9、10行).將種群中的非支配解存入外部存檔(第11行).每一次迭代完成后，新產(chǎn)生的輔助種群被當(dāng)作下一次循環(huán)的新種群(第13行)，并執(zhí)行反饋策略(第14行)，如此循環(huán)直到滿足循環(huán)終止條件為止(第3行).

表1　元胞多目標(biāo)遺傳算法的偽代碼

3CMOGA-HES算法

大部分進(jìn)化算法在求解優(yōu)化問題時(shí)，總是力求在算法的多樣性和收斂性方面尋求一種平衡,在全局搜索和局部尋優(yōu)的過程中尋找一種平衡.本文在研究元胞多目標(biāo)遺傳算法的基礎(chǔ)上，為了很好的平衡算法的全局搜索和局部尋優(yōu)能力，分別引入一種混合精英策略和差分進(jìn)化策略.使用混合精英策略，促使更多的精英個(gè)體參與到進(jìn)化過程中，但為了避免算法陷入局部收斂，將種群中每個(gè)個(gè)體放置于二維元胞自動(dòng)機(jī)模型中，使每個(gè)個(gè)體只能同規(guī)定的鄰居個(gè)體進(jìn)行遺傳操作，從而有利于精英個(gè)體在算法中緩慢擴(kuò)散，降低了算法的選擇壓力，提高全局搜索能力.利用差分進(jìn)化策略具有搜索能力強(qiáng)，有利于保持算法的多樣性的特點(diǎn)，加強(qiáng)算法的多樣性和局部尋優(yōu)能力.

3.1混合精英策略

在進(jìn)化過程中，精英個(gè)體對(duì)算法的性能產(chǎn)生巨大的影響，尤其是對(duì)算法的收斂性，正確的引入精英個(gè)體有利加快算法的收斂速度，提高算法效率.現(xiàn)有基于精英策略的進(jìn)化算法中，對(duì)精英個(gè)體的保存通常采用兩種經(jīng)典的方法：一種是外部存檔法，利用外部存檔保存當(dāng)前所有的非支配解，并一定數(shù)目反饋至種群，實(shí)現(xiàn)精英個(gè)體參與種群進(jìn)化，其中代表算法有SPEA2[3]等；另一種是NSGA-II[1]算法使用的輔助種群小生境法，將父代個(gè)體產(chǎn)生的子代個(gè)體保留至輔助種群中，一次進(jìn)化后，將父代個(gè)體和子代個(gè)體融合，通過支配關(guān)系和擁擠距離進(jìn)行排序，優(yōu)先選擇其中精英個(gè)體組成下一代的進(jìn)化種群.

在MOCell算法中，使用外部存檔來存儲(chǔ)進(jìn)化過程中得到的非支配解，作為一種精英機(jī)制可以使得MOCell具有較快的收斂速度.然而，精英個(gè)體僅僅只是存儲(chǔ)在外部文檔中，并沒有有效地參與到種群的進(jìn)化過程中.為了能充分發(fā)揮非劣解在進(jìn)化過程中的作用，本文將兩種上述的外部存檔和輔助種群小生境法進(jìn)行結(jié)合，形成一種混合精英策略(Hybrid Elite Strategy，HES)，其示意圖如圖3所示.具體操作：

UniPop=Union(Archiveg+AuxPopg)

(1)

(2)

Ranking()=Sorting(Distance(UniPopi,D),F(UniPopi,D))

(3)

OfferspringPop=Select(Ranking(UniPop))

(4)

其中：g為當(dāng)前進(jìn)化代數(shù)；Archiveg為外部存檔；AuxPopg為輔助種群；UniPop為合并后的種群；OfferspringPop為子代種群；Distance()為擁擠距離評(píng)估函數(shù)；D為決策空間大??；F()為適應(yīng)度函數(shù)；Sorting()為根據(jù)個(gè)體支配關(guān)系和擁擠距離進(jìn)行排序函數(shù)；Ranking()為排序函數(shù)；Selcet()為選擇函數(shù).

將種群分布于元胞拓?fù)浣Y(jié)構(gòu)中，可以提高算法的多樣性，文獻(xiàn)[5,9,11,12]表明元胞遺傳算法有較好的多樣性.本算法通過將外部存檔和輔助種群融合，進(jìn)行快速非支配排序后，外部存檔中的個(gè)體能得到充分地利用，種群中的優(yōu)良個(gè)體能更多地被保留下來，尤其在進(jìn)化初期可以促使精英個(gè)體引導(dǎo)進(jìn)化，從而加快收斂速度.由于將種群分布元胞結(jié)構(gòu)中，也促使種群中優(yōu)良個(gè)體緩慢的擴(kuò)散，從而可以緩解算法陷于局部收斂的可能性，能夠有效的平衡算法的收斂性和多樣性.

3.2差分進(jìn)化策略

差分進(jìn)化策略(Differential Evolution，DE)利用了群體中個(gè)體之間的距離和方向信息，具有全局并行直接搜索的特點(diǎn)，適于求解高維、非線性的多目標(biāo)問題，而且實(shí)施起來相對(duì)較容易[13].對(duì)于差分進(jìn)化策略，存在多種進(jìn)化模式，每種進(jìn)化策略之間存在各自的特點(diǎn)，文獻(xiàn)[14～16]對(duì)五種常見的進(jìn)化模式進(jìn)行了探討，分析出不同的進(jìn)化模式的優(yōu)缺點(diǎn).

本文為了平衡算法的全局搜索和局部尋優(yōu)的能力，引入DE/rand-to-best/1/bin進(jìn)化策略，該策略的具體方法為：

(5)

式中：Vi,D代表基準(zhǔn)個(gè)體i，D代表決策空間大小，Xbest,D表示當(dāng)前最優(yōu)秀個(gè)體，Xr1,D、Xr2,D、和Xi,D代表隨機(jī)選擇的個(gè)體，K和F表示差分控制參數(shù).結(jié)合元胞空間結(jié)構(gòu)的特點(diǎn)和元胞遺傳算法的特性，對(duì)于個(gè)體的選擇為：Xi,D為元胞中心個(gè)體；Xr1,D和Xr2,D代表為從鄰居個(gè)體中隨機(jī)選擇兩個(gè)個(gè)體；對(duì)于Xbest,D個(gè)體，則從外部文檔中隨機(jī)的選擇一個(gè)個(gè)體.

對(duì)于產(chǎn)生的個(gè)體Vi,D=[vi,1,…,vi,j,…,vi,D]中的每一分量vi,j，通過比較randj與交叉因子CR或j與K的大小關(guān)系，以判斷是否使用Vi,j來替換Xi,j，從而得到新個(gè)體ui,D=[ui,1,…,ui,j,…,ui,D].其具體表達(dá)式為：

(6)

其中：K∈[0,D-1]之間的任意整數(shù)；randj∈[0,1]的任意隨機(jī)數(shù).

3.3CMOGA-HES算法流程

綜合3.1節(jié)和3.2節(jié)在經(jīng)典的元胞遺傳算法上兩方面改進(jìn)，CMOGA-HES算法的算法流程如下所示：

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

Step2根據(jù)DE進(jìn)化策略，選擇中心個(gè)體與2個(gè)鄰居個(gè)體和1個(gè)外部存檔個(gè)體，由4個(gè)父代個(gè)體進(jìn)行差分交叉操作，最后執(zhí)行多項(xiàng)式變異操作[1]，產(chǎn)生子代.對(duì)于新產(chǎn)生的子代個(gè)體與父代進(jìn)行對(duì)比，如果優(yōu)秀子代替換父代個(gè)體；否則，不替換.

Step3將外部存檔中的個(gè)體和輔助種群進(jìn)行融合，根據(jù)支配關(guān)系和擁擠距離信息進(jìn)行排序，選擇優(yōu)秀個(gè)體組成下一代種群.

Step4判斷是否滿足終止條件，滿足則輸出非支配解集，否則轉(zhuǎn)向Step2.

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

為了對(duì)改進(jìn)算法的性能做出全面評(píng)估，本文選用多目標(biāo)優(yōu)化領(lǐng)域經(jīng)常采用的測試函數(shù)作為測試基準(zhǔn)函數(shù)，包括ZDT[17]系列，WFG[18]系列和DTLZ[19]系列，其中ZDT系列和WFG系列是兩目標(biāo)測試函數(shù)，DTLZ系列是三目標(biāo)測試函數(shù).

4.1性能指標(biāo)

為了評(píng)價(jià)算法求解測試問題的性能，兩個(gè)關(guān)鍵指標(biāo)必須要考慮到.一個(gè)是收斂性，即盡量使算法求出的Pareto前端與真實(shí)前端間的距離最??；另外一個(gè)是多樣性，即盡量使得到的Pareto前端均勻?qū)拸V的沿著真實(shí)前端分布.為了對(duì)以上指標(biāo)進(jìn)行評(píng)價(jià)，一些研究人員提出了多種性能評(píng)價(jià)指標(biāo).本文選取HV[20]與IGD[21]兩個(gè)評(píng)價(jià)指標(biāo)對(duì)算法性能進(jìn)行綜合評(píng)價(jià)，另外還選取Epsilon[22]指標(biāo)對(duì)收斂性進(jìn)行評(píng)價(jià).

(1)超體積(Hypervolume,HV)

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

(7)

式中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á)式如式(8)

(8)

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

(3)Epsilon(ε)

(9)

4.2同類算法對(duì)比分析

首先將改進(jìn)算法CMOGA-HES與未使用混合精英策略的CMOGA-non-HES、MOCell以及 CellDE[19]進(jìn)行比較，以便確定引入混合精英策略和差分進(jìn)化策略可以提高算法的性能.選用的測試函數(shù)由ZDT系列、DTLZ 系列和WFG系列組成，這些問題的特征已經(jīng)足夠支持其得到的結(jié)論.算法的參數(shù)配置如表2所示.

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

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

按照表2中的參數(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é)果如表3～表5所示，為了方便查看，表中每個(gè)問題的平均值和方差表示為：平均值/方差，其中最優(yōu)值都用深灰色背景標(biāo)出，次優(yōu)值都用淺灰色背景標(biāo)出.

表3是HV指標(biāo)的平均值和標(biāo)準(zhǔn)差，這個(gè)指標(biāo)是對(duì)算法的多樣性和收斂性進(jìn)行綜合評(píng)判，其取值越大越好.由表3可知，在21個(gè)測試問題中，CMOGA-HES得到了11個(gè)問題的最優(yōu)值，9個(gè)次優(yōu)值，未加混合精英策略的CMOGA-non-HES獲得了2個(gè)最優(yōu)值，7個(gè)次優(yōu)值，MOCell 得到了7個(gè)問題的最優(yōu)值和4個(gè)次優(yōu)值，而CellDE 只得到了1個(gè)問題的最優(yōu)值和1個(gè)次優(yōu)值，在這個(gè)指標(biāo)中，CMOGA-HES具有明顯的優(yōu)勢.對(duì)表4進(jìn)一步分析，在2目標(biāo)測試問題ZDT系列和WFG系列求解中，CMOGA-HES獲得了8個(gè)最優(yōu)值，6個(gè)次優(yōu)值，MOCell表現(xiàn)次之，獲得5個(gè)最優(yōu)值，3個(gè)次優(yōu)值，CMOGA-non-HES獲得了1個(gè)最優(yōu)值，5個(gè)次優(yōu)值.由此可知，CMOGA-HES在14個(gè)2目標(biāo)測試函數(shù)上面，均獲得次優(yōu)值以上的解，表明該算法在解決2目標(biāo)問題上有較明顯的優(yōu)勢.對(duì)于3目標(biāo)DTLZ系列測試問題，CMOGA-HES獲得了3個(gè)最優(yōu)值，3個(gè)次優(yōu)值，MOCell算法獲得2個(gè)最優(yōu)值，CellDE和CMOGA-non-HES各獲得1個(gè)最優(yōu)值，說明在解決 DTLZ 系列問題時(shí)，CMOGA-HES算法具有一定的優(yōu)勢.

表4中Epsilon性能指標(biāo)可知，CMOGA-HES獲得最優(yōu)值比例為11/21，次優(yōu)值為8/21，相對(duì)應(yīng)的CMOGA-non-HES獲得3個(gè)最優(yōu)值，7個(gè)次優(yōu)值，CellDE獲得3最優(yōu)值，2個(gè)次優(yōu)值，NSGA-II最優(yōu)值和次優(yōu)值各獲得4個(gè).由統(tǒng)計(jì)，對(duì)于是否添加HES策略對(duì)比表明，HES策略有利于提高算法的收斂性，而對(duì)于CellDE、MOCell和CMOGA-non-HES算法都采用外部存檔，三種算法的性能接近，MOCell算法稍微占優(yōu).對(duì)表4的結(jié)果做更細(xì)致的分析，對(duì)于ZDT系列測試問題，CMOGA-HES占有絕對(duì)優(yōu)勢，全部獲得最優(yōu)值，改進(jìn)算法的優(yōu)勢較為明顯；對(duì)于WFG系列問題，CMOGA-HES獲得4個(gè)最優(yōu)值和4個(gè)次優(yōu)值，CMOGA-non-HES得到1個(gè)最優(yōu)值和3個(gè)次優(yōu)值，CellDE算法獲得1個(gè)最優(yōu)值和一個(gè)次優(yōu)值，MOCell獲得了3個(gè)最優(yōu)值與1個(gè)次優(yōu)值，這說明在 WFG 系列問題上，改進(jìn)的算法有一定的優(yōu)勢.在3目標(biāo)測試問題 DTLZ 系列上，CMOGA-HES、CMOGA-non-HES和CellDE算法各獲得2個(gè)最優(yōu)值，MOCell算法獲得1個(gè)最優(yōu)值，但是CMOGA-HES獲得了4個(gè)次優(yōu)值，再次表明改進(jìn)算法相對(duì)于另外3種存在一定優(yōu)勢.

(續(xù))表4

從表5 IGD 指標(biāo)，可以直觀的看出，在 21 個(gè)測試問題中，CMOGA-HES得到了9個(gè)問題的最優(yōu)值和8個(gè)次優(yōu)值，CMOGA-non-HES、MOCell和CellDE 各得到了4個(gè)問題的最優(yōu)值.整體而言，CMOGA-HES還是占有較明顯的優(yōu)勢.在對(duì)于2目標(biāo)測試問題求解上，改進(jìn)的算法相對(duì)另外3種算法占有較為明顯的優(yōu)勢；對(duì)于3目標(biāo)問題，改進(jìn)的算法和CellDE算法的性能相當(dāng).

為了在統(tǒng)計(jì)意義上更加全面的比較分析多個(gè)算法的性能和穩(wěn)定性，采用Friedman檢驗(yàn)對(duì)結(jié)果進(jìn)行分析，圖4～圖6給出了4種算法的在不同指標(biāo)上的排序，圖中數(shù)字1～4依次表示算法CMOGA-HES、CMOGA-non-HES、CellDE和MOCell.對(duì)于分布性指標(biāo)HV，數(shù)值越大說明分布性越好，Epsilon和IGD指標(biāo)，數(shù)值越小說明性能更好.對(duì)于HV指標(biāo)，CMOGA-HES算法的數(shù)值最大，且是CellDE算法的兩倍多.由1和2算法對(duì)比，可再次證實(shí)HES策略有利于提高算法的性能.對(duì)于IGD指標(biāo)，CMOGA-HES算法性能最優(yōu)，2和4算法性能相當(dāng).對(duì)于收斂性指標(biāo)Epsilon，CMOGA-HES算法獲得數(shù)值最小，且遠(yuǎn)遠(yuǎn)小于其他算法，說明改進(jìn)的算法收斂性能優(yōu)異.

綜合以上分析，我們可以得出結(jié)論，從總體上來看，改進(jìn)算法CMOGA-HES較CMOGA-non-HES、CellDE和MOCell性能有明顯提高.一者說明，HES策略有利于提高算法的收斂性能，而元胞種群結(jié)構(gòu)有助于算法的多樣性，HES策略與元胞種群結(jié)構(gòu)相互配合，較好的平衡了算法的多樣性和收斂性；二者，引入的差分進(jìn)化策略，有助于平衡種群的全局搜索和局部尋優(yōu)能力.

4.3CMOGA-HES與其他算法對(duì)比分析

為了清楚改進(jìn)算法與其他算法相比的競爭性，將改進(jìn)算法與多目標(biāo)優(yōu)化領(lǐng)域的兩個(gè)經(jīng)典算法進(jìn)行比較，即NSGA-II和SPEA2算法，且兩種算法采用兩種不同的精英保存機(jī)制，更便于對(duì)比.本文中，SPEA2算法的參數(shù)配置，其種群大小和外部文檔的大小都設(shè)置為100，其他參數(shù)與NSGA-II算法的參數(shù)相同.每種算法獨(dú)立運(yùn)行50次，實(shí)驗(yàn)結(jié)果如表6和表7所示，表格中每個(gè)問題的最優(yōu)解都用深灰色背景標(biāo)出.

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

從表6可以看出，在Epsilon指標(biāo)上改進(jìn)算法CMOGA-HES得到了12個(gè)問題中的10個(gè)最優(yōu)值，SPEA2和NSGA-II都僅得到了1個(gè)最優(yōu)值.所以，就Epsilon指標(biāo)而言，與其他兩個(gè)算法相比CMOGA-HES具有明顯優(yōu)勢，表明該算法的收斂性較好，也說明HES策略相對(duì)于單個(gè)的精英保留策略有較好的收斂性.在2目標(biāo)問題求解上，CMOGA-HES依舊保持絕對(duì)的優(yōu)勢，且在ZDT4和ZDT6問題上有一個(gè)數(shù)量級(jí)上的優(yōu)勢.對(duì)于求解3目標(biāo)DTLZ系列問題，CMOGA-HES得到了7個(gè)問題中的5個(gè)最優(yōu)值，SPEA2和NSGA-II各得到了1個(gè)問題中的最優(yōu)值，由此表明，改進(jìn)的算法在求解3目標(biāo)問題是占有較明顯的優(yōu)勢.

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

從表7可以看出，在IGD指標(biāo)上CMOGA-HES得到了12個(gè)問題中的9個(gè)最優(yōu)值，NSGA-II得到了12個(gè)問題中的2個(gè)最優(yōu)值，SPEA2獲得1個(gè)最優(yōu)值.因此，CMOGA-HES在IGD指標(biāo)上比其他兩個(gè)算法具有顯著優(yōu)勢.

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

5工程實(shí)例

為了進(jìn)一步驗(yàn)證CMOGA-HES的性能，將其應(yīng)用于含有約束條件的桁架結(jié)構(gòu)優(yōu)化設(shè)計(jì)問題.本文以10桿桁架結(jié)構(gòu)作為對(duì)象，如圖10所示.10桁架屬于懸臂術(shù)架結(jié)構(gòu),各桿件材料相同，密度為ρ=2768kg/m3，彈性模量E=68950MPa，許用應(yīng)力δ=172.3MPa，載荷P=444.5KN，L=914.4mm.設(shè)計(jì)變量上限為0.0258m2，下限為64.5×10-5m2.本文取優(yōu)化目標(biāo)分別為桁架結(jié)構(gòu)總質(zhì)量和節(jié)點(diǎn)1、2、3、4的最大位移.

為了進(jìn)一步驗(yàn)證CMOGA-HES的性能，將其應(yīng)用于含有約束條件的桁架結(jié)構(gòu)優(yōu)化設(shè)計(jì)問題，并與SPEA2算法對(duì)比分析.兩算法相同的參數(shù)如下：種群規(guī)模大小NP=100，變異概率pm=1/len，其中l(wèi)en為決策變量的個(gè)數(shù)，最大進(jìn)化代數(shù)為300代，其中CMOGA-HES的CR=0.1,F=0.5,K=0.5；SPEA2的交叉概率pc=0.9.

圖11為兩種算法獲得Pareto前端比較圖，可以明顯看出CMOGA-HES獲得極端值點(diǎn)更加寬廣，分布更加均勻，能夠?yàn)闆Q策者提供更多的選擇方案，說明了算法的工程有效性.

6結(jié)論

本文提出一種混合精英策略的元胞多目標(biāo)遺傳算法，CMOGA-HES.首先，在分析元胞多目標(biāo)遺傳算法的基礎(chǔ)上，可知含有元胞種群結(jié)構(gòu)的算法其多樣性較好，為了進(jìn)一步提高算法的收斂性，將一種混合精英策略用于處理種群與外部存檔之間的關(guān)系.其次，為了更好的平衡算法的全局搜索和局部尋優(yōu)的能力，分析不同的進(jìn)化模式的優(yōu)缺，將一種差分進(jìn)化交叉算子引入算法中.最后，通過21個(gè)測試函數(shù)，進(jìn)行同類算法比較分析，表明混合精英策略能夠進(jìn)一步提高算法的收斂性，且CMOGA-HES較對(duì)比算法整體性能更優(yōu)；將其與NSGA-II和SPEA2兩種典型的精英保存策略的算法進(jìn)行對(duì)比分析，CMOGA-HES在Epsilon和IGD指標(biāo)上都有較明顯的優(yōu)勢，說明從收斂性和均勻性上綜合考察，改進(jìn)算法具有一定的競爭力.為了驗(yàn)證算法在求解約束問題和解決實(shí)際工程問題的性能，將其用于10桿桁架多目標(biāo)優(yōu)化問題中，求解結(jié)果表明了本文算法的實(shí)用性及可行性.

參考文獻(xiàn)

[1]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.

[2]Knowles J,Corne D.The pareto archived evolution strategy:A new baseline algorithm for pareto multiobjective optimisation[A].Evolutionary Computation,1999 .CEC 99.Proceedings of the 1999 Congress on[C].Washington,DC:IEEE,1999.98-105.

[3]Bleuler S,Brack M,Thiele L,et al.Multiobjective genetic programming:Reducing bloat using SPEA2[A].Evolutionary Computation，2001.Proceedings of the 2001 Congress on[C].Seoul：IEEE,2001.536-543.

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

[5]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.

[6]Enrique Alba,Bernabé Dorronsoro.Cellular Genetic Algorithms[M].New York:Springer-Verlag New York Inc,2008.3-47.

[7]Alba E,Dorronsoro B.The exploration/exploitation tradeoff in dynamic cellular genetic algorithms[J].IEEE Transactions on Evolutionary Computation,2005,9(2):126-142.

[8]Kirley M.MEA:A metapopulation evolutionary algorithm for multi-objective optimisation problems[A].Evolutionary Computation,2001,Proceedings of the 2001 Congress on[C].Seoul :IEEE,2001.949-956.

[9]魯宇明,黎明,李凌.一種具有演化規(guī)則的元胞遺傳算法[J].電子學(xué)報(bào),2010,38(7):1603-1607.

Lu Yu-ming,Li Ming,Li Ling.The cellular genetic algorithm with evolutionary rule[J].Acta Electronica Sinica,2010,38(7):1603-1607.(in Chinese)

[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]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[C].Berlin：Springer Berlin Heidelberg,2008.661-670.

[12]詹騰,張屹,朱大林,劉錚,等.基于多策略差分進(jìn)化的元胞多目標(biāo)遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2014,20(6):1342-1351.

Zhan Teng,Zhang Yi,Zhu Dalin,Liu Zheng,et al.Cellular multi-objective genetic algorithm based on multi-strategy differential evolution[J].Computer Integrated Manufacturing Systems,2014,20(6):1342-1351.(in Chinese)

[13]史彥軍.復(fù)雜布局的協(xié)同差異演化方法與應(yīng)用研究[D].大連：大連理工大學(xué)，2005.

SHI Yan-Jun.Thecooperative co-evolutionary differential evolution and its applications for complex layout optimization[D].Dalian:Dalian University of Technology,2005.(in Chinese)

[14]Qin A K,HUANG V L,SUSANTHAN P.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation,2009,13(2):398-417.

[15]賀毅朝,王熙照,劉坤起,王彥祺.差分演化的收斂性分析與算法改進(jìn)[J].軟件學(xué)報(bào)，2010,21(5):875-885.

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)

[16]彭虎,吳志健,周新宇,鄧長壽.基于精英區(qū)域?qū)W習(xí)的動(dòng)態(tài)差分進(jìn)化算法[J].電子學(xué)報(bào),2014,42(8):1522-1530.

Peng Hu,Wu Zhijian,Zhou Xinyu,Deng Changshou.Dynamic differential evolution algorithm based on elite local learning[J].Acta Electronica Sinica,2014,42(8):1522-1530.(in Chinese)

[17]Zitzler E,Deb K,Thiele L.Comparison of multi-objective evolutionary algorithms:Empirical results[J].Evolutionary Computation,2000,8(2):173-195.

[18]Huband S,Barone L,While L,et al.A scalable multi-objective test problem toolkit[A].Proceedings of the Evolutionary Multi-criterion Optimization’05[C].Berlin,Germany:Springer,2005.280-295.

[19]Deb K,Thiele L,Laumanns M,et al.Scalable multi-objective optimization test problems[A].Proceedings of the 2002 Congress on Evolutionary Computation[C].Honolulu,USA：IEEE,2002.825-830.

[20]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.

[21]Bosman T,Thierens D.The balance between proximity and diversity in multi-objective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2003,7(2):174-188.

[22]Zitzler E,Thiele L,Laumanns M,Fonseca C M,Fonseca V G .Performance assessment of multi-objective optimizers:an analysis and review[J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.

王福才男，1966年1月出生于山東煙臺(tái)，現(xiàn)為魯東大學(xué)信息與電氣工程學(xué)院副教授，研究方向?yàn)樾畔⑴c自動(dòng)化，主持國家及省部級(jí)科研項(xiàng)目10余項(xiàng)，在國內(nèi)外期刊發(fā)表論文10余篇.

E-mail:fucaiwang2002@aliyun.com

周魯蘋女，1970年4月出生于山東煙臺(tái)，現(xiàn)為魯東大學(xué)信息與電氣工程學(xué)院講師，研究方向?yàn)樾畔⑴c自動(dòng)化，主持參與省部級(jí)科研項(xiàng)目6項(xiàng)，在國內(nèi)外期刊發(fā)表論文10余篇.

Cellular Multi-objective Genetic Algorithm Based on Hybrid Elite and Application

WANG Fu-cai,ZHOU Lu-ping

(DepartmentofInformationandElectricalEngineering,LudongUniversity,Yantai，Shandong264025,China)

Abstract:In order to maintain better convergence of Pareto sets and to balance the global search and local optimization ability,the cellular multi-objective genetic algorithm based hybrid elite strategy (CMOGA-HES) was introduced.The algorithm is integrated into a hybrid elitist strategy to improve the convergence performance，which is based on analyzing the cellular population structure characteristics.For better balance between exploitation and exploration,a differential evolution crossover operator is proposed.Comparing with the similar cellular genetic algorithm by testing 21 benchmark functions,CMOGA-HES can improve the algorithm performance and outperform several state-of-the-art multi-objective metaheuristics in terms of convergence and diversity.The results of engineering example showed the feasibility of the proposed algorithm.

Key words:multi-objective;cellular genetic algorithm;hybrid elite strategy;differential evolution;function optimization;truss structure

作者簡介

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

中圖分類號(hào):TP301

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

文章編號(hào)：0372-2112 (2016)03-0709-09

基金項(xiàng)目:山東省自然科學(xué)基金(No.ZR2010FL013)

收稿日期:2014-07-28;修回日期:2014-09-15；責(zé)任編輯：梅志強(qiáng)