動態懲罰分解策略下的高維目標進化算法

王麗萍， 張夢紫， 吳 峰, 章鳴雷,葉 楓

1(浙江工業大學 信息智能與決策優化研究所， 杭州 310023)

2(浙江工業大學 經貿管理學院， 杭州 310023)

1 引 言

高維目標優化問題一直是研究的熱點與難點之一.一方面，在多目標優化問題中，隨著維度的增加，目標空間中的Pareto前沿性狀愈加復雜，種群規模不足，使得解集難以分布整個前沿[1].另一方面，維數增大存在收斂性不足的問題，算法在平衡多樣性與收斂性方面面臨更嚴峻的挑戰[2].

多目標進化算法主要分為三類[3]：

1) 基于支配的多目標進化算法，如Deb提出的NSGA-II[4]和Zitzler提出的SPEA2[5]，這類算法在二維和三維問題上效果很好，但高維問題中幾乎所有解都是非支配關系，搜索能力隨著目標個數增加表現出明顯衰減，甚至停滯[6]；

2) 基于指標的多目標進化算法，如SIBEA[7]等，此類算法如超體積指標的計算成本會隨著目標維度增加而呈指數型增長[8]；

3) 基于分解的多目標進化算法，該類算法將多目標問題分解為多個單目標子問題，并同時優化所有子問題，有效降低計算成本，并可拓展至高維，典型算法有Zhang等人提出的MOEA/D[9]和Cheng等人提出的RVEA[10].

MOEA/D通過聚合函數將多目標問題分解成一系列單目標子問題，聚合函數與權重向量有關，由于權重向量的設置影響解在前沿的分布[11]，從而聚合函數也會影響解的質量[12].

聚合函數主要有三種[13]：加權和聚合法(WS)，切比雪夫聚合法(Tch)以及基于懲罰的邊界交叉聚合法(PBI).WS搜索能力比Tch強[14]，但WS不適用于凹形前沿問題[7]，Tch雖然可以同時適用于凹形前沿與凸形前沿，但是在前沿形狀較為復雜的問題中效果極差[15]，而PBI在超過2維的優化問題中優于WS和Tch.

但是PBI聚合法存在一個重要缺陷，該方法對于算法收斂性與多樣性的平衡由懲罰參數θ控制，而θ值是人為預設值，θ越小越傾向于提高算法收斂性，θ越大則越傾向于提高解的多樣性[13]，且θ越小在非凸前沿上效果越差[16].Sato等人曾提出一種反向PBI(Inverted PBI)策略[17]，由于缺失邊界點等原因，參考點可能會偏離真實理想解較遠，種群難以逼近真實前沿，反向PBI策略通過尋找距離目標空間中最差解的收斂方向最遠且分布方向最近的點來解決這個問題，然而該策略并未考慮懲罰參數θ值自身對于算法性能的影響.許多使用PBI策略的算法中都將懲罰參數值設置為原始MOEA/D算法中的θ=5.0[18]，然而Ishibuchi提出在多目標knapsack問題中，θ=1.0比θ=5.0的效果更好[16]，設置單一懲罰參數值解決多目標優化問題并不合理[19].因此, Yang等人提出一種自適應PBI(Adaptive PBI)策略[20]，對傳統PBI聚合法中的θ值進行自適應變化，使其隨著算法迭代代數的增加而從小增大；設置θ值的變化范圍為[1,10]，目的是將θ=5.0包含在內.

但是，上述對傳統PBI策略所做的研究與改進并沒有對θ值的影響考慮全面，懲罰參數在整個算法進化過程中應同時考慮兩方面，一方面是θ值對不同位置子問題的影響，另一方面為如何使θ值更合理地平衡算法收斂性與多樣性.對此，本文提出一種基于動態懲罰分解策略的高維目標進化算法MOEA/D-DPS，使得懲罰參數θ在每個子問題上隨算法迭代而各自變化.首先，根據每個權重向量分量的極值差來確定不同子問題上所綁定的θ值，然后在算法進化方向上，引入參數k來引導聚合函數進行自適應選擇，從而使每個子問題上的θ值都有各自合適且不同的變化范圍，動態調整不同子問題的搜索能力，保證算法在搜索早期加快收斂速度，后期盡可能維持解的多樣性.

