基于重構(gòu)鄰域策略的分解多目標(biāo)進(jìn)化算法

曹 鴿,郭海東,王麗萍,徐夢娜

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

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

3(浙江工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

E-mail:gimmg@zjut.edu.cn

1 引 言

多目標(biāo)優(yōu)化問題各個目標(biāo)之間相互沖突,通常情況下,無法使各個目標(biāo)同時達(dá)到最優(yōu)[1],只能獲得一組近似Pareto最優(yōu)解.在生物工程[2,3],經(jīng)濟(jì)學(xué)[4],工程學(xué)[5]等領(lǐng)域存在大量的多目標(biāo)問題,因此研究并解決多目標(biāo)優(yōu)化問題具有十分重要的現(xiàn)實(shí)意義.

近幾十年以來,大量的多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithms,MOEAs)被相繼提出,MOEAs可以分成三類:

1)基于支配的方法,例如Deb[6]等提出基于Pareto支配關(guān)系的快速非支配排序算法(Fast and Elitist Multiobjective Genetic Algorithm,NSGA-II),Zitzler[7]等提出強(qiáng)化Pareto算法(Improving the Performance of the Strength Pareto Evolutionary Algorithm,SPEA2),但該類算法會隨目標(biāo)維度上升非支配解的數(shù)量呈指數(shù)增長,導(dǎo)致基于Pareto關(guān)系對優(yōu)秀解的選擇壓力嚴(yán)重衰減,算法容易陷入局部最優(yōu);

2)基于指標(biāo)的方法,Zitzler[8]提出基于超體積的多目標(biāo)進(jìn)化算法SMS-EMOA(Improving hypervolume-based multiobjective evolutionary algorithms by using objective reduction methods),但是HV指標(biāo)的計算代價會隨目標(biāo)維度增加呈指數(shù)增長;且在目標(biāo)維度高于5維的情況下很難實(shí)現(xiàn)實(shí)際應(yīng)用;

3)基于分解的方法,Zhang[9]等提出了一種基于分解的多目標(biāo)進(jìn)化算法(MOEA/D),將復(fù)雜的MOP(Multi-objective Optimization Problem)分解成多個簡單的優(yōu)化子問題,再同時對這些子問題進(jìn)行求解.這些子問題之間的鄰域關(guān)系是基于聚合函數(shù)來定義的,每個子問題通過來自其相鄰子問題的信息進(jìn)行優(yōu)化.

鄰域結(jié)構(gòu)在MOEA/D中起到重要的作用,原始MOEA/D和其大部分的變體算法,在算法迭代初始,將所有子問題鄰域大小都設(shè)置成固定數(shù)值,這使得每代中所有子問題分配到相同計算資源.然而由于子問題計算復(fù)雜度均不相同,對所有子問題都設(shè)置同樣大小的鄰域資源進(jìn)行優(yōu)化時,會造成邊界子問題搜索資源浪費(fèi)的問題,而較密集的子問題將面臨搜索資源不足的困境.針對以上問題,有學(xué)者提出了以下改進(jìn)算法.Zhao[10]提出了一種自適應(yīng)改變鄰域大小的方式來改善固定鄰域存在的缺陷.Zhang[11]提出動態(tài)資源分配策略，有效改善了解集的分布性.Qi[12]提出自適應(yīng)權(quán)重調(diào)整策略，Wang[13]提出基于全局替換策略的多目標(biāo)進(jìn)化算法(MOEA/D Based on Global Replacement，MOEA/D-GR). Jiang[14]提出了一個小生境引導(dǎo)下的交配選擇范圍設(shè)定方案,在優(yōu)化的MOP的POF(Pareto-optimal front)不連續(xù)時仍能有效保持種群多樣性.Chiang[15]提出了基于MOEA/D-DE[16]的自適應(yīng)父代選擇機(jī)制,根據(jù)決策空間上個體之間的歐幾里德距離來選擇父代解進(jìn)行基因重組,而不是目標(biāo)空間中子問題的權(quán)重向量之間的距離.選擇決策空間中距離最近的T個個體作為交配池,并每隔一定代數(shù)自適應(yīng)調(diào)整交配池.Zhang[17]在算法運(yùn)行每一代中都應(yīng)用自組織映射來確定種群在決策空間中的分布結(jié)構(gòu),并為每個解構(gòu)建交配池,僅允許相同交配池內(nèi)的解進(jìn)行基因重組操作.此外,根據(jù)過去一定代數(shù)內(nèi)產(chǎn)生新解的表現(xiàn)自適應(yīng)調(diào)整鄰域大小.

