對不連續(xù)帕累托前沿的一種改進(jìn)的MOEA/D*

張寧 高尚

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

隨著Schaffer［1］提出了第一個(gè)多目標(biāo)進(jìn)化算法（MOEA），越來越多的人將進(jìn)化算法應(yīng)用于求解多目標(biāo)優(yōu)化問題。傳統(tǒng)的MOEA主要是基于帕累托支配的思想，例如文獻(xiàn)［2～4］。他們已通過實(shí)驗(yàn)與應(yīng)用驗(yàn)證了對處理多目標(biāo)優(yōu)化問題的有效性。但是近年來基于分解的MOEAs越來越被人們關(guān)注，例如文獻(xiàn)［5～9］。

Zhang和Li最先提出了基于分解的多目標(biāo)進(jìn)化算法的框架［5］。相比于基于帕累托最優(yōu)的方法，大多情況下MOEA/D可以得到更好的帕累托近似前沿，并且其效率也已被證實(shí)。自此之后，越來越多的學(xué)者對MOEA/D展開了深入的研究：Li和Zhang將差分進(jìn)化操作應(yīng)用于MOEA/D［10］；Ke Li提出了一種結(jié)合支配與分解的MOEA，通過結(jié)合支配和分解的優(yōu)點(diǎn)以平衡進(jìn)化的收斂性與多樣性［11］；Xiaoyu He等提出一種基于動態(tài)分解的MOEA，使用解本身作為權(quán)向量而不是使用預(yù)定義的權(quán)向量［12］。

雖然MOEA/D對于簡單帕累托前沿的MOP有著非常好的表現(xiàn)，但是對于復(fù)雜帕累托前沿的問題，并不能得到一個(gè)很好的近似解集。尤其是對于不連續(xù)的帕累托前沿問題，MOEA/D得到的近似帕累托前沿，幾乎都會出現(xiàn)近似帕累托前沿分布不均勻以及無法覆蓋完整帕累托前沿的問題。

本文提出了一種改進(jìn)的MOEA/D解決這些問題。核心思想是使用基于密度的聚類算法判斷是否為不連續(xù)帕累托前沿的優(yōu)化問題。如果是，則將其轉(zhuǎn)化為數(shù)個(gè)連續(xù)帕累托前沿的優(yōu)化問題并協(xié)同演化。通過權(quán)向量重生成和種群重分配解決不均勻和不完整的問題。本文將這種算法命名為MOEA/D-DE-DC。

2 相關(guān)知識

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

在現(xiàn)實(shí)世界中存在著許多多目標(biāo)優(yōu)化問題（MOP），其可以被定義為

其中x為決策向量，Ω為n維決策空間，F(xiàn):Ω∈Rm中包含了m個(gè)需要同時(shí)優(yōu)化的目標(biāo)函數(shù)，Rm為目標(biāo)空間。

2.2 MOEA/D

MOEA/D的主要思想是將一個(gè)多目標(biāo)問題通過聚合函數(shù)分解為若干個(gè)單目標(biāo)問題，然后同時(shí)優(yōu)化所有的單目標(biāo)問題。Zhang和Li提出了三種聚合函數(shù)：懲罰邊界交叉、加權(quán)和以及切比雪夫［5］。在本文中，為了簡單我們選擇使用切比雪夫分解方法，公式如下：

其中λ為權(quán)向量，z為參考點(diǎn)。每一個(gè)權(quán)向量所對應(yīng)的子問題的最優(yōu)解就是MOP問題的帕累托最優(yōu)解，所以可以將所有子問題最優(yōu)解的集合看作PF的良好近似。

2.3 DBSCAN

DBSCAN是一種經(jīng)典的基于密度的聚類算法［13］。它具有無需預(yù)先設(shè)定聚類的數(shù)量，可以識別任意形狀的簇等優(yōu)點(diǎn)。本文中的算法需要在第一階段結(jié)束時(shí)對得到的近似PF進(jìn)行聚類，通過聚類的數(shù)量判斷是否屬于不連續(xù)PF的問題，所以將DBSCAN引入其中。DBSCAN需要的輸入的參數(shù)為鄰域半徑ε和正整數(shù)MinPts。

3 MOEA/D-DE-DC

3.1 算法的總體框架

