一種基于目標(biāo)空間轉(zhuǎn)換權(quán)重求和的超多目標(biāo)進(jìn)化算法

梁正平 駱婷婷 王志強,2 朱澤軒 胡凱峰

現(xiàn)實應(yīng)用中存在各種各樣的多目標(biāo)優(yōu)化問題(Multi-objective optimization problems,MOPs),如電能分配[1]、污水處理控制[2]、服務(wù)質(zhì)量優(yōu)化[3]、車輛路徑規(guī)劃[4]、軟件項目管理[5]、微電網(wǎng)管理[6],等等.由于MOPs 的不同目標(biāo)函數(shù)之間通常相互沖突,MOPs 的最優(yōu)解集不是單一的解而是一組折衷解,即帕累托最優(yōu)解集(Pareto optimal set).雖然一些性能優(yōu)越的多目標(biāo)進(jìn)化算法(Multi-objective evolutionary algorithms,MOEAs),如NSGA-II[7],SPEA2[8]和MOEA-PPF[9]等能很好的處理MOPs,但在解決超多目標(biāo)優(yōu)化問題(Many-objective optimization problems,MaOPs)時,上述算法的性能將顯著下降.原因是隨著目標(biāo)函數(shù)的增加,非支配個體在種群中所占的比例將呈指數(shù)式增長,基于帕累托關(guān)系的算法會逐漸喪失收斂壓力[10].為解決該問題,學(xué)術(shù)界從不同角度對超多目標(biāo)進(jìn)化算法(Manyobjective evolutionary algorithms,MaOEAs) 進(jìn)行了較廣泛的探討[11-15],大致可分為以下四類:1) 基于放松支配.該類算法的主要思想是通過擴(kuò)大支配范圍來增強種群往PF 方向收斂的壓力.代表性方法有?支配[16],L支配[17]和模糊支配[18-19]等;2) 基于指標(biāo).該類算法將個體的指標(biāo)值作為環(huán)境選擇的衡量標(biāo)準(zhǔn),如IBEA[20],HypE[21]和ARMOEA[22]等;3) 基于分解.該類算法將MaOPs 分解為多個單目標(biāo)優(yōu)化問題(Single-objective optimization problems,SOPs)[23],隨后在進(jìn)化框架下同時優(yōu)化這些SOPs,如MOEA/D[24],NSGAIII[25]和SPEAR[26]等.4)混合型.該類算法采用兩種或者兩種以上的方法來實現(xiàn)對超多目標(biāo)問題的優(yōu)化,如Two_arch2[27]和HpaEA[28]均融合了基于支配和基于指標(biāo)的方法,SRA[29]則采用了多指標(biāo)的策略.在上述算法中,基于分解的MaOEAs 受到了學(xué)術(shù)界的高度關(guān)注,該類算法的核心是對參考向量和分解方法的設(shè)計.

參考向量主要影響種群在PF 上分布的均勻性,即多樣性.在經(jīng)典的分解類算法MOEA/D 中,采用一組均勻分布在目標(biāo)空間上的向量集作為參考向量.該參考向量在規(guī)則PF 問題上能取得優(yōu)越的性能,但不能很好地處理退化、不連續(xù)、凹凸混合等不規(guī)則PF 問題.原因在于不規(guī)則PF 上參考向量的分布不均勻,進(jìn)而造成種群在PF 上分布不均勻.針對該問題,學(xué)術(shù)界提出了很多對均勻分布的參考向量進(jìn)行調(diào)整的方法,如CA-MOEA[30]通過層次聚類方法來調(diào)整每代的參考向量,MOEA-AWA[31]則根據(jù)種群中的精英個體來對參考向量進(jìn)行調(diào)整,類似的調(diào)整方法還有g(shù)-DBEA[32]和DDEANS[33]等.然而,由于頻繁調(diào)整參考向量,參考向量調(diào)整類算法的性能在處理規(guī)則PF 問題時容易惡化[34].

分解方法主要影響種群的搜索效率,即收斂性.現(xiàn)有研究表明[35-37],切比雪夫方法可有效處理各種PF 形狀的問題但搜索效率很低,權(quán)重求和方法雖然不能處理好非凸PF 問題但搜索效率卻很高.為此,Ishibuchi 等提出了兩種改進(jìn)方案,分別為自適應(yīng)切比雪夫和權(quán)重求和方法AS[37],同時使用切比雪夫和權(quán)重求和方法SS[38],以綜合切比雪夫和權(quán)重求和各自的優(yōu)勢.此外,Wang 等提出了局部權(quán)重求和方法LWS[39],在綜合性能上取得了顯著的效果.但由于LWS 加入了局部的思想,一定程度上降低了權(quán)重求和方法的搜索效率.

總體而言,雖然學(xué)術(shù)界已對基于分解的MaOEAs進(jìn)行了較廣泛研究,但該類方法的性能仍存在較大提升空間.為盡可能不損害權(quán)重求和方法搜索效率高的優(yōu)勢,同時又能處理好各類PF 為非凸型的問題,本文從改進(jìn)現(xiàn)有分解方法的角度,提出了一種基于目標(biāo)空間轉(zhuǎn)換權(quán)重求和的超多目標(biāo)進(jìn)化算法,簡稱NSGAIII-OSTWS.其中目標(biāo)空間轉(zhuǎn)換權(quán)重求和(Objective space transformation based weighted sum,OSTWS)將各種類型問題的PF 轉(zhuǎn)換為凸型曲面,再利用權(quán)重求和方法對問題進(jìn)行優(yōu)化.具體地,首先利用預(yù)估PF 的形狀計算個體到預(yù)估PF 的距離;然后,根據(jù)該距離值將個體映射到目標(biāo)空間中預(yù)估凸型曲面與理想點之間的對應(yīng)位置;最后,采用權(quán)重求和函數(shù)計算出映射后個體的適應(yīng)值,據(jù)此實現(xiàn)對問題的優(yōu)化.為驗證OSTWS的有效性,本文在NSGAIII 框架的基礎(chǔ)上,將OSTWS 與現(xiàn)有的7 個分解方法在WFG、DTLZ 和LSMOP 測試問題集上進(jìn)行了對比,同時將所提的NSGAIII-OSTWS 與9 個具有代表性的MaOEAs 進(jìn)行了對比,實驗結(jié)果表明NSGAIII-OSTWS具備良好的競爭性能.