初始MOEA/D和大部分變體算法基因重組操作父代的選擇僅僅基于鄰域關(guān)系,這種方式不利于算法的優(yōu)化.因此,適當(dāng)?shù)恼{(diào)整選擇父代的方式,可以大大提升算法性能.本文提出一種重構(gòu)鄰域策略,從鄰域和精英解集合中選擇父代來進(jìn)行交叉變異操作產(chǎn)生新解,其中,精英解集合分兩步篩選確定,利用垂直距離更新策略篩選出預(yù)備精英解集,再通過計算每個預(yù)備精英的“潛力值”,并根據(jù)“潛力值”排名來篩選精英解集.這種方式突破了以往的MOEA/D選擇父代來進(jìn)行基因重組模式,在不改變鄰域規(guī)模的前提下(通過鄰域關(guān)系確定的鄰域和精英解集組成的新鄰域規(guī)模保持一定),本文提出的重構(gòu)鄰域策略在一定程度上可以避免父代中的精英解在迭代過程中丟失,從而有效改善了新一代解的質(zhì)量,提升了算法收斂速度.

2 研究背景及MOEA/D-DU缺陷分析

2.1 多目標(biāo)優(yōu)化問題

多目標(biāo)優(yōu)化問題在數(shù)學(xué)上的定義如下:

Minimize F(x)=(f1(x),f2(x),f3(x),…,fm(x))T

Subjecttox∈Ω

(1)

其中,x=(x1,x2,…,xn)T是決策變量向量,Ω是決策空間內(nèi)的可行區(qū)域,F:Ω→Rm,包含m個目標(biāo)fi(x)(i=1,2,3,…,m).

2.2 MOEA/D-DU

在MOEA/D-DU(Balancing convergence and diversity in decomposition-based many-objective optimizers)[18]中,采用改進(jìn)版本的切比雪夫聚合法將問題(1)分解成若干個子問題:

(2)

其中:

ⅰ.Z*為參考點(diǎn),通常算法使用搜索過程中Fj的最小值來表示；

ⅱ.λ=(λ1,λ2,…,λN)T為在空間中生成均勻分布的權(quán)重向量,λj,p≥0，p∈({1,2,…,m}).

初始化種群x1,x2,…,xN(xi∈Ω),其中xi為第i個子問題的當(dāng)前解.

在MOEA/D-DU中,計算任意兩個權(quán)重向量之間的歐幾里德距離,然后選擇距離每個權(quán)重向量最近的T個權(quán)重向量,對于每一個權(quán)重向量λi(i∈[1,N]),其鄰域設(shè)為B(i)={i1,…,iT}.每個子問題互相獨(dú)立的依靠于鄰域信息進(jìn)行優(yōu)化,在鄰域中選擇父代解并進(jìn)行基因重組操作產(chǎn)生新解,以此來保持解集的多樣性.

2.3 MOEA/D-DU缺陷分析

在MOEA/D更新策略中,交叉變異產(chǎn)生的新解可以替換鄰域內(nèi)的解,不限制替換解個數(shù),這在一定程度上加快種群收斂速度,但是一個新解替換鄰域內(nèi)多個解的更新替換方式可能會導(dǎo)致算法陷入局部最優(yōu),同時降低解集多樣性.

MOEA/D-DU算法提出垂直距離更新策略,每一代通過計算新解到每個權(quán)重向量λj(j=1,2,…,N)的垂直距離,dj,2(y)(j=1,2,…,N),然后從這N個距離中選擇K個最小的距離,然后將這K個距離以遞增的順序排序,假設(shè)順序?yàn)?dj1,2(y),dj2,2(y),…,djK,2(y),解y逐個與解xj1,xj2,…，xjk進(jìn)行比較,直到解xjk(k∈{1,2,…,K})的聚合函數(shù)值比解y的大,則解xjk被解y替代,并且更新過程終止.由于在當(dāng)前種群中新解只替換一個解,這在一定程度上提高了解集的質(zhì)量,保持了解集的多樣性,但是大大降低了種群收斂到Pareto前沿面的速度,相比于新解替換多解的算法,算法的收斂速度較為緩慢.

以測試函數(shù)DTLZ3為例,從圖1可以看出,在二維目標(biāo)優(yōu)化問題上,在350代之前,MOEA/D-DU的GD指標(biāo)值隨代數(shù)變化曲線在MOEA/D的上方,說明MOEA/D-DU在算法收斂前期的收斂速度與MEOA/D相比較緩慢,在450代之后,MOEA/D-DU的GD值隨代數(shù)變化曲線在MOEA/D的下方,并逐漸趨于穩(wěn)定,即MOEA/D-DU的GD值更優(yōu),說明MOEA/D-DU求得的近似Pareto前沿能較好地逼近真實(shí)的Pareto前沿面,但是從曲線總體走向而言,算法收斂到Pareto前沿面的速度相比MOEA/D較為緩慢.

綜上所述,MOEA/D-DU提高了解集的多樣性,但是在一定程度上犧牲了種群收斂到近似Pareto前沿面的速度,因此,本文提出重構(gòu)鄰域策略,在一定程度上提高算法的收斂速度,同時通過改變解集的鄰域結(jié)構(gòu)平衡算法的多樣性和收斂性.

圖1 測試函數(shù)DTLZ3在3維目標(biāo)問題上收斂性對比

3 基于重構(gòu)鄰域策略的多目標(biāo)進(jìn)化算法(MOEA/D-RNS)