本文主要工作如下：簡述了MOEA/D算法和PBI聚合方法，重點分析了PBI方法的缺陷并提出改進策略，將改進策略DPS與原始PBI策略，以及同樣對懲罰參數θ進行改進的SPS策略[21]和APBI策略融入到原始MOEA/D算法中，通過仿真實驗進行對比分析.實驗結果表明：MOEA/D-DPS算法與其他算法相比，在大部分測試函數上所得解集整體質量更優.

2 相關背景

2.1 MOEA/D算法

Zhang等人[9]提出的基于分解的多目標進化算法(MOEA/D)基于如下m維最小化多目標優化問題：

MinimizeF(x)={f1(x),f2(x),…,fm(x)}T
Subject tox∈Ω

(1)

其中x是決策變量，Ω是決策空間，F:Ω→Rm為m維目標向量，Rm表示目標空間，fi(x)是第i個待優化的目標函數，F(x)為所得目標解集.

MOEA/D算法描述如下：

輸入：

1) 多目標優化問題；

2) 算法停止條件；

3)N：MOEA/D中包含的子問題個數；

4)λ1,…,λN：均勻分布的N條權重向量；

5)T：每條權重向量鄰域中包含的權重數量；

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

Step1.初始化

Step1.1.計算任意兩條權重向量的歐氏距離，并為每條權重向量選出T條距離最近的權重向量.對每個i=1,2,…,N，設置鄰域B(i)={xi1,xi2,…,xiT)}，其中λi1,λi2,…,λiT是λi的T條最小距離權重.

Step1.2.隨機生成初始種群x1,x2,…,xN，設FVi=F(xi).

Step1.3. 初始化z=(z1,z2,…,zm)T.

Step2. 迭代更新

當i=1,2,…,N時, 執行以下步驟：

Step2.1. 繁殖：從B(i)中隨機選擇2個個體，使用遺傳算子生成新解y.

Step2.2. 修正：采用啟發式的改進策略修正y，生成y′.

Step2.3. 更新z：若zj

Step2.4. 更新解：如果存在gte(y′|λj,z)≤gte(xj|λj,z)，則設xj=y′，FVj=F(y′)，j∈B(i).

Step2.5. 更新PF：將PF中所有被F(y′)支配的向量移除，加入非支配F(y′).

Step3. 停止條件：如果滿足所有停止條件，則停止迭代，并輸出PF.否則，返回Step 2.

2.2 聚合方法

MOEA/D有多種聚合函數，本節主要討論PBI聚合法，該策略適用于連續型多目標優化問題，在超過2維的問題中，尤其是權重向量數目不多的情況下，可以得到比切比雪夫聚合法更均勻的解[7].

圖1 PBI方法示意圖Fig.1 PBI strategy illustration

PBI聚合函數表示為[23]：

mingpbi(x|l,z*)=d1+θd2

(2)

(3)

d2=‖F(x)-(z*-d1λ)‖

(4)

其中θ>0是人為預設懲罰參數，z*為理想參考點.如圖1所示，PBI聚合方法由兩個部分組成：d1表示F(x)在權重向量λi上的投影到參考點的距離，通過最小化d1使候選解在搜索過程中逼近最優Pareto前端，帶動算法收斂；d2是F(x)與權重向量λi之間的垂直距離，用來調整解在目標空間中的分布.懲罰參數θ則定義了適度值中收斂性與分布性的比例.

3 改進策略

3.1 PBI聚合缺陷分析

3.1.1 基于同一子問題的影響

懲罰參數θ對算法性能的影響顯著，其值過大或過小都會弱化算法性能.圖2直觀地表示了θ在不同取值下，目標函數等高線形狀不同，其中陰影部分代表個體i的占優區域，即陰影區域內的個體無法支配個體i，空白區域內的個體可以支配個體i.從左到右依次對比三幅圖可以發現，隨著懲罰參數增大，個體i的占優區域擴大，即個體i成為非支配個體的概率增加(一個個體成為非支配個體的概率=陰影區域面積/(空白區域面積+陰影區域面積))，從而使個體i在迭代過程中更容易保留到下一代，有利于維持種群的多樣性.反之，懲罰參數越小，可以支配個體i的個體數量越多，個體i在迭代過程中被替代的可能性增加，從而有利于促進種群迭代，加快算法收斂速度.