本文的內(nèi)容安排如下.第1 節(jié)介紹與本文相關(guān)的背景知識.第2 節(jié)闡述目標(biāo)空間轉(zhuǎn)換權(quán)重求和方法OSTWS,以及基于OSTWS 的超多目標(biāo)進(jìn)化算法NSGAIII-OSTWS.第3 節(jié)介紹實驗設(shè)計、實驗結(jié)果,并進(jìn)行相關(guān)討論.最后對本文進(jìn)行總結(jié)并指出未來的研究方向.

1 背景知識

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

一般來說,一個MOP 的數(shù)學(xué)定義可表述為:

其中,x是決策空間 Ω 中的n維決策向量,m是目標(biāo)函數(shù)的個數(shù),Rm是目標(biāo)空間.F:Ω→Rm組成m個目標(biāo)函數(shù).目標(biāo)數(shù)m大于3 的MOPs 也被稱為超多目標(biāo)優(yōu)化問題,即MaOPs.假設(shè)x和y是決策空間中的兩個不同候選解,x支配y(記為x?y) 當(dāng)且僅當(dāng)?i∈{1,2,···,m},fi(x)≤fi(y) 且?i ∈{1,2,···,m},fi(x)＜fi(y).如果候選解x不被任何其他解所支配,則稱候選解x為帕累托最優(yōu)解.所有帕累托最優(yōu)解的集合稱為帕累托最優(yōu)解集(Pareto optimal set,PS),即PS={x/?y ∈Ω,x ?y}.所有帕累托最優(yōu)解對應(yīng)的目標(biāo)向量構(gòu)成帕累托最優(yōu)前沿(Pareto optimal front,PF),即PF={F(x)|x ∈PS}.

1.2 分解方法

分解方法決定了基于分解的MaOEAs 的搜索效率,對算法的性能有著重要影響.研究者們設(shè)計了許多不同的分解方法,并在各種MaOPs 上展現(xiàn)出了優(yōu)越的性能.常見的分解方法有以下三種:

1)權(quán)重求和(Weighted sum,WS)法:WS 方法通過加權(quán)的方式將所有目標(biāo)組合成一個單一的目標(biāo),其數(shù)學(xué)定義如下:

2)切比雪夫(Techebycheff,TCH)法:TCH 方法將MaOP 轉(zhuǎn)化為一個SOP 的數(shù)學(xué)定義如下:

3)基于懲罰的邊界交叉(Penalty-based boundary intersection,PBI)法:PBI 方法構(gòu)造子問題的數(shù)學(xué)定義如下:

其中,θ(θ＞0) 為一個事先設(shè)定的懲罰因子,d1為向量 (F(x)-z*) 在權(quán)重向量w上的投影長度,d2為F(x)到w的垂直距離.圖1(c)為PBI 方法的示意圖.由PBI 的定義(式(4)) 和圖1(c) 可知,θ是平衡收斂性(用d1衡量)和多樣性(用d2衡量)的關(guān)鍵性參數(shù).近來有研究表明[43-44],當(dāng)PBI 處理PF為凸的問題時,較大的θ可以獲得較好的種群分布,而較小的θ值有利于種群更好地收斂到PF.

圖1 分解方法WS,TCH 和PBI 在參考向量w 上的二維示意圖,其中虛線為等高線Fig.1 Illustration of the decomposition methods WS,TCH and PBI on reference vector w,where dashed lines are contour lines

2 NSGAIII-OSTWS 算法

2.1 動機

在基于分解的算法中,分解方法將MaOP 轉(zhuǎn)化為若干個SOPs,然后在進(jìn)化框架下以協(xié)同的方式優(yōu)化每個SOPs.如果沒有選擇合適的分解方法,或者使用的分解方法不能很好地將MaOP 轉(zhuǎn)化為SOPs,基于分解的MaOEAs 最終獲得的種群就有可能無法逼近PF.

目前,上節(jié)介紹的三種分解方法,即WS、TCH和PBI,已在基于分解的MaOEAs 中被廣泛應(yīng)用.圖1 是這三種方法在二維目標(biāo)空間下的示意圖.每個子圖中的等高線將目標(biāo)空間劃分為兩個區(qū)域,位于同一條等高線上的解具有相同的質(zhì)量,靠近理想點z*區(qū)域的解質(zhì)量則要優(yōu)于另外一區(qū)域.如圖1(a)所示,WS 的等高線是一條經(jīng)過候選解且垂直于參考向量的直線,其優(yōu)越區(qū)域[39]占整個區(qū)域的1/2.從圖1(b)可以看出,TCH 的等高線則為經(jīng)過候選解和參考向量的兩條相互垂直的直線,其優(yōu)越區(qū)域為 1/ 2m,隨著目標(biāo)函數(shù)m的增加,該值會顯著減小.圖1(c)中,PBI 的等高線是經(jīng)過候選解和參考向量的兩條相交直線,它的優(yōu)越區(qū)域由懲罰因子θ決定.θ值越大,則優(yōu)越區(qū)域的面積越小,通常情況下該區(qū)域的面積小于整個區(qū)域面積的1/2.由上述分析可知,WS 的優(yōu)越區(qū)域是最大的.換言之,采用WS 可以更大概率搜索到比目前更優(yōu)的解,即收斂速度最快.然而,當(dāng)采用WS 處理非凸問題時,PF 中的大部分點會被丟失[24],從而嚴(yán)重?fù)p失種群的多樣性[39].綜上所述,相比TCH 和PBI 而言,WS 具有更強的收斂性但卻不能處理好非凸問題.

