吳天緯，安斯光，孫崎嶇，李 梅，孫麗宏，申屠南瑛

中國計量大學(xué) 機電工程學(xué)院，杭州 310018

1 引言

經(jīng)典的多目標(biāo)進化算法（Multi-Objective Evolutionary Algorithm，MOEA），特別是基于pareto排序的優(yōu)化算法，可以高效地處理2～3 個目標(biāo)的優(yōu)化問題，例如NAGA-II[1]和SPEA2[2]。但是，經(jīng)過實驗和實踐發(fā)現(xiàn)，這些算法在遇到超過3個目標(biāo)的多目標(biāo)優(yōu)化問題時，幾乎都會遇到收斂能力急劇下降的問題，而且復(fù)雜度也會隨之升高，計算時間更長；另外，pareto 前沿（pareto front）的可視化問題也隨之而來。一些學(xué)者將這些問題稱為“維數(shù)災(zāi)難”，也將優(yōu)化問題目標(biāo)數(shù)大于3 個的問題稱為高維多目標(biāo)優(yōu)化問題（Many-objective Optimization Problem，MaOP）[3]。

近年來，國內(nèi)外學(xué)者提出一系列方法來處理高維多目標(biāo)優(yōu)化問題，大致分為如下4類。（1）基于新型支配關(guān)系的算法。這類方法通過拓展pareto 支配區(qū)域或提出新的支配關(guān)系以達到減少非支配個體數(shù)目的目的[4-5]。（2）基于分解的算法。這類算法通過給定權(quán)重偏好或者參考點信息，使用分解策略，將原多目標(biāo)問題的各個目標(biāo)進行聚合，得到可求解單個pareto最優(yōu)解的單目標(biāo)優(yōu)化問題[6-7]。（3）基于指標(biāo)的算法。這類算法將性能評價指標(biāo)用于比較兩個個體或兩個種群之間的優(yōu)劣[8-9]。（4）基于目標(biāo)降維的算法。這類方法是通過減少目標(biāo)個數(shù)來處理高維多目標(biāo)優(yōu)化問題[10-12]。

在實際應(yīng)用中，用戶往往只需要在較短時間內(nèi)得到一定數(shù)量的pareto最優(yōu)解，算法并不需要分布到整個pareto前沿?；谀繕?biāo)降維的算法通過降低目標(biāo)維數(shù)來處理高維多目標(biāo)問題，這種方式可以降低問題復(fù)雜度，提高算法收斂速度。但降維算法可能會去除或融合過多目標(biāo)，導(dǎo)致算法分布性能下降。聚合樹算法（Aggregation Tree，AT）是一種基于目標(biāo)降維的高維多目標(biāo)優(yōu)化算法，它是一種非參數(shù)的目標(biāo)降維方法，優(yōu)勢在于其不局限于目標(biāo)之間的線性或非線性關(guān)系。聚合樹算法復(fù)雜度低，可以快速地計算出各目標(biāo)間的沖突度。但是聚合樹算法魯棒性較差，且只是對高維多目標(biāo)優(yōu)化問題的預(yù)處理，為用戶提供參考，并不能完整地對高維多目標(biāo)問題進行優(yōu)化。

針對上述問題，本文提出改進聚合樹-NSGA-III（The Improved Aggregation Tree-NSGA-III，IAT-NSGA-III）高維多目標(biāo)降維優(yōu)化算法，主要貢獻如下：

（1）提出數(shù)組疊加機制，并定義沖突趨勢和沖突度誤差，以提高算法的魯棒性。

（2）采用種群合并降維的方式，并定義降維截止沖突度，以減少目標(biāo)信息丟失，保證算法對pareto 前沿的搜索能力。

（3）改進聚合樹-NSGA-III 算法可對高維多目標(biāo)問題進行完整的降維優(yōu)化，為高維多目標(biāo)優(yōu)化問題提供了一種可快速優(yōu)化并同時具有較優(yōu)的綜合性能的優(yōu)化算法。

最后，與各類經(jīng)典高維多目標(biāo)優(yōu)化算法對比，驗證了本文算法在運行時間具有較大優(yōu)勢的同時，也具有較為優(yōu)秀的分布性能和收斂性能。

2 聚合樹算法

2.1 聚合樹算法原理

聚合樹算法的目的是計算各個目標(biāo)間的沖突度，以供用戶對高維多目標(biāo)問題進行決策分析。聚合樹算法定義了一種非參數(shù)秩沖突（Non-parametric Rank Conflict），其數(shù)學(xué)公式為：