圖2 θ=0,θ=1,θ=2時PBI等高線示意圖Fig.2 Illustration of PBI contour lines with θ=0,θ=1,θ=2

3.1.2 基于不同子問題的影響

圖3示意圖中有7條代表不同位置的權重向量，表示7個不同的子問題，加粗實線表示懲罰參數為1的情況，加粗虛線表示懲罰參數為5的情況，以權重向量λ1和λ4為例.向量λ1位于邊界處，λ2與之相鄰，解A和解B分別為向量λ1和向量λ2對應子問題上的理想最優解，解B在解A鄰域范圍內，當懲罰參數為1時，如解A處實線所示，解B在實線與坐標軸區域范圍內，即解B的目標函數值小于解A的目標函數值，所以在更新替代過程中解A點將被解B替代；當懲罰參數為5時，如解A處虛線所示，解B在虛線與坐標軸區域范圍之外，表示解B的目標函數值大于解A，所以更新時解A將被保留進入下一次迭代.顯然，對于邊界子問題而言，懲罰參數過小容易丟失邊界點，難以維持前沿形狀，最終損失了解的多樣性.

圖3 不同子問題上的解在θ=1和θ=5時的更新示意圖Fig.3 Update illusion of the solutions on different sub-problems with θ=1 and θ=5

權重向量λ4位于中間位置，解C是該向量上所綁定的解，解D是該向量鄰域內的解，相對于解C和解D來說，解D距離標準前沿比解C近得多，解D若可以保留進入下一次迭代有利于算法收斂到前沿，但當懲罰參數為5時，即如解C處虛線所示，解D位于解C的目標函數等高線之外，表示解D的目標函數值比解C處大，所以更新時解D將不會被保留；當懲罰參數為1時，如解C處實線所示，解D目標函數值比解C處小，此時解D可能進入下一次迭代.所以對于中間位置的子問題來說，較大的懲罰參數值不利于帶動解的收斂，若懲罰參數值過大甚至可能導致解無法收斂到Pareto前沿.

3.2 動態懲罰分解策略

采用PBI策略時如果設置一個固定的懲罰參數，則該參數值對于臨近邊界的子問題來說容易偏小，從而丟失邊界點，而同樣的參數值對于位于中間的子問題來說也許偏大，阻礙了解的收斂.基于以上對PBI策略中懲罰參數值的缺陷分析，本文提出一種基于動態懲罰分解策略的高維目標進化算法MOEA/D-DPS.該問題可以通過改變懲罰參數的性質來解決，使懲罰參數值在算法初始化時，根據權重向量位置的不同，對每條權重向量分別綁定一個合適的值，即使懲罰參數值從中間向量向邊界向量逐漸遞增，由此給每個子問題都分配了一個合適的懲罰參數.

但是，若每條權重向量上所綁定的懲罰參數在算法進化過程中為固定值，那么中間向量所綁定的懲罰參數從算法迭代開始到結束始終維持在很小的值，在算法后期不利于解的均勻分布.同樣，邊界向量所綁定的懲罰參數若始終維持較大的值，在搜索早期將阻礙算法收斂，甚至導致邊界點收斂不到前沿.該問題可以在算法迭代的過程中通過動態調整各個子問題上所綁定的懲罰參數來解決，在搜索早期采用較小的參數值，確保算法的收斂性，在算法后期采用較大的參數值，更好地平衡算法的收斂性與多樣性.由此每個子問題上綁定的懲罰參數在算法進化過程中都有各自合適的變化范圍.

改進后的懲罰參數公式如下所示：

θi=e(kmin→kmax)wi

(5)

(6)

λmid={λp|arg minwi}

(7)

λbou={λp|arg maxwi}

(8)

