基于距離優(yōu)勢關系的高維多目標進化算法

顧清華，徐青松，李學現(xiàn)

1.西安建筑科技大學 管理學院，西安710001

2.西安建筑科技大學 資源工程學院，西安710001

3.西安市智慧工業(yè)感知計算與決策重點實驗室，西安710001

在實際生活中，如無人機任務規(guī)劃、雷達的波形設計等問題往往是高維多目標優(yōu)化問題[1]。多目標優(yōu)化進化算法是解決這些問題的重要手段，但是現(xiàn)有的多目標優(yōu)化算法在處理高維多目標問題上會面臨維數(shù)詛咒難題。傳統(tǒng)的Pareto 支配關系很難有效區(qū)分非支配層級，導致種群的大多數(shù)個體都處于非支配層級。為了解決這一問題，許多學者從增大選擇壓力出發(fā)提出了新的方法來克服這一問題，根據(jù)增大選擇壓力方式的不同，這些方法大致分為三類：

第一種策略是發(fā)展新的優(yōu)勢關系，主要思想是增加兩個候選解在多目標優(yōu)化問題上的可比性。Sato等提出了控制解的支配區(qū)域[2]的方法，使用三角函數(shù)通過設定參數(shù)來改變目標函數(shù)的適應度值，進而使解的優(yōu)勢區(qū)域發(fā)生改變。雖然控制優(yōu)勢區(qū)域能增強算法的選擇壓力，但是參數(shù)難以確定，不恰當?shù)膮?shù)設定會降低算法的多樣性。定義模糊優(yōu)勢關系，在L-支配[3]中通過比較優(yōu)劣解的個數(shù)以及目標函數(shù)的范數(shù)來比較個體間的優(yōu)勢關系。在(1-k)-支配[4]中通過預設的參數(shù)k比較劣解集及相等解的個數(shù)來確定個體的優(yōu)勢關系。在模糊支配[5]通過高斯公式轉換兩個個體的表現(xiàn)值，表現(xiàn)值相乘得出的值相比較來定義優(yōu)勢關系。這種方式的好處在于能有效化解目標維度的增加帶來的Pareto優(yōu)勢互相抵消，但是這種方式并不能有效保證算法的收斂性。

第二種策略是將原有的Pareto 優(yōu)勢與特定的選擇方式結合。通過Pareto 優(yōu)勢來進行初次比較淘汰劣解后再進行二次選擇。例如KnEA[6]在二元錦標賽中結合支配關系引入拐點準則和加權距離，利用非支配解拐點的偏向來提高算法的收斂性。在VaEA[7]中通過最大角優(yōu)先原則與消除差解原則選擇收斂性與分布性更好的解參與進化，但是這使得算法不能很好解決規(guī)則Pareto前沿面問題。

第三種策略是將傳統(tǒng)的Pareto 優(yōu)勢與基于分解的思想相結合，既保留了Pareto 支配的支配層級，又結合了基于分解的適應度值和獨立子空間等特性。在MOEADD[8]中保留基于分解的子空間特征，通過引入Pareto支配關系增強更新過程中算法的收斂性，并且設計種群局部密度維護算法多樣性。在RPDNSGA-Ⅱ[9]中提出了一種基于分解的支配關系，并且引入?yún)⒖键c。結合Pareto 支配并按照參考點關聯(lián)候選解的數(shù)量，以及計算候選解到理想點的距離來判斷解的優(yōu)劣。

雖然上述三種策略能一定程度上增強算法的性能，但是這些方法大多需要預先設定合適的參數(shù)，而且較難維持算法在高維多目標問題上的多樣性，使得大多數(shù)的非支配解集聚集在前沿面上的一小部分區(qū)域?；诖嬖诘膯栴}，為了增強算法在高維目標空間中的多樣性，本文提出一種新的支配關系。首先，在非支配排序階段不僅考慮了收斂性，同時進行了多樣性的維護，而且所提出的距離優(yōu)勢關系不需要預先定義參數(shù)。其次，結合所提出的距離優(yōu)勢關系對VaEA 算法進行了改進，不僅提升了VaEA 算法在高維多目標問題上的性能，而且提升了VaEA算法解決規(guī)則Pareto前沿面問題的能力。最后，通過一系列測試問題驗證所提出支配關系的適用性。