算法1為MOEA/D-DE-DC的總體框架。由于我們不知道一個(gè)MOP問題的PF是否為不連續(xù)的，所以整個(gè)算法分為兩個(gè)階段。第一階段使用正常的MOEA/D-DE算法，獲得PS和近似PF。第二階段，通過DBSCAN判斷PF是否為不連續(xù)的，如果是不連續(xù)的，則將種群按聚類劃分，將其轉(zhuǎn)化為數(shù)個(gè)連續(xù)的PF的子問題并協(xié)同演化，最后輸出近似PF。如果是連續(xù)的PF則仍然使用第一階段的算法完成演化。

3.2 參考點(diǎn)集的設(shè)置

在算法1中步驟8需要為每一個(gè)類設(shè)置參考點(diǎn)。我們定義這一組參考點(diǎn)為參考點(diǎn)集Z，公式如下：

其中c為通過聚類算法得到的類別數(shù)。為了方便后面內(nèi)容的描述，這里還給出反置參考點(diǎn)集R的定義：

3.3 權(quán)向量的重生成和種群的重分配

由于將整個(gè)種群劃分為C個(gè)子種群，如果C大于1，在第一階段中生成的權(quán)向量已經(jīng)不適用于第二階段了，需要為每一個(gè)子種群生成一組新的權(quán)向量。而每一個(gè)子種群的權(quán)向量的個(gè)數(shù)決定了最終解集的分布。為了解決在第一階段結(jié)束帕累托解集分布不均勻的現(xiàn)象，需要通過每一子類種群中目標(biāo)向量分布空間的大小占總分布空間的比重來衡量其需要生成的權(quán)向量的數(shù)目，公式如下：

其中Ni為第i個(gè)子種群生成權(quán)向量的數(shù)量，對于每一個(gè)子種群的權(quán)向量的分解方法仍然使用的是Das和Dennis的方法［14］。第i組權(quán)向量的鄰居數(shù)量設(shè)置為：

然后將種群重新分配給新生成的數(shù)組權(quán)向量。不重新生成新的種群，是為了最大程度的利用第一階段的計(jì)算資源，加快優(yōu)化速度。種群重分配的過程如算法3中所示：

這種算法的好處在于可以最大程度地保存種群的多樣性，同時(shí)又不會使得某個(gè)個(gè)體重復(fù)的次數(shù)過多。在分配個(gè)體的時(shí)候引入貪心策略，因?yàn)榉N群重分配不需要達(dá)到最優(yōu)，在第二階段的進(jìn)化中算法可以自行調(diào)整。

3.4 種群更新

種群更新的詳細(xì)過程如下：

算法3種群更新

輸入：經(jīng)過聚類的種群x；

經(jīng)過聚類的近似帕累托前沿FV。

輸出：經(jīng)過聚類的種群x；

經(jīng)過聚類的近似帕累托前沿FV。

步驟1 Fori=1，2，…，c，j=1，2，…，NiDo：

步驟1.1選取父代個(gè)體：生成一個(gè)隨機(jī)數(shù)u∈[0，1]，然后通過公式4.1設(shè)置Q；

步驟1.2生成子代：從Q中隨機(jī)選擇兩個(gè)索引k與l，將xi、xk和xl使用差分進(jìn)化算子產(chǎn)生子代個(gè)體x′，在通過多項(xiàng)式變異產(chǎn)生x″；

步驟1.3調(diào)整：若x″不在鄰域目標(biāo)可行域中，則重新生成x″；否則計(jì)算其所屬子類種群的索引b；

步驟1.4更新參考點(diǎn)zb：對每一個(gè)a=1，2，…，m，如果，則將

步驟1.5計(jì)算評價(jià)函數(shù)F(x″)

步驟1.6更新種群：設(shè)置o=0，然后：1）如 果o=nr或Q=? ，則 轉(zhuǎn) 至 步 驟1，否 則 從M={(b，1)，(b，2)，…，(b，Nb)}中隨機(jī)選擇一個(gè)索引（b，d）；

3）將（b，d）從M中刪除，o=o+1，轉(zhuǎn)至1）。

步驟2輸出x和FV。

步驟1.1Q的計(jì)算公式如下：

其中u為隨機(jī)數(shù)，取值范圍為[0，1]；δ，ζ為控制參數(shù)，0<ζ<δ<1。

步驟1.3中需要計(jì)算鄰域可行目標(biāo)域。對于i=1，2，…，c，定于第i個(gè)子類種群的鄰域目標(biāo)可行域SPi為

其中ρ表示收縮因子，是控制σi大小的參數(shù)，取值范圍為(0，0.5)。

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

4.1 測試函數(shù)與對比算法