其中，公式(5)中的θi表示第i個子問題上綁定的懲罰參數值，k表示一個由小增大的正數,用于引導θi隨算法進化而動態調整，設kmin=1，kmax=10，確保動態變化過程中包含θ=5這個基本值.wi∈[0,1]是第i條權重向量的向量分量極值差，即通過計算該權重向量的向量分量最大值與最小值之差所得，所以公式(5)中的wi在算法初始階段可以通過公式(6)計算得出，因此，懲罰參數θi的大小在算法進化過程中的變化由k值的變化決定.公式(7)中的λmid代表中間向量，即位于中間位置的權重向量，公式(8)中的λbou代表邊界向量，即位于邊界位置的權重向量，中間向量的wi趨于0，比如二維目標中的向量(0.51,0.49)，邊界向量的wi趨于1，比如向量(0.99,0.01).由此，每個子問題上都綁定了一個不同的懲罰參數，且隨著算法進化都有各自不同的變化區間，不僅提高了不同位置解的質量，還平衡了不同搜索時期算法的收斂性與多樣性.

3.3 k值變化

正如懲罰參數公式(5)-公式(6)所示，懲罰參數值隨算法進化而動態調整是由k值的變化決定.k值在算法搜索早期較小，目的是促進候選解的收斂，之后隨著進化代數逐漸增大，使算法在促進收斂的同時，盡可能維持算法的多樣性不下降.本文對k值做三種最典型的變化[23]，通過仿真實驗進行對比，選擇實驗結果最優的一種變化趨勢帶入改進的動態懲罰分解策略, 在后文中與其他算法進行仿真實驗對比. 三種k值變化公式如下:

(9)

(10)

(11)

其中kmax為k值最大值，本文中設置為10，目的是使算法迭代過程中包含θ=5.

圖4k值的三種線型變化示意圖
Fig.4 Three different lines or curves ofk

klin、kexp、ksig三個公式分別表示k值作線性變化、指數變化和S型變化.其中S型變化中的σ設為0.5，該參數取值將在后文參數分析中加以說明.圖4是三種k值變化線型示意圖，直觀地表示了三種曲線的增長趨勢.

4 實驗結果與分析

為驗證改進后的動態懲罰分解策略在算法中的性能有效性，本文選用一種測試高維目標優化問題較普遍的DTLZ1-4系列測試函數進行仿真實驗，并與基于PBI策略的原始MOEA/D算法，即MOEA/D-PBI[9]，以及同樣對懲罰分解策略進行改進的MOEA/D-APBI[20]和MOEA/D-SPS[21]進行對比分析.

4.1 實驗設置

由于PBI策略適用于2維以上問題，所以本節選擇在3、5、8、10維四個目標維度上進行仿真實驗.其中鄰域大小T=20，雜交算子pc=1.0，雜交位置為2，變異概率pm=1/n，n為決策變量個數，變異位置為5.目標維度為3維時，最大進化代數在測試函數DTLZ1-2和DTLZ4上設為500代，DTLZ3設為1000代，目標維度為5、8、10維時，最大進化代數在測試函數DTLZ1-2和DTLZ4上設為1000代，DTLZ3上為2000代，原因是在DTLZ3測試函數上，初始種群距離前沿很遠，需要更大的進化代數.種群大小N在3、5、8、10維上分別為105、126、156、275，仿真實驗在所有測試函數上各運行20次, 所有指標均取20次結果的均值及標準差.

實驗結果用IGD[24]指標(Inverted generational distance)、HV[25]指標(Hyper Volume)、GD[26]指標(Generational Distance)和SP[27]指標(Spacing)來衡量解集質量.其中IGD指標和HV指標可以評估解的綜合性能，IGD值越小，解的整體質量越高，而HV值越大，則算法綜合性能越好；GD指標用來衡量算法收斂性，值越小，算法所得解集越逼近PF，表明算法收斂性越好；SP指標衡量所得解在PF上的分布均勻性，值越小，分布越均勻，算法多樣性越好.

4.2 k值三種變化仿真結果

4.2.1σ參數分析

本文對k值做了三種變化，首先對S型變化中的σ進行參數分析.σ取值范圍設為[0.1,1.0]，仿真實驗在3維DTLZ1-4四個不同性質的測試函數上進行，計算所得解集的GD值和SP值，每個σ值代入公式(11)，算法獨立運行20次取均值，所得結果如圖5所示.

