基于極值點搜索和非支配排序的高維多目標優化算法

朱春陽，郭曉彤，孫浩然，孫文學

1(南京航空航天大學 計算機科學與技術學院，南京 210016) 2(西安建筑科技大學 管理學院，西安 710055)

1 引 言

在工程技術，經濟，管理，軍事和系統工程領域大量的存在著這樣一類問題，他們往往可以歸納為在某種約束條件下同時使多個目標達到最優，這種含有多個目標的最優化問題被稱為多目標優化問題，多目標優化問題中當需要被優化的目標數在4個以及以上的時候被稱為高維多目標優化問題.

不失一般性，以最小化問題為例，一個具有n個決策變量，m個目標函數的多目標優化問題(Multi-objective Optimization Problems，MOPs)可表述為：

minimizeF(x)=(f1(x)，.…，fm(x))Tsubject tox∈Ω

(1)

其中，x∈Ω是決策向量，Ω是決策空間，F：Ω→Rm由m個實值目標函數組成，Rm是目標空間，可行目標集被定義為集合{F(x)|x∈Ω}.

使u，v∈Rm，對于任意的i∈{1，…，m}，滿足ui≤vi，并且在至少一個目標上滿足uj

定義1.理想點(Z*)定義為：

(2)

定義2.Pareto極值點(B)定義為：

(3)

定義3.邊界解(PCS)：對于一個具有m個目標的多目標優化問題，對于Pareto最優解集而言，如果一個解能夠滿足最小化k個目標(k< m)，并且最大化其他目標，那么，這樣的解被稱為邊界解.

Pareto最優解集代表了一種資源的配置狀態，在該種狀態下，無法通過改變資源的配置狀態達到改善某一個目標的同時而不損害其它的目標.

由于Pareto最優解集不是單一解而是一組解集，而另一方面，進化算法是基于群體智能的啟發式搜索算法，這就決定了利用進化算法求解多目標優化問題具有天然的優勢.因此在過去的十年里，利用進化算法求解多目標優化問題一直被看作是近似Pareto最優解集的一種主要方法.

在進化多目標優化算法中，解的選擇對算法的性能有很大的影響，通常我們希望能夠得到具有以下性質的一組解集：

1)收斂性：所得到的解集能夠盡可能近的靠近Pareto前沿.

2)多樣性：所得到的解集能夠盡可能均勻的分布在整個Pareto前沿上.

基于對解集收斂性和多樣性的綜合考量，一批性能優異的多目標優化算法被提出[1-3].這些算法在2，3個目標的優化問題中已經取得了令人滿意的表現.但是，當處理高維多目標優化問題時，由于非支配排序的選擇壓力喪失[4]；所需要的種群規模與計算復雜度的沖突加劇[4];交叉變異效率在高維多目標空間嚴重降低[5]等原因，使得利用進化算法處理高維多目標優化問題面臨很大的挑戰.

在過去的幾年里，很多研究工作圍繞著以上的挑戰進行開展并設計出了很多具有很高性能的高維多目標優化算法，比如：

1)直接通過修改非支配關系來加強算法在高維空間的選擇壓力，這一類算法包括：偏好排序[6]，基于格子的支配[7]，基于模糊的支配[8]等.

2)利用適應度評估機制來改善多目標優化算法的性能，這類算法具體細分為基于度量指標的算法[3]和基于分解的算法[9]，前者往往通過度量指標來指導算法的演化過程從而達到收斂性和多樣性的平衡，后者則是將一個多目標優化問題通過聚合函數的方式分解成一組單目標優化子問題，然后子問題之間按照一種基于群體的協作的方式進行優化.

3)將基于分解和基于非支配關系結合起來的混合多目標優化算法[10，11]，這類算法旨在結合基于分解和基于非支配關系的優點來求解高維多目標優化問題.

本文在第二章首先對基于支配的多目標優化算法NSGA-II進行分析，之后詳細介紹提出的基于極值點搜索和非支配排序的高維多目標優化算法.第三章介紹了本文中使用的基準測試問題集、評價算法性能指標以及相關實驗參數的設置細節.在第四章我們將改進后的算法與6個當前領域主流算法在標準測試問題集上進行比較，并就算法的各個功能模塊的有效性進行實驗論證.

2 多目標優化算法的設計

2.1 對NSGA-II的分析及改進方案