為充分發(fā)揮WS 搜索效率高的優(yōu)勢,同時又能處理好各類PF 形狀為非凸的問題,研究者們提出了一些WS 的改進(jìn)方法,如AS[37]和SS[38]等.然而,這些方法的主要思想僅是利用TCH 方法來處理WS 不能處理好的凸型PF 問題,并未對WS 方法本身進(jìn)行改進(jìn).最近,Wang 等[39]提出了一種新穎的WS 方法,即局部權(quán)重求和方法LWS.該方法的主要思想是對于每個搜索方向,只在其相鄰解中挑選最優(yōu)解.LWS 方法能夠較好處理包括PF 非凸在內(nèi)的各類型PF 問題,但由于LWS 在求解最優(yōu)解時加入了局部的思想,也在一定程度上降低了WS方法搜索效率高的優(yōu)勢.為驗證該結(jié)論,本文將LWS 方法和WS 方法分別嵌入到基于分解的算法NSGAIII[25],形成算法NSGAIII-WS 和NSGAIIILWS.圖2 為這兩個算法在PF 為凸的測試問題ZDT1[45]上的最終種群分布圖.其中,運行次數(shù)為20 次,迭代次數(shù)為120 代,種群大小為200,決策變量數(shù)的大小參照文獻(xiàn)[45]設(shè)置,其它參數(shù)與NSGAIII保持一致.從圖2 可以看出,NSGAIII-WS 算法獲得的種群具有更好的收斂性.為盡可能發(fā)揮權(quán)重求和方法搜索效率高的優(yōu)勢,同時又能處理好非凸型PF 問題,本文提出了一種新穎的方法——目標(biāo)空間轉(zhuǎn)換權(quán)重求和方法.

圖2 NSGAIII-WS 和NSGAIII-LWS 算法在ZDT1上獲得的最終種群分布Fig.2 The final population distribution obtained by NSGAIII-WS and NSGAIII-LWS algorithm on ZDT1

2.2 目標(biāo)空間轉(zhuǎn)換權(quán)重求和方法

目標(biāo)空間轉(zhuǎn)換權(quán)重求和方法OSTWS 的核心思想,是將各種問題的PF 轉(zhuǎn)換為凸型曲面,并基于該凸型曲面進(jìn)行求解.OSTWS 方法的偽代碼如算法1 所示.

首先,采用NSGAIII[25]中的歸一化策略對種群U進(jìn)行歸一化處理,然后利用2REA[46]中的估PF 方法預(yù)估出PF 的形狀.種群歸一化的目的是維持種群的多樣性.在進(jìn)化前期,由于種群中的大部分個體并未收斂到PF,歸一化會存在較大的誤差,但在進(jìn)化后期,大部分個體都已靠近或收斂到PF,此時種群歸一化所帶來的誤差會逐漸降低.預(yù)估的過程是先選取一組候選曲率p值逐一計算種群中非支配個體到理想點的Lp范式值,并據(jù)此計算出各p值所對應(yīng)的標(biāo)準(zhǔn)方差.方差越小,代表該p值所對應(yīng)的曲面越能擬合當(dāng)前種群的分布.最終選取具有最小方差的p值所對應(yīng)的曲面作為預(yù)估的PF 形狀.之后,將種群中的所有個體映射到所預(yù)估的PF 上,映射公式如下:

接下來,以原點作為理想點,分別計算原始個體與映射個體到理想點之間的歐氏距離值d1(x)和d2(x),并將d1(x) 減去d2(x),以此得到目標(biāo)空間轉(zhuǎn)換所需的距離值d(x).隨后,根據(jù)d(x)值將個體轉(zhuǎn)換到目標(biāo)空間中凸曲面與理想點之間對應(yīng)的位置,從而完成目標(biāo)空間的轉(zhuǎn)換.具體的做法是以等距離d(x)的形式將原始種群中的所有個體映射到預(yù)設(shè)的凸曲面內(nèi).預(yù)設(shè)凸曲面的定義如下:

其中,[f1(x),f2(x),···,fm(x)]為預(yù)設(shè)凸曲面上的一個向量,C為預(yù)設(shè)凸曲面的曲率值,種群中個體映射到預(yù)設(shè)凸曲面內(nèi)的數(shù)學(xué)公式如下:

最后,將最小化求解問題轉(zhuǎn)化為最大化求解問題并采用WS 方法計算出目標(biāo)空間轉(zhuǎn)換后個體的適應(yīng)值,適應(yīng)值越大代表個體越優(yōu)秀.