1 相關背景

1.1 高維多目標優(yōu)化問題

高維多目標優(yōu)化問題是指目標維度超過4 的多目標優(yōu)化問題，不失一般性，以最小化為例，高維多目標的一般表現(xiàn)形式如下：

其中，m≥4，Ω是決策空間，x=(x1,x2…,xn)∈Ω是決策變量。

1.2 VaEA算法

VaEA算法是由Xiang等于2017年提出的一種基于向量角的多目標進化算法，VaEA算法的基本框架與大多數(shù)基于支配關系的算法類似，圖1給出了VaEA算法的流程圖。首先，在決策空間中隨機初始化生成N個個體的種群。然后，根據(jù)每個個體的適應值選擇更優(yōu)的個體進入交配池。在接下來的操作中，通過應用交叉和變異操作來生成一組子代解Q，并合并父代與子代種群。最后，使用Pareto支配關系對合并后的種群進行非支配排序，按照非支配層級由低到高加入外部檔案，并采用環(huán)境選擇操作使外部檔案的種群規(guī)模為N。VaEA算法的核心是設計了最大角優(yōu)先原則與消除差解原則，其中最大角優(yōu)先原則是指，優(yōu)先選擇臨界層中與外部檔案中個體關聯(lián)角度最大的個體加入外部檔案，這是為了增強種群的多樣性。另一方面，消除差解原則是為了維護種群的收斂性，將一些收斂性太差的個體剔除，選擇與這些差解多樣性相似，但是收斂性更好的個體加入外部檔案，直到外部檔案的種群規(guī)模為N。

圖1 VaEA算法流程圖Fig.1 Flow chart of VaEA algorithm

2 提出算法

2.1 整體框架

本文提出的VaEA-DDR 算法整體框架與VaEA算法一致，區(qū)別在于VaEA-DDR算法使用距離優(yōu)勢關系對種群進行非支配排序。算法1給出了具體流程。

算法1VaEA-DDR算法流程

輸入：種群P，種群規(guī)模N，最大迭代次數(shù)Gmax。輸出：最終種群P。

2.2 距離優(yōu)勢關系

距離優(yōu)勢關系結合小生境技術[10]，不僅考慮到解的收斂性，同樣使解的多樣性得到了增強。具體來說，如果解X1距離支配解X2，即X1?DDRX2，則滿足下列條件：

其中，d(X)是個體到理想點的歐氏距離，將這一距離作為適應度值來選擇更優(yōu)的解。表示兩個候選解的目標值之間的夾角，即：

算法2距離優(yōu)勢關系

輸入：種群P，種群規(guī)模N。

圖2 說明了距離優(yōu)勢關系在雙目標空間的優(yōu)勢區(qū)域。從圖中可以看出，解X1的優(yōu)勢區(qū)域由兩部分組成，在設定的小生境內根據(jù)候選解到理想點的距離可以得出區(qū)域1，根據(jù)式（2）中的第二個公式可以得出另一個優(yōu)勢區(qū)域2。解X1與解X2在同一小生境內，比較兩個解到理想點的距離可以得出解X1?DDR解X2。解X1與解Y不在同一小生境內，θX1Y＞，但是根據(jù)式（2）中第二個公式可以得出解X1?DDR解Y。從這里可以看出，某些目標函數(shù)值較差的候選解可能會被認為是非支配解，但是在這里并沒有試圖定義一種新的方式解決這個問題。一方面，這些較差的解還在預設的范圍內，而且這些較差的非支配解數(shù)量較少，不會影響算法的收斂性；另一方面，如果將這些消除，這些差解將會極大增加距離優(yōu)勢關系的計算復雜度。

圖2 雙目標空間中距離優(yōu)勢關系支配區(qū)域Fig.2 Dominated area of distance dominancerelationship in dual-objective space

圖3 雙目標空間中不同種群分布示意圖Fig.3 Schematic diagram of distribution of different populations in dual-objective space

3 仿真實驗與結果分析

3.1 測試問題與對比算法