如果n是被分析的解的數(shù)量，則非參數(shù)秩歸一化將每個目標(biāo)值歸一化為1到n，這種歸一化解決的問題對任何先前的無中斷規(guī)范化不敏感的目標(biāo)有效，且當(dāng)目標(biāo)使用不同單位且不具有可比性時或無法推斷每個目標(biāo)的重要性值但想要理解它們之間的關(guān)系時有用。

兩個目標(biāo)之間可能的沖突值范圍從Cmin=0 到：

根據(jù)上述定義和與這種沖突測量相關(guān)的問題可以看出，非參數(shù)秩沖突測度也可以用作衡量和諧的度量，這是目標(biāo)的增加或減少的對應(yīng)關(guān)系，與pareto前沿的形狀無關(guān)。非參數(shù)秩沖突測量更穩(wěn)健，因為通常它對任何先前的歸一化更不敏感。與任何非參數(shù)測量一樣，這涉及以較少假設(shè)為代價的信息丟失。

2.2 聚合樹算法可改進點

聚合樹算法復(fù)雜度低，使用靈活，可以快速地為用戶提供各目標(biāo)間的沖突信息，但同時也存在以下問題。

（1）原算法的魯棒性較差。沖突度計算依賴于初始種群大小，且當(dāng)目標(biāo)間的沖突度較大，或者各個目標(biāo)間的沖突度大小接近時，原算法無法得到較為準(zhǔn)確的沖突趨勢和沖突度結(jié)果。

（2）在降維方法上原算法直接去除冗余目標(biāo)。這種方法會導(dǎo)致目標(biāo)信息的丟失，而影響優(yōu)化算法對完整pareto前沿的搜索能力。

（3）在何時應(yīng)停止降維這一問題上原算法并沒有給出建議，需要用戶自行決策。在目標(biāo)間沖突度較大的情況下去除冗余目標(biāo)會影響優(yōu)化算法的分布性能。

3 改進聚合樹-NSGA-III高維多目標(biāo)降維優(yōu)化算法

針對降維優(yōu)化算法分布性能的丟失和原聚合樹算法的不足之處，本文提出了改進聚合樹-NSGA-III 高維多目標(biāo)降維優(yōu)化算法。

3.1 數(shù)組疊加機制

為加強聚合樹算法的魯棒性，本文提出了數(shù)組疊加計算機制。數(shù)組疊加機制可描述如下：

Ni為第i次迭代時種群P的規(guī)模，Nd為每次疊加的數(shù)組D的規(guī)模，Np為初始種群P的規(guī)模。改進聚合樹算法在初始化時會首先生成規(guī)模為Np的種群P，對初始種群P進行非參數(shù)秩歸一化后，使用公式（1）計算沖突度，同時算法會記錄下沖突度最小的兩個目標(biāo)編號Xr(a,b)和最小沖突度值ci，并更新至C和X(a,b)；隨后開始數(shù)組疊加，每次疊加的數(shù)組D大小為Nd，第二次計算沖突度時的種群規(guī)模為Np+Nd，疊加之后再次進行沖突度計算和記錄。直到計算結(jié)果滿足算法條件后，數(shù)組疊加停止。

3.2 沖突趨勢和沖突度誤差

改進聚合樹算法（The Improved Aggregation Tree，IAT）在每次迭代中記錄下的沖突度最小的目標(biāo)都會變化，但隨著數(shù)組的疊加增大，數(shù)組記錄下的沖突度最小的兩個目標(biāo)會趨于穩(wěn)定，本文稱之為沖突趨勢穩(wěn)定。但是對于一些多目標(biāo)問題，沖突趨勢可能在一開始就趨于穩(wěn)定，每次計算出的沖突度結(jié)果卻有較大波動。所以本文同時定義沖突度誤差來保證算法所計算出的沖突度結(jié)果的精確性。沖突度誤差ce定義如下：

其中，ci為第i次迭代中計算出的沖突度，cimax和cimin分別為到第i次迭代中沖突度的最大值和最小值。由沖突度誤差ce定義可知，IAT 在迭代到3 次時開始計算ce。若沖突度誤差ce小于設(shè)定值ceset，IAT 數(shù)組疊加終止，并保存當(dāng)前的沖突度ci，作為當(dāng)前計算的兩個目標(biāo)間沖突度大小。沖突度誤差的設(shè)定值由用戶的經(jīng)驗確定。若沖突度誤差的值設(shè)置得較低，則算法計算出的結(jié)果精度較高，但計算時間則也會更長。在沖突趨勢和沖突度誤差的雙重保證下，提升了聚合樹算法的魯棒性。使用沖突度誤差ce的數(shù)組疊加機制算法描述如下：

算法1ArrayOverlay（P,D）