(a) DTLZ1-4測試函數的SP指標對比圖

(b) DTLZ1-4測試函數的GD指標對比圖圖5 DTLZ1-4測試函數的SP(a)和GD(b)指標對比圖Fig.5 SP(a) and GD(b) values of the analysis of σ

從圖5(a)的SP指標對比結果來看，σ=0.5時在DTLZ3和DTLZ4上得到最小SP值，表示此時算法多樣性最優，σ=0.2、σ=0.7、σ=0.9和σ=1.0時，SP值明顯大于σ其他取值時所得結果，且σ=1.0時SP指標遠大于σ=0.1處，折線圖總體以0.5為低峰向兩邊增大;在DTLZ1-2及DTLZ4上，σ值的變化對SP指標影響較小，但也能發現DTLZ4上σ=5時SP值最小，DTLZ1上σ=1.0處SP值顯然呈上升趨勢. 從圖5(b)的GD指標對比圖來看，在DTLZ3上，σ在[0.1,0.5]上的GD值呈下降趨勢, 且斜率較大,σ在[0.5,1.0]上的GD值呈上升趨勢，且變化幅度比[0.1,0.5]區域小，GD值以σ=0.5為最小值向兩邊遞增；在DTLZ1-2及DTLZ4上，σ值的變化對SP指標影響不大.

綜合來看，在4個測試函數上，GD值和SP值的變化在DTLZ1-2和DTLZ4上變化不大，在DTLZ3上的變化較大，其原因可能是因為DTLZ3測試函數是多峰函數，而本文所提出的動態懲罰分解策略由于考慮了不同位置的權重上應設置不同的懲罰參數，所以對多峰函數的優化效果更顯著.此外，DTLZ3上的SP和GD值都呈現出兩邊高、中間低的變化趨勢，究其原因在于公式(11)的S型變化公式中分母隨算法進化代數增加而產生的變化對于σ取值有局限性.當σ=0.5時,gen>(1/2)*Maxgen代之后,k值才開始逐漸趨向最大值,即算法的搜索周期正好被一分為二，前半個周期中k值很小，從而使得懲罰參數θ值始終處于較小的變化范圍，算法趨向于促進解的收斂，在后半周期中反之，k值突然增大，使得懲罰參數θ值增大，算法逐漸以維持解的多樣性為主.

表1 MOEA/D中融入k值三種線型HV指標對比結果Table 1 HV value by MOEA/D using three different lines of k

然而，當σ=0.1時，在gen>50代開始，k值就逐漸開始向最大值逼近，但此時目標空間中的解集可能并未收斂到前沿，k值的快速增大為時過早，損害了算法的收斂性，導致GD指標值過大.同理，當σ=1.0時，在進化代數達到最大進化代數的時候，k→0.5×kmax，即此時的k值最大值只能取到當σ=0.5時的k值最大值的1/2，從而導致懲罰參數θ值偏小，算法始終強調收斂性，無法合理調整解在目標空間中的分布，導致SP值過大，丟失了解集的多樣性.由此，本文設S型變化中的參數σ=0.5來進行后續仿真實驗.

4.2.2k值變化仿真分析

表1是將使用三種不同k值變化的動態懲罰分解策略分別融入原始MOEA/D算法后，在3、5、8、10四個目標維度的DTLZ1-4系列測試函數上求得的HV指標值.實驗結果表明：在3維DTLZ1、10維DTLZ2和DTLZ3、以及5維DTLZ4上，MOEA/D-Klin或MOEA/D-Kexp所得結果最優，而MOEA/D-Ksig次之；在3維DTLZ3上，線性變化MOEA/D-Klin和指數變化MOEA/D-Kexp均優于S型變化MOEA/D-Ksig；除此之外，所有結果中，S型變化MOEA/D-Ksig所得HV均值均為最大值，可見MOEA/D-Ksig算法所得解集質量為三者最優.這可能是因為當k值呈指數變化時，懲罰參數值在大部分時期都較小，僅在迭代快結束時突然增大，使得算法過于強調收斂，損失了解集多樣性，導致算法性能下降；當k值呈S型變化時，懲罰參數值在算法前期始終處于較小的值，有利于算法完全收斂到前沿位置，在算法中期變化較大，使得懲罰參數在中后期的值維持在一個較大的值，充分保證了解集在目標空間中的均勻分布，所以算法所得解集整體質量更優；而當k值呈線性變化時，懲罰參數值隨著進化代數增加而均勻增大，可能會產生未完全收斂到前沿的結果.因此，在k值的三種變化中，S型變化最合適，本文后續仿真對比實驗將選擇對k值采用S型變化.