為了驗證VaEA-DDR算法性能，選取了DTLZ系列測試集進行實驗研究。表1 給出了測試問題及其特征。根據(jù)目前幾個主要的研究方向，選用近年最具有代表性的算法作為對比算法，包括NSGA-Ⅲ[11]、MOEADD[8]、MOMBI-Ⅱ[12]、RPD-NSGA-Ⅱ[9]、NSGA-Ⅱ-SDR[10]、VaEA[7]。

表1 測試問題及其特征Table 1 Test problems and their characteristics

3.2 性能評價指標

文中采用的性能評價指標主要有：反轉世代距離（inverted generational distance，IGD）[13]，該指標是對收斂性和多樣性的綜合性評價指標；廣義分布（Spread/Δ）[14]，該指標主要評估算法多樣性；世代距離（generational distance，GD）[15]，該指標主要評估算法收斂性。

設P為近似集，P*為沿真實帕累托前沿均勻分布的非支配點集，|P*|是P*中解的個數(shù)，|P|是P中解的個數(shù)，dist(z*,P)是z*與P中最近鄰域之間的歐幾里德距離。則三個性能評價指標計算公式分別如下：

3.3 參數(shù)設置

實驗過程中涉及的多目標算法存在一些參數(shù)需要設定，具體如下：

（1）種群規(guī)模：表2 概述了不同數(shù)量目標的種群規(guī)模N和權重向量的數(shù)量。

表2 權重向量的數(shù)量和種群規(guī)模Table 2 Number of weight vectors and population size

（2）鄰域規(guī)模：鄰域T的大小設置為0.1N。

（3）PBI中的懲罰因子：θ=5.0。

飛機在恐怖的黑暗中又堅持飛行了近兩個鐘頭。一直沒有聲音的廣播突然傳出機長的緊急通知：“飛機遇到特大氣流，大家忍耐一下，正在聯(lián)系準備迫降?！辈恢诌^了多久，廣播中再次傳來了機長的通知，內容大致是：飛機準備迫降在阿拉斯加阿留申群島的薛米亞美國空軍基地。但是這個島太小，機場不具備降落大型民用客機的條件，跑道不夠長，沒有足夠的照明設施。加上眼下氣候惡劣，有大風暴，能見度很低。我們飛機自身的受損情況不明，起落架不知道能不能打開。所以能否安全降落仍是未知數(shù)。請大家做好自救準備！

（4）運行次數(shù)及終止條件：每個算法在每個測試實例上獨立運行30次，算法的終止條件是5、8、10、15目標上算法運行迭代次數(shù)分別為200、300、300、500次。

3.4 實驗結果分析與討論

本節(jié)給出了VaEA-DDR算法與NSGA-Ⅲ、MOEADD、MOMBI-Ⅱ、RPD-NSGA-Ⅱ、NSGA-Ⅱ-SDR以及VaEA算法對比的實驗結果。實驗結果為在PlatEMO平臺[16]獨立運行30 次結果的平均值與標準差。在PlatEMO 中，采用顯著性水平為0.05 的Wilcoxon 秩和檢驗對結果進行分析，“+”“-”“=”分別表示對比算法的結果比提出算法的結果好、差以及在統(tǒng)計學上相似。

表3 給出了7 種算法在5、8、10、15 目標DTLZ 與IDTLZ測試問題上獲得的IGD 平均值與標準差。從表中可以知道，VaEA-DDR算法所取得的最佳IGD值的個數(shù)為16 個。比NSGA-Ⅲ、MOEADD、MOMBI-Ⅱ、RPD-NSGA-Ⅱ、NSGA-Ⅱ-SDR以及VaEA取得更佳IGD值的個數(shù)分別為22、21、25、24、22、23。

VaEA-DDR 算法在DTLZ1 與IDTLZ1問題上表現(xiàn)不佳，在DTLZ1 測試問題上，MOEADD 算法為表現(xiàn)最佳的算法。在IDTLZ2 問題上，VaEA-DDR 與NSGA-Ⅱ-SDR 算法的IGD 值十分接近。這是因為DTLZ1 與IDTLZ1 都是具有線性Pareto 最優(yōu)面的測試問題，但是在本文中定義的支配關系通過基于到理想點的距離來選擇適應度更好的解，這種支配關系較難判斷線性平面上解的收斂程度。這可能會造成在解決具有線性平面的多目標問題時，文中提出的算法較難具有很強的競爭力。