為更直觀地展示OSTWS 方法,圖3 示例了使用OSTWS 方法將線形、凸形和凹形PF 中的個體轉(zhuǎn)換到凸目標(biāo)空間的整個過程.以3(a)為例,首先,預(yù)估出真實PF 的形狀(直線),并將種群中的所有個體(a,b,c)映射到直線上(a＇,b＇,c＇),然后計算出原始個體(a,b,c)與映射后個體(a＇,b＇,c＇)之間的歐氏距離值d1,d2,d3.值得注意的是,距離值(d1,d2,d3)具有正負(fù)之分,如果原始個體到理想點的歐氏距離大于映射后個體到理想點的歐氏距離,則上述距離值為正,否則為負(fù).接下來,將原始種群中的所有個體(a,b,c)以等距離 (d1,d2,d3)形式映射到預(yù)設(shè)凸曲線內(nèi),完成種群到凸目標(biāo)空間的轉(zhuǎn)換,轉(zhuǎn)換后的個體為a′′,b′′,c′′.最后,采用WS方法逐一計算個體(a′′,b′′,c′′) 的適應(yīng)值,適應(yīng)值越大的個體被挑選到下一代進(jìn)化過程中的概率也越大.

圖3 OSTWS 方法將PF 形狀為線形(a),凸形(b)和凹形(c)種群中的個體轉(zhuǎn)換到凸目標(biāo)空間的整個過程Fig.3 The whole process of transforming the population individuals from linear (a),convex (b) and concave(c) into convex objective space by OSTWS method

2.3 將OSTWS 方法整合到NSGAIII 中

在進(jìn)化算法領(lǐng)域,MOEA/D 和NSGAII 是兩個基于分解的經(jīng)典算法,NSGAIII 則是NSGAII 在高維目標(biāo)空間下的改進(jìn)版.相比MOEA/D,NSGAIII 專門針對MaOPs,且在高維空間下能夠更好地維持種群的多樣性[25,47-48].為公平比較各種分解方法在處理MaOPs 時的有效性,本文選擇NSGAIII作為基礎(chǔ)算法,并將OSTWS 方法嵌入NSGAIII形成新的算法NSGAIII-OSTWS,算法2 為其偽代碼.首先,初始化規(guī)模為N的種群U和參考向量W,然后對種群U進(jìn)化過程,直至算法達(dá)到最大迭代次數(shù).

算法2.NSGAIII-OSTWS 算法

2.4 時間復(fù)雜度分析

時間復(fù)雜度是衡量算法性能的一個重要方面,影響算法的整體計算開銷.下面根據(jù)NSGAIII-OSTWS 的主要流程對其時間復(fù)雜度進(jìn)行詳細(xì)分析.算法2 第4 行的子代個體生成中,二進(jìn)制交叉和多項式變異需要O(DN)的計算開銷,其中D為決策變量的數(shù)量.算法2 第6 行對規(guī)模為2N的種群進(jìn)行非支配層排序要花費O(Nlogm-2N)[25]的計算代價.算法2 第15 行,即算法1,其計算開銷包括以下四方面:1) 將規(guī)模為2N的種群進(jìn)行歸一化(算法1 第1 行),需要O(mN) 的計算開銷.2)計算出2N個個體到預(yù)設(shè)曲面的距離(算法1 第4～7行),需要O(mN) 的計算開銷.3) 將2N個個體的目標(biāo)空間轉(zhuǎn)換到特定曲面內(nèi)(算法1 第8～9 行),需要O(mN)的計算開銷.4)計算目標(biāo)空間轉(zhuǎn)換后2N個個體到參考向量W的權(quán)重求和值(算法1 第10～12 行),需要O(mN|W|) 的計算開銷,其中|W|是參考向量的個數(shù).因此,算法1 的時間復(fù)雜度為O(mN|W|).之后,在最壞情況下NSGAIII-OSTWS 需對2N個個體進(jìn)行參考向量的歸屬,此時需要花費O(mN|W|) 的計算代價.最后,NSGAIIIOSTWS 需挑選N-|Up |個個體至下一代進(jìn)化過程需要O(L|W|) 的計算量,其中L=|Fl|.此外,在通常情況下,N≈|W|,N＞m.考慮到以上因素和計算結(jié)果,NSGAIII-OSTWS 的時間復(fù)雜度為Max(O(DN),O(mN|W|)).

3 實驗與分析

3.1 實驗設(shè)置

1) 測試問題和評價指標(biāo)

為檢驗NSGAIII-OSTWS 的性能,本文選取了超多目標(biāo)優(yōu)化領(lǐng)域中使用最為廣泛的兩組測試問題集WFG[51]、DTLZ[52]和最新的大規(guī)模決策變量測試問題集LSMOP[53].在DTLZ 中,DTLZ8-9 為帶約束的問題,因此本文只考慮對DTLZ1-7 問題的研究.參照文獻(xiàn)[39],WFG 和DTLZ 中的決策變量數(shù)目統(tǒng)一設(shè)置為D=100,其中WFG 中的位置變量數(shù)設(shè)為k=m-1.LSMOP 的相關(guān)參數(shù)與原文[53]保持一致.

為定量評估算法的求解性能,分別采用世代距離(Generational distance,GD[54]),覆蓋PF(Coverage over the pareto front,CPF[55]) 和修正的反轉(zhuǎn)世代距離(Modified inverted generational distance,IGD+[56]) 進(jìn)行收斂性、多樣性和綜合性(平衡收斂性和多樣性的能力)性能衡量,其計算公式分別如下:

其中U為算法輸出的最終種群,A為測試問題PF面上的一組均勻參考點.對于目標(biāo)維度不相同的縮放問題(如:WFG),在計算GD 和IGD+指標(biāo)之前需對A和U進(jìn)行歸一化處理[48].GD 和IGD+值越小,代表算法的性能越好.參照文獻(xiàn)[57],本實驗設(shè)置計算GD 和IGD+所需的參考點數(shù)為10 000.

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

