遞歸替換尋優(yōu)策略的分解多目標(biāo)進(jìn)化算法

王麗萍,豐美玲,邱飛岳,章鳴雷

1(浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院,杭州 310023)

2(浙江工業(yè)大學(xué) 信息智能與決策優(yōu)化研究所,杭州 310023)

3(浙江工業(yè)大學(xué) 現(xiàn)代教育技術(shù)研究所,杭州 310023)

1 引 言

在科學(xué)研究和實(shí)際應(yīng)用中存在多個(gè)目標(biāo)優(yōu)化問(wèn)題,稱之為多目標(biāo)優(yōu)化問(wèn)題MOPs(Multi-objective Optimization Problems).多目標(biāo)優(yōu)化問(wèn)題中目標(biāo)函數(shù)之間一般是相互沖突的,沒(méi)有一個(gè)最優(yōu)解能同時(shí)優(yōu)化所有目標(biāo)[1-3].由于進(jìn)化算法一次運(yùn)行能提供多個(gè)Pareto最優(yōu)解,且不受目標(biāo)函數(shù)數(shù)學(xué)性質(zhì)的影響,因此利用進(jìn)化算法求解多目標(biāo)優(yōu)化問(wèn)題成為近年來(lái)的研究熱點(diǎn)[4,5].

基于Pareto支配的多目標(biāo)進(jìn)化算法(如NSGA-II[6],SPEA2[7])是被最早提出的算法.這些算法在解決兩個(gè)或三個(gè)目標(biāo)的問(wèn)題上表現(xiàn)出較好的性能.然而,隨著目標(biāo)數(shù)目的增加,算法的搜索能力呈明顯下降趨勢(shì).主要原因是種群中非支配解的比例急劇增長(zhǎng),導(dǎo)致對(duì)種群的選擇壓力不足,使得種群進(jìn)化速度減慢,甚至過(guò)早停滯.

為增強(qiáng)種群朝Pareto前沿進(jìn)化,Zhang et al[8]于2007年提出了基于分解的多目標(biāo)進(jìn)化算法MOEA/D (Multi-objective evolutionary algorithms based on decomposition).MOEA/D算法的基本思想是,將MOPs中的多個(gè)目標(biāo)按一定的權(quán)重分解成若干個(gè)單目標(biāo)子問(wèn)題,然后進(jìn)行并行優(yōu)化,使子問(wèn)題的解逐漸逼近真實(shí)的Pareto前沿.這種機(jī)制有效的原因是每個(gè)子問(wèn)題的最優(yōu)解實(shí)際上對(duì)應(yīng)著給定MOP的Pareto最優(yōu)解.這些最優(yōu)解的集合可以看作是真實(shí)Pareto前沿面一個(gè)良好的近似.

