基于小生境的多目標進化算法

顧清華，駱家樂，李學現

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

2.西安建筑科技大學 西安市智慧工業感知、計算與決策重點實驗室，西安 710055

3.西安建筑科技大學 資源工程學院，西安 710055

多目標優化問題廣泛存在于工程應用領域，這類問題的顯著特征是具有多個相互沖突的目標。這類問題不能得到單一的最優解，而是一組折衷解，稱為帕累托最優解。一般來說，傳統的數學規劃方法不僅計算復雜，而且難以有效地求解該類問題。進化算法被認為是求解該類問題的有效方法。然而，隨著目標維數的增加，非支配解的數量呈指數增長[1]，基于帕累托支配的選擇標準無法區分候選解，導致難以獲取兼具良好收斂性和多樣性的解集。為了解決以上問題，許多方法被提出，大致可以分為以下三類。

第一類是定義新的支配關系取代算法中普遍采用的帕累托支配關系。在廣義帕累托最優支配GPO（generalized Pareto optimality）[2]和角度支配（angle dominance）[3]中，通過擴大單個解的支配區域來放松嚴格的帕累托支配關系，不可避免地會面臨確定不同特征問題松弛程度的障礙。受到分解方法的啟發，一些學者提出了SDEA支配（scalarization-based dominance evolutionary algorithm）[4]和RPS支配（reference points strengthened dominance relation）[5]。即使將以上支配關系嵌入進化算法能夠促進解的收斂性，但是由于缺乏多樣性維護機制，導致解的多樣性較差。為了維護解的多樣性，Tian等人[6]利用候選解之間角度的小生境技術提出了SDR支配（strengthened dominance relation）。在SDR支配的基礎上，Yang等人[7]和Shen等人[8]分別提出了CDR支配（considering convergence dominance relation）和自適應控制SDR支配中收斂度和小生境的大小的支配關系CSDR（controlled strengthened dominance relation）。但是，其中涉及到多個參數，不同的問題對這些參數的敏感程度不同。

第二類是設計特殊的收斂性和多樣性維護策略。例如，在向量角引導搜索的算法VaEA（vector anglebased evolutionary algorithm）[9]中，最大向量角優先原則和劣解消除原則用于臨界層選擇候選解。但是，解決規則特征的帕累托前沿問題的性能差[10]。在MSEA（multi-stage evolutionary algorithm）[11]、TSEA（multistage evolutionary algorithm）[12]、TSGA-II（two-stage genetic algorithm）[13]中，兩階段搜索策略來選擇候選解，其中，第一個階段基于收斂性選擇候選解，第二階段基于多樣性選擇候選解。但是，兩階段搜索策略不但需要設定較多的參數來預判進化所處的階段，而且進化狀態也難以預判，如果誤判進化所處的階段會削弱算法的性能。受到拐點驅動種群搜索策略的啟發，Zhao等人[14]設計了一種偏好拐點促進種群向帕累托前沿搜索的算法。但是，識別拐點是一個難題，而且難以控制拐點區域的范圍。此外，一些學者設計了自適應參考點的方法[15-16]處理不規則帕累托前沿的問題，但是缺點就是每一代都加入了許多參考點，降低了算法的效率且處理規則的帕累托前沿問題的性能差。

第三類是采用分解的方法。其中，分解方法包含兩種分解思想。第一種分解思想是將多目標優化問題分解為一組單目標子問題。MOEA/D（decomposition-based many-objective evolutionary algorithm）[17]是該種類型最具代表性的算法。但是，它僅僅適合求解2至3個目標的優化問題。因此，許多MOEA/D的變體[18-20]被提出來求解高維多目標優化問題（目標維數超過三個的優化問題）。第二種分解思想是將目標空間劃分為一系列子區域。例如，在NSGA-III（nondominated sorting genetic algorithm）[21]和MaOEADRA（many-objective evolutionary algorithm based on dominance and decomposition）[22]中，目標空間被一組權重向量劃分為許多子區域。但是，它們求解退化和不連續等特征的帕累托前沿問題性能較差。因此，一些學者設計了自適應分解策略[23-24]求解不規則帕累托前沿問題。