圖6 4種算法在DTLZ1-4系列測試函數上的IGD走勢圖Fig.6 Change of IGD value on DTLZ1-4 by four different algorithms

4.3 各算法的指標對比分析

為了驗證使用動態懲罰分解策略的算法性能，減少隨機因素對算法的影響，在每個測試函數上，MOEA/D-PBI、MOEA/D-APBI、MOEA/D-SPS及MOEA/D-DPS四種算法各自獨立運行20次，取HV平均值與標準差作為最終HV指標實驗結果，以及繪制IGD值最小時的IGD走勢圖，以便直觀地表示出各算法在3、5、8、10維DTLZ1-4系列測試函數上的算法性能，從而衡量解的整體質量和算法的收斂效果.

4.3.1 基于IGD指標的比較

圖6是四種對比算法在DTLZ1-4系列測試函數上的IGD值隨進化代數增加而變化的趨勢圖，且每張圖都包含了1/2進化代數后的IGD趨勢子圖，清晰又直觀地展現了各算法的IGD走勢，其中三角形、星形、正方形、圓形線條分別表示MOEA/D-APBI、MOEA/D-SPS、MOEA/D-DPS和MOEA/D-PBI四種算法.

首先縱向分析圖6子圖，對比同一測試函數、不同目標維度上的IGD值，可以發現隨著目標維度的增大，算法最終所得IGD值逐漸增大，這說明算法性能隨著維度的增加會逐漸衰減，其原因在于隨著目標維度的增加，Pareto前沿性狀越來越復雜，算法收斂到Pareto前端需要更多的進化代數，而改進后由動態懲罰分解策略引導的MOEA/D-DPS算法隨著目標維度增加所得最終IGD值仍然嚴格優于其他三種對比算法，說明改進后的算法隨著目標增加所得解集的整體質量仍然比其他三種算法更高.

綜合來看，1、在3維DTLZ3、8維DTLZ1上MOEA/D-DPS算法所得IGD值在算法前期較大，而在算法后期逐漸減小至小于其他三種算法，這可能是因為這兩個測試函數均為多峰性狀，而DPS策略中每個子問題初始的懲罰參數由權重向量的位置決定，且隨算法進化而動態調整，尤其位于峰谷附近的子問題所關聯的懲罰參數值相差更大，所以多峰函數易使懲罰參數的分布更加不規則, 從而增加算法前期的不穩定性；2、在10維DTLZ2和DTLZ4上MOEA/D-DPS算法所得IGD值在算法前期同樣較大，而在算法后期優于其他三種算法，這可能是因為目標維度較大，增大了DPS策略在算法運行過程中的不穩定性；3、除此之外，MOEA/D-DPS算法在其他所有測試函數上的IGD值均嚴格優于其他三種算法，且隨著算法進化代數的增加，IGD值的趨勢平穩.這說明MOEA/D-DPS算法性能更優.

4.3.2 基于HV指標的對比