為提高算法性能,Zhang et al[9]在2009年提出將差分算子DE引入到MOEA/D中,有效提高算法的收斂速度,增強(qiáng)解決復(fù)雜PS(Pareto Set)問(wèn)題的能力,但該算法的新解替換掉所有較差的解,未考慮替換次數(shù),這導(dǎo)致種群中個(gè)體的副本過(guò)多,使得算法的多樣性明顯下降.Qi et al[10]在2014年通過(guò)對(duì)原始Tchebycheff聚合函數(shù)做幾何分析,提出了一種新的權(quán)向量初始化方法MOEA/D-AWA(MOEA/D with Adaptive Weight Vector Adjustment),該算法根據(jù)復(fù)雜Pareto前沿周期性調(diào)整權(quán)值,使子問(wèn)題的權(quán)重向量能夠自適應(yīng)地重新分布,提高解分布的均勻性,然而使用的周期性參數(shù)的不同會(huì)影響解的性質(zhì),并且該算法在替換時(shí)未考慮替換次數(shù),一定程度上延緩了收斂速度.Li et al[11]于2014年提出一種穩(wěn)態(tài)匹配模型來(lái)協(xié)調(diào)MOEA/D中解與子問(wèn)題相互選擇,稱為MOEA/D-STM(Stable Matching-Based Selection in Evolutionary Multi-objective Optimization),該方法把子問(wèn)題和解看作是兩個(gè)不同的代理,子問(wèn)題傾向于選擇那些使其能獲得最小聚合函數(shù)值的解,而解傾向于選擇那些與其距離最近的子問(wèn)題.該算法的目的是實(shí)現(xiàn)多樣性和收斂性的平衡,但在選擇過(guò)程中折中越多,越容易使得解與合適的子問(wèn)題偏離程度大,并且該算法在新解替換舊解時(shí),仍未考慮替換次數(shù),導(dǎo)致算法整體性能明顯下降.同年,Wang et al[12]提出使用全局替換策略的MOEA/D-GR(A Replacement Strategy for Balancing Convergence and Diversity in MOEA/D)算法,新解與能夠取得最小聚合函數(shù)值的子問(wèn)題相結(jié)合,然后選擇與該子問(wèn)題距離最近的若干個(gè)子問(wèn)題作為替換鄰域.MOEA/D-GR算法旨在為新解找到一個(gè)最合適的子問(wèn)題,但一味強(qiáng)調(diào)收斂性導(dǎo)致新解在鄰域內(nèi)出現(xiàn)多個(gè)副本,犧牲了算法的多樣性.Yuan et al[13]于2015年提出根據(jù)新解到相關(guān)子問(wèn)題的垂直距離確定替換鄰域的MOEA/D-DU算法(Balancing Convergence and Diversity in Decomposition-Based Many-Objective Optimizers),該策略有效提高算法的多樣性,但一味強(qiáng)調(diào)多樣性而忽略算法的收斂性,使得算法的收斂性明顯下降.2016年,Zhou et al[14]針對(duì)不同的子問(wèn)題,提出一種新的動(dòng)態(tài)分配計(jì)算資源策略MOEA/D-GRA(A Generalized Resource Allocation Strategy for Decomposition-based MOEAs),該策略同樣一味強(qiáng)調(diào)算法的收斂性卻忽略算法的多樣性.

為維持多樣性的同時(shí)提高算法的收斂性,本文根據(jù)新解到對(duì)應(yīng)方向向量的垂直距離確定替換鄰域,繼而提出遞歸替換尋優(yōu)策略.該策略主要思想是,在替換鄰域內(nèi),新解根據(jù)聚合函數(shù)值大小替換舊解,被替換掉的舊解不被立刻丟棄,而是將舊解重新視為“新解”,在剩下的替換鄰域內(nèi)遞歸查找是否存在比該解更差的解.若存在,則替換之,將被替換掉的舊解又重新視為“新解”,如此循環(huán),直到當(dāng)前替換鄰域內(nèi)不存在能夠被舊解所替換的解.遞歸替換尋優(yōu)策略盡可能避免保留較差解,丟棄較優(yōu)解,保證最終被丟棄的舊解是當(dāng)前替換鄰域內(nèi)最差的解.根據(jù)垂直距離確定替換鄰域,有效保證算法的多樣性,在此基礎(chǔ)上提出遞歸替換尋優(yōu)策略,在維持多樣性的同時(shí)提高算法的收斂性.

2 背景知識(shí)

2.1 分解機(jī)制

分解機(jī)制是將MOP分解為一系列的子問(wèn)題,然后利用單目標(biāo)進(jìn)化算法求解每個(gè)子問(wèn)題[15].在MOEA/D中,加權(quán)和法、切比雪夫法和基于懲罰的邊界交叉法是最常用的分解方法[16,17].本文采用的分解方法是切比雪夫函數(shù)的改進(jìn)版本.設(shè)λ1,λ2,…,λN是當(dāng)前子問(wèn)題的權(quán)重向量,Z*是理想點(diǎn),Z*=min{fi(x)|x∈X}對(duì)于任意的i∈{1,2,…,m},λi≥0該函數(shù)定義為

(1)

改進(jìn)版本的切比雪夫函數(shù)有以下兩個(gè)優(yōu)點(diǎn).第一,在目標(biāo)空間中,均勻分布的權(quán)重向量可以產(chǎn)生均勻分布的搜索方向;第二,每個(gè)權(quán)重向量唯一對(duì)應(yīng)于Pareto前沿面上的一個(gè)Pareto最優(yōu)解.這兩個(gè)優(yōu)點(diǎn)在一定程度上提高了算法的多樣性.

2.2 權(quán)重向量產(chǎn)生方法

