一種新角度支配關系的多目標進化算法

張浩楠，過曉芳

(西安工業大學 基礎學院,西安 710021)

在科學研究和工程領域中,經常會遇到同時需要優化多個目標的最優化問題,即多目標優化問題[1]。多目標優化問題中的特點是解之間相互沖突,最優解不是唯一的,而是一組互不支配的折中解,稱為Pareto最優解[2]。隨著目標個數的增加,最優解集合的數量不斷增大,算法計算量越來越大,運用傳統的多目標優化算法求解變得非常困難[3]。由于多目標進化算法基于種群的特性能夠在一次運行中獲得一組折中解,并且其不對所求問題需滿足的數學性質等做出要求,因此多目標進化算法已廣泛應用于各種多目標優化問題的求解[4-6]。目前,多目標進化算法求解多目標優化問題大致分為以下三類:基于支配的多目標進化算法[7-8],基于分解的多目標進化算法[9-11]以及基于指標的多目標進化算法[12-14]。

在求解高維的多目標優化問題的時候,隨著優化目標個數的增加,傳統的Pareto支配無法提供足夠的選擇壓力[15]。基于支配的多目標進化算法能夠更好地提高解的選擇壓力,因此研究者們從不同視角提出了多種改進的支配關系。現階段,支配關系大致可分為以下幾類:① 基于支配區域擴展的方法。文獻[16-17]提出了α-支配,該支配準則的基本思想是在兩個目標之間設置折衷率的上、下界,使得種群中性能較差的DRSs被支配,減少種群中非支配解比例,增加選擇壓力,提升算法的收斂性。但該支配準則中的參數值α不易設置,較難找到一個分布、收斂均良好的折中解集。文獻[18]提出了控制支配區域支配方法(CDAS),該方法通過自定義參數S控制解支配區域的擴張或收縮程度,從而達到提升收斂性或增強多樣性的目的。但CDAS的參數S在面對不同的問題時不容易確定,并且其難以同時提高解集的收斂性或多樣性。文獻[19]針對CDAS中參數不易設置進行改進,提出自控制支配區域支配方法(S-CDAS),該算法在比較二者支配關系時,不需使用外部參數S可自行控制每個解的支配面積,實現了解集收斂性和多樣性之間更好的平衡。該類方法能夠有效地增加解的選擇壓力,但沒有兼顧多樣性,會使非支配解集集中在Pareto前沿的某一部分,邊界解可能會被支配。② 基于網格的方法。文獻[20-21]提出了ε-支配。該支配準則通過將目標空間劃分為多個超立方體網格,在擴大支配區域的同時,保證每個網格中只存在一個非支配解,既增大選擇壓力,也維持了分布的均勻性。但采用ε-支配的算法進行進化迭代的過程中,最優前沿上一些極端解容易被其他解支配,導致邊界解丟失,多樣性不夠理想。文獻[22]提出了Grid支配,該支配方法在ε-支配需自行設置參數的基礎上進行改進,采用自適應網格結構,并且通過解的位置采用單獨居中的網格進行計算,在增加算法選擇壓力的同時,維護種群的多樣性。但該支配方法可能會消除相鄰的良好收斂解,從而導致算法收斂性能降低。該類方法通過將目標空間劃分為多個網格,以保證種群的多樣性,同時擴大解的支配區域,從而提高了選擇壓力,但該類算法的網格規模不易選取,時間復雜度較大。③ 基于小生境的方法。文獻[23]提出了增強支配關系的準則(SDR),該支配方法不需要用戶預先定義,根據種群的分布自定義定制支配區域,并在此區域中搜索收斂性最佳的解,從而更好地平衡了解集的收斂性和多樣性,但該算法性能差異同領域定制的規則緊密相關。該類方法能夠保證解的多樣性,但對復雜Pareto前沿的求解效果不太理想。④ 基于角度的方法。文獻[24]提出了角度支配(AD支配),該支配方法通過構建由解和各軸節點組成的角度向量進行非支配排序,由于角度向量與坐標軸緊密相關,靠近PF和邊界的解具有較高的非支配排序等級。因此AD支配在擴大解的支配區域的同時,又能有效地保持邊界解,兼顧了解集的收斂性和分布的廣泛性,但采用角度支配時解集均勻性仍可提升。該類方法增加解之間的選擇壓力,以保證解的收斂性,但解集的多樣性不能很好地保證。