輸入：初始種群P，疊加數(shù)組D

輸出：最小沖突目標(biāo)X(a,b)，最小沖突度值ci

ford=1 todmax

/*dmax為設(shè)定的最大數(shù)組疊加次數(shù)*/

P′?P+D；

利用式（1）計算目標(biāo)間沖突度ci；

C?ci；

ifX(a,b)=Xr(a,b)

X(a,b)?Xr(a,b)；

end

利用式（9）計算沖突度誤差ce；

ifce≤ceset

end for

end

end

ReturnX(a,b)，ci

3.3 目標(biāo)合并降維

原聚合樹算法雖然使用靈活，但無法直接嵌入其他算法。如何更好地利用聚合樹算法也是本文的研究目標(biāo)之一。在文獻[13]中的電機設(shè)計中，聚合樹被當(dāng)作是對目標(biāo)的預(yù)處理算法，在找出了沖突度最小的目標(biāo)后，需要用戶自行決策去除冗余目標(biāo)。這種直接去除冗余目標(biāo)的降維方法會丟失部分目標(biāo)信息，不利于MOEA對pareto前沿的搜索，導(dǎo)致算法收斂能力和分布能力下降。

本文所提算法采用目標(biāo)合并的降維方法，并與NSGAIII算法結(jié)合。在IAT計算出各目標(biāo)間沖突度，并將目標(biāo)根據(jù)沖突度大小排序后，會將這些降維信息保存至C和X(a,b)中，算法會根據(jù)X(a,b)中的信息將目標(biāo)種群合并，以達到降維的目的[14]。最后，使用NSGA-III 算法內(nèi)核對降維后的多目標(biāo)優(yōu)化問題進行優(yōu)化。同時，C中的沖突度信息則會以樹狀圖的形式繪制，供用戶查看各目標(biāo)之間的沖突關(guān)系。

3.4 終止條件

根據(jù)沖突度的定義，降維并不是無限制的。若目標(biāo)間的沖突度較大，則目標(biāo)間的和諧程度越差，一個目標(biāo)的良好價值意味著另一個目標(biāo)的不良價值，此時則不宜對目標(biāo)進行合并降維。因此，本文算法還需考慮的問題是目標(biāo)降維應(yīng)何時停止。定義降維截止沖突度Cs，算法終止條件為：

C為算法記錄的沖突度集合，ci為第i次降維時的目標(biāo)沖突度。若ci滿足終止條件，算法則不再降維，并開始對當(dāng)前維度的多目標(biāo)問題進行優(yōu)化；若ci不滿足終止條件，最后算法會將多目標(biāo)問題降維至單目標(biāo)問題進行優(yōu)化。使用降維截止沖突度Cs作為終止條件的目標(biāo)合并降維算法描述如下：

算法2ObjectiveReduction(Xvalue,X,C)

輸入：目標(biāo)種群Xvalue，沖突目標(biāo)X，目標(biāo)間沖突度C

輸出：降維后的目標(biāo)種群Xvalue′

fori=1 toM/*M為目標(biāo)維數(shù)*/

ifci≤Cs(ci∈C)

(a,b)?X(a,b)；

Xvalue′(M+i)?Xvalue(a)+Xvalue(b)；

Xvalue′(a,b)? ? ；

else

Xvalue′(a,b)?Xvalue(a,b)；

end for

end

ReturnXvalue′

3.5 算法流程

IAT-NAGA-III完整算法流程如下所示：

步驟1設(shè)置參數(shù)，設(shè)定初始種群P的規(guī)模Np、疊加數(shù)組D的規(guī)模Nd，最大疊加次數(shù)dmax，沖突度誤差ceset，降維截止沖突度Cs。

步驟2初始化種群P，并對種群進行非參數(shù)秩歸一化處理，計算目標(biāo)間沖突度，并將最小沖突度大小和目標(biāo)編號分別更新至C和X(a,b)。

步驟3初始化疊加數(shù)組D，進行數(shù)組疊加，并對新的種群P進行非參數(shù)秩歸一化處理，計算目標(biāo)間沖突度，更新最小沖突度C和最小沖突目標(biāo)的編號X(a,b)。

步驟4判斷沖突趨勢，計算沖突度誤差ce，若ce＞ceset，則跳至步驟3，再次進行數(shù)組疊加；若ce≤ceset或疊加次數(shù)d=dmax，則進行下一步驟。

步驟5重新初始化種群P，判斷降維終止條件，若ci≤Cs，則將沖突度最小的兩個目標(biāo)種群進行相加合并，完成降維，并跳至步驟2；若ci＞Cs，則停止降維，進行下一步驟。