在MOEA/D中,子問(wèn)題對(duì)應(yīng)的權(quán)重向量分布的均勻性,在一定程度上反映了算法所求得的Pareto解的均勻性.因此,權(quán)重向量能否均勻地分布在整個(gè)取值空間對(duì)于MOEA/D所求得解的質(zhì)量至關(guān)重要.為此,本文選取MOEA/D中原始的權(quán)重向量生成方法.

(2)

2.3 MOEA/D算法流程

輸入:

①M(fèi)OP問(wèn)題;

②停止準(zhǔn)則;

③N:MOEA/D分解的子問(wèn)題個(gè)數(shù);

④λ1,λ2,…,λN:均勻分布的N個(gè)權(quán)重向量;

⑤T:每一個(gè)鄰域內(nèi)的權(quán)重向量個(gè)數(shù).

輸出:PF:{F(x1),F(x2),…,F(xN)}.

Step1.初始化:

Step1.1.計(jì)算任意兩個(gè)權(quán)重向量之間的歐式距離,為每個(gè)權(quán)重向量選出最近的T個(gè)向量作為其鄰域.設(shè)B(i)={i1,i2,…,iT},i=1,2,…,N,其中λi1,λi2,…,λiT為距離λi最近的T個(gè)權(quán)重向量.

Step1.2.初始化種群x1,x2,…,xN,設(shè)FVi=F(xi),i=1,2,…,N.

Step1.3.采用基于問(wèn)題的特定方法初始化z=(z1,z2,…,zm)T.

Step2.更新:

Fori=1,2,…,N,do

Step2.2.改進(jìn):應(yīng)用問(wèn)題特定的修正或啟發(fā)式的改進(jìn)策略作用于y生成y′.

Step2.3.更新z:若zj>fj(y′),則zj=fj(y′),j=1,2,…,m.

Step2.4.更新鄰域解:若gte(y′|λj,z)≤gte(xj|λj,z),j∈B(i),則xj=y′,FVj=F(y′).

Step3.停止判斷:若滿足停止準(zhǔn)則,則算法停止,輸出PF,否則返回Step2繼續(xù)執(zhí)行.

3 MOEA/D-LR算法

3.1 對(duì)比算法缺陷分析及改進(jìn)策略描述

在原始的MOEA/D中,替換鄰域與選擇鄰域相同,是將與該子問(wèn)題最接近的若干個(gè)子問(wèn)題作為替換鄰域.然而,新解并不一定適合該鄰域內(nèi)的子問(wèn)題,可能導(dǎo)致接近Pareto前沿的新解被舍棄,不利于引導(dǎo)種群的進(jìn)化.

MOEA/D-GR算法較好的克服了這個(gè)缺陷,其主要思想是,一旦產(chǎn)生一個(gè)新解,它就被關(guān)聯(lián)到能獲得最小聚合函數(shù)值的那個(gè)子問(wèn)題上.然后,與這個(gè)子問(wèn)題最接近的若干個(gè)子問(wèn)題被選擇作為該子問(wèn)題的替換鄰域,新解會(huì)嘗試替換這些子問(wèn)題的當(dāng)前解.但是,利用子問(wèn)題的聚合函數(shù)值為一個(gè)新解找到一個(gè)最合適的子問(wèn)題有時(shí)并非十分合理.當(dāng)權(quán)重向量稀疏分布時(shí),各個(gè)權(quán)重向量之間距離較遠(yuǎn),從而各個(gè)子問(wèn)題的最優(yōu)值有著很大的差異,這將導(dǎo)致不同聚合函數(shù)值之間并不具有可比性.另外,MOEA/D-GR一味強(qiáng)調(diào)收斂性,導(dǎo)致新解在鄰域內(nèi)出現(xiàn)多個(gè)副本,使得算法的多樣性明顯下降.

MOEA/D-DU在一定程度上較好的解決了MOEA/D-GR存在的該問(wèn)題,它采用一個(gè)純幾何的觀念,利用垂直距離來(lái)盡可能地避免那些雖然取得好的聚合函數(shù)值,但在目標(biāo)空間中遠(yuǎn)離聚合函數(shù)所對(duì)應(yīng)的權(quán)重向量的解.然而,以上算法都沒(méi)有考慮到在替換鄰域內(nèi),被替換掉的舊解可能仍可以替換該鄰域內(nèi)的其他解,即存在比替換掉的解更差的解.