本文提出一種重構(gòu)鄰域策略算法MOEA/D-RNS,算法從子問題鄰域和精英解組成的新鄰域集合中選擇父代進(jìn)行交叉變異產(chǎn)生新解.其中,精英解分兩步篩選確定,利用更新策略篩選出預(yù)備精英解集,再通過計算每個預(yù)備精英的“潛力值”,并根據(jù)“潛力值”排序來選擇精英解.

3.1 潛力值定義

潛力值定義:比較解j與鄰域內(nèi)每個解的聚合函數(shù)值,將解j優(yōu)于或等于該鄰域解的數(shù)量定義為解j在其鄰域內(nèi)的潛力值.

圖2 潛力值定義

如圖2所示,j的鄰域?yàn)閍、b、c、d、e,比較j與a、b、c、d、e的聚合函數(shù)值,圖中j的聚合函數(shù)值均優(yōu)于鄰域內(nèi)的a、b、c、d、e這5個解,故j的潛力值為5.潛力值可以反映在某個特定子問題上解質(zhì)量的好壞.

3.2 算法介紹

算法1為MOEA/D-RNS的整體框架,算法2和算法3分別為預(yù)備精英的潛力值計算和重構(gòu)鄰域策略.

算法1為MOEA/D-RNS算法整體框架,加入了重構(gòu)鄰域策略(RNS),預(yù)備精英初始化設(shè)置為全體個體,設(shè)置精英的評判下限T_num,潛力值大于T_num的預(yù)備精英被判定為精英.步驟2為計算每個預(yù)備精英潛力值num,具體步驟見算法2.

算法1.MOEA/D-RNS算法

輸出:B(i){i1,i2,…,iT1}

1.Fori=1 toN

2.通過算法2計算預(yù)備精英的潛力值

3.QL(1)≥QL(2)≥…≥QL(T2) //對每個預(yù)備精英根據(jù)潛力值的大小進(jìn)行非減排序,并選取前T2個

4.Best←{best1,best2,…,bestT2} //將步驟2選出的T2個個體(best1,best2,…,bestT2)視為精英點(diǎn)

5.重構(gòu)鄰域策略(算法3)

6.Mating Selection

7.y←GeneticOperators(xi;xk)

8.UpdateIdealPoint(y;z*)

9.(P1)←UpdatePopulation(y;z*;Λ;P;K)

10.a1//找到新解可替換的第一個解a1

11.nn=nn∪P1(1:a1) ∥更新預(yù)備精英

12.End for

從預(yù)備精英中選擇精英:每代迭代開始,對上一代選出的所有預(yù)備精英解進(jìn)行如下操作:計算并比較預(yù)備精英解j與其鄰域B(j)解的聚合函數(shù)值,將預(yù)備精英優(yōu)于鄰域解的數(shù)量定義為潛力值QL,具體過程見算法2.再將潛力值按照非升序排名,取潛力值排名前T2個預(yù)備精英為精英,將這T2個精英作為精英集sindex.

步驟3-步驟4:對所有預(yù)備精英按照潛力值大小進(jìn)行非減排序,選取前T2個預(yù)備精英作為精英,在此之后清空預(yù)備精英集,以便后續(xù)預(yù)備精英選取操作.步驟5為重構(gòu)鄰域策略,具體操作見算法3.步驟5為算法3重構(gòu)鄰域策略下的父代選擇操作.

步驟9-步驟11為選擇預(yù)備精英的操作,其中步驟9為MOEA/D-DU的更新過程,選擇預(yù)備精英:在每代的算法迭代過程中,為下一代算法迭代挑選預(yù)備精英,對每個個體i均做如下操作:將離新解y最近的K個鄰域解(更新策略選出的離新解最近的K個權(quán)重向量對應(yīng)的K個鄰域解),保存在集合P1中,計算新解y和這K個鄰域解的聚合函數(shù)值.考慮到不可被新解替換的解可能是鄰域內(nèi)較好的解,在一定程度上認(rèn)為這樣的解可以為算法帶來性能上的提升,所以將不可替換的解也設(shè)置成預(yù)備精英,首先找到新解可替換的第一個解a1,將1,…,a1對應(yīng)的個體視為預(yù)備精英,并被納入集合nn,即nn=nn∪P1(1:a1),∪表示集合合并操作,預(yù)備精英保存在nn中.

算法2.計算預(yù)備精英的潛力值

初始化:潛力值QL

1.L=length(nn)

∥L為預(yù)備精英的數(shù)量

2.Fork=1 to length(nn)

3.P2=B(nn(k),:)

∥P2為當(dāng)前預(yù)備精英的鄰域

4.Form=1 toT

5.IfF(nn(k))>=F(P2(m))∥預(yù)備精英和鄰域解聚合函數(shù)值比較

6.QL=QL+1 ∥若預(yù)備精英k的聚合函數(shù)值優(yōu)于其鄰域解m,則潛力值加1

7.End

8.End for

9.num(nn(k))=QL

∥更新潛力值num

10.End for