快速非支配排序算法(NSGA-II)[1]采用模擬二進制交叉(SBX)和多項式變異(polynomial mutation)來產生新解，并將新解和父代解合并到一起組成混合種群，混合種群根據支配關系被劃分到不同的層(F1，F2，…，FL)，分層后的種群將按照由低到高的順序一層一層的保存到精英種群中，直到Fi層，i≤L，Fi層是所能保存的精英解中的最高的一層，由于種群規模限制，不能將Fi層的所有解都保存到精英種群中，這時，算法采用擁擠度距離這一多樣性度量策略，將Fi層中多樣性較好的一部分解保存到精英種群中，從而完成算法的一次迭代.NSGA-II正是采用以上策略，通過反復的迭代，直至獲得一組近似的Pareto最優解集.

實踐證明NSGA-II算法在處理2、3個目標的優化問題時能夠表現出較好的性能和魯棒性，但是在處理高維多目標優化問題時仍存在一些不足.具體表現在以下幾個方面：

1.由于在高維空間中解與解之間幾乎都是相互非支配的，這導致僅依靠非支配排序作為選擇性壓力的NSGA-II的收斂效率急速下降.

2.由于在高維空間中，解與解之間的距離很遠，生成的新解距離父代解很遠，這會導致基于群體智能的生成新解的有效性降低，即交叉和變異操作的效率降低，無法高效的產生優良的子代解供算法選擇.

基于此，我們提出了基于極值點搜索和非支配排序的高維多目標優化算法.所謂極值點搜索，即在算法運行的第一階段，通過極值點搜索算法找到優化問題的近似極值點，從而大幅度的減小目標域的搜索空間.在找到近似的極值點后，算法進入第二階段，在此階段通過近似的極值點將目標空間進行劃分，空間劃分后，只對內部空間的解采用非支配排序和擁擠度距離選擇精英解，以此來提升算法的收斂效率.值得注意的是空間劃分后，內部空間的解與解之間的距離更近，這使得非支配排序的選擇性壓力在高維空間上能夠得到大幅度的提升，由于解與解之間的距離變近，交叉變異操作的效率能夠得到提高.從而提升算法在處理高維多目標問題的性能.

2.2 改進的多目標優化算法

在本節將詳細介紹提出的基于極值點搜索和非支配排序的高維多目標優化算法NSGA-II-BS，其中BS表示極值點B和Search.NSGA-II-BS的算法流程如圖1所示.

圖1 算法流程圖Fig.1 Algorithm flow chart

其中gmax表示NSGA-II-BS算法的最大迭代次數，Δg、gmax1作為極值點搜索算法是否終止的判定條件，將在2.2.3小節中詳細介紹.

2.2.1 初始化

在初始化階段，通過在決策空間中隨機采樣的方法初始化生成含有N個個體的種群P.

1)利用式(2)對理想點進行初始化.

2)利用式(3)對極值點進行初始化.

3)初始化m條參考線：

(4)

對于第i條參考線γi={0，1，…，0}T，其中第i個元素為1其他的元素均為為0.

4)初始化判定條件：Δg=1×106.

2.2.2 極值點搜索算法

在本小節，我們將詳細闡述極值點搜索算法.Pareto極值點是由Pareto前沿上的各個目標的最大值所組成的向量，極值點只存在于目標空間.因此不能直接在決策空間中搜索，基于以上原因，我們采用邊界解搜索的策略，通過邊界解來間接搜索Pareto極值點，從而達到搜索極值點的目的.算法流程如下：

輸入：

①初始種群：P.

Step1.生成新解

將初始解集P采用差分進化(Differential Evolution，DE)[9]和多項式變異(Polynomial Mutation)[1]操作生成新解，重復以上步驟直至N個新解全部生成，并與父代解組成混合種群Q.

Step2.劃分子種群

根據到相應參考線γi的垂直距離，均勻的劃分為m個子種群SubPi，i∈{1，…，m}，每個子種群SubPi包含2×N/m個距離參考線γi垂直距離最近的解.

Step3.選擇解

①對于每一個子種群SubPi

1)通過比較非支配關系，將子種群中的非支配解集P1和被支配解集P2分離.

2)如果|P1|≥N/m，那么P1中距離相關聯的參考線γi垂直距離最近的前N/m將會被保存下來.

3)如果|P1|

②合并每個子種群中保留下來的解組成精英解集P.