為了克服以上缺陷,本文首先根據(jù)新解到對(duì)應(yīng)方向向量的垂直距離確定替換鄰域,同時(shí)結(jié)合遞歸替換尋優(yōu)策略,提出改進(jìn)算法MOEA/D-LR,在維持算法多樣性的同時(shí),提高算法的收斂性.

MOEA/D-LR算法及其四個(gè)比較算法具體策略描述如下:

如圖1(a)所示,在選擇鄰域B(i)(λ2,λ3,λ4)內(nèi)任取兩個(gè)個(gè)體進(jìn)行雜交,產(chǎn)生新解x.對(duì)于MOEA/D算法,如圖1(b)所示,替換鄰域與選擇鄰域相同也為λ2,λ3,λ4,由于新解x在該鄰域內(nèi)權(quán)重向量上的聚合函數(shù)值均大于其他個(gè)體,故新解x被丟棄.然而新解x明顯更接近于真實(shí)的Pareto前沿,丟棄x將導(dǎo)致算法的收斂性下降.

對(duì)于MOEA/D-GR算法,如圖1(c)所示,為新解x找到它最合適的子問(wèn)題x6,確定替換鄰域?yàn)棣?,λ6,λ7,新解x優(yōu)于x5,x6,x7,故x將同時(shí)替換x5,x6,x7,這將使得x在該鄰域內(nèi)產(chǎn)生多個(gè)副本,導(dǎo)致算法的多樣性明顯下降,難以促進(jìn)種群的收斂.

對(duì)于MOEA/D-DU算法,如圖1(d)所示確定替換鄰域?yàn)棣?,λ7,λ5,x優(yōu)于x6,故x將替換x6,x6被丟棄.然而在該鄰域內(nèi),x6比x5更接近Pareto前沿,這將導(dǎo)致較好的解x6被丟棄,較差的解x5被保留,使得算法的收斂性顯著下降.

對(duì)于MOEA/D-LR算法,如圖1(e)所示,根據(jù)新解x到方向向量的垂直距離確定替換鄰域?yàn)棣?,λ7,λ5,x優(yōu)于x6,故x將替換x6,被替換掉的解x6不被立刻丟棄,而是視為“新解”,遞歸查找是否x6能替換鄰域內(nèi)的其他解.重新計(jì)算在該鄰域內(nèi),x6到除λ6以外的權(quán)重向量的垂直距離,得到替換鄰域?yàn)棣?,λ7,x6優(yōu)于x5,故x6將替換x5,x5沒(méi)有比鄰域內(nèi)其他解優(yōu),即x5是該鄰域內(nèi)最差的解,丟棄x5.由以上分析可得,與MOEA/D相比,MOEA/D-LR在提高多樣性的同時(shí)提高算法的收斂性;與MOEA/D-GR相比,MOEA/D-LR在維持收斂性的同時(shí)提高算法的多樣性;與MOEA/D-DU相比,MOEA/D-LR算法在維持多樣性的同時(shí)其收斂性顯著提高.

圖1 五種算法的解集更新示意圖Fig.1 Solution set update of the five algorithms

3.2 算法主要修改部分

3.2.1 替換鄰域的確定

在MOEA/D算法流程中,將Step2.4更新鄰域解部分使用函數(shù)UpdateCurrentPop(y,z*,P,K)代替.

UpdateCurrentPop(y,z*,P,K)

Step2.4.1.j←1toN執(zhí)行,計(jì)算y到每個(gè)權(quán)重向量λj的垂直距離,記為dj,2(y).

Step2.4.2.從N個(gè)距離dj,2(y),j=1,2,…,N中選擇最小的K個(gè)距離,得到dj1,2(y)dj2,2(y)…djk,2(y).

Step2.4.3.k←1toK執(zhí)行,若gte(y|λjk,z)

Step2.4.4.被替換掉的舊解xjk不被立刻丟棄,而是存儲(chǔ)為temp,temp←xjk.

函數(shù)UpdateCurrentPop除了返回上述定義的值外,還需返回最小的K個(gè)垂直距離所對(duì)應(yīng)的權(quán)重向量的編號(hào)(即替換鄰域B(i))以及被替換掉的舊解xjk的值.在MOEA/D的基礎(chǔ)上,根據(jù)垂直距離確定替換鄰域,并結(jié)合遞歸替換尋優(yōu)策略,提出了改進(jìn)算法MOEA/D-LR,將上述算法流程增加如下步驟(加在Step2.4.4后):