表2是四種算法在3、5、8、10維DTLZ1-4系列測試函數上的HV指標仿真實驗結果，其中加粗部分是同一測試函數上所得HV最大值，表示其對應算法所得解集的整體質量優于其他三種算法.分析表3結果可以得到：1、在3維DTLZ2和8維DTLZ4上，MOEA/D-SPS和MOEA/D-PBI算法所得HV指標均值最大，MOEA/D-DPS次之；2、在3維DTLZ3和5維DTLZ4上，MOEA/D-DPS算法所得結果弱優于其他三種算法的HV值；3、在其他所有測試函數上，MOEA/D-DPS算法所得HV均值均嚴格優于其他三種算法；4、MOEA/D-APBI 算值均嚴格優于其他三種算法；4、MOEA/D-APBI 算法在所有測試函數上的HV指標都為最小值，算法性能最差，這是因為在PBI策略中僅僅使懲罰參數隨著進化代數呈現自適應變化是遠遠不夠的，尤其是在高維目標問題中，沒有對測試函數形狀、權重向量位置等因素加以考慮，無法有效平衡算法的收斂性與多樣性，而MOEA/D-DPS算法在為不同位置的子問題分配合適的懲罰參數的基礎上，使其根據算法的進化而動態調整，從而使所得解集的整體質量比MOEA/D-APBI算法更高, 且大部分結果亦優于MOEA/D-PBI算法和MOEA/D-SPS算法.

表2 MOEA/D-DPS算法與MOEA/D-PBI、MOEA/D-SPS、MOEA/D-APBI的HV指標對比結果Table 2 HV value of MOEA/D-DPS、MOEA/D-PBI、MOEA/D-SPS and MOEA/D-APBI

4.4 各算法的前沿對比分析

本節給出了四種算法在DTLZ4測試函數上的仿真前沿圖，圖7是各算法獨立運行20次之后所得IGD值最小的一組前沿對比.在3維前沿圖中，"+"代表標準前沿，實心圓點代表算法所得真實前沿.在5、8、10維前沿圖中，所示線條即為算法所求解集.

圖7 各算法在DTLZ4測試函數上的前沿對比Fig.7 Pareto fronts of four different algorithms on DTLZ4

由圖7可知，在3維真實前沿上，MOEA/D-PBI和MOEA/D-APBI的解集集中分布在各頂點附近，中間位置難以收斂，MOEA/D-SPS可以收斂到距離中心較近的區域，而由動態懲罰分解策略所引導的MOEA/D-DPS算法則收斂到了中心區域，可見其多樣性相比其他算法更好.在5維上，MOEA/D-PBI的前沿線條濃度最濃，表示位于同一位置的解較多，提供其他位置信息的能力相比其他三種算法而言不足；而MOEA/D-DPS的前沿線條濃度較淡，原因在于其所得位置信息最多，解的分布范圍廣，多樣性優，比如在[0.8,1.0]區域獲得了4個位置信息，而其他三種算法只能夠得到3個位置信息.目標維度為8時，在[0.15,1]區域中，MOEA/D-SPS和MOEA/D-DPS的均勻性更好，MOEA/D-PBI和MOEA/D-APBI的線條較雜亂，而在[0,0.15]區域中，MOEA/D-DPS的解集較為清晰地分出了兩個層級位置，MOEA/D-PBI只分出了一層，而MOEA/D-SPS和MOEA/D-APBI在這一區域中解集十分混亂，無法分出層級，這說明MOEA/D-DPS算法在8維目標維度上所得多樣性更優.在10維上，四種算法在[0,0.15]區域中的線條都較雜亂，但相比之下，MOEA/D-DPS與MOEA/D-PBI兩種算法所得線條清晰度更好，且MOEA/D-DPS所得線條濃度比MOEA/D-PBI淡，說明所得解集位置信息更多，即此時解集多樣性優于MOEA/D-PBI.因此，改進后所得MOEA/D-DPS算法性能優于其他三種算法.

5 結論與展望

為了優化PBI策略，更好地平衡算法收斂性與多樣性的沖突，提高高維目標優化問題中解集的整體質量，本文提出一種基于動態懲罰分解策略的高維目標進化算法MOEA/D-DPS.該算法通過計算每條權重向量的向量分量極值差，為每個單目標子問題綁定合適的初始懲罰參數，并且隨著算法進化對該參數進行動態調整，從而提高邊界點的多樣性與中間點的收斂性，同時使算法在搜索早期促進收斂, 后期以維持多樣性為主，由此提高解集的整體質量. 仿真實驗證明：MOEA/D-DPS算法所得解集質量更優，改進后的動態懲罰分解策略對算法性能的提高是有效的.在未來的工作中，我們將繼續研究優化高維目標問題和具有復雜Pareto前沿的多目標優化問題，并應用到實際問題中.