動態(tài)懲罰分解策略下的高維目標(biāo)進(jìn)化算法

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

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

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

1 引 言

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

多目標(biāo)進(jìn)化算法主要分為三類[3]：

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

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

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

MOEA/D通過聚合函數(shù)將多目標(biāo)問題分解成一系列單目標(biāo)子問題，聚合函數(shù)與權(quán)重向量有關(guān)，由于權(quán)重向量的設(shè)置影響解在前沿的分布[11]，從而聚合函數(shù)也會影響解的質(zhì)量[12].

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

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

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

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

2 相關(guān)背景

2.1 MOEA/D算法

Zhang等人[9]提出的基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)基于如下m維最小化多目標(biāo)優(yōu)化問題：

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

(1)

其中x是決策變量，Ω是決策空間，F(xiàn):Ω→Rm為m維目標(biāo)向量，Rm表示目標(biāo)空間，fi(x)是第i個待優(yōu)化的目標(biāo)函數(shù)，F(xiàn)(x)為所得目標(biāo)解集.

MOEA/D算法描述如下：

輸入：

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

2) 算法停止條件；

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

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

5)T：每條權(quán)重向量鄰域中包含的權(quán)重數(shù)量；

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

Step1.初始化

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

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

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

Step2. 迭代更新

當(dāng)i=1,2,…,N時, 執(zhí)行以下步驟：

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

Step2.2. 修正：采用啟發(fā)式的改進(jìn)策略修正y，生成y′.

Step2.3. 更新z：若zj

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

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

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

2.2 聚合方法

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

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

PBI聚合函數(shù)表示為[23]：

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

(2)

(3)

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

(4)

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

3 改進(jìn)策略

3.1 PBI聚合缺陷分析

3.1.1 基于同一子問題的影響

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

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

3.1.2 基于不同子問題的影響

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

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

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

3.2 動態(tài)懲罰分解策略

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

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

改進(jìn)后的懲罰參數(shù)公式如下所示：

θi=e(kmin→kmax)wi

(5)

(6)

λmid={λp|arg minwi}

(7)

λbou={λp|arg maxwi}

(8)

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

3.3 k值變化

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

(9)

(10)

(11)

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

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

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

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

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

4.1 實驗設(shè)置

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

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

4.2 k值三種變化仿真結(jié)果

4.2.1σ參數(shù)分析

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

(a) DTLZ1-4測試函數(shù)的SP指標(biāo)對比圖

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

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

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

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

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

4.2.2k值變化仿真分析

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

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

4.3 各算法的指標(biāo)對比分析

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

4.3.1 基于IGD指標(biāo)的比較

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

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

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

4.3.2 基于HV指標(biāo)的對比

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

表2 MOEA/D-DPS算法與MOEA/D-PBI、MOEA/D-SPS、MOEA/D-APBI的HV指標(biāo)對比結(jié)果Table 2 HV value of MOEA/D-DPS、MOEA/D-PBI、MOEA/D-SPS and MOEA/D-APBI

4.4 各算法的前沿對比分析

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

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

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

5 結(jié)論與展望

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