即使以上的方法在一定程度上能提高多目標進化算法的求解性能，但是，大多數方法需要預先設定參數，而且大多數參數對于不同特征的問題普適性較差，不合適的參數會削弱算法的求解性能，導致難以平衡收斂性和多樣性。此外，目標維數的增加會嚴重削弱對帕累托前沿的選擇壓力，給算法的收斂過程和多樣性維護產生極大的挑戰，特別是對于大部分采用帕累托支配關系作為主要選擇標準的算法。針對以上問題，本文做了兩點貢獻：（1）首先，基于小生境，提出了SDN支配關系（niching based strengthened dominance），其中，設計了一個聚合函數和一種采用目標向量角的密度估計方法分別度量單個解的收斂性和分布性。因此，相較于現存的僅考慮收斂性的支配關系，被提出的支配關系同時考慮了解集的收斂性和多樣性。（2）將提出的支配關系嵌入VaEA，設計了VaEA-SDN算法，其中，SDN支配關系取代VaEA中的帕累托支配關系，極大地提升了VaEA求解多目標優化問題平衡收斂性和多樣性的能力。

1 相關背景

1.1 多目標優化問題

以最小問題為例，多目標優化問題可以用以下數學公式（1）表示：

其中，x=( x1,x1,…,xn)T∈Ω是n維決策向量，Ω是決策空間，?M是M維目標空間，F:Ω→?M是由決策空間Ω映射到M維目標空間?M的目標值組成的目標向量，fi()x是決策變量映射到目標空間在第i個目標上的目標值。

1.2 帕累托支配、非支配解、帕累托最優集、帕累托前沿

定義1（帕累托支配）對于一個最小化的問題，對于給定的兩個解x和y，解x帕累托支配解y，被標記為xy，當且滿足：

如果對于給定的兩個解x和y，如果解x不滿足帕累托支配解y的條件，解y也不滿足帕累托支配解x的條件，那么解x和y是互不支配的，被標記為xy，y。

定義2（非支配解）對于決策空間的一個解x∈Ω，如果不存在任何x′∈Ω支配解x，被標記為′∈Ω，x′x，那么解x被稱為非支配解。

定義3（帕累托最優集）由非支配解構成的集合稱為帕累托最優集，被標記為

定義4（帕累托前沿）由帕累托最優集映射到目標空間組成的集合稱為帕累托前沿，PF={F (x)∈|x∈P}。

定義5（小生境）在進化算法中，所有解構成的集合被稱為種群，每一個種群成員對應一個解，生物體的生存空間對應進化算法中的目標空間。小生境[25]是指目標空間的局部子種群。

定義6（目標向量角）目標向量角指目標空間的兩個解之間的銳角，它可以反映兩個解在搜索方向的相似性。對于兩個解u和v，二者之間的目標向量角可以按以下公式（3）計算：

其中，F′(u)和F′(v)是兩個解各自歸一化后的目標向量，F′(u)·F′(v)是兩個解目標向量的內積，‖ F′(u)‖和‖ F′(v)‖是兩個解目標向量的二范數，arccos(·)是兩個解的目標向量之間的反余弦值。

2 VaEA-SDN算法

2.1 提出算法的整體框架

大多數的多目標進化算法主要依靠帕累托支配關系作為選擇子代的方式。然而，在以非支配解占主導空間的高維目標空間，帕累托支配關系無法在非支配解之間提供足夠的選擇壓力。此外，帕累托支配關系并沒有考慮解集的多樣性。對于一個多目標進化算法來說，應該同時考慮解的收斂性和多樣性。然而，小生鏡可以較好地維持解集的多樣性[25]。在大多數的多目標進化算法中，采用歐式距離來評估解在目標空間的分布性。但是，正如文獻[9]，歐式距離并不適合度量高維目標空間解的分布，而目標向量角可以利用角度反映解在目標空間的搜索的相似性。同時考慮到解集的收斂性，聚合函數可以度量解在搜索方向的收斂度。如果種群成員的分布性和收斂度均很好，那么最終整個種群的收斂性和多樣性將有效地得到維護。因此，基于小生境，提出了一種同時考慮收斂性和多樣性的支配關系來促進種群的收斂性和多樣性，其中，一個聚合函數和目標向量角的密度估計方法來分別度量解的收斂度和分布性。此外，結合VaEA，將被提出的支配關系取代VaEA中的帕累托支配關系。

被提出的支配關系結合VaEA的優勢和必要性解釋如下：

在VaEA中，首先，通過帕累托支配關系對種群非支配排序[26]到不同的前沿面。然后，將位于臨界層中的解與外部檔案集中的解關聯起來，采用最大向量角優選原則和裂解消除原則[9]從臨界層選擇解來分別維護種群的多樣性和收斂性。然而，在VaEA中，外部檔案集中解的選擇是基于帕累托支配關系。因此，在高維空間，VaEA難以對外部檔案集進行維護。相較于帕累托支配關系，本文提出的支配關系在非支配排序階段就同時考慮了解的收斂性和多樣性。此外，VaEA中的最大向量角優選原則和裂解消除原則一定程度上維護了位于臨界層解的收斂性和多樣性。VaEA通過新的非支配排序后，可以進一步提高種群的收斂性和多樣性。