由于分解算法的種群規(guī)模取決于參數(shù)H和m,其中H為沿每個目標(biāo)軸所考慮的分區(qū).為公平起見,本章所測試的目標(biāo)維度及其對應(yīng)的種群大小統(tǒng)一設(shè)置為表1 所示.為避免參考向量分布不均勻的情況,當(dāng)m＞5 時,本文采用兩層參考向量生成方法生成參考向量[58].交叉和變異操作所需的參數(shù)設(shè)置如表2 所示.在NSGAIII-OSTWS 中,曲率C值的參數(shù)經(jīng)驗設(shè)置為2,其影響在實驗分析部分進(jìn)行研究.比較算法的其他參數(shù)設(shè)置與其原始論文保持一致.所有算法的終止準(zhǔn)則被指定為最大迭代次數(shù)(MAXGen),本文中所有測試問題的MAXGen 設(shè)為300.每個算法在每個測試問題上獨立運行20 次.為檢驗算法性能的顯著性差異,采用Wilcoxon[59]秩和檢驗來評估一種算法在GD 或IGD+值方面是否優(yōu)于另一種算法.符號 “+”,“-” 和 “≈”表示相應(yīng)的競爭算法在5%的顯著性水平上分別比所提算法NSGAIII-OSTWS 更好,更差和無統(tǒng)計性差異.

表1 種群大小設(shè)置Table 1 Setting of the population size

表2 交叉變異參數(shù)設(shè)置Table 2 Parameter settings for crossover and mutation

3.2 實驗結(jié)果與分析

1) OSTWS 方法的有效性驗證

為驗證目標(biāo)空間轉(zhuǎn)換權(quán)重求和方法(OSTWS)的有效性,本小節(jié)將OSTWS 方法與其他7 個分解方法,即切比雪夫方法(TCH)、懲罰邊界交叉方法(PBI[24])、局部權(quán)重求和方法(LWS[39])、自適應(yīng)切比雪夫和權(quán)重求和方法(AS[37])、同時使用切比雪夫和權(quán)重求和方法(SS[38])、自適應(yīng)Lp 方法(PaS[36]) 和自適應(yīng)懲罰方法(APS[60]) 在算法NSGAIII 的框架上進(jìn)行比較實驗.表3、表4 和表5 分別統(tǒng)計了上述分解方法在DTLZ1-DTLZ7、WFG1-WFG9 和LSMOP1-LSMOP9 測試問題上所獲得的GD 均值和標(biāo)準(zhǔn)差(括號內(nèi)為標(biāo)準(zhǔn)差),其中每個問題的最佳結(jié)果以灰色背景突出顯示.圖4為各個算法在所有測試問題上的平均IGD+表現(xiàn)分,分值越小表示該算法整體性能越好.

圖4 NSGAIII-OSTWS,NSGAIII-LWS,NSGAIII-TCH,NSGAIII-PBI,NSGAIII-AS,NSGAIII-SS,NSGAIII-APS和NSGAIII-PaS,在所有測試問題實例中的平均IGD+性能得分排名.得分越小,整體性能越好Fig.4 Ranking in the average performance score over all test problem instances for the algorithms of NSGAIII-OSTWS,NSGAIII-LWS,NSGAIII-TCH,NSGAIII-PBI,NSGAIII-AS,NSGAIII-SS,NSGAIII-APS and NSGAIII-PaS.The smaller the score,the better the overall performance in terms of IGD+

由表3、表4 和表5 可以看出,NSGAIII-OSTWS 在絕大部分DTLZ 測試問題上都取得了最佳GD 均值,此外,雖然NSGAIII-OSTWS 沒能在所有的WFG 和LSMOP 測試問題中獲得最具競爭力的GD 性能,但總體上獲得了最優(yōu)的性能,這表明本文所提出的OSTWS 方法是非常有效的,原因在于充分利用了WS 方法搜索效率高的優(yōu)勢.

表3 OSTWS,LWS,TCH,PBI,AS,SS,PaS 和APS 方法在框架為NSGAIII,測試問題為DTLZ1-7 上獲得的GD 值統(tǒng)計結(jié)果(均值和標(biāo)準(zhǔn)差).每個實例算法中的最好結(jié)果以加粗突出顯示Table 3 The statistical results (mean and standard deviation) of the GD values obtained by OSTWS,LWS,TCH,PBI,AS,SS,PaS and APS methods on the NSGAIII framework and DTLZ1-7 test problems.The best average value among the algorithms for each instance is highlighted in bold

表3 OSTWS,LWS,TCH,PBI,AS,SS,PaS 和APS 方法在框架為NSGAIII,測試問題為DTLZ1-7 上獲得的GD 值統(tǒng)計結(jié)果(均值和標(biāo)準(zhǔn)差).每個實例算法中的最好結(jié)果以加粗突出顯示 (續(xù)表)Table 3 The statistical results (mean and standard deviation) of the GD values obtained by OSTWS,LWS,TCH,PBI,AS,SS,PaS and APS methods on the NSGAIII framework and DTLZ1-7 test problems.The best average value among the algorithms for each instance is highlighted in bold (continued table)

表4 OSTWS,LWS,TCH,PBI,AS,SS,PaS 和APS 方法在框架為NSGAIII,測試問題集為WFG1-9 上獲得的GD 值統(tǒng)計結(jié)果(均值和標(biāo)準(zhǔn)差).每個實例算法中的最好結(jié)果以加粗突出顯示Table 4 The statistical results (mean and standard deviation) of the GD values obtained by OSTWS,LWS,TCH,PBI,AS,SS,PaS and APS methods on the NSGAIII framework and WFG1-9 test problems.The best average value among the algorithms for each instance is highlighted in bold