盡管以上改進的支配關系明顯增強了算法求解的性能,但均無法更好地兼顧收斂性和多樣性。采用ε-支配和AD支配的算法,都通過擴大解支配區域的方法提高算法的收斂性。基于網格的支配方法確保每個網格中只存在一個非支配解,維持解集分布的均勻性,但存在邊界解丟失的問題,導致解集分布廣泛性不夠理想。AD支配使得靠近PF和邊界的解具有較高的非支配排序等級,能有效地保持邊界解,維持解集分布多樣性,但均勻性仍有提高的余地。基于此,文中將ε-支配與AD支配進行有效結合,擬提出了一種網格-角度支配關系(Epsilon-Angle Dominance Relation,ε-AD)。該支配關系具有如下特點:①ε-AD支配在以上兩種支配方法的基礎上,進一步擴大解的支配區域,提升算法的收斂性;② 利用AD支配準則偏好邊界解這一特性,ε-AD支配在進化過程中可有效保持邊界解,提升解集分布的廣泛性;③ε-AD支配基于網格的支配方式,保證每個網格中只能有一個非支配解,維持解分布的均勻性。文中將ε-AD支配嵌入到經典NSGAII算法框架中代替原有的Pareto支配,設計了一種新角度支配關系的多目標進化算法(Epsilon-Angle-NSGAII,ε-AD-NSGAII)。

1 新角度支配關系的多目標進化算法

文中給出多目標優化相關概念和定義,給出新的角度支配關系定義,將新支配關系嵌入到NSGAII算法中,提出一種新角度支配關系的多目標進化算法:ε-AD-NSGAII。

1.1 多目標優化相關概念和定義

定義1多目標優化問題。多目標問題一般描述為

minf(x)=(f1(x),f2(x),…,fm(x)),

(1)

式中:x=(x1,x2,…,xn)為n維決策空間中的解;fm(x)為第m個子目標函數。