Step4.更新極值點將各個子種群中距離相應參考線γi，i∈{1，…，m}垂直距離最近的非支配解組成解集，并利用式(3)對極值點進行更新.

Step5.終止條件

如果滿足終止條件，則終止算法并輸出P和極值點B；否則，返回Step 1.

2.2.3 極值點搜索算法的終止條件

ΔgNSGA-II-BS首先采用了極值點搜索算法搜索優化問題的極值點.之后采用基于近似極值點的非支配排序算法來獲得一組相互非支配的精英解.顯然，給極值點搜索算法分配固定的計算資源是不合理的，因為我們無法預知算法要處理的優化問題的極值點的搜索的難易程度，因此，我們提出自適應的切換機制，通過判斷是否搜索到近似的極值點來決定是否切終止極值點搜索.Δg表示的是在第g代的判定值，它表示的是極值點與前200代相比的最大相對變化率，即每隔200代計算一次Δg的值，計算公式為：

(5)

當Δg小于一個預先設定的值0.001，這就意味著極值點B的變化率已經非常小，并認定，已經找到了近似的極值點B，此時算法將終止極值點搜索.gmax1表示極值點搜索算法的最大迭代數，作為補充，一旦自適應機制失效，極值點搜索算法最多運行gmax1代后自動切換到算法的下一步.

圖2 相關概念在2個目標空間的示意圖Fig.2 Schematic diagram for relevant concepts in the two objective space

2.2.4 基于近似極值點的非支配排序算法

本小節將以NSGA-II為算法框架，并結合近似的極值點，提出基于近似極值點的非支配排序算法，算法流程如下：

輸入：

①極值點搜索算法所保留的種群：P.

②近似的極值點：B.

Step1.生成新解

從輸入種群P中隨機選擇兩個解，然后對這兩個解進行模擬二進制交叉(SBX)和多項式變異(polynomial mutation)操作生成新解y，重復以上步驟直至N個新解全部生成，并與父代解組成混合種群Q.

Step2.選擇解

①利用近似的極值點B對目標空間進行空間劃分，即x，x∈Q，如果?i，i∈{1，…，m}，滿足fi(x)≤Bi，這類解所組成的解集被標記為內部空間解集Qin.對于x，x∈Q，如果?i，i∈{1，…，m}，使得fi(x)>Bi，那這類解所組成的解集被標記為外部空間解集Qout.

②如果|Qin|≤N，Qin將全部保留進P，在Qout中距離理想點Z*歐幾里得距離最近的N-|Qin|個解將會保留進P.

③如果|Qin|>N，對于Qin中的解，將采用NSGA-II的非支配排序和擁擠度選擇策略，挑選出排名前N的個體保存進P.

Step3.終止條件

如果滿足終止代數條件，則終止算法并輸出P；否則，返回Step 1.

3 實驗設置

本章將介紹算法對比實驗中使用到的基準測試問題，算法性能的度量指標以及相關對比算法的參數設置.

3.1 測試問題

在本文實驗中采用目前演化計算領域主流的高維多目標測試問題集DTLZ[12]，該組測試問題的主要特點是可以根據需求拓展不同的優化目標數.

本文實驗中我們將目標數設置為5，6， 8.對于決策變量數n，我們將按照n=m+r-1的形式進行設置，其中m∈{5，6，8}，對于DTLZ1我們將r設置為5，對于DTLZ2-6我們將r設置為10，對于DTLZ7我們將r設置為20.

3.2 性能指標

在本文實驗中，實驗結果的性能度量指標采用反向迭代距離(Inverted Generational Distance，IGD)[13].IGD是指計算真實Pareto前沿上的點到求出的近似Pareto前沿的最小距離的平均值.式(6)中P*是真實Pareto前沿，P是算法近似的Pareto前沿，IGD定義為：

(6)

其中，dist(v，P)表示的是v到P中最近點的歐幾里得距離.

通過式(6)可以看出，優化算法得到的近似Pareto前沿越接近真實Pareto前沿，并且在整個前沿上分布越均勻，那么計算出的IGD值就會越小.反之，距離Pareto前沿越遠，且分布越不均勻，得到的IGD值就越大.因此，IGD度量指標可以有效地綜合評估種群的收斂性和多樣性.

3.3 參數設置

實驗中將會用到NSGA-II以及另外6種算法：MOEADD[11]，MOEA/D-DE[9]，NSGA-III[10]，MOEA-R&D[14]，MOEA/D-SAS[15]和GrEA[7].