表4 OSTWS,LWS,TCH,PBI,AS,SS,PaS 和APS 方法在框架為NSGAIII,測試問題集為WFG1-9 上獲得的GD 值統(tǒng)計結(jié)果(均值和標(biāo)準(zhǔn)差).每個實例算法中的最好結(jié)果以加粗突出顯示 (續(xù)表)Table 4 The statistical results (mean and standard deviation) of the GD values obtained by OSTWS,LWS,TCH,PBI,AS,SS,PaS and APS methods on the NSGAIII framework and WFG1-9 test problems.The best average value among the algorithms for each instance is highlighted in bold (continued table)

表4 OSTWS,LWS,TCH,PBI,AS,SS,PaS 和APS 方法在框架為NSGAIII,測試問題集為WFG1-9 上獲得的GD 值統(tǒng)計結(jié)果(均值和標(biāo)準(zhǔn)差).每個實例算法中的最好結(jié)果以加粗突出顯示 (續(xù)表)Table 4 The statistical results (mean and standard deviation) of the GD values obtained by OSTWS,LWS,TCH,PBI,AS,SS,PaS and APS methods on the NSGAIII framework and WFG1-9 test problems.The best average value among the algorithms for each instance is highlighted in bold (continued table)

表5 OSTWS,LWS,TCH,PBI,AS,SS,PaS 和APS 方法在框架為NSGAIII,測試問題集為LSMOP1-9 上獲得的GD 值統(tǒng)計結(jié)果(均值和標(biāo)準(zhǔn)差).每個實例算法中的最好結(jié)果以加粗突出顯示Table 5 The statistical results (mean and standard deviation) of the GD values obtained by OSTWS,LWS,TCH,PBI,AS,SS,PaS and APS methods on the NSGAIII framework and LSMOP1-9 test problems.The best average value among the algorithms for each instance is highlighted in bold

表5 OSTWS,LWS,TCH,PBI,AS,SS,PaS 和APS 方法在框架為NSGAIII,測試問題集為LSMOP1-9 上獲得的GD 值統(tǒng)計結(jié)果(均值和標(biāo)準(zhǔn)差).每個實例算法中的最好結(jié)果以加粗突出顯示 (續(xù)表)Table 5 The statistical results (mean and standard deviation) of the GD values obtained by OSTWS,LWS,TCH,PBI,AS,SS,PaS and APS methods on the NSGAIII framework and LSMOP1-9 test problems.The best average value among the algorithms for each instance is highlighted in bold (continued table)

下面具體分析各個算法在DTLZ1-DTLZ7、WFG1-WFG9 和LSMOP1-LSMOP9 測試問題上的性能.DTLZ1 是一個線性問題,NSGAIII-OSTWS 在該問題上獲得了最佳的GD 值,即在線性的DTLZ1 問題上,OSTWS 方法的收斂性要強于其它所對比的分解方法.DTLZ2-4 和WFG4-9 為凹問題,對于DTLZ2-4,NSGAIII-OSTWS 獲得了最優(yōu)性能.為直觀展示各個算法在凹問題上的收斂性能,圖5 例舉了所有算法在10 維DTLZ2問題上的最終種群分布圖.從圖5 可以看出,算法NSGAIII-OSTWS 的種群分布在目標(biāo)空間[0,1]內(nèi),其它算法的種群大部分都分布在目標(biāo)空間[0,1.2]內(nèi),這表明算法NSGAIII-OSTWS 能很好的將種群收斂到PF 上,而其它算法卻不能.雖然WFG4-9同樣為凹問題,但相對于DTLZ2-4 來說,WFG4-9測試問題具有多峰、帶欺騙和變量不可分離等更加復(fù)雜的特點,從而給算法帶來了更大的挑戰(zhàn).但從表4 可以看出,NSGAIII-OSTWS 在大部分WFG4-9 測試問題上都能取得最佳的性能指標(biāo)值.DTLZ5-6 和WFG3 為退化問題,對于DTLZ5-6,NSGAIIIOSTWS 仍然表現(xiàn)出了最佳的收斂能力.在WFG3上,由GD 指標(biāo)的統(tǒng)計數(shù)據(jù)可知NSGAIII-OSTWS 的性能則一般.WFG1 是一個凹凸混合問題,WFG2 和DTLZ7 為不連續(xù)問題,在這三個問題上,NSGAIII-OSTWS 的性能會有所下降.原因是OSTWS 很難快速且準(zhǔn)確地預(yù)估出此類PF 的形狀,需要消耗一定的迭代次數(shù),從而降低了種群的收斂速度.但本文所采用的預(yù)估PF 方法最終能較好地預(yù)估出這些問題的PF 形狀,故在處理這些不規(guī)則測試問題時依然取得了較好的性能.相對于DTLZ和WFG 測試問題集,LSMOP 具有更大規(guī)模的決策變量,種群的收斂難度增大,對現(xiàn)有的超多目標(biāo)算法提出了更大的挑戰(zhàn).由于OSTWS 繼承了權(quán)重求和分解方法的高搜索效率,因此相對于原始的NSGAIII 算法,NSGAIII-OSTWS 在難收斂的大規(guī)模決策變量問題處理上仍具有顯著的優(yōu)勢,能較快地將種群進(jìn)化至PF.從表5 可以看出,本文所提出的算法NSGAIII-OSTWS 在LSMOP 的大部分測試問題上都取得了最佳的GD 指標(biāo)值,這再次驗證了OSTWS 方法具有很強的搜索效率.綜合統(tǒng)計結(jié)果可以看出,NSGAIII-OSTWS 在DTLZ、WFG和LSMOP 測試集上雖然沒能在每個測試實例上都獲得最優(yōu)的GD 結(jié)果,但總體收斂性能優(yōu)異.