依據以上的解釋，提出的VaEA-SDN算法整體框架與VaEA算法類似，區別在于VaEA-SDN使用被提出的SDN支配關系取代帕累托支配關系對種群進行非支配排序[26]。圖1展示了VaEA-SDN算法的流程圖，以下步驟是對VaEA-SDN算法流程的具體解釋。

圖1 VaEA-SDN流程圖Fig.1 Flow chart of VaEA-SDN

VaEA-SDN算法的具體步驟如下：

輸入參數：種群的規模N，迭代次數t=0，最大迭代次數Gmax；

1.生成數量為N的初始種群Pt；

2.通過遺傳算子執行交叉變異產生子代Qt；

3.將父代種群和子代種群合并Pt?Qt=Rt；

4.產生參考集RP_Set；

5.將聯合種群Rt與每一個參考點RP關聯；

6.使用SDN支配關系對聯合種群Rt中的解非支配排序到不同等級的前沿面[ F1,F2,…,Fl,…]，其中Fl被稱為臨界層，Fl滿足該要求|F1|+|F2|+…+| Fl-1|＜N,且|F1|+|F2|+…+|Fl|≥N。

7.將Rt中位于F1至Fl-1的個體加入外部檔案集St，即St=F1?F2?…?Fl-1；

8.采用最大向量角優選原則和裂解消除原則[9]從臨界層Fl中一個一個地選擇K個解加入到St，其中K=N-||St，直到檔案集St中的種群規模等于N以構成下一代的種群Pt+1，t=t+1；

9.當迭代次數t達到預先設定的最大迭代次數Gmax，算法結束，輸出Pt+1；否則，返回步驟2到步驟8算法繼續執行。

輸出：最終的種群Pt+1

2.2 參考點的產生和關聯操作

參考點的產生：由于被設計的SDN支配關系的定義需要利用參考點構成的小生境。本文用文獻[27]中的方法產生一組均勻分布在目標空間的參考點。對于一個具有M個目標的優化問題，參考點的數量H按公式（4）確定：

其中，p是沿每個目標軸的分割數。

關聯操作：首先，每個參考點與原點連接起來產生對應的參考方向。然后，計算種群中每個解與所有參考方向之間的目標向量角。最后，將每個解與最小角度對應的參考方向相關聯。

2.3 SDN支配關系

SDN支配關系利用參考點的構成的小生境，它的主要特點是如果候選解位于同一個小生境中，收斂度小的解支配收斂度大的解。否則，具有收斂度小且低密度估計值的解支配另一收斂度大且高密度估計值的解。

定義7（SDN支配關系）對于給定一個種群P和一組參考點RP_Set。當且僅當以下任一條件成立，一個解u被稱為SDN支配另一個解v，標記為uSDNv。

A RP(u)=RP(v)且Con(u)＜Con(v)

B RP(u)≠RP(v)且Con(u)＜Con(v )D(u)＜D(v)

其中，RP(u)表示解u關聯的參考點，Con(u)表示解u的收斂度，它通過將M個目標值相加計算得出，更小Con(u)值意味著解u更好的收斂性。D(u)表示解u的密度估計，它是根據解u所處小生境中解的數量及其與解u之間的目標向量角確定。每個小生境內的解由關聯到同一個參考點的解構成。更小的D()u值意味著u解更好地分布。

對于該支配關系的解釋如下：當解u帕累托支配解v（滿足條件1），則uSDNv。當解u和v是互不帕累托支配，但是關聯到同一個參考點時（滿足條件（2）A），僅僅依據收斂性度量Con來比較兩個解。如果解u的收斂度小于解（即Con(u)＜Con(v)）的收斂度D，則uSDNv。在同一個小生境中，優先考慮收斂性好的解可以確保種群的收斂性。當解u和v是互不帕累托支配且關聯到不同的參考點時，同時依據解Con和D來比較兩個解。如果解u的收斂度小于解v的收斂度（即Con(u)＜Con(v)）且解u的密度估計值小于解v的密度估計值（即D(u)＜D(v)）（滿足條件（2）B），則uSDNv。在不同的小生境內同時強調收斂性和多樣性，可以使種群在保證收斂性的情況下維護種群的多樣性。以下是如何計算Con和D。

對于給定的一個解u，解u的收斂度按以下公式（5）和（6）計算：

其中，f~i(u)是解u在第i個目標上歸一化的目標值，fimin(x)是種群在第i個目標上的最小值，fimax是種群在第i個目標上的最大值。

解u的密度估計值按以下公式（7）～（9）計算：