其中MOEA/D-DE和MOEA/D-SAS采用切比雪夫聚合函數，其他對比算法參數均按照相應的參考文獻進行設置.所有的對比算法的種群規模設置在5個目標時為210，在6個目標時GrEA、MOEA-R&D和NSGA-II-BS為180，其他對比算法的種群規模設置為182.在8個目標時MOEA-R&D和NSGA-II-BS的種群規模設置為160，其他對比算法的種群規模設置為156.所有算法每次運行都將進行300000次的函數評估，并獨立運行30次.對于NSGA-II-BS，交叉分布指數和多項式變異分布指數均為1，最大變異概率為0.1，Pm=1/n(n為決策變量個數)，gmax1=gmax-50.

4 實驗結果與分析

本章第一小節將進行一組算法對比實驗，以探究NSGA-II-BS的算法性能.接下來兩個小節將通過實驗來論證算法的各個功能模塊的有效性.

4.1 與當前主流的的高維多目標優化算法的比較

NSGA-II-BS與NSGA-II 以及6個當前主流的高維多目標優化算法進行比較，這些算法涵蓋了基于非支配排序策略，基于分解的策略，基于格子支配的策略，基于非支配排序和分解混合的策略等.我們將算法運行30次所取得的IGD平均值進行統計，實驗結果如表1所示，通過實驗我們發現MOEA/DD在處理DTLZ1，DTLZ2，DTLZ3和DTLZ4這類Pareto前沿是規則流型的優化問題時表現出了較高的性能，本文采用Wilcoxon秩和檢驗對所得數據進行顯著性測試.+和-分別表示在相應測試問題上NSGA-II-BS顯著優于或劣于該算法，如無則表示該算法與NSGA-II-BS相比無顯著性差異,粗體表示在相應測試問題上該算法IGD均值最小.

表1 NSGA-II-BS與6個主流高維多目標優化算法在IGD均值指標上的對比結果Table 1 Comparison results of NSGA-II-BS with six classical algorithms for IGD mean values

但是，這類基于在目標空間均勻分布權重向量(參考線)來保證收斂性和多樣性的優化算法在處理Pareto前沿是不規則的流型的優化問題時還能保持這樣的高性能嗎？通過進一步的實驗我們發現，NSGA-II-BS在7個問題上對比其他的算法具有顯著性的優勢，值得注意的是，DTLZ5，DTLZ6和DTLZ7具有不規則的Pareto前沿，這也就意味著基于在目標空間均勻分布權重向量(參考線)來保證收斂性和多樣性的算法在處理這類問題上的性能大大降低[16]，與此同時，我們通過實驗結果發現，我們的NSGA-II-BS在處理這類不規則的優化問題上仍然具有很好的性能，并優于對比的其他算法，這表明，NSGA-II-BS在處理不同類型的高維多目標優化問題時具有很好的算法魯棒性.

4.2 極值點搜索算法終止條件的有效性驗證

在2.2.3節中提出極值點搜索算法的終止條件，在本節將通過實驗來論證極值點搜索算法終止的有效性，圖3展示了算法在5個目標的DTLZ測試問題的計算資源的分配，其中黑色柱體表示極值點搜索算法的計算資源，白色柱體表示基于近似極值點的非支配排序算法的計算資源，從圖中可以觀察到，計算資源的分配在不同的測試問題上表現出不同的偏好，從圖中觀察可知，對于DTLZ1和DTLZ3測試問題，NSGA-II-BS分配更多的計算資源用于極值點的搜索，根據文獻[12]可知，DTLZ1和DTLZ3屬于收斂非常困難的測試問題，這表明，終止條件能夠有效的根據測試問題的收斂難易程度來自適應的控制極值點搜索算法的終止.

圖3 計算資源分配示意圖Fig.3 Distribution of computing resources

4.3 極值點搜索算法的有效性驗證

在NSGA-II-BS中，極值點搜索算法具有很重要的作用，如果極值點不能有效的被搜索到，對算法的性能將會產生一定的影響.本小節將通過實驗來驗證極值點搜索算法的有效性，我們將NSGAII-BS算法在4個目標DTLZ測試問題上搜索到的極值點與真實的Pareto前沿的極值點進行比較，對比結果如表2所示，比較發現，我們的極值點搜索算法能夠有效的近似出真實的極值點，值得注意的是DTLZ5，DTLZ6屬于退化類型的測試問題，具有不規則的Pareto前沿，實驗發現，我們的算法能夠有效的搜索到這類優化問題的極值點，這也證明我們的極值點搜索算法具有很好的魯棒性.