圖5 NSGAIII-OSTWS,NSGAIII-LWS,NSGAIII-TCH,NSGAIII-PBI,NSGAIII-AS,NSGAIII-SS,NSGAIII-PaS 和NSGAIII-APS 在10 維DTLZ2 問題上所獲得的解集Fig.5 Solution set of NSGAIII-OSTWS,NSGAIII-LWS,NSGAIII-TCH,NSGAIII-PBI,NSGAIII-AS,NSGAIII-SS,NSGAIII-PaS and NSGAIII-APS on DTLZ2 problem with 10-objectives

為進(jìn)一步測試本文所提出的OSTWS 在多樣性維持上的性能,我們在前沿面為線性(DTLZ1)、凹型(DTLZ2)、退化(DTLZ5)和不連續(xù)(DTLZ7)的問題上,將NSGAIII-OSTWS 與其他7 個算法進(jìn)行對比.表6 展示了上述算法在最新多樣性評價指標(biāo)CPF 上的平均測試結(jié)果,可以看出OSTWS 在整體上取得了最佳的多樣性性能.

表6 OSTWS,LWS,TCH,PBI,AS,SS,PaS 和APS 方法在框架為NSGAIII,測試問題集為DTLZ1,DTLZ2,DTLZ5 和DTLZ7 上獲得的CPF 值統(tǒng)計結(jié)果(均值和標(biāo)準(zhǔn)差).每個實例算法中的最好結(jié)果以加粗突出顯示Table 6 The statistical results (mean and standard deviation) of the CPF values obtained by OSTWS,LWS,TCH,PBI,AS,SS,PaS and APS methods on the NSGAIII framework and DTLZ1,DTLZ2,DTLZ5 and DTLZ7 test problems.The best average value among the algorithms for each instance is highlighted in bold

為直觀地展示算法在平衡收斂性和多樣性上的綜合性能,圖4 給出了各個算法在IGD+上的性能打分圖,分值越小表示該算法整體性能越好.從圖4可以看出,算法NSGAIII-OSTWS 獲得了最小的IGD+打分值,這表明與NSGAIII 的變體相比,NSGAIII-OSTWS 具有很強的綜合性能.

2)算法整體性能驗證與分析

為測試算法NSGAIII-OSTWS 的綜合性能,將NSGAIII-OSTWS 與9 個先進(jìn)的MaOEAs 進(jìn)行對比實驗,分別為NSGA-III[25]、Two_arch2[27]、SRA[29]、SPEAR[26]、DDEANS[33]、HpaEA[28]、ARMOEA[22]、MaOEA-IT[61]和PaRP/EA[62].表7、表8和表9 分別為上述算法在DTLZ、WFG 和LSMOP 測試問題集上所獲得的IGD+統(tǒng)計結(jié)果.

表7 NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS,HpaEA,ARMOEA,MaOEA-IT 和PaRP/EA在DTLZ1-7 上上獲得的IGD+值的統(tǒng)計結(jié)果Table 7 The statistical results of the IGD+ values obtained by NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS,hpaEA,ARMOEA,MaOEA-IT and PaRP/EA on DTLZ1-7

從表7,表8 和表9 的數(shù)據(jù)可以看出,與其它先進(jìn)的MaOEAs 相比,NSGAIII-OSTWS 在絕大部分測試問題上取得了最佳IGD+值,這表明NSGAIIIOSTWS 在平衡收斂性和多樣性上非常具有競爭力.首先,由表7,表8 和表9 可以看出,NSGAIIIOSTWS 的性能要明顯優(yōu)于經(jīng)典算法NSGAIII,說明OSTWS 在很大程度上提高了NSGAIII 的整體性能,這再次驗證了OSTWS 的有效性.其次,NSGAIII-OSTWS 的整體性能要強于其它最新算法Two_arch2、SRA、SPEAR、DDEANS、HpaEA、ARMOEA、MaOEA-IT 和PaRP/EA,尤其是在規(guī)則問題上,如DTLZ1-4 和WFG4-9.原因是NSGAIII-OSTWS 在規(guī)則問題上易于預(yù)估出PF 的形狀,從而有利于加速種群的收斂.值得注意的是,DDEANS 也獲得了較好的性能,原因是DDEANS采用了參考向量調(diào)整的方法,從而能在不規(guī)則測試問題上,如DTLZ7 和WFG1-2,較好地維持種群的多樣性.

表8 NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS,HpaEA,ARMOEA,MaOEA-IT 和PaRP/EA在WFG1-9 上上獲得的IGD+值的統(tǒng)計結(jié)果Table 8 The statistical results of the IGD+ values obtained by NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS,HpaEA,ARMOEA,MaOEA-IT and PaRP/EA on WFG1-9

表9 NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS,HpaEA,ARMOEA,MaOEA-IT 和PaRP/EA在LSMOP1-9 上獲得的IGD+值的統(tǒng)計結(jié)果Table 9 The statistical results of the IGD+ values obtained by NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS,HpaEA,ARMOEA,MaOEA-IT and PaRP/EA on LSMOP1-9