其中，Angle(u,v)是解u和它的鄰近解v之間的目標向量角；θ是RP(u)和它的M個鄰近參考向量之間的平均向量角；θi是RP(u)和它的第i個鄰近參考向量之間的角度。如果一個解的鄰近解越多，且鄰近解與該解之間的夾角越小，則該解將被賦予更大的密度估計值，表明其更擁擠。因此，該解的分布性就差，不利于種群的多樣性。如果大多數候選解的收斂度和密度估計值均越小，種群的收斂性和多樣性就越好。

需要注意的是，如果某一個參考方向僅僅被關聯到一個解，說明在該搜索方向上只有一個解引導搜索。為了維持種群的多樣性，該解毫無保留地保存到下一代。

用一個簡單的例子來說明SDN支配。由于在高維空間幾乎所有解都是互不帕累托支配的，因此，假設被比較的兩個解互不帕累托支配，一個解SDN支配另一個解，存在兩種情況：

情況1兩個被比較的解關聯到同一個參考點，僅強調收斂性。依據它們各自的收斂度來確定二者之間的支配關系。正如圖2中展示的那樣，解c和解f是互不支配的，但是它們關聯到同一個參考點RP3。因為Con(c)＜Con(f)，所以cSDNf。

圖2 闡述兩個解之間的SDN支配關系Fig.2 Illustration of SDN dominance relationship between two solutions

情況2兩個被比較的解關聯到不同的參考點，收斂性和分布性同時強調。同時依據它們各自的收斂度和密度估計值來確定二者之間的支配關系。正如圖2中展示的那樣，解a和解c是互不支配的，它們分別關聯到RP2和RP3。因為Con(a)＜Con(f)且D(a)＜D(C)，所以aSDNc。

經過以上對SDN支配定義及解釋，可以得到SDN的以下屬性。

屬性1 SDN支配在同一個小生境或不同小生境內具備傳遞性，即，對于?x,y,z∈U,其中U是算法獲得的所有解構成的集合，如果xSDNy并且ySDNz,那么xSDNz。

證明x,y,z在同一個小生境內，即RP(x)=RP(y)=RP(z)。

因此，可以推出RP(x)＜RP(z),Con(x)＜Con(z),即xSDNz。

x,y,z在不同的小生境內，即RP(x)≠RP(y)≠RP(z)。

因此，可以推出Con(x)＜Con(z),D(x)＜D(z),即xSDNz。

依據以上分析可知，在高維目標空間，幾乎所有的解都是非支配解，帕累托支配關系無法提供足夠的選擇壓力。但是，SDN支配可以在候選解之間形成一個嚴格的排序，同時管理候選解的收斂性和多樣性。

就收斂性而言，在同一個小生境內優先選擇收斂度最好的解（例如，圖3中被標綠的解i）可以保證種群在該搜索方向上向帕累托前沿收斂，并且還可以加快向帕累托前沿的收斂速度，因為SDN支配在同一個小生境內具備傳遞性。

圖3 SDN支配在雙目標空間平衡收斂性和多樣性Fig.3 Balancing between convergence and diversity for SDN dominance in dual objective space

就多樣性而言，在所有小生境內都僅僅保留一個收斂度最好的解和優先考慮不同小生境內同時具備良好收斂性和分布性的解可以保證種群的多樣性。例如，如果所有小生境都分別保留一個收斂性最好的解（圖3中被標綠的解）到下一代，種群將會朝各個方向朝帕累托前沿搜索。因此，優先選擇圖3中被標綠的解可以在保證收斂性良好的情況下，較好地維持種群的多樣性。此外，例如，當圖3中位于兩個不同小生境內的解d和解b做比較時，優先選擇具備良好收斂性和分布性的解d可以在維護收斂的同時提高多樣性，因為SDN支配在不用小生境內同樣具備傳遞性。

2.4 計算復雜度分析

對于一個具有M個目標且種群規模性為N的優化問題，VaEA-SDN的計算復雜度分析如下：歸一化聯合種群Rt計算復雜度為O(MN)；對于關聯操作，計算種群成員與參考方向目標向量角的計算復雜度為O(HN)，其中H是參考點的數量，但是，參考點的數量等于種群的規模。因此，關聯操作的計算復雜度為O(N2)；計算收斂性度量Con的計算復雜度為O(MN)；計算密度估計值度量D的計算復雜度為O(N2)；類似利用帕累托支配關系對種群進行非支配排序的比較次數，SDN支配對種群非支配排序的計算復雜度為O(MN2)；最后，假設通過非支配排序后，臨界層Fl包括L個解，參照VaEA，最大向量角優選原則和裂解消除原則的選擇過程需要O(ML2)。因此，VaEA-SDN進化一代的總體計算復雜度為O(MN2)。表1展示了下文進行仿真實驗的7種算法的計算復雜。從表1展現的結果來看，對比算法的計算復雜度參照原始論文，SDN支配并未增加VaEA的計算復雜度，這個結果是可以預知的。因為SDN支配和VaEA中的帕累托支配對解進行非支配排序的比較次數是一樣的。此外，相比其他5個對比算法，VaEA-SDN也并未增加計算復雜度。