3.2.2 遞歸替換尋優(yōu)策略

UpdateCurrentPop-LR(y,z*,P,K)

Step2.4.5.刪除舊解xjk所對(duì)應(yīng)的權(quán)重向量,將剩下的權(quán)重向量作為新的替換鄰域.

Step2.4.6.將被替換掉的舊解temp重新視為“新解”(y←temp),在新的替換鄰域內(nèi)遞歸查找是否 “新解”能夠替換其他的解.

Step2.4.7.若gte(y|λjk,z)

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

4.1 測(cè)試函數(shù)及參數(shù)設(shè)置

為驗(yàn)證本文提出的MOEA/D-LR算法的性能,將該算法與原始的MOEA/D算法[8]、MOEA/D-DRA[18]、MOEA/D-GR[12]和MOEA/D-DU[13]進(jìn)行實(shí)驗(yàn)仿真對(duì)比.本文選取的測(cè)試用例為兩目標(biāo)的WFG系列測(cè)試函數(shù)WFG1-WFG9和三目標(biāo)的DTLZ系列測(cè)試函數(shù)DTLZ1-DTLZ6[19,20].

為保證算法對(duì)比的公平性,本文所有的實(shí)驗(yàn)數(shù)據(jù)都是通過(guò)每個(gè)算法在每個(gè)測(cè)試問(wèn)題上重復(fù)獨(dú)立運(yùn)行20次獲得.本文遺傳操作的交叉算子采用SBX算子,交叉分布指數(shù)ηc為20,交叉概率Pc為1.0,分布指數(shù)ηm設(shè)置為20,變異概率Pm為1/n,其中n表示決策變量的個(gè)數(shù).所有算法的種群規(guī)模N均設(shè)置為100,鄰域大小T設(shè)置為N*0.2.在MOEA/D-DU和MOEA/D-LR中,替換鄰域K的設(shè)置與選擇鄰域相同,均為N*0.2.WFG系列測(cè)試函數(shù)的最大迭代次數(shù)Maxgen設(shè)置為250,DTLZ2和DTLZ4測(cè)試函數(shù)的最大迭代次數(shù)Maxgen為500,DTLZ1、DTLZ3、DTLZ5、DTLZ6測(cè)試函數(shù)的最大迭代代數(shù)為Maxgen為1000.

4.2 性能評(píng)價(jià)指標(biāo)

為避免單個(gè)性能度量指標(biāo)的片面性,能夠更加準(zhǔn)確、全面地對(duì)該算法進(jìn)行評(píng)價(jià),本文采用IGD[21]、S[22]和HV[23]指標(biāo)來(lái)分析算法的收斂性和分布性.IGD指標(biāo)能夠同時(shí)反映出算法收斂性和多樣性.IGD指標(biāo)值越小,表明所求得的近似Pareto前沿越接近整個(gè)真實(shí)的Pareto前沿,解集的收斂性和分布性整體效果越好.S指標(biāo)用于評(píng)估算法所求得的近似解在目標(biāo)空間上的均勻性.S指標(biāo)越小,表明所求得的Pareto解在目標(biāo)空間上的分布越均勻.HV指標(biāo)用于衡量多目標(biāo)進(jìn)化算法所求得的近似Pareto前沿的分布性和收斂性,HV指標(biāo)越大,表示算法所求得的解集的整體性能越優(yōu).

4.3 改進(jìn)算法在WFG函數(shù)上性能對(duì)比分析

本文首先使用WFG系列測(cè)試函數(shù)對(duì)提出的MOEA/D-LR算法進(jìn)行性能測(cè)試.表1和表2列出了每個(gè)算法在每個(gè)測(cè)試函數(shù)上20次運(yùn)行的IGD、HV的均值和標(biāo)準(zhǔn)差,表中所有算法在每個(gè)函數(shù)上的各項(xiàng)最優(yōu)值被加粗顯示.為分析的簡(jiǎn)便,本文還畫出了WFG系列9個(gè)測(cè)試函數(shù)、5種算法所求得的HV指標(biāo)值的盒圖.

4.3.1 IGD指標(biāo)對(duì)比

通過(guò)分析表1數(shù)據(jù)可以得到以下幾點(diǎn)結(jié)論:

表1 20次運(yùn)行的IGD的統(tǒng)計(jì)結(jié)果Table 1 Statistical results of IGD for 30 runs

1)在WFG系列測(cè)試函數(shù)上,算法MOEA/D-GR所求得的IGD均值與MOEA/D基本相差不大,原因在于MOEA/D-GR僅強(qiáng)調(diào)算法的收斂性而忽略了算法的多樣性,新解將替換鄰域內(nèi)聚合函數(shù)值小的解全部替換,使得新解在對(duì)應(yīng)的鄰域內(nèi)出現(xiàn)多個(gè)副本,導(dǎo)致算法的多樣性明顯下降,難以促進(jìn)種群的收斂.

2)在測(cè)試函數(shù)WFG1-WFG9上,可以看出MOEA/D-DU的IGD均值和標(biāo)準(zhǔn)差都比原始的MOEA/D算法小,原因在于MOEA/D-DU算法采用垂直距離確定替換鄰域的策略,維持了解的多樣性,引導(dǎo)解朝向Pareto前沿進(jìn)化,防止解陷入局部最優(yōu),提高解的性能.

3)比較MOEA/D-LR算法與MOEA/D算法可得,在WFG系列測(cè)試函數(shù)上,MOEA/D-LR算法無(wú)論是IGD均值還是標(biāo)準(zhǔn)差都明顯優(yōu)于MOEA/D算法.原因在于,MOEA/D-LR算法首先根據(jù)新解到方向向量的垂直距離確定替換鄰域,且新解在對(duì)應(yīng)的鄰域內(nèi)只替換一次,避免了解集副本過(guò)多,多樣性下降的情況,該策略有效地維持了解的多樣性.其次,新解替換掉舊解后,被替換掉的舊解沒(méi)有被立刻丟棄,而是在剩下的替換鄰域內(nèi)遞歸查找,是否該舊解能夠替換鄰域內(nèi)的其他解.該遞歸替換尋優(yōu)策略可以保證最終被丟棄的解是鄰域內(nèi)最差的解,有效避免了舍棄較優(yōu)解,保留較差解,從而極大提高解的收斂性.

表2 20次運(yùn)行的HV的統(tǒng)計(jì)結(jié)果Table 2 Statistical results of IGD for 20 runs

圖2 20次運(yùn)行的HV盒圖Fig.2 Box plots of HV with 20 runs

4.3.2 HV指標(biāo)對(duì)比

表2列出了每個(gè)算法在每個(gè)測(cè)試函數(shù)上20次運(yùn)行的HV均值和標(biāo)準(zhǔn)差.分析表2的數(shù)據(jù)可得,除測(cè)試函數(shù)WFG2和WFG3外,MOEA/D-LR算法獲得了所有函數(shù)的最大HV均值,這說(shuō)明MOEA/D-LR算法求解到的Pareto前沿近似解集具有良好的收斂性和分布性,性能明顯優(yōu)于四個(gè)比較算法.圖2繪制了所有算法20次運(yùn)行的HV盒圖,分析圖2中的盒圖可得,除WFG2和WFG3外,MOEA/D-LR算法的中位數(shù)均大于四個(gè)比較算法,并且該算法的四分位距較小,說(shuō)明其求解的精度和魯棒性好.此外,MOEA/D-LR算法產(chǎn)生的異常點(diǎn)也明顯少于其他四個(gè)比較算法,這同樣證明了該算法具有良好的魯棒性.

4.3.3 Pareto前沿對(duì)比分析

為直觀顯示出MOEA/D-LR算法收斂性的提高,使用20次運(yùn)行中IGD最小的那次實(shí)驗(yàn)數(shù)據(jù),繪制出MOEA/D,MOEA/D-LR在WFG1-WFG9測(cè)試問(wèn)題上的近似Pareto前沿與真實(shí)Pareto前沿對(duì)比圖.其中細(xì)線表示理想的Pareto前沿,圓圈和三角形分別表示MOEA/D和MOEA/D-LR算法求得的Pareto最優(yōu)解,每幅圖中的小圖代表部分區(qū)域進(jìn)行放大后的子圖.從上述Pareto前沿對(duì)比圖可以看出,MOEA/D-LR算法求得的解集比原始的MOEA/D求出的解集更接近理想的Pareto前沿,在WFG1、WFG6測(cè)試問(wèn)題上尤為突出.其中MOEA/D-LR在WFG6上求得的解集十分接近真實(shí)的Pareto前沿,而MOEA/D求得的解集距離真實(shí)的Pareto前沿較遠(yuǎn),原因在于當(dāng)進(jìn)化代數(shù)為250代時(shí),MOEA/D-LR算法在WFG6上已接近完全收斂,而MOEA/D由于進(jìn)化代數(shù)不夠,未收斂于理想的Pareto前沿,這同樣證明了遞歸替換尋優(yōu)策略能夠極大提高算法的收斂性.