定義2Pareto支配。對于式(1)中的MOP問題,設x,y為決策空間中任意兩個解,稱x支配y(記為x

(2)

定義3ε-支配。對于式(1)中的MOP問題,設x,y為決策空間中任意兩個解,稱xε-支配y(記為x<εy)當且僅當滿足以下條件:

圖1為ε-支配概念圖,從圖1中可以看出,若解x,y根據Pareto支配關系進行比較,二者之間沒有支配關系。但若按ε-支配關系的定義,解x支配的區域為陰影區域,此時x<εy。

圖1 ε-支配概念圖

定義4AD支配。對于式(1)中的MOP問題,設x,y為決策空間中任意兩個解,稱xAD支配y(記為x

(4)

圖2為AD支配概念圖,從圖2中可以看出,若解x,y根據Pareto支配關系進行比較,二者之間沒有支配關系。但若按照AD支配關系進行比較,支配區域擴張,此時x

圖2 AD支配概念圖

1.2 網格-角度支配

為直觀解釋所提出的ε-AD支配的概念,圖3為此支配關系在兩目標空間下的情景,陰影部分為當前種群中任意解x的ε-AD支配區域。如圖3所示,假設比較任意兩個解x和y間的優劣,若兩個解之間距離小于閾值λ,選用ε-支配計算其適應度值,以提升接近Pareto前沿時解分布的均勻性;若兩個解之間距離大于或等于閾值λ,選用AD支配計算其適應度值,降低了遠離Pareto前沿時優秀解被支配掉的概率。解x經過ε-AD支配后的適應度向量為f(x)=(f1(x),f2(x)),見定義5,而fi(x)的計算見式(5)。

圖3 ε-AD支配概念圖

定義5設x,y為決策空間中任意兩個解,x經過ε-AD支配后的適應度向量的第i個分量fi(x)定義為

(5)

定義6對于式(1)中的MOP問題,設x,y為決策空間中任意兩個解,稱xε-AD支配y(記為x<ε-angley)當且僅當滿足以下條件:

(6)

1.3 新角度支配關系的多目標進化算法

文中以NSGAII算法為例說明如何將ε-AD支配整合到基于Pareto支配的算法框架中。

算法1ε-AD支配方法

輸入:種群P中任意兩個解x、y,解之間的對比閾值λ

輸出:x、y之間的ε-AD支配關系

Step 1:計算x、y間歐式距離d。

Step 3:當d≥λ時,若xAD支配y,則xε-AD支配y;若yAD支配x,則yε-AD支配x;否則,x、y互不ε-AD支配。

Step 4:當d<λ時,若xε-支配y,則xε-AD支配y;若yε-支配x,則yε-AD支配x;否則,x、y互不ε-AD支配。

Step 5:輸出任意兩個解x、y間的ε-AD支配關系比較。

算法2新角度支配關系的多目標進化算法

輸入:種群規模N,最大迭代次數Tmaxgen

輸出:最末代種群Pmaxgen

Step 1:初始化迭代計數器t=0。

Step 2:隨機生成種群大小為N的初始種群P。

Step 3:根據二元錦標賽選擇法構建交配池Pmating。

Step 4:對Pmating進行交叉、變異操作,產生子代種群Q。

Step 5:合并父代種群P和子代種群Q:R=P∪Q。

Step 6:根據算法 1對中間種群R中任意兩個解間的ε-AD支配關系進行比較。

Step 7:根據ε-AD支配關系將種群P劃分為l層的非支配層(F1,F2,…,Fl)。

Step 8:當滿足|P+Fj|≤N,則P=P∪Fj。

Step 9:當|P+Fj|≤N,計算Fj的擁擠距離。

Step 10:從Fj中刪除k個擁擠距離最大的解:k=|P|+|Fj|-N。

Step 11:Fj中保留下的解和P構成新的種群P。

Step 12:重復步驟3到步驟11,直至達到最大迭代次數Tmaxgen,轉至步驟13。

Step 13:輸出最末代種群Pmaxgen。

1.4 時間復雜度分析

對采用ε-AD支配的一次種群排序過程來說,N為種群大小,M為目標數,其步驟為:① 計算每個個體在每個目標下的角度值,其時間復雜度為O(N*M);② 計算每個個體在每個目標下的網格適應度值,其時間復雜度為O(1);③ 進行非支配排序,其時間復雜度為O(N2)。綜上,采用ε-AD支配的一次種群排序過程的時間復雜度為O(M*N+N2)。

2 實驗結果與分析

文中采用GD[25],IGD[26]和SPACING[27]評價指標,選取DTLZ[28]和WFG[29]測試問題集,將ε-AD-NSGAII與其他四種多目標進化算法的性能進行比較。關于對比算法的選取,將ε-支配和AD支配嵌入NSGAII框架,構造ε-NSGAII和AD-NSGAII,作為改進支配關系的對比算法。選擇目前新提出的基于參考點支配的RPDNSGAII和基于差分的多目標進化算法MOEA/D-DE作為另外兩個對比算法。將五類算法生成解集合的收斂性和分布性進行比較。

2.1 測試問題、評價指標及其相關參數設置

2.1.1 測試問題

文中實驗選用3個優化目標下的DTLZ和WFG兩個系列的測試問題,考察算法求解多目標優化問題的能力。上述兩個測試問題集具有多種Pareto前沿特征,其中DTLZ測試問題集包含具有非凸、有偏、不連續、多模、混合等問題特性的測試函數,WFG測試問題集包含具有欺騙、偏轉、多模等問題特性的測試函數,以及一組包含多種幾何結構的形狀函數。為了保證實驗公正性,文中實驗均在CPU 3.70 GHz、內存16 GB的PC上運行,所有算法均在PlatEMO平臺上運行,編程工具為Matlab R2018a。

2.1.2 評價指標

為綜合評估算法的收斂性和多樣性,文中采用以下3個性能指標,即世代距離(GD)、反轉世代距離(IGD)和空間評價方法(Spacing)。綜合3個性能指標,能夠很好地度量解集的收斂性和多樣性。

采用GD度量作為收斂性評價指標,它表示算法所求得的非支配解集PFknown中的個體與Pareto最優解集PFtrue之間的距離,其表達式為

(7)

式中:n為PFknown中的向量數;p為2;di為所獲得解集中向量與PFtrue中最近向量之間的歐氏距離。該指標越低,表示算法的收斂性越好。

采用IGD評價指標,度量了Pareto最優解集PFtrue中的個體到算法所求得的非支配解集PFknown的平均距離,其表達式為

(8)

采用Spacing評價指標,能夠衡量算法所求得的非支配解集PFknown中個體的分布是否均勻,其表達式為

(9)

2.1.3 參數設置

文中5種算法的對比實驗均采用以下設置:進化種群規模為100,每次運行最大評估次數為50 000,進行交叉操作時使用模擬二進制交叉算子(SBX算子),交叉率pc為1,進行變異操作時使用多項式變異算子(PM算子),變異率pm為1/n(n為決策變量數目),交叉、變異算子參數ηc及ηm均為20。另外,采用DTLZ和WFG測試問題時,網格大小ε取值為0.001～0.2,放大系數k取值為30～60,閾值λ取值為0.005～1。

2.2 結果與分析

為驗證ε-AD支配在多目標優化中的有效性,用ε-AD支配、AD支配和ε-支配替換NSGAII算法中的pareto支配,構造ε-AD-NSGAII、AD-NSGAII以及ε-NSGAII算法,將ε-AD-NSGAII與ε-NSGAII、AD-NSGAII、RPDNSGAII以及MOEA/D-DE算法進行比較。為減少隨機因素對算法性能評估的影響,將上述5種算法在所有測試問題上均獨立運行30次。表1～表3給出算法性能指標的統計結果,加粗標記為對應指標上表現更好,(+/-/=)為一致性檢驗結果。

表1 5種算法在DTLZ和WFG問題集上獲得的GD均值與標準差

2.2.1 不同測試問題中的GD比較分析

分析ε-AD-NSGAII與ε-NSGAII、AD-NSGAII、RPDNSGAII以及MOEA/D-DE在解決多目標優化問題時收斂性上的差別。表1給出了上述5種算法在DTLZ和WFG測試問題集中16個測試問題上所獲得的GD均值與標準差。由表1可知,在16個測試問題中,ε-AD-NSGAII獲得了8個最佳GD均值,RPDNSGAII獲得了4個最佳GD均值,AD-NSGAII獲得了3個最佳GD均值,MOEA/D-DE獲得了1個最佳GD均值,ε-NSGAII沒有獲得最佳GD均值。同時由一致性檢驗結果可知,與ε-NSGAII、AD-NSGAII、RPDNSGAII和MOEA/D-DE相比,ε-AD-NSGAII分別在14、13、12和14個測試問題上有更好的表現。由于使用ε-AD支配的進化算法在大多數問題上都能獲得更好的收斂性,因此使用ε-AD支配的進化算法在解決多目標優化問題上更能快速、準確得找到最優解集,具備較好的收斂性。

2.2.2 不同測試問題中的IGD比較分析

分析ε-AD-NSGAII與ε-NSGAII、AD-NSGAII、RPDNSGAII以及MOEA/D-DE在在解決多目標優化問題時收斂性和多樣性上的差別。表2給出了上述5種算法在DTLZ和WFG測試問題集中16個測試問題上所獲得的IGD均值與標準差。由一致性檢驗結果可知,在16個測試問題中,與ε-NSGAII、AD-NSGAII、RPDNSGAII和MOEA/D-DE相比,ε-AD-NSGAII分別在15、15、8和15個測試問題上有更好的表現。由此可見,新提出的算法較之ε-NSGAII、AD-NSGAII和MOEA/D-DE,具有明顯較優的綜合能力上的優勢。關于ε-AD-NSGAII與RPDNSGAII的對比分析,ε-AD-NSGAII采用一種將ε-支配和AD支配進行有效結合的支配關系對解集進行排序,RPDNSGAII采用基于參考點的支配關系,能夠使用一組分布良好的參考點對解集進行排序,以上兩個算法都能在測試問題上取得相似的效果。綜上,使用ε-AD支配的進化算法,其具有較優的收斂性和多樣性之能力。

表2 5種算法在DTLZ和WFG問題集上獲得的IGD均值與標準差

2.2.3 不同測試問題中的Spacing比較分析

分析ε-AD-NSGAII與ε-NSGAII、AD-NSGAII、RPDNSGAII以及MOEA/D-DE在解決多目標優化問題時分布的多樣性上的差別。表3給出了上述5種算法在DTLZ和WFG測試問題集中16個測試問題上所獲得的Spacing均值與標準差。由表3可知,在16個測試問題中,ε-AD-NSGAII獲得了13個最佳Spacing均值,AD-NSGAII獲得了2個最佳Spacing均值,MOEA/D-DE獲得了1個最佳Spacing均值,RPDNSGAII和ε-AD-NSGAII沒有獲得最佳Spacing均值。同時由一致性檢驗結果可知,與ε-NSGAII、AD-NSGAII、RPDNSGAII和MOEA/D-DE相比,ε-AD-NSGAII分別在13、13、16和15個測試問題上有更好的表現。綜上所述,使用ε-AD支配的進化算法求得的解集分布更均勻,ε-AD支配具有更優的多樣性保持能力。

表3 5種算法在DTLZ和WFG問題集上獲得的Spacing均值與標準差

2.2.4 不同測試問題中的收斂速度比較

為更加直觀地比較ε-AD-NSGAII、ε-NSGAII和AD-NSGAII的尋優性能,選取3個優化目標下的DTLZ和WFG兩個問題集作為測試問題,各算法在上述測試問題集上均獨立執行30次取均值,每次運行最大評估次數為50 000,以獲得穩定的GD和Spacing均值。圖4～圖11為3種算法在上述測試問題上的GD和Spacing指標的進化軌跡圖。其中,橫坐標為進化代數,縱坐標為指標值。

圖4 3種算法在3維DTLZ1、DTLZ2測試函數上的GD、Spacing進化軌跡圖

圖5 3種算法在3維DTLZ3、DTLZ4測試函數上的GD、Spacing進化軌跡圖

圖6 3種算法在3維DTLZ5、DTLZ6測試函數上的GD、Spacing進化軌跡圖

圖7 3種算法在3維DTLZ7、WFG1測試函數上的GD、Spacing進化軌跡圖

圖8 3種算法在3維WFG2、WFG3測試函數上的GD、Spacing進化軌跡圖

圖9 3種算法在3維WFG4、WFG5測試函數上的GD、Spacing進化軌跡圖

圖10 3種算法在3維WFG6、WFG7測試函數上的GD、Spacing進化軌跡圖

圖11 3種算法在3維WFG8、WFG9測試函數上的GD、Spacing進化軌跡圖

由圖4～圖11可以看出,三種算法隨評估次數的增加,它們所獲得的GD均值和Spacing均值都隨進化代數的增長總體上呈下降趨勢,并且都能較快地下降至一個相對較小的值,而在后續進化過程中,指標值呈現出緩慢變小的趨勢。但對大多數問題而言,ε-AD-NSGAII算法獲得的GD均值和Spacing均值是在三者中下降最快的。因此,圖4～圖11中各算法獲得的軌跡直觀地表明了ε-AD-NSGAII算法比其他兩種算法能夠較快地獲得高質量解集。

3 結 論

1) 為有效平衡多目標進化算法的收斂性和多樣性,論文提出一種網格-角度支配關系,并將此策略嵌入到經典NSGAII算法框架中代替原有的Pareto支配,設計了一種基于網格-角度支配的ε-AD-NSGAII算法。該算法通過將ε-支配與AD支配進行有效結合,在擴大解支配區域以提升算法收斂性的基礎上,能夠維持解集分布的均勻性以及保持邊界解,有效提升算法所獲得解集的多樣性。

2) 文中基于DTLZ和WFG測試問題集,采用GD、IGD、Spacing三種評價指標,分別評估了ε-AD-NSGAII、ε-NSGAII、AD-NSGAII、RPDNSGAII以及MOEA/D-DE的有效性。實驗結果表明,在16個測試問題中,ε-AD-NSGAII算法分別取得了8個最佳的GD指標值、7個最佳的IGD指標值以及13個最佳的Spacing指標值,由此表明ε-AD-NSGAII算法較之其余4種算法具有較好的收斂性和多樣性。同時,通過對比ε-AD-NSGAII、ε-NSGAII、AD-NSGAII在上述測試集獲得的GD和Spacing指標的進化軌跡圖,可知ε-AD-NSGAII算法相比其余2種算法能夠較快地獲得高質量解集。

3) 在未來的工作中,進一步將網格-角度支配關系嵌入不同算法框架中,研究其對收斂性和多樣性的影響,求解高維多目標優化問題,以及使用網格-角度支配關系的算法求解現實中的多目標優化問題,并不斷改進算法的性能。