表1 7種算法的計算復雜度Table 1 Computational complexity of seven algorithms

3 仿真實驗設計

3.1 測試問題和對比算法

為了測試被提出算法的性能，兩組被廣泛使用的基準測試系列問題DTLZ（Deb-Thiele-Laumanns-Zitzler）[28]和MaF（many-objective function）[29]來執行仿真實驗。因為MaF2和DTLZ2的都是凹特征的帕累托前沿測試問題，故在MaF測試問題上執行實驗時，沒有選擇MaF2作為測試問題。其他測試問題的特征如表2所示。同時，選擇6個先進的算法NSGA-III[21]、VaEA[9]、MSEA[11]、NSGAII-CSDR[8]、RPS-NSGAII[5]和CDR-MOEA[7]作為對比算法。

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

3.2 算法性能評價指標

世代距離（generational distance，GD）[28]、覆蓋帕累托前沿范圍（coverage over the Pareto front，CPF）[30]以及反轉世代距離（inverted generational distance，IGD）[31]被用來定量評估算法的性能。其中，IGD值越小，表示算法獲得的解集兼具良好的收斂性和多樣性，即算法平衡收斂性和多樣性的能力越好；GD值越小，僅表示算法獲得解集的收斂性越好；CPF值越大，僅表示算法獲得解集的多樣性越好。

設P*是算法獲得的解集，PF*是沿真實帕累托前均勻分布的解集，||P*和 ||PF*分別是解集P*和PF*中解的數量。評價算法性能的三個指標的定義如下：

（1）IGD指標

其中，d(z,P*)是真實前沿面PF*上的解z到P*上解的最小歐式距離。

（2）GD指標

其中，d(v,PF*)是算法獲得解集P*中解v到至真實帕累托前沿上的解的最小歐式距離。

（3）CPF指標

CPF將所獲得的解集通過真實帕累托前沿投影到低維空間計算投影解集的超立方體的體積，來度量解的多樣性。

其中，Vol()P*是算法獲得解集構成的超立方體體積，Vol( )

PF*是真實帕累托前沿面上的解集構成的超立方體的體積。lM-1v表示算法獲得的解v在M-1維目標空間構成的立方體的邊長，lM-1Y表示真實帕累托前沿面上的解Y在M-1維目標空間構成的立方體的邊長。vi和qi算法獲得解v和解q在映射空間第i個目標值，yi和pi是真實帕累托前沿面上的解在映射空間第i個目標值。

所有仿真實驗都在基于MATLAB的進化多目標優化平臺Plat-EMO[32]上進行，每個實驗結果均是20次獨立運行的平均值和標準差。依據評價指標，使用顯著性水平為0.05的Wilcoxon秩和檢驗[33]在統計學上將對比算法的結果與VaEA-SDN的結果兩兩進行比較，其中“+”“-”和“=”分別表示對比算法的性能比VaEA-SDN顯著優、顯著劣以及在統計學上性能相似。

3.3 參數設置

（1）遺傳算子：依據所有對比算法的原始論文，交叉概率pc=1；變異概率pm=1/D，D是決策變量的數量；交叉分布指標nc=20；變異分布指標nm=20。

（2）種群的規模：種群的規模N等于參考點的數量H，表3中展示了不同的目標對應的種群規模，正如文獻[7]和[21]所建議的那樣。

（3）算法的終止條件：每個算法在每個測試問題上都獨立運行20次。每次算法在3、5、8、10個目標的測試問題上運行的終止條件是對應的最大迭代次數或評價次數[21]，如表3所示。

表3 種群的規模和最大迭代次數Table 3 Population size and maximum number of iterations

（4）對比算法中的參數按原始論文設置：在NSGAIICSDR中，控制小生境規模的兩個參數kmax=1.6，Δk=1.1，控制收斂度的兩個參數amax=60，Δa=15。

3.4 實驗結果分析

在本節中，首先驗證被提出的支配關系的有效性。將在VaEA中嵌入SDN支配的VaEA-SDN與VaEA進行對比仿真實驗，采用GD和CPF作為評價指標以驗證被提出的支配關系可以提高VaEA的收斂性和多樣性，實驗結果如表4所示。然后，為了評估VaEA-SDN平衡收斂性和多樣性的性能，采用IGD作為評價指標，將VaEA-SDN與6個對比算法在DTLZ和MaF系列問題上進行仿真實驗，仿真結果分別如表5和表6所示。對于每個測試問題，最好的結果突出顯示。