算法3重構(gòu)鄰域策略,算法迭代過程中,每個子問題i將D(i)={i1,…,iT1}(鄰域B(i)中取前T1個個體組成的集合)和精英集sindex(T2個精英構(gòu)成)組成的集合作為重構(gòu)后的鄰域,這里用D(i)和sindex組成的集合替換鄰域B(i).T1和T2滿足:T=T1+T2,保證算法的鄰域大小與其他對比算法相同.

算法3.重構(gòu)鄰域策略

1.Fori=1 toN

2. If Rand

3.BB=[B(i,1:T1) sindex(1:T2)]

4.P=BB(Rand(Size(B,2)))

5. Else

6.EE=[E(i,1:N-T2)sindex(1:T2)]

7.P=EE(Rand(Size(E,2))

8.End

9.IfP(1)==P(2)

10.P(2)=P(3);

11.End

4 仿真實(shí)驗(yàn)及分析

4.1 參數(shù)設(shè)置

為了驗(yàn)證本文所提出的算法性能,我們對ZDT1-4系列測試函數(shù)和DTLZ1-4系列測試函數(shù)進(jìn)行測試,分析改進(jìn)算法MOEA/D-RNS與對比算法MOEA/D[9]、MOEA/D-DE[16]、MOEA/D-DU[18]和NSGA-Ⅲ[19]在IGD和GD指標(biāo)上的性能表現(xiàn),測試均在PlatEMO平臺[20]上進(jìn)行,對每個測試函數(shù)獨(dú)立運(yùn)行30次取平均值和標(biāo)準(zhǔn)差.

根據(jù)決策變量的公式n=m+k-1,測試函數(shù)DTLZ1對應(yīng)的k設(shè)置為5,DTLZ2-4對應(yīng)的k設(shè)置為10,ZDT1-4系列測試函數(shù)的決策變量設(shè)置為30.此外,所有算法的其它參數(shù)均保持一致.采用模擬二進(jìn)制交叉和多項式變異,交叉概率Pc=1.0,變異概率Pm=1/n,交叉分布指數(shù)(ηc)=20,變異分布指數(shù)(ηm)=20.本文中設(shè)置,0≤T1,T2≤T/2,所有的對比算法T均設(shè)置為20.隨著目標(biāo)維度增加,逼近Pareto前沿面所需的解數(shù)量會呈現(xiàn)指數(shù)上升,所以需要相應(yīng)的調(diào)整種群規(guī)模大小,對比算法的種群規(guī)模N設(shè)定如表1所示.ZDT1-4系列測試函數(shù)評價次數(shù)設(shè)定為30000,DTLZ1-4系列測試函數(shù)在不同維度(m)上的評價次數(shù)設(shè)定如表2所示.

4.2 算法性能評價指標(biāo)

仿真實(shí)驗(yàn)中,為了衡量算法性能,使用如下指標(biāo):

1) 反向世代距離(IGD)

IGD指標(biāo)反映解集的收斂性和多樣性的組合信息,計算公式如下,其中,P*表示理想Pareto前沿面PFture,P表示算法迭代得到的近似Pareto前沿面PFknow,另外d(v,P)表示v到P的最小歐幾里得距離.IGD指標(biāo)值越小,表示算法得到的解集質(zhì)量越高.

(3)

2) 世代距離(GD)

GD指標(biāo)反映算法的收斂性,計算公式如下,其中,n為種群個數(shù),di為算法計算得到的第i個解與PFtrue中最近解之間的歐幾里得距離,GD指標(biāo)值越小,表示算法迭代得到的近似Pareto前沿越逼近已知的Pareto前沿,算法的收斂性越好.

(4)

mHN2991003131055621083,3240102,2275測試函數(shù)m≤5m>5DTLZ115000?m100000DTLZ21000020000DTLZ320000?m150000DTLZ41000020000

4.3 參數(shù)T_num影響分析

T_num是重構(gòu)鄰域策略中一個重要的參數(shù),影響精英解集的選擇,為了研究潛力值評價下限T_num對算法性能的影響,重構(gòu)鄰域策略對T_num的敏感性,分析T_num=2,4,6,8,10,12,14,16,18,20時,在2,5,8,10維目標(biāo)上對DTLZ1-4系列測試問題進(jìn)行了測試,除T_num之外的所有其他參數(shù)保持一致,圖3為T_num對算法收斂性分析.

從圖3可以看出,對于5,8和10維目標(biāo)優(yōu)化問題,MOEA/D-RNS算法在DTLZ1-4系列測試問題上,T_num設(shè)置不同的值對算法收斂性影響很小;對于2維目標(biāo)優(yōu)化問題,MOEA/D-RNS算法在測試問題DTLZ1和DTLZ3上,T_num設(shè)置不同的值對算法收斂性影響較為明顯,T_num取16時,算法在測試函數(shù)DTLZ1上收斂性較好,而在測試函數(shù)DTLZ3上的收斂性卻相對要差.

綜上所述,在5維和10維目標(biāo)測試問題上,T_num取值不同對MOEA/D-RNS算法性能幾乎沒有影響;在2維目標(biāo)測試問題上,T_num取值對MOEA/D-RNS算法性能影響較大;在8維目標(biāo)測試問題上,T_num取值對測試問題DTLZ1影響較大,但對測試問題DTLZ2-4幾乎沒有影響.在我們后續(xù)的實(shí)驗(yàn)中,T_num設(shè)置成10.

