改進聚合樹的高維多目標降維優化算法

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

中國計量大學 機電工程學院，杭州 310018

1 引言

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

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

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

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

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

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

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

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

2 聚合樹算法

2.1 聚合樹算法原理

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

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

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

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

2.2 聚合樹算法可改進點

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

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

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

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

3 改進聚合樹-NSGA-III高維多目標降維優化算法

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

3.1 數組疊加機制

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

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

3.2 沖突趨勢和沖突度誤差

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

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

算法1ArrayOverlay（P,D）

輸入：初始種群P，疊加數組D

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

ford=1 todmax

/*dmax為設定的最大數組疊加次數*/

P′?P+D；

利用式（1）計算目標間沖突度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 目標合并降維

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

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

3.4 終止條件

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

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

算法2ObjectiveReduction(Xvalue,X,C)

輸入：目標種群Xvalue，沖突目標X，目標間沖突度C

輸出：降維后的目標種群Xvalue′

fori=1 toM/*M為目標維數*/

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設置參數，設定初始種群P的規模Np、疊加數組D的規模Nd，最大疊加次數dmax，沖突度誤差ceset，降維截止沖突度Cs。

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

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

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

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

步驟6更新沖突目標Xred和目標間沖突度ci作為最終降維信息，根據Xred將目標合并降維成新的目標種群Pn，用NSGA-III 內核對降維后的目標種群Pn進行優化。

步驟7迭代次數達到NSGA-III內核迭代次數預設值，算法結束，根據沖突目標Xred和目標間沖突度ci繪制樹狀圖，輸出評價指標值、運行時間等統計數據。

4 數值實驗

4.1 實驗參數設置

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

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

4.2 改進聚合樹算法結果及分析

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

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

表1 DTLZ1～4測試函數

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

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

4.3 數值實驗結果及分析

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

表2 對比算法在不同維度DTLZ測試函數集上的運行結果

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

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

表3 各算法在不同維度DTLZ測試集上的IGD標準差（Std）對比

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

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

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

5 總結

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