表4 VaEA和VaEA-SDN在DTLZ測試問題上的GD值和CPF值Table 4 GD and CPF values obtained by VaEA and VaEA-SDN on DTLZ test problems

表5 7種算法在DTLZ測試問題上的IGD值Table 5 IGD values of seven algorithms on DTLZ test problems

表6 7種算法在MaF測試問題上的IGD值Table 6 IGD values of seven algorithms on MaF test problems

3.4.1 SDN支配有效性驗證

相較于VaEA-SDN，在超過5個目標具有多模態特征的DTLZ1和大部分DTLZ3測試問題上，VaEA的收斂性指標更好，多樣性指標較差。這是因為隨著目標維數的增加，DTLZ1的局部帕累托前沿的數量會線性遞增，而DTLZ3的局部帕累托前沿的數量是呈指數倍增加，VaEA中采用的帕累托支配關系過度地強調解的收斂性，沒有考慮解的多樣性，使得VaEA陷的局部收斂性較好，但是難以向全局最優搜索，GD值更好，CPF值較差。8和10目標的DTLZ2的帕累托前沿上的點至坐標原點的歐式距離均為1，SDN利用目標求和來度量解的收斂性，可以保證解的收斂性良好，但可能會使解偏離均勻分布的參考向量。3目標的DTLZ5和DTLZ6最終會在三維空間退化成一條曲線，使得VaEA-SDN的小生境內集中過多的解，其中采用的密度估計方法難以判斷解的分布性。故而VaEA-SDN在這幾個測試實例上的多樣性比VaEA差。

但是VaEA-SDN的優勢還是很明顯的，從表4中的結果可知，VaEA-SDN在DTLZ的24個測試實例中均獲得了18個最佳GD值和CPF值。VaEA-SDN在DTLZ4和DTLZ5上均取得了最佳的收斂性，同時在這兩個測試問題上，多樣性也取得了令人滿意的表現。同樣，對于帕累托前沿特征綜合了DTLZ4和DTLZ5更復雜的DTLZ6，VaEA-SDN在收斂性和多樣性方面均展現了強大的競爭力。對于DTLZ4和DTLZ2，SDN支配在所有測試實例上均改善了VaEA的收斂性。特別是SDN支配使VaEA的多樣性在具有偏好特點的DTLZ4所有測試實例均得到了改善。

為了直觀地觀察改進策略的性能，圖4中畫出算法VaEA和VaEA-SDN在DTLZ測試系列中具有代表性的10目標DTLZ3和8目標DTLZ6上GD值的迭代曲線。很明顯，無論從收斂速度還是收斂精度方面比較，SDN支配均極大地改善了VaEA的性能。

圖4 VaEA和VaEA-SDN在DTLZ3和DTLZ6上GD值的變化Fig.4 Variation of GD values of VaEA and VaEA-SDN on DTLZ3 and DTLZ6

綜合以上分析和表4中的仿真結果可知SDN支配可以有效地保證了VaEA的收斂性，同時提高VaEA的多樣性，這為接下來執行廣泛的實驗驗證VaEA-SDN平衡收斂性和多樣性的競爭力奠定了基礎。

3.4.2 DTLZ系列測試問題上的性能驗證與分析

表5展示了7種算法在DTLZ基準測試問題上IGD的平均值和標準差。顯然，VaEA-SDN是最佳的優化算法，CDR-MOEA緊隨其后，因為在24個測試實例上VaEA-SDN和CDR-MOEA分別獲得了12和9個 最佳IGD，而NSGA-Ⅲ、VaEA、MSEA、NSGAII-CSDR和RPSNSGAII獲得的最佳結果數分別為3、0、3、2、0。相較于VaEA，VaEA-SDN在總共24個測試實例上有22個結果超過了VaEA。以下是對實驗結果的詳細分析。

DTLZ1和DTLZ3是具有多模態特征的測試問題，這會對算法收斂到全局最優產生極大的挑戰。從表5的結果可以觀察到，在這兩個測試問題上，VaEA-SDN性能略次于NSGAII-CSDR和CDR-MOEA。從圖5所有算法在10目標的DTLZ3上所獲解集的平行坐標圖來看，NSGA-III、VaEA、MSEA以及RPS-NSGAII所獲解集的收斂性很差，僅僅只有VaEA-SDN、NSGAII-CSDR和CDR-MOEA可以獲得收斂性且多樣性良好的解集。主要因為這3種算法均在非支配排序階段同時對解的收斂性和多樣性進行了維護。這對于算法然收斂到全局最優具有優勢。NSGAII-CSDR和CDR-MOEA利用候選解之間的角度來自適應地確定小生鏡的規模。此外，CDR-MOEA還采用了一種角度距離維護多樣性。NSGAII-CSDR依據進化進程利用參數更新小生境的規模和收斂性度量方法。因此，相比VaEA-SDN，NSGAIICSDR和CDR-MOEA處理具有多模態特征問題的表現更勝一籌。