DTLZ2～5 是凹優(yōu)化問題，從實驗結果可以知道VaEA算法表現(xiàn)最佳。為了更直觀了解IGD值的變化，圖4 給出了7 種算法在15 目標上DTLZ2、DTLZ4、DTLZ5 以及IDTLZ2 的IGD 值變化曲線。從圖4（a）中可以看出VaEA-DDR算法最快降至最小值并穩(wěn)定在最小值，相比VaEA 算法在早期IGD 值收斂更快。MOMBI-Ⅱ算法IGD 值表現(xiàn)最差，NSGA-Ⅱ-SDR 算法的IGD 值出現(xiàn)了明顯的波動，雖然在早期算法具有很好的收斂性，但是隨著迭代次數(shù)的增加IGD 值會迅速增加，這說明NSGA-Ⅱ-SDR算法在迭代過程的早期能很迅速接近最優(yōu)解，但是可能會出現(xiàn)遠離最優(yōu)解集的情況。從圖4（b）中仍可以看出VaEA-DDR算法相對VaEA算法在前期IGD值下降更迅速。

DTLZ5 問題最后會收斂為一條退化曲線，在該問題上改進的VaEA-DDR算法表現(xiàn)出絕對優(yōu)勢。對比VaEA 算法與VaEA-DDR 算法的實驗結果可以看出，VaEA算法的性能僅相比MOMBI-Ⅱ算法有優(yōu)勢，這說明本文提出的距離優(yōu)勢關系對VaEA 算法的性能有較大提升。從圖4（c）可以看出大部分算法的IGD值出現(xiàn)了明顯的波動，其中MOMBI-Ⅱ算法的IGD值一直處于上升趨勢，這說明算法形成的解正在遠離Pareto前沿面。NSGA-Ⅲ、RPD-NSGA-Ⅱ、NSGA-Ⅱ-SDR 以及VaEA 算法出現(xiàn)了不同程度的波動，但是VaEA-DDR 算法IGD 值一直處于下降趨勢，這說明VaEA-DDR能較好處理退化問題。

IDTLZ2 問題是一個凸優(yōu)化問題，從實驗結果看VaEA-DDR 算法僅在8 目標與10 目標問題上具有最佳的IGD值。從圖4（d）可以看出在15目標上VaEADDR 算法IGD 值下降與NSGA-Ⅱ-SDR 算法基本一致，最終僅比VaEA算法略差。這說明在凸優(yōu)化問題上，文中提出的距離優(yōu)勢關系對算法性能的提升較小。

圖4 7種算法在15目標上獲得的IGD值變化曲線Fig.4 IGD value change curves of 7 algorithms on 15 objectives

為了檢驗提出的距離優(yōu)勢關系是否能增強VaEA算法多樣性，表4給出了7種算法在5、8、10、15目標DTLZ 和IDTLZ 測試問題上獲得的Spread 平均值與標準差。從表4 中可以知道VaEA-DDR 算法具有最佳Spread 值的個數(shù)為16，相比6 種對比算法具有更優(yōu)Spread 值的個數(shù)分別為24、24、27、28、21、10。由此可知距離優(yōu)勢關系顯著增強了VaEA 算法多樣性。

為了檢驗距離優(yōu)勢關系能否有效保證算法的收斂性，表5 對VaEA 與VaEA-DDR 算法的GD 值進行對比。從表中可以看出，改進后的VaEA-DDR 算法在DTLZ1、DTLZ4 與IDTLZ1 問題上表現(xiàn)出絕對優(yōu)勢，VaEA 算法僅在15 目標DTLZ2，5 目標與8 目標DTLZ3 和DTLZ5 以及IDTLZ2 測試問題上比VaEADDR 具有更好的GD 值。這說明距離優(yōu)勢關系并沒有削弱算法的收斂性，在DTLZ1 問題上可以明顯看出，距離優(yōu)勢關系有效增強了算法的收斂性。