步驟6更新沖突目標(biāo)Xred和目標(biāo)間沖突度ci作為最終降維信息，根據(jù)Xred將目標(biāo)合并降維成新的目標(biāo)種群Pn，用NSGA-III 內(nèi)核對降維后的目標(biāo)種群Pn進行優(yōu)化。

步驟7迭代次數(shù)達到NSGA-III內(nèi)核迭代次數(shù)預(yù)設(shè)值，算法結(jié)束，根據(jù)沖突目標(biāo)Xred和目標(biāo)間沖突度ci繪制樹狀圖，輸出評價指標(biāo)值、運行時間等統(tǒng)計數(shù)據(jù)。

4 數(shù)值實驗

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

為了驗證本文算法的可行性，本章采用DTLZ1-4[15]作為測試函數(shù)，并使用基于新型支配關(guān)系的ε-MOEA算法和基于指標(biāo)的HypE算法作為比較算法。DTLZ測試函數(shù)詳細(xì)描述如表1所示。

目標(biāo)維數(shù)M分別為6、8、10，變量個數(shù)分別為6、8、10。IAT-NSGA-III 的IAT 部分初始種群P的規(guī)模Np=50，疊加數(shù)組D的規(guī)模Nd=50，最大疊加次數(shù)dmax=10。三種算法的迭代次數(shù)及種群大小保持一致。變量的約束條件為0 ≤xi≤1。沖突度誤差ce設(shè)置為0.05，降維截止沖突度Cs設(shè)置為30%。實驗平臺為：Intel?Core?i5-8500 CPU @3.00 GHz，8 GB RAM，MATLAB 2014a。

4.2 改進聚合樹算法結(jié)果及分析

首先給出原聚合樹算法（AT）與改進聚合樹（IAT）算法結(jié)果對比，如圖1、圖2所示。

從圖中可以看出，AT在任意兩次計算目標(biāo)維數(shù)為5的DTLZ2算例的沖突度結(jié)果中，目標(biāo)f1與f2間的沖突度分別為47.20%和25.76%，f3與聚合的新目標(biāo)f1+f2的沖突度分別為52.32%和44.16%，沖突度的誤差較大；IAT 在任意兩次計算目標(biāo)維數(shù)為5 的DTLZ2 算例的沖突度結(jié)果中目標(biāo)f1與f2間的沖突度分別為42.49%和42.68%，f3與聚合的新目標(biāo)f1+f2的沖突度分別為48.11%和49.65%，沖突度的誤差相較于原算法大幅減小。從圖中可以看出，AT 在任意兩次計算目標(biāo)維數(shù)為10 的DTLZ2 算例中的沖突度結(jié)果中，沖突度最小的兩個目標(biāo)分別為f3和f4、f1和f2，兩次計算的整體沖突趨勢相差較大；IAT 在任意兩次計算目標(biāo)維數(shù)為10 的DTLZ2 算例中的沖突度結(jié)果中，沖突度最小的兩個目標(biāo)分別都為f1和f2，兩次計算的整體沖突趨勢保持一致，且每個目標(biāo)間沖突度的誤差都較小。由此可知，聚合樹算法的魯棒性顯著提升。

表1 DTLZ1～4測試函數(shù)

圖1 AT與IAT計算5維DTLZ2沖突度結(jié)果對比

圖2 AT與IAT計算10維DTLZ2沖突度結(jié)果對比

4.3 數(shù)值實驗結(jié)果及分析

在數(shù)值實驗部分，使用反世代距離[16]（Inverted Generational Distance，IGD）作為性能評價指標(biāo)。三種算法保持種群大小相同，主程序迭代次數(shù)相同，各獨立運行20 次，取IGD 均值、極值，運行時間均值，另外為了比較三種算法的穩(wěn)定性，給出了各算法IGD 的標(biāo)準(zhǔn)差（Std）。表2 中為各對比算法在DTLZ 測試函數(shù)集上的IGD 均值、最大值、最小值，最優(yōu)結(jié)果用加粗字體表示，IGD 均值越小，表示算法收斂性能和分布性能越好。

表2 對比算法在不同維度DTLZ測試函數(shù)集上的運行結(jié)果