為直觀展示各個算法在平衡種群收斂性和多樣性上的能力,圖6 給出了所有算法在10 維DTLZ4問題上的最終種群分布圖.從圖6 可以看出,算法NSGAIII-OSTWS 獲得的種群具有良好的收斂性和多樣性,而對比算法NSGA-III、Two_arch2、SRA、SPEAR、DDEANS、HpaEA、ARMOEA 和MaOEA-IT 獲得的種群都沒有收斂到PF,這反映了NSGAIII-OSTWS 的優(yōu)越性.此外,為進(jìn)一步觀察各個算法的收斂性能,圖7 給出了各個算法在DTLZ、WFG 和LSMOP 測試問題上的平均GD表現(xiàn)分,分值越小表示該算法的收斂性性能越好.從圖7 可以看出,算法NSGAIII-OSTWS 在絕大部分測試問題上都獲得了最低的GD 表現(xiàn)分,表明與其它類型的算法相比,NSGAIII-OSTWS 具有很強的收斂能力,這歸功于NSGAIII-OSTWS 算法采用的OSTWS 方法具有很高的搜索效率,從而使得種群能快速的收斂到PF.但對于退化和不連續(xù)的不規(guī)則測試問題DTLZ5-7,由于較難準(zhǔn)確預(yù)估出真實PF 的形狀,導(dǎo)致NSGAIII-OSTWS 在處理DTLZ5-7 問題時收斂性會有所下降.

圖6 SRA,SPEAR,DDEANS,HpaEA,ARMOEA,MaOEA-IT 和PaRP/EA 在10 維DTLZ4 問題上所獲得的解集Fig.6 Solution set of NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS HpaEA,ARMOEA,MaOEAIT and PaRP/EA on DTLZ4 problem with 10-objectives

圖7 NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS,HpaEA,ARMOEA,MaOEA-IT 和PaRP/EA在所有測試問題,即DTLZ(Dx),WFG(Wx) 和LSMOP(Lx) 上的平均GD 表現(xiàn)分,分值越小,算法的整體性能越好.通過實線連接NSGAIII-OSTWS 的得分,以便易于評估分?jǐn)?shù)Fig.7 Average performance score of NSGAIII-OSTWS,NSGAIII,Two_arch2,SRA,SPEAR,DDEANS,HpaEA,ARMOEA,MaOEA-IT and PaRP/EA on all test problems,namely DTLZ(Dx),WFG(Wx)and LSMOP(Lx).The smaller the score,the better the overall performance in terms of GD.The values of NSGAIII-OSTWS are connected by a solid line to easier assess the score

3)參數(shù)C的敏感性分析

NSGAIII-OSTWS 算法的核心是將各種問題的PF 轉(zhuǎn)換為凸型曲面,其中參數(shù)C用于控制預(yù)設(shè)凸曲面的曲率,因此對算法的性能有著一定的影響.由于預(yù)設(shè)曲面為凸形,其曲率值C＞1.圖8 為不同預(yù)設(shè)凸曲線在參考向量w上獲得的最優(yōu)解示意圖.從中可以看出,當(dāng) 1＜C ＜2 時,由參考向量w獲得的最優(yōu)解逐漸靠近w;當(dāng)C=2 時,w獲得的最優(yōu)解正好位于w上;當(dāng)C＞2 時,w獲得的最優(yōu)解逐漸遠(yuǎn)離w.由于參考向量主要用于對種群多樣性的管理,最優(yōu)解越靠近參考向量越有利于多樣性的維護(hù),因此C值取2 相比其它取值更能維持種群的多樣性.為驗證這一結(jié)論,本小節(jié)在凹凸混合問題WFG1、凹問題WFG4、線性問題DTLZ1 和不連續(xù)問題DTLZ7 上測試了C為{1.2,2,3,4,5,6,7,8,9,10}的IGD+性能.圖9 為實驗結(jié)果,可以看出,隨著C值的增加,NSGAIII-OSTWS 的整體性能先逐漸提升后逐漸惡化,當(dāng)C=2 時,算法具有最佳的性能,這驗證了當(dāng)C值取2 時算法具備良好性能這一結(jié)論.

圖8 不同預(yù)設(shè)凸曲線在參考向量w 上獲得的最優(yōu)解示意圖Fig.8 The optimal solution obtained by different preset convex curves on the reference vector w

圖9 不同 C 值在WFG1,WFG4,DTLZ1 和DTLZ7 問題的3,5,8 和10 目標(biāo)維度上的IGD+均值Fig.9 The median IGD+ values of different C values on WFG1,WFG4,DTLZ1 and DTLZ7 problems with 3-,5-,8-,and 10-objectives

4 結(jié)論

為充分發(fā)揮權(quán)重求和搜索效率高的優(yōu)勢,同時又能處理好PF 形狀為非凸的問題,本文提出了一種基于目標(biāo)空間轉(zhuǎn)換權(quán)重求和的超多目標(biāo)進(jìn)化算法,簡稱NSGAIII-OSTWS,其中目標(biāo)空間轉(zhuǎn)換權(quán)重求和方法(OSTWS)將各種問題的PF 轉(zhuǎn)換為凸型曲面,再對其進(jìn)行優(yōu)化求解.為驗證NSGAIIIOSTWS 的有效性,NSGAIII-OSTWS 與7 個NSGAIII 的變體以及9 個最新的MaOEAs 在WFG、DTLZ 和LSMOP 測試問題集上進(jìn)行了實驗對比.實驗結(jié)果表明,相比其他算法,NSGAIII-OSTWS具備良好的競爭性能.

雖然所提算法NSGAIII-OSTWS 在處理MaOPs 上取得了優(yōu)越的性能,但仍有一些開放性的工作值得進(jìn)一步的探索.例如,不規(guī)則問題的PF 形狀難以精確預(yù)估,這勢必導(dǎo)致個體映射的不準(zhǔn)確進(jìn)而影響算法的性能.因此,未來需要進(jìn)一步研究如何更加精確地映射個體.此外,將本文所提出的算法應(yīng)用于現(xiàn)實生產(chǎn)和生活中各類實際問題的求解具有重要的價值,這也是未來需要進(jìn)一步開展的工作.本文所提算法的源代碼已在https://github.com/CIA-SZU/LTT 上公開.