表5 VaEA與VaEA-DDR算法GD值對比Table 5 Comparison of GD values between VaEA and VaEA-DDR algorithms

綜上所述，本文提出的距離優(yōu)勢關系極大提升了VaEA算法求解高維多目標問題上算法的多樣性，在增強算法多樣性的同時有效維護了算法的收斂性。

3.5 汽車碰撞測試實驗的實際應用

為了驗證改進后的算法在實際應用上的求解性能，在經(jīng)典的高維多目標汽車碰撞的實際問題[17]上對算法性能進行測試。汽車碰撞問題為9 目標測試問題，決策變量的個數(shù)為11個，包括汽車相關構件的厚度、材料性質等。最大的迭代次數(shù)為800 次，種群大小設置為11d-1，d為決策變量數(shù)量。在實際問題上運行20 次得到的IGD 與HV 平均值用來評估實驗結果。注意，計算IGD值時，所有算法得到的非支配集作為參考集；計算HV 時，所有算法得到的非支配集的最差目標函數(shù)加上一個小閾值作為參考點。表6 給出了7 種算法在實際問題上獲得的IGD 和HV值。從實驗結果看，改進后的算法獲得了最佳的IGD和HV值，相比原算法有一定的提升。這說明在實際問題上，使用距離優(yōu)勢關系改進后的算法仍能具備良好的求解性能。

表6 7種算法在汽車碰撞實驗獲得的IGD與HV值Table 6 IGD and HV values obtained by 7 algorithms in car crash experiment

3.6 距離優(yōu)勢關系適用性驗證

為了驗證所提出的距離優(yōu)勢關系的適用性，本節(jié)給出了結合距離優(yōu)勢關系改進的NSGA-Ⅲ算法的實驗對比。表7 給出了NSGA-Ⅲ與NSGA-Ⅲ-DDR算法在PlatEMO 平臺獨立運行30 次后得到的IGD值、Spread值以及GD值。

從表7 中可以知道，改進后的NSGA-Ⅲ-DDR 算法具有最優(yōu)的IGD值、Spread值以及GD值最佳的個數(shù)為23、26、15。尤其是從Spread 值上可以看出，改進后的NSGA-Ⅲ-DDR 算法基本上都具有最佳值，NSGA-Ⅲ算法僅在5目標的DTLZ1問題與15目標的DTLZ5 問題上具有更優(yōu)的Spread 值，這再次驗證了距離優(yōu)勢關系能顯著提升算法的多樣性。同時，從GD 值上可以看出，兩種算法均具有一半的最優(yōu)值，這說明了距離優(yōu)勢關系能有效保證算法的收斂性。綜合上述分析，說明了距離優(yōu)勢關系對NSGA-Ⅲ算法的性能同樣有提升，具有較強的適用性。

4 結束語

為了增強算法在高維目標空間的多樣性，本文提出了一種距離優(yōu)勢關系。首先，通過計算候選解到理想點的距離作為適應度值選擇更優(yōu)解，能保證求解過程中算法的收斂性。其次，通過構建的小生境選擇技術，保證了在同一小生境內只保留一個最優(yōu)解，能在非支配排序階段有效加強算法的多樣性?；谒岢龅膬?yōu)勢關系對VaEA算法進行改進，在DTLZ 與IDTLZ 測試問題上進行對比實驗。從實驗結果可以知道，改進的VaEA-DDR 算法取得最佳IGD 值與Spread 值的個數(shù)分別為16、16，并且在多樣性方面具有顯著性優(yōu)勢。同時在NSGA-Ⅲ算法上驗證了所提出距離優(yōu)勢關系的適用性，實驗結果表明本文提出的距離優(yōu)勢關系具有良好的適用性。在汽車碰撞實驗中，改進后的算法能取得最優(yōu)的表現(xiàn)，這說明使用距離優(yōu)勢關系改進的算法能應用于實際問題求解。

雖然從實驗結果來看距離優(yōu)勢關系對算法的性能有較大提升，但是目前算法不能非常有效區(qū)分依據(jù)距離優(yōu)勢關系劃分的非支配層級。在后續(xù)的研究過程中可以進一步完善研究算法的選解過程，提升距離優(yōu)勢關系的適應性。