根據(jù)表2 中的數(shù)據(jù)，在測試函數(shù)DTLZ1 的優(yōu)化上，IAT-NSGA-III在目標(biāo)維數(shù)為6、8、10時都取得了最優(yōu)結(jié)果，且在目標(biāo)維數(shù)為10時優(yōu)勢最大；在測試函數(shù)DTLZ2上，IAT-NSGA-III 在目標(biāo)維數(shù)為 6、8、10 時都取得了次優(yōu)結(jié)果，雖然IGD 均值不及ε-MOEA 算法，但是也可以看出IAT-NSGA-III 在維數(shù)增加后其運算能力并沒有出現(xiàn)大幅下降的現(xiàn)象，表現(xiàn)出了較好的穩(wěn)定性；在測試函數(shù) DTLZ3 中，IAT-NSGA-III 在目標(biāo)維數(shù)為 6、8、10 時都取得了最優(yōu)結(jié)果，而另外兩種算法在這個測試函數(shù)中失去了對pareto 前沿的搜索能力，算法收斂性能大幅下降；在測試函數(shù)DTLZ4中，IAT-NSGA-III在目標(biāo)維數(shù)分別為6、8、10是都取得了次優(yōu)結(jié)果，均好于HypE算法。

此外，為對比各算法在不同測試函數(shù)上的穩(wěn)定性，給出IGD 標(biāo)準(zhǔn)差對比，如表3 所示，最優(yōu)結(jié)果用加粗字體表示。值越小，表示算法穩(wěn)定性越好。從表3中可以看出，IAT-NSGA-III 算法在目標(biāo)維數(shù)分別為6 和8 的DTLZ1 測試中取得了最優(yōu)結(jié)果，在目標(biāo)維數(shù)為10 時取得了次優(yōu)結(jié)果；在測試函數(shù)DTLZ2中，IAT-NSGA-III在目標(biāo)維數(shù)為6 時取得了最優(yōu)結(jié)果，在目標(biāo)維數(shù)為8 時取得了次優(yōu)結(jié)果；在測試函數(shù)DTLZ3中，IAT-NSGA-III算法在目標(biāo)維數(shù)為6、8時取得了最優(yōu)結(jié)果，在目標(biāo)維數(shù)為10時取得了次優(yōu)結(jié)果；在測試函數(shù)DTLZ4中，IAT-NSGAIII在目標(biāo)維數(shù)為6、8時取得了最優(yōu)結(jié)果，在目標(biāo)維數(shù)為10 時取得了次優(yōu)結(jié)果。IAT-NSGA-III 共取得了7 次最優(yōu)和4次次優(yōu)的結(jié)果，由此可以看出IAT-NSGA-III算法具有較好的穩(wěn)定性。

表3 各算法在不同維度DTLZ測試集上的IGD標(biāo)準(zhǔn)差（Std）對比

除了用反世代距離評價指標(biāo)IGD 來評判算法綜合性能以外，運行時間也是衡量算法性能的重要指標(biāo)。三種算法在不同維度DTLZ 測試集上的平均運行時間對比如表4 所示，最優(yōu)結(jié)果用加粗字體表示。從表4 中可以看出，得益于IAT 的降維，IAT-NSGA-III 除了在目標(biāo)維數(shù)為6的DTLZ3測試函數(shù)中取得了次優(yōu)結(jié)果之外，在其他的數(shù)值實驗中都取得了最優(yōu)結(jié)果，且目標(biāo)維度越大，IAT-NSGA-III優(yōu)勢越明顯。

表4 各算法在不同維度DTLZ測試集上的平均運行時間對比s

綜合表2、表3 和表4 來看，本文所提IAT-NSGA-III算法通過減少目標(biāo)維數(shù)，降低了算法復(fù)雜度，在運行時間有較大優(yōu)勢的同時，還保證了算法對pareto前沿的搜索能力，具有較優(yōu)的收斂性能和分布性能。由此可以說明，IAT-NSGA-III通過更加精確穩(wěn)定的計算出目標(biāo)間沖突度，并通過合并沖突度較小的冗余目標(biāo)來達到減少目標(biāo)維數(shù)的方法是可行、有效的。

5 總結(jié)

針對實際應(yīng)用中的高維多目標(biāo)優(yōu)化問題，提出改進聚合樹-NSGA-III 高維多目標(biāo)降維優(yōu)化算法，它是一種可快速降維優(yōu)化并同時具有較優(yōu)的綜合性能的優(yōu)化算法。在該算法中，基于聚合樹算法原理，提出數(shù)組疊加機制計算沖突度，并定義沖突趨勢和沖突度誤差，以提高算法的魯棒性；采用合并目標(biāo)的降維方式，定義降維截止沖突度，以減少目標(biāo)信息丟失，保證算法的對pareto前沿的搜索能力；與NSGA-III算法結(jié)合，以對高維多目標(biāo)問題進行完整降維優(yōu)化。最后，與各類經(jīng)典高維多目標(biāo)優(yōu)化算法對比，驗證了本文算法在運行時間具有較大優(yōu)勢的同時，也具有較為優(yōu)秀的分布性能和收斂性能。