4.4 ZDT1-4系列測試問題性能分析

為了驗(yàn)證使用重構(gòu)鄰域策略改變父代選擇方式的MOEA/D-RNS算法性能,測試算法在ZDT1-4系列測試函數(shù)上的GD指標(biāo)以及IGD指標(biāo),衡量改進(jìn)算法MOEA/D-RNS收斂性和綜合性能,對比結(jié)果如表3和表4所示,其中黑色加粗的數(shù)據(jù)表示對比結(jié)果中的最優(yōu)值,表格中STD(Standard deviation)為30次數(shù)據(jù)的標(biāo)準(zhǔn)差.

對MOEA/D-RNS及其對比算法在 ZDT系列測試函數(shù)上的 GD 指標(biāo)30次數(shù)據(jù),每10代取平均之后繪圖,GD指標(biāo)隨算法迭代代數(shù)變化(50-600代)的曲線如圖4所示,仿真結(jié)果顯示,在測試函數(shù)ZDT1(單模態(tài)的連續(xù)凸函數(shù))上,MOEA/D-RNS在種群搜索前期,收斂速度較快,并在350代之后趨于穩(wěn)定,算法優(yōu)于MOEA/D、MOEA/D-DE、MOEA/D-DU;在測試函數(shù)ZDT2(單模態(tài)的連續(xù)凹函數(shù))上,在算法收斂前期,相比于MOEA/D-DU、MOEA/D-DE和NSGA-Ⅲ,MOEA/D-RNS收斂速度較快,略差于MOEA/D;在測試函數(shù)ZDT3(多模態(tài)的不連續(xù)函數(shù))上,MOEA/D-RNS收斂速度優(yōu)于MOEA/D和MOEA/D-DU,但劣于NSGA-Ⅲ和MOEA/D-DE;在ZDT4(多模態(tài)的連續(xù)凸函數(shù))上,由于MOEA/D-RNS加入重構(gòu)鄰域策略,加快種群收斂速度,使種群快速收斂到前沿面,算法顯著優(yōu)于MOEA/D-DU、MOEA/D-DE,略優(yōu)于NSGA-Ⅲ.

圖3 T_num對算法收斂性影響分析

圖4 ZDT1-4 GD指標(biāo)值隨代數(shù)變化圖

另外一方面,從圖4(a)中可以看到,在ZDT1測試問題上,MOEA/D-DU算法在搜索后期出現(xiàn)了嚴(yán)重的種群退化現(xiàn)象,另外MOEA/D和NSGA-Ⅲ也在算法搜索過程中出現(xiàn)了不同程度種群退化的問題;從圖4(b)中可以看到MOEA/D在種群進(jìn)化過程中出現(xiàn)較為嚴(yán)重的種群退化問題.本文提出的MOEA/D-RNS有效改善了種群退化的問題,提升了算法收斂速度,從而使得算法在搜索后期將更多的計算資源用于種群多樣性提升.

從表3的IGD指標(biāo)對比可知,MOEA/D-RNS在測試函數(shù)ZDT1和ZDT2上綜合性能顯著優(yōu)于其他對比算法;在測試函數(shù)ZDT3上,MOEA/D-RNS顯著優(yōu)于MOEA/D-DE、NSGA-Ⅲ和MOEA/D,略優(yōu)于MOEA/D-DU;在測試函數(shù)ZDT4上,MOEA/D-RNS顯著優(yōu)于MOEA/D-DU、MOEA/D-DE和MOEA/D,略優(yōu)于NSGA-Ⅲ.說明加入了重構(gòu)鄰域策略的MOEA/D-RNS能有效改善解集的分布性和算法收斂性,因此相比于對比算法,MOEA/D-RNS算法求得的IGD指標(biāo)值更優(yōu).

表3 ZDT1-4系列測試函數(shù)在IGD指標(biāo)上的測試結(jié)果對比

Table 3 Test results Comparison of IGD indicator on ZDT1-4 test Functions

fMOEA/D-RNSMOEA/D-DUNSGA-IIIMOEA/D-DEMOEA/DMean(STD)Mean(STD)Mean(STD)Mean(STD)Mean(STD)ZDT14.3423e-3(8.17e-4)9.2061e-3(8.29e-3)6.8310e-3(9.52e-3)1.1428e-2(5.13e-3)1.1316e-2(7.85e-3)ZDT24.3423e-3(8.17e-4)5.9653e-2(9.41e-2)5.6148e-3(4.73e-3)9.6273e-3(3.32e-3)5.9777e-2(8.52e-2)ZDT31.0901e-2(5.14e-5)1.6811e-2(1.16e-2)4.3523e-2(5.72e-2)3.2702e-2(1.97e-2)2.9379e-2(2.18e-2)ZDT46.0437e-3(1.26e-3)2.4126e-2(1.62e-2)8.9931e-3(7.75e-3)2.1496e-2(1.20e-2)2.1707e-2(1.17e-2)