為了驗(yàn)證本改進(jìn)算法的性能。選取了廣泛使用的測試測試函數(shù)ZDT，DTLZ，WFG和MOP。其中ZDT1和ZDT2的PF為連續(xù)的；其他測試函數(shù)的PF均為不連續(xù)。MOP4為三目標(biāo)測試函數(shù)，其余測試函數(shù)為兩目標(biāo)。所有測試函數(shù)的決策域均為30維。使用MOEA/D-DE與其改進(jìn)的算法MOEA/D-DE-DC進(jìn)行對比。

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

本次實(shí)驗(yàn)使用Matlab2019平臺。操作系統(tǒng)為Win7。為了相對公平，兩算法相同的參數(shù)都設(shè)為相同的值。所有算法的參數(shù)設(shè)置如下：

1）DBSCAN的參數(shù)設(shè)置：MinPts=2，WFG2中ε=0.3，MOP4中ε=0.2，其余ε=0.1。

2）DE算子：CR=1.0，F(xiàn)=0.5。多項(xiàng)式變異算子：η=20，pm=1/n。

3）每個(gè)測試函數(shù)獨(dú)立運(yùn)行20次。算法在達(dá)到最大迭代次數(shù)600次后停止運(yùn)行。

4）兩目標(biāo)的種群規(guī)模為100，三目標(biāo)的種群規(guī)模為300。

5）其他控制參數(shù)：Mr=0.75，h=4，ζ=0.3，δ=0.9，T=N/10，nr=2。兩目標(biāo)問題ρ設(shè)為0.35，三目標(biāo)ρ設(shè)為0.3。

4.3 評價(jià)指標(biāo)

本文采用多目標(biāo)進(jìn)化算法中最廣泛使用的評價(jià)指標(biāo)，即IGD（Inverted Generational Distance）［15］。IGD可以提供有關(guān)所得解集的多樣性與收斂性的可靠信息。設(shè)PF為從真實(shí)POF均勻采樣的一組解，PF*為目標(biāo)空間中的一組近似解，IGD的計(jì)算公式如下：

其中d(a，PF*)是a與PF*中所有點(diǎn)的歐幾里德距離的最小值。IGD的值越低表示PF*越趨近與真實(shí)PF。本次實(shí)驗(yàn)中所有測試函數(shù)從PF中采樣點(diǎn)的數(shù)量設(shè)置為500。

4.4 性能測試

表1 MOEA/D-DE與MOEA/D-DE-DC的IGD

圖1 為兩個(gè)算法種群的平均IGD值隨迭代次數(shù)變化的折線圖。因?yàn)閮蓚€(gè)算法前半部分相同所以只截取了從401～600次迭代的數(shù)據(jù)。從圖中可以看出MOEA/D-DE-DC在不連續(xù)的多目標(biāo)優(yōu)化問題中在IGD度量方面都表現(xiàn)的更加優(yōu)秀。其中450次迭代是MOEA/D-DE-DC第一階段與第二階段的分界線?？梢钥吹綀D3～圖5在迭代次數(shù)450的刻度附近都存在一段尖峰，這是因?yàn)榉N群的重分配一般會對解集的分布產(chǎn)生一定的影響。隨后IGD值都快速地收斂到了一個(gè)更低的值，說明本算法對處理不連續(xù)PF的問題有很大提升。

圖1 MOEA/D-DE與MOEA/D-DE-DC的IGD收斂曲線

圖2 為兩個(gè)算法在個(gè)測試函數(shù)上得到的近似PF，所有圖均取20次獨(dú)立測試的第一次測試數(shù)據(jù)繪制。由圖可以明顯地看出所有MOEA/D-DE-DC的不連續(xù)PF的測試函數(shù)獲得的近似PF分布明顯更加均勻與完整。

圖2 MOEA/D-DE與MOEA/D-DE-DC在測試函數(shù)上的近似帕累托前沿分布圖

5 結(jié)語

本文提出了一種改進(jìn)的MOEA/D，即MOEA/D-DE-DC。其可用于解決不連續(xù)PF的多目標(biāo)優(yōu)化問題中出現(xiàn)的近似PF不均勻與不完整的問題。將其與未改進(jìn)的MOEA/D-DE進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明MOEA/D-DE-DC在不連續(xù)PF的優(yōu)化問題中性能有著顯著的提升。通過將不連續(xù)的PF問題轉(zhuǎn)化為數(shù)個(gè)連續(xù)的PF子問題，可以有效地降低PF形狀對算法性能的影響。將來，我們計(jì)劃研究MOEA/D解決更多目標(biāo)以及更復(fù)雜PF的MOP的能力。