圖3 WFG系列Pareto對(duì)比圖Fig.3 Comparison chart of Pareto on WFG

表3 20次運(yùn)行的HV和S的統(tǒng)計(jì)結(jié)果Table 3 Statistical results of HV and S for 20 runs

圖4 五種算法在WFG問(wèn)題上的IGD變化趨勢(shì)Fig.4 IGD trend of five algorithms on WFG

4.4 改進(jìn)算法在DTLZ函數(shù)上性能對(duì)比分析

在表3中,對(duì)MOEA/D和MOEA/D-LR算法HV均值和標(biāo)準(zhǔn)差進(jìn)行比較可得,MOEA/D-LR的HV均值均大于MOEA/D,表明該算法的整體性能明顯優(yōu)于MOEA/D算法.除DTLZ1和DTLZ6外,MOEA/D-LR的標(biāo)準(zhǔn)差均小于MOEA/D,表明該算法具有良好的魯棒性.從指標(biāo)S的數(shù)據(jù)可得,在測(cè)試函數(shù)DTLZ1,DTLZ2和DTLZ4上,MOEA/D-LR算法的S指標(biāo)值明顯小于MOEA/D算法,表明改進(jìn)算法MOEA/D-LR具有良好的分布性,在測(cè)試函數(shù)DTLZ6上,改進(jìn)算法的分布性略優(yōu)于原始的MOEA/D算法.此外,MOEA/D-LR算法的S指標(biāo)值標(biāo)準(zhǔn)差非常小,這同樣也表明該算法的魯棒性強(qiáng).

4.5 WFG函數(shù)IGD指標(biāo)值的進(jìn)化情況

為進(jìn)一步探究MOEA/D-LR算法的性能,本文給出了MOEA/D-LR和四個(gè)比較算法在WFG系列測(cè)試函數(shù)上IGD指標(biāo)值隨種群進(jìn)化代數(shù)的變化曲線圖,其中橫坐標(biāo)是種群的進(jìn)化代數(shù),縱坐標(biāo)是20次運(yùn)行的IGD均值.本文以三個(gè)測(cè)試函數(shù)(WFG1、WFG4、WFG8)為例進(jìn)行分析,結(jié)果如圖4所示.從圖中觀察可得,MOEA/D-LR算法在收斂速度和最終的收斂結(jié)果上都要優(yōu)于四個(gè)比較算法.由圖4(a)可得,在測(cè)試函數(shù)WFG1上,當(dāng)進(jìn)化代數(shù)為250代左右時(shí),MOEA/D-LR算法的收斂速率明顯提高,IGD均值非常小,這表明該算法已接近完全收斂,而其他四個(gè)比較算法的IGD均值均較大,表明這四個(gè)比較算法在同等迭代次數(shù)上均未完全收斂,并且,MOEA/D-LR算法的整體收斂速度明顯快于其他四個(gè)比較算法.觀察圖4(a-c)前幾代的IGD變化曲線圖可得,三角形的下降速度明顯快于另外四種形狀,說(shuō)明引入遞歸替換尋優(yōu)策略后,在種群進(jìn)化的初期階段,對(duì)促進(jìn)種群的收斂有著顯著的效果,MOEA/D-LR算法能夠有效地促進(jìn)種群的進(jìn)化,提高算法所求解集的收斂性.

5 結(jié) 論