表4 ZDT1-4系列測試函數(shù)在GD指標(biāo)上的測試結(jié)果對比

Table 4 Test results comparison of GD indicator on ZDT1-4 test functions

fMOEA/D-RNSMOEA/D-DUNSGA-IIIMOEA/D-DEMOEA/DMean(STD)Mean(STD)Mean(STD)Mean(STD)Mean(STD)ZDT12.8703e-5(7.47e-6)1.8626e-4(5.40e-5)9.3503e-5(3.25e-5)1.0476e-3(5.25e-4)4.8025e-4(2.57e-4)ZDT23.8861e-5(4.97e-5)6.8304e-4(3.97e-4)7.4041e-5(3.03e-5)9.5857e-4(5.85e-4)8.0239e-4(5.73e-4)ZDT36.5362e-5(8.82e-5)2.7251e-4(8.99e-5)6.5537e-5(2.39e-5)1.5133e-3(9.70e-4)1.0193e-3(1.75e-3)ZDT42.7852e-4(1.71e-4)2.1187e-3(2.15e-3)2.8415e-4(2.01e-4)2.8782e-2(2.70e-2)2.9316e-3(3.12e-3)

4.5 DTLZ1-4系列測試問題性能分析

為了進(jìn)一步驗(yàn)證重構(gòu)鄰域策略在高維目標(biāo)優(yōu)化問題上的算法性能,采用GD、IGD指標(biāo)衡量MOEA/D-RNS及四種對比算法在2-10維目標(biāo)上的整體性能,對DTLZ1-4系列測試函數(shù)均運(yùn)行30次并取平均值作為最終的測試值,測試結(jié)果如表5、表6所示.

表5 DTLZ1-4系列測試函數(shù)在IGD指標(biāo)上測試結(jié)果對比

Table 5 Test results comparison of IGD indicator on DTLZ1-4 test functions

fMMOEA/D-RNSMOEA/D-DUNSGA-ⅢMOEA/D-DEMOEA/DMean(STD)Mean(STD)Mean(STD)Mean(STD)Mean(STD)DTLZ121.9512e-3(2.26e-4)1.9295e-3(2.20e-4)2.1353e-3(4.26e-4)2.3197e-3(1.92e-3)2.8352e-3(8.26e-4)31.9188e-2(1.57e-4)1.9197e-2(1.47e-4)1.9084e-2(1.22e-4)8.8421e-2(1.40e-1)1.9610e-2(5.20e-4)55.2793e-2(1.16e-4)5.3840e-2(6.01e-4)5.3074e-2(3.83e-4)7.1506e-1(5.94e-1)1.1173e-1(2.63e-4)89.0471e-2(2.56e-4)9.0463e-2(3.63e-4)1.0803e-1(3.53e-2)1.4081e-1(3.61e-3)1.5170e-1(2.75e-3)101.2216e-1(1.85e-3)1.2312e-1(1.87e-3)1.3706e-1(3.69e-2)3.4944e-1(2.32e-1)1.8269e-1(2.08e-2)DTLZ224.0691e-3(5.25e-5)4.1392e-3(7.48e-5)4.1707e-3(9.41e-5)4.1274e-3(4.73e-5)4.3403e-3(1.36e-4)35.3848e-2(8.33e-4)5.4779e-2(1.20e-3)5.1141e-2(1.93e-4)7.1479e-2(1.05e-3)6.7963e-2(6.39e-4)52.0134e-1(4.72e-3)2.0712e-1(4.95e-3)1.8589e-1(5.13e-3)4.3386e-1(3.22e-2)3.1804e-1(1.94e-3)83.1974e-1(1.16e-3)3.2095e-1(1.64e-3)3.3053e-1(4.19e-2)5.6291e-1(1.95e-2)5.4157e-1(1.31e-3)104.7920e-1(4.17e-3)4.9317e-1(4.01e-3)5.3919e-1(1.15e-1)7.1579e-1(4.67e-2)6.8061e-1(2.32e-2)DTLZ327.9587e-3(3.17e-3)6.4780e-2(2.13e-1)1.5401e-2(1.20e-2)2.4912e+0(4.14e+0)2.4025e-2(1.28e-2)35.2807e-2(1.25e-3)6.5839e-2(1.89e-2)5.3366e-2(3.87e-3)3.7475e+0(8.18e+0)3.5268e-1(6.75e-1)51.9411e-1(1.28e-2)4.0842e-1(3.87e-1)5.6281e+1(1.27e+1)1.4031e+1(1.38e+1)7.5186e-1(1.75e+0)83.1698e-1(1.10e-3)3.1851e-1(2.93e-3)5.0716e-1(6.02e-1)2.2590e+0(4.10e+0)5.5711e-1(8.13e-2)104.5369e-1(3.72e-3)4.7742e-1(1.21e-2)2.3889e+0(2.81e+0)7.8227e+0(1.23e+1)7.3956e-1(6.28e-2)DTLZ424.0866e-3(4.92e-5)4.1426e-3(6.87e-5)1.2722e-1(2.80e-1)6.0954e-3(1.66e-3)1.7760e-1(3.17e-1)35.4751e-2(1.14e-3)5.6133e-2(1.35e-3)1.4646e-1(2.27e-1)1.9102e-1(6.57e-2)5.2151e-1(3.12e-1)51.9359e-1(3.27e-3)2.0830e-1(2.88e-3)2.1819e-1(7.83e-2)4.3733e-1(2.92e-2)5.1677e-1(2.26e-1)83.3278e-1(2.50e-3)3.3783e-1(2.31e-3)3.6237e-1(6.37e-2)6.5478e-1(4.03e-2)6.4785e-1(1.66e-1)104.5202e-1(6.49e-4)4.5473e-1(1.21e-3)5.0502e-1(5.26e-2)7.6172e-1(3.20e-2)7.3044e-1(1.01e-1)