圖5 7種算法在10目標DTLZ3上解集的平行坐標圖Fig.5 Parallel coordinates of solution sets obtained by seven algorithms on 10-objective DTLZ3

DTLZ2是一個相對簡單的測試問題。VaEA-SDN在DTLZ2的所有測試實例上均取得了最佳的表現。NSGA-III在該測試問題上的性能也不錯。由于DTLZ2的帕累托前沿均勻分布在目標空間，VaEA-SDN和NSGA-III都引入一組均勻分布的參考點。因此，在保持良好收斂的情況下有效地維護解集的多樣性。

DTLZ4是具有偏好特點的測試問題。在該測試問題上，VaEA-SDN表現最佳。從圖6解的分布可以直觀地觀察到NSGAII-CSDR和CDR-MOEA所獲解的多樣性特別差。VaEA、MSEA和RPS-NSGAII雖然可以獲取接近且覆蓋整個帕累托前沿的解，但是解的多樣性較差。即使NSGA-III得到解集多樣性較好，但是只有少數解分布在真實帕累托前沿上。只有VaEA-SDN在該測試實例上可以得到收斂性和多樣性均良好的解集。

圖6 7種算法在3目標DTLZ4上獲得的非支配解集Fig.6 Non-dominated solution sets obtained by seven algorithms on 3-objective DTLZ4

DTLZ5帕累托前沿面具有退化的特點。CDR-MOEA在該問題上表現最佳，這是因為CDR-MOEA利用單個解與鄰近參考向量的角度距離可以使解在處理退化問題時保持解盡可能位于鄰近個體中心，有效地維護解的多樣性。雖然VaEA-SDN在該問題上沒有獲得最佳的IGD值，但是，它的性能并不差，僅僅緊隨CDR-MOEA其后。在8、10個目標上，VaEA-SDN的表現仍然比NSGA-III、VaEA、MSEA、NSGAII-CSDR和RPS-NSGAII好。圖7（a）展示了7種算法在10目標的DTLZ5上IGD值的變化曲線，相比于VaEA，SDN支配關系極大改善了VaEA的性能，并且進化過程性能穩定。

DTLZ6是在DTLZ5上改進得到的測試問題。與3目標的DTLZ5類似，具有3個目標的DTLZ6最終都會退化成一條曲線。正如在3.4.1小節分析的那樣，在這兩個測試實例上VaEA-SDN難以判斷解的分布，故而VaEA-SDN在3目標的DTLZ6上表現出了中等的性能。但是，隨著目標維數的增加，VaEA-SDN實現了最佳的性能。從圖7（b）可以看出來，即使VaEA-SDN在進化早期性能不如CDR-MOEA和NSGAIII-CSDR，但是它的性能改善幅度最大且收斂速度最快，并且在進化末期獲得了最佳的表現。

圖7 7種算法在10目標的DTLZ5和DTLZ6上IGD值的變化Fig.7 Variation of IGD values of seven algorithms on DTLZ5 and DTLZ6 with 10-objective

3.4.3 MaF系列測試問題上性能驗證與分析

DTLZ測試系列問題缺乏凸特征的測試問題。為了更全面地驗證被提出VaEA-SDN的優勢，MaF系列測試問題被用來執行進一步的實驗。

表6展示了7種算法在MaF系列測試問題上的IGD值，很明顯VaEA-SDN在MaF系列測試問題上極具優勢。因為VaEA-SDN在MaF的所有測試實例上均優于NSGA-III和RPS-NSGAII。此外，相比其他6個算法，VaEA-SDN在MaF4和MaF5的所有測試實例上均展現了最好的表現，同時在MaF1和MaF3也取得了3個最佳的結果。值得注意的是在3目標MaF系列測試上，MSEA的性能與VaEA-SND性能類似，取得了較好的結果。這是因為不像在高維目標空間，在較低維的3目標MaF上依然會出現較多的非支配解，MSEA利用帕累托帕累托支配關系不斷重復判斷種群進化所處的階段，然后每次都僅僅替換掉收斂性和多樣性最差的解。因此，MSEA可以在較低維空間保持解集的良好分布和收斂。