為維持算法多樣性的同時(shí)提高算法的收斂性,提出基于遞歸替換尋優(yōu)策略的MOEA/D-LR算法.該算法根據(jù)新解到對(duì)應(yīng)方向向量的垂直距離確定替換鄰域,保持解在目標(biāo)空間中的均勻分布,有效維持解集的多樣性;采用遞歸替換尋優(yōu)策略對(duì)鄰域內(nèi)的解集進(jìn)行替換,盡可能快速引導(dǎo)解集朝Pareto前沿進(jìn)化,提高解的收斂性.實(shí)驗(yàn)結(jié)果表明,MOEA/D-LR算法的Pareto前沿近似解集更逼近真實(shí)的Pareto前沿,解集的分布性也更好,性能明顯優(yōu)于其他四個(gè)比較算法.在接下來(lái)的工作中,我們將考慮對(duì)MOEA/D-LR算法進(jìn)行擴(kuò)展以探究其在高維多目標(biāo)優(yōu)化問(wèn)題上的性能.

：

[1] Zheng Jin-hua.Multi-objective evolutionary algorithm and its application[M].Beijing:Science Press,2007.

[2] Eiben A E,Smith J E.Introduction to evolutionary computing[M].Springer:Berlin,2003.

[3] Ishibuchi H,Sakane Y,Tsukamoto N,et al.Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations[C].IEEE International Conference on Systems,Man and Cybernetics,IEEE Press,2009:1758-1763.

[4] Gong Mao-guo,Jiao Li-cheng,Yang Dong-dong,et al.Research on evolutionary multi-objective optimization algorithms[J].Journal of Software,2009,20(2):271-289.

[5] Gong D W,Liu Y P,Sun X Y,et al.Parallel many-objective evolutionary optimization using objectives decomposition[J].Acta Automatica Sinica,2015,41(8):1438-1451.

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

[7] Zitzler E,Laumanns M,Thiele L.SPEA2:improving the strength pareto evolutionary algorithm[C].Evoltionary Methods for Design,Optimisation and Control,Spain,2002:95-100.

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

[9] Li H,Zhang Q.Multiobjective optimization problems with complicated pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.

[10] Qi Y,Ma X,Liu F,et al.Moea/d with adaptive weight adjustment[J].Evolutionary Computation,2014,22(2):231-264.

[11] Li K,Zhang Q,Kwong S,et al.Stable matching-based selection in evolutionary multiobjective optimization[J].IEEE Transactions on Evolutionary Computation,2014,18(6):909-923.

[12] Wang Z,Zhang Q,Gong M,et al.A replacement strategy for balancing convergence and diversity in MOEA/D[C].Proceedings of IEEE Congress on Evolutionary Computation,Beijing,2014:2132-2139.

[13] Yuan Y,Xu H,Wang B,et al.Balancing convergence and diversity in decomposition-based many-objective optimizers[J].IEEE Transactions on Evolutionary Computation,2015,20:1-1.

[14] Zhou A,Zhang Q.Are all the subproblems equally important？Resource allocation in decomposition-based multiobjective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2016,20(1):52-64.

[15] Zhang Y,Hu S,Wu J,et al.Multi-objective optimization of double suction centrifugal pump using Kriging meta models[J].Advances in Engineering Software,2014,74(4):16-26.

[16] Messac A,Ismail-Yahaya A,Mattson C.The normalized normal constraint method for generating the Pareto frontier[J].Struct Multidisc.Optim,2003,25:86-98.

[17] Jan M A,Khanum R A.A study of two penalty-parameterless constraint handling techniques in the framework of MOEA/D[J].Applied Soft Computing,2013,13(1):128-148.

[18] Zhang Q,Liu W,Li H.The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances[C].Evolutionary Computation,CEC ′09,IEEE Congress on,IEEE,2009:203-208.

[19] Huband S,Barone L,While L,et al.A scalable multi-objective test problem toolkit[J].Lecture Notes in Computer Science,2005,3410:280-295.

[20] Deb K,Thiele L,Laumanns M,et al.Scalable multi-objective optimization test problems[C].Evolutionary Computation,CEC ′02,Proceedings of the 2002 Congress on,IEEE,2002:825-830.

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

[22] Veldhuizen D A V,Lamont G B.On measuring multiobjective evolutionary algorithm performance [C].Evolutionary Computation,Proceedings of the 2000 Congress on,IEEE,2000,1:204-211.

[23] Deb K,Agrawal R B.Simulated binary crossover for continuous search space[J].Complex Systems,2000,9(2):115-148.

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

[1] 鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2007.

[4] 公茂果,焦李成,楊咚咚,等.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào),2009,20(2):271-289.