4.5.1 算法綜合性能(IGD)分析

從表5所示的IGD指標(biāo)測試結(jié)果來看,在測試函數(shù)DTLZ2、DTLZ3和DTLZ4上,MOEA/D-RNS在表中所給的所有目標(biāo)維度優(yōu)化問題上嚴(yán)格優(yōu)于所有對比算法;在測試函數(shù)DTLZ1上,對于3、5和10維目標(biāo)優(yōu)化問題,MOEA/D-RNS優(yōu)于所有對比算法,但對于2、8維這兩個目標(biāo)優(yōu)化問題,MOEA/D-RNS綜合性能(IGD)優(yōu)于MOEA/D-DE、MOEA/D和NSGA-Ⅲ,但劣于MOEA/D-DU.

說明在高維目標(biāo)優(yōu)化問題上,重構(gòu)鄰域策略能得到更高質(zhì)量的解集,使種群更快收斂到近似Pareto前沿面,能更好平衡算法收斂性和解集分布性,改善算法整體性能.

4.5.2 解集收斂性分析

表6 DTLZ1-4系列測試函數(shù)在GD指標(biāo)上測試結(jié)果對比

Table 6 Test results comparison of GD indicator on DTLZ1-4 test functions

fMMOEA/D-RNSMOEA/D-DUNSGA-ⅢMOEA/D-DEMOEA/DMean(STD)Mean(STD)Mean(STD)Mean(STD)Mean(STD)DTLZ125.3127e-5(4.70e-5)4.9548e-5(4.45e-5)8.6408e-5(7.32e-5)8.9595e-5(2.19e-4)1.7180e-4(1.22e-4)32.1613e-4(5.16e-5)2.1456e-4(4.07e-5)2.0437e-4(3.91e-5)1.4580e-2(3.61e-2)5.7574e-4(1.61e-4)59.6515e-4(1.96e-5)9.8608e-4(1.73e-4)1.0471e-3(1.84e-5)1.2707e+0(5.03e-1)1.0903e-3(2.35e-5)81.5151e-2(4.58e-2)5.9758e-2(1.20e-1)3.5133e-2(8.87e-2)8.9715e-2(8.93e-2)3.1293e-2(5.94e-2)102.1892e-3(1.20e-4)2.2725e-3(9.80e-5)1.7131e-1(2.68e-1)4.0333e-1(2.82e-1)2.8703e-3(1.13e-4)DTLZ221.7153e-5(4.33e-6)2.6257e-5(5.49e-6)5.0440e-5(1.38e-5)7.0171e-5(9.58e-6)2.6100e-5(1.97e-5)34.6578e-4(1.94e-5)4.6858e-4(1.78e-5)6.5389e-4(4.68e-5)1.6326e-3(1.95e-4)6.8120e-4(6.21e-5)52.8013e-3(6.27e-5)3.2696e-3(2.20e-4)5.9351e-3(6.42e-4)1.6477e-2(2.80e-3)3.8768e-3(2.48e-4)89.4810e-3(6.26e-4)1.0507e-2(2.93e-4)1.3150e-2(7.67e-4)1.7856e-2(1.41e-3)1.6602e-2(1.68e-4)105.3196e-3(4.35e-4)5.7067e-3(5.00e-4)1.1947e-2(1.52e-3)1.8114e-2(1.58e-3)9.6151e-3(3.91e-4)DTLZ325.9767e-4(3.83e-4)1.0681e-2(3.46e-2)2.8292e-3(9.29e-3)5.4706e-1(9.74e-1)8.0034e-4(1.58e-3)37.6258e-4(2.37e-4)4.3217e-3(9.76e-3)1.2808e-3(7.52e-4)5.5718e-1(1.24e+0)4.2392e-2(9.00e-2)53.6635e-3(2.63e-3)3.9711e-2(4.86e-2)1.2597e+1(1.81e+0)7.1299e+0(1.90e+0)8.4046e-2(2.38e-1)81.2013e-2(1.06e-4)9.0417e-2(1.87e-1)2.8297e-1(6.33e-1)6.0520e-1(1.19e+0)1.8357e-2(1.37e-3)106.2853e-3(2.59e-4)1.0985e-2(1.25e-2)1.9017e+0(2.20e+0)2.8382e+0(2.27e+0)1.4387e-2(1.88e-3)DTLZ421.8463e-5(4.12e-6)2.9708e-5(5.77e-6)5.0329e-5(2.23e-5)1.8521e-4(1.27e-4)5.4556e-5(1.50e-4)34.5385e-4(1.92e-5)4.6494e-4(1.86e-5)6.0539e-4(1.56e-4)1.2740e-3(6.62e-4)3.1899e-4(2.13e-4)52.8130e-3(4.99e-5)2.9555e-3(8.82e-5)6.2451e-3(8.39e-4)5.3922e-3(1.28e-3)2.9445e-3(7.68e-4)89.0966e-3(2.20e-4)8.6040e-3(2.08e-4)1.2813e-2(1.04e-3)7.9923e-3(6.97e-4)8.8173e-3(2.89e-3)104.0594e-3(3.01e-4)4.1642e-3(3.17e-4)1.2839e-2(3.27e-3)6.5094e-3(1.82e-3)4.9143e-3(8.13e-4)