為了更直觀地觀察各個算法的性能指標，圖8展示了所有對比算法在3、5、8、10目標的MaF1和MaF5上所獲IGD值的三維柱狀圖。從圖8可以清晰地觀察到RPS-NSGAII和NSGA-III在MaF1上性能較差，而CDRMOEA和NSGAII-CSDR在MaF5上的性能較差，特別是它們在8和10目標的MaF5上IGD值都很大，說明這兩個算法處理具有偏好的凸問題難以獲得收斂且分布良好的解集。

圖8 7種算法在MaF1和MaF5上獲得的平均IGD值Fig.8 Averange IGD values obtained by seven algorithms on MaF1 and MaF5

圖9展示了所有對比算法在10目標的MaF4和MaF5上的IGD變化曲線。對于10目標的MaF4，圖9（a）可以觀察到VaEA-SDN比VaEA更快且更好地收斂，且在該測試實例上取得了最佳性能。對于10目標的MaF5，圖9（b）可以觀察到VaEA和VaEA-SDN在整個進化過程中性能一直是最好的兩個算法，但是，VaEA在進化早期的性能劣于VaEA-SDN。

圖9 7種算法在10目標的MaF4和MaF5上IGD值的變化Fig.9 Variation of IGD values of seven algorithms on MaF4 and MaF5 with 10-objective

此外，為了直觀地比較各個算法所獲的解集質量，圖10展示了所有對比算法在10目標MaF3上所獲解集的平行坐標圖。NSGA-III、VaEA、MSEA、RPS-NSGAII、CDR-MOEA在該測試實例上IGD的值都特別大，說明這5種算法處理多模態且凸的MaF3時根本無法收斂。從圖10展示的結果來看，僅僅只有NSGAII-CSDR和VaEA-SDN可以獲得一組近似到帕累托前沿的解。

圖10 7種算法在10個目標的MaF3上解集的平行坐標圖Fig.10 Parallel coordinates of solution sets obtained by seven algorithms on 10-objective MaF3

最后，VaEA-SDN在MaF的16個測試實例上取得了14個最好的結果，而它的6個對比算法NSGA-III、VaEA、MSEA、NSGAII-CSDR、RPS-NSGAII以及CDRMOEA僅僅分別獲得了0、2、6、1、0、1個最佳結果。因此，綜合以上的分析，VaEA-SDN對于處理凸特征的系列復雜問題同樣具備極大的優勢。

3.5 汽車碰撞安全實驗的應用

為了驗證VaEA-SDN算法的實用性，將其應用于汽車碰撞安全設計問題的優化[34]。該問題旨在優化車輛前部結構的耐撞性。第一個目標是吸能，第二個目標是汽車正面碰撞時加速度，第三個目標是偏置碰撞時的腳趾板侵入。該優化問題包含3個相互沖突且需要同時最小化的目標。本次實驗最大迭代次數設置為1 000，種群的大小設置為91。所有算法在該問題上20次運行得到的平均IGD值用作比較結果。由于計算IGD值需要一組參考集，參照文獻[21，35]，將所有算法在該實際問題上獲得的非支配解的合并解集作為參考集。正如表7所示，采用多階段搜索策略的MSEA獲得了最佳的結果，但是它的計算復雜度最高。雖然VaEA-SDN在該實際應用不是最佳的算法，但是，它的性能僅僅稍遜于MSEA，同時相較于其他5個先進的對比算法，VaEASDN取得了最佳的結果。因此，VaEA-SDN在實用性方面具備一定的應用價值。

表7 7種算法汽車安全設計優化中獲得的IGD值Table 7 IGD values obtained by seven algorithms in vehicle safety design optimization

4 結論及未來的工作

為了提高多目標進化算法解決多目標優化問題平衡收斂性和多樣性的能力，提出了SDN支配關系。相較于帕累托支配關系，被提出的支配關系在非支配排序階段同時管理了解的收斂性和多樣性。然后，將該支配關系嵌入VaEA設計了多目標進化算法VaEA-SDN。最后，VaEA-SDN與6個先進的多目標進化算法在DTLZ和MaF測試系列問題上進行了廣泛的對比仿真實驗。實驗結果表明，VaEA-SDN求解多目標優化問題可以有效地平衡解集的收斂性和多樣性。最后，汽車碰撞安全實驗的應用也驗證了VaEA-SDN算法的實用性。但是，VaEA-SDN也有一定的局限性，解決多模態特征的問題上性能稍遜于NSGAII-CSDR和CDR-MOEA，解決退化特征的問題上稍遜于CDR-MOEA。因此，相較于NSGAII-CSDR和CDR-MOEA，解決具有多模態[36-37]和退化特征[38]的實際問題也會有一定的局限性。將來可以考慮設計一種約束處理策略到VaEA-SDN中去解決現實應用中的約束多目標優化問題。