表2 極值點對比Table 2 Comparison for nadir points

由于空間限制，以上數據只保留到小數點后一位

本文采用Wilcoxon秩和檢驗對所得數據進行顯著性測試.+和-分別表示在相應測試問題上NSGA-II-BS顯著優于或劣于該算法，如無則表示該算法與NSGA-II-BS相比無顯著性差異，粗體表示在相應測試問題上該算法IGD均值最小由于空間限制，以上數據只保留到小數點后一位

5 結束語

本文所設計的基于極值點搜索和非支配排序的高維多目標優化算法充分繼承了原始NSGA-II算法優良的魯棒性的優點，并通過提出的極值點搜索算法來大大的縮小了目標搜索空間，提升了非支配排序的選擇性壓力，并通過縮小的搜索空間，在一定程度上緩解了原始NSGA-II在處理高維多目標優化問題時由于解與解之間距離很遠而導致的模擬二進制交叉和多項式變異效率降低的缺點.算法對比實驗中，NSGA-II-BS顯示出了較好的性能，尤其是處理Pareto前沿不規則的測試問題時更是展現了其優異的算法魯棒性.在接下來的工作中，我們將考慮對NSGA-II-BS進行擴展以探究其在處理高維含有約束的優化問題和高維離散優化問題上的性能.

[1] Deb K，Pratap A，Agarwal S，et al.A fast and elitist mul-tiobjective genetic algorithm：NSGA-II[J].Evolutionary Computation，IEEE Transactions on，2002，6(2)：182-197.

[2] Zitzler E，Laumanns M，Thiele L.SPEA2：improving the strength pareto evolutionary algorithm for multiobjective optimization[C].Evolutionary Methods for Design，Optimization and Control with Applications To Industrial Problems，Proceedings of the Eurogen'2001，Athens，Greece，September，2001.

[3] Bader J，Zitzler E.HypE：an algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation，2011，19(1)：45-76.

[4] Li B，Li J，Tang K，et al.Many-objective evolutionary algorithms：a survey[J].Acm Computing Surveys，2015，48(1)：1-35.

[5] Deb K，Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach，Part I：solving problems with box constraints[J].IEEE Transactions on Evolutionary Computation，2014，18(4)：577-601.

[6] Pierro F D，Khu S T，Savic D A.An investigation on preference order ranking scheme for multiobjective evolutionary optimization[J].Evolutionary Computation IEEE Transactions on，2007，11(1)：17-45.

[7] Yang S，Li M，Liu X，et al.A grid-based evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation，2013，17(5)：721-736.

[8] He Z，Yen G G，Zhang J.Fuzzy-based pareto optimality for many-objective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation，2014，18(2)：269-285.

[9] Li H，Zhang Q.Multiobjective optimization problems with complicated pareto sets，MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation，2009，13(2)：284-302.

[10] Deb K，Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach，Part I：solving problems with box constraints[J].IEEE Transactions on Evolutionary Computation，2014，18(4)：577-601.

[11] Li K，Deb K，Zhang Q，et al.An evolutionary many-objective optimization algorithm based on dominance and decomposition[J].Evolutionary Computation IEEE Transactions on，2015，19(5)：694-716.

[12] Kalyanmoy Deb，Lothar Thiele，Marco Laumanns，et al.Scalable test problems for evolutionary multiobjective optimization[M].Evolutionary Multiobjective Optimization，2006：105-145.

[13] Bosman P A N，Thierens D.The balance between proximity and diversity in multiobjective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation，2003，7(2)：174-188.

[14] He Z，Yen G G.Many-objective evolutionary algorithm：objective space reduction+diversity improvement[J].IEEE Transactions on Evolutionary Computation，2015，20(1)：145-160.

[15] Cai X，Yang Z，Fan Z，et al.Decomposition-based-sorting and angle-based-selection for evolutionary multiobjective and many-objective optimization[J].IEEE Transactions on Cybernetics，2016,47(9)：2824-2837.

[16] Ishibuchi H，Yu S，Masuda H，et al.Performance of decomposition-based many-objective algorithms strongly depends on pareto front shapes[J].IEEE Transaction on Evolutionary Computation,2017,21(2)：169-190.