從表6的GD指標(biāo)測試結(jié)果來看,在測試函數(shù)DTLZ1上,對于5、8、10維目標(biāo)優(yōu)化問題,MOEA/D-RNS均優(yōu)于其他四種對比算法,對于2、3維目標(biāo)優(yōu)化問題,MOEA/D-RNS優(yōu)于NSGA-Ⅲ、MOEA/D-DE和MOEA/D,略差于MOEA/D-DU.在測試函數(shù)DTLZ2和DTLZ3上,MOEA/D-RNS對于2-10維目標(biāo)優(yōu)化問題均優(yōu)于所有對比算法.在測試函數(shù)DTLZ4上,對于2、5、10維目標(biāo)優(yōu)化問題,MOEA/D-RNS嚴(yán)格優(yōu)于其他對比算法;對于3維目標(biāo)優(yōu)化問題,MOEA/D-RNS優(yōu)于MOEA/D-DU、NSGA-Ⅲ和MOEA/D-DE,但劣于MOEA/D;對于8維目標(biāo)優(yōu)化問題,MOEA/D-RNS優(yōu)于NSGA-Ⅲ,劣于其他對比算法.

這是由于測試函數(shù)DTLZ1及DTLZ3屬于復(fù)雜多模態(tài)測試函數(shù),并且在目標(biāo)空間中,初始種群離真實(shí)Pareto前沿面較遠(yuǎn),算法收斂到近似Pareto前沿所需迭代代數(shù)較多,在這類測試函數(shù)上,MOEA/D-RNS算法重構(gòu)鄰域策略算法搜索過程中加快種群收斂的效果較為明顯,MOEA/D-RNS算法重構(gòu)鄰域策略在整個種群中挑選精英解集,在精英解集和鄰域子集組成的新鄰域中挑選父代,使整個種群都盡可能地與優(yōu)秀的個體進(jìn)行交叉變異,進(jìn)而改善后代解集的質(zhì)量,從而加速種群收斂.特別是在測試函數(shù)DTLZ3上,對于2、3、5、10維目標(biāo)優(yōu)化問題,MOEA/D-RNS算法GD指標(biāo)值遠(yuǎn)遠(yuǎn)優(yōu)于其他對比算法,說明在此測試函數(shù)上,改進(jìn)算法MOEA/D-RNS加快種群收斂速度和改善種群退化狀況效果較為顯著.

4.6 策略有效性分析

通過ZDT1-4和DTLZ1-4系列測試問題分析說明:加入了垂直距離更新策略的MOEA/D-DU與MOEA/D-RNS相比于MOEA/D-DE、MOEA/D和NSGA-Ⅲ這三種對比算法,能夠有效改善算法在高維目標(biāo)優(yōu)化問題中解偏離搜索方向的問題,有效平衡算法的收斂性與多樣性.MOEA/D-DU在搜索過程中存在種群退化的問題,加入了重構(gòu)鄰域策略的MOEA/D-RNS有效解決此問題,使得種群更快逼近Pareto前沿面,提升了算法收斂速度,從而也使得在算法搜索過程中有更多的計算資源用于提升種群多樣性.

5 總 結(jié)

本文結(jié)合垂直距離更新策略,提出了一種分兩步篩選精英解集的方式,在不改變鄰域規(guī)模的前提下改變了交叉變異操作中的父代選擇方式,改善了父代解集質(zhì)量,加快了種群收斂到Pareto前沿的速度,保持種群多樣性,提高了算法整體性能.測試結(jié)果表明使用了重構(gòu)鄰域策略的MOEA/D-RNS,在初始種群距離已知的Pareto前沿面較遠(yuǎn)時收斂效果顯著,同時保證了解集的多樣性,并且在高維目標(biāo)優(yōu)化問題上重構(gòu)鄰域策略仍能較好的提升算法整體性能.重構(gòu)鄰域策略不僅在MOEA/D-DU上適用,在其他分解算法上仍能對算法有較好的性能提升效果.