基于R2 指標和參考向量的高維多目標進化算法

陳國玉 李軍華 黎明 陳昊

多目標優化問題(Multi-objective optimization problems,MOPs)[1]是指多個目標被同時優化的問題.在現實生活中,經常遇到優化問題包含四個及以上目標,這類問題統稱為高維多目標優化問題(Many-objective optimization problems,MaOPs)[2?4].雖然一些經典的多目標進化算法(Multi-objective evolutionary algorithms,MOEAs),NSGA-II[5]、SPEA2[6]等能夠很好地處理多目標優化問題(兩個或三個目標),但是在解決高維多目標優化問題上效果較差.

近年來,為了提高解決高維多目標優化問題的能力,研究者們提出了許多優秀的算法,這些MOEAs 主要可以分為三類.1) 基于各種增強收斂性的算法:該類算法主要是改進Pareto 支配關系或者提出其他增強收斂性的方法,通過這些方法提高處理高維多目標優化問題時的收斂性.例如改進的Pareto 支配:?支配[7]、L 最優[8]、模糊支配[9]和優先級排序[10]等.以及其他基于增強收斂性的算法:GrEA[11]、KnEA[12]等.2) 基于分解的算法:該類算法是把一個復雜的高維多目標優化問題分解為一組單目標優化問題(Single-objective optimization problems,SOPs) 或者易于管理的多目標優化問題[13?15],如RVEA[16]、SPEA/R[17]和NSGAIII[18]等.3) 基于評價指標的算法:該類算法是采用評價指標作為選擇標準來衡量解的質量,選擇機制通過比較解的質量找到更好的解.這類算法的典型代表包括IBEA[19]、HypE[20]和SMS-EMOA[21]等.

雖然大多數多目標進化算法能夠很好地處理一些高維多目標優化問題,但這些算法對Pareto 前沿的形狀十分敏感[22],導致在處理不同形狀的PF 時不能很好地平衡收斂性和多樣性.針對上述問題,本文提出了一個基于R2 指標和參考向量的高維多目標進化算法(R2-RVEA).該算法的主要創新在于:1) R2-RVEA 基于Pareto 支配作為選擇標準選取非支配解,僅當非支配解的數目超過種群規模時,算法進一步采用R2 指標選擇和種群分解策略共同管理多樣性;2) R2-RVEA 基于R2 指標進一步選擇種群分解淘汰的解,這有利于保留具有良好收斂性和多樣性的解.

1 相關工作

1.1 基于指標的多目標進化算法

目前,相關文獻提出了許多評價指標,有衡量收斂性的評價指標:世代距離(GD)[23];衡量多樣性的評價指標:PD[24];同時衡量收斂性和多樣性的評價指標:反世代距離(IGD)[25]、超體積(HV)[26]、R2[27]以及IGD-NS[28].這些指標廣泛的應用于評估解集的質量,有些指標還被用作MOEAs 的選擇標準.

基于評價指標的MOEAs 比較典型的算法有:IBEA[19]、HypE[20]、SMS-EMOA[21].Zitzler 等在2004 年提出IBEA[19],該算法首先用二進制評價指標來定義優化目標,然后使用它作為選擇標準.通過幾個MOPs 測試問題的實驗,結果表明IBEA 的性能優于NSGA-II[5]和SPEA2[6].同時,IBEA 的主要貢獻是為基于評價指標的MOEAs 提供了一個通用框架,它可以嵌入其他評價指標設計算法.

SMS-EMOA[21]是由Beume 等提出的基于評價指標的MOEAs.該算法采用了HV 指標作為選擇標準,通過實驗對比,可以看出SMS-EMOA 能夠很好地處理多目標優化問題,但是在處理高維多目標優化問題時,HV 的計算成本會隨著目標數目的增加呈指數型增加.針對這個問題,Bader 和Zitzler 提出了一種基于快速HV 的進化算法用于高維多目標優化(HypE)[20].在HypE 中,為了減少HV 計算成本的消耗采用Monte Carlo 估計法進行估計近似的HV 值而不是計算精確的HV 值,這使得HV 的計算效率在目標數很大時明顯提高.

近年來,陸續出現了一些基于指標的MOEAs,例如:Tian 等[29]提出了一種基于指標的MOEAs(AR-MOEA),該算法采用了IGD-NS 指標作為選擇標準,并且設計了一種參考點適應方法調整參考點來處理不同形狀的PF;還有Sun 等提出的一種基于IGD 指標的進化算法(MaOEA/IGD)[30],該算法采用了IGD 指標挑選出收斂性和多樣性良好的解,并且利用計算效率較高的支配表方法來分配解的等級值.

最近的一些研究表明R2 指標能夠很好地平衡收斂性和多樣性.R2-IBEA[31]消除了選擇中的支配排序,利用R2 指標作為選擇標準進行個體選擇.通過實驗表明,該算法能夠在空間中產生分布較好的個體.Trautmann 等提出了一個基于R2 指標選擇的多目標搜索算法(R2-EMOA)[32],該算法首先采用非支配排序管理種群,而R2 指標作為第二選擇標準管理非支配排序的臨界層.此外,MOMBIII[33]通過采用成就量化函數(ASF) 替代加權切比雪夫度量以處理高維多目標優化問題,并提出一種參考點更新方法來解決歸一化過程中解集的多樣性對選擇參考點敏感的問題.通過與多個算法大量的對比實驗表明,MOMBI-II 能夠很好地處理超多目標優化問題.近期,Li 等提出了一個基于兩階段R2指標的高維多目標進化算法(TS-R2EA)[34],首先采用R2 指標作為主要選擇方法,參考向量引導的目標空間劃分方法則作為第二選擇策略.這些基于R2指標的算法在處理MOPs 和MaOPs 上都展現了良好的性能,此外,R2 指標低計算復雜度和弱支配兼容性的特性非常適合作為選擇標準應用到算法中.

1.2 基于分解的多目標進化算法

MOEA/D[13]是基于分解的MOEAs 的代表性算法,它設置了一組均勻分布的權重向量,將高維多目標優化問題分解為一組子問題,而每個子問題的優化都是使用其相鄰子問題的當前信息.此外,在RVEA[16]中,它采用一組均勻分布的參考向量,把高維多目標優化問題分解為一組單目標問題(SOPs),使得候選解收斂到每個單目標問題的最優情況,而無需考慮不同目標之間的沖突,通過大量實驗證明,RVEA 能夠很好地處理高維多目標優化問題.

基于分解的多目標進化算法基本上采用參考點、參考向量以及權重向量等分解目標空間,由于它們作用相同,本文統一定義為參考向量.Das 和Dennis 提出的系統化方法[35]是一種廣泛使用的參考向量生成方法,該方法把點放在標準化的超平面上(一個(M ?1)維的單元網格) 傾向于所有目標軸并且在每個坐標軸上都有一個截距.如果每個目標都考慮到p個網格,則一個M目標上總數為N的參考向量為:

例如在一個3 目標(M=3)問題上,考慮到每個目標有4 個網格(p=4),則生成總數為15 的參考向量如圖1 所示.

圖1 目標問題上展示的15 個參考向量Fig.1 15 reference vectors are shown on 3-objective problem

2 基于R2 指標和參考向量的高維多目標進化算法

2.1 基于分解的多目標進化算法

R2-RVEA 采用Pareto 支配作為選擇標準,選取非支配解指導種群進化,當非支配解的數目超過種群規模時,算法進一步采用種群分解策略和R2 排序選擇管理多樣性.由于很多時候種群分解選取解的數目無法滿足種群規模,利用R2 排序能夠從種群分解淘汰的解中保留收斂性和多樣性較好的解來進一步滿足種群規模.如算法1 所示,R2-RVEA 的主要框架包含了下面的步驟:首先,初始生成一個規模為N的種群,以及一個均勻分布的參考向量集合V規模為N;然后,在主循環中,子代Qt由父代Pt隨機生成,合并到父代種群Pt中進入環境選擇;最后,執行環境選擇從合并種群中挑選出N個候選解進入下一代.在下面會著重介紹三個子部分,分別是環境選擇、種群分解和R2 排序.

算法1.R2-RVEA 算法框架

2.2 環境選擇

如算法2 所示,環境選擇的最初階段只采用非支配排序獲得當前種群的非支配解集合At,如果At中解的數目小于等于種群規模N,At就會作為種群Pt+1進入下一代,這使得種群可以快速地收斂到PF 上,并且避免較差解誤導種群進化方向.

算法2.環境選擇

i ∈{1,···,M},分別表示第i個解的標準化前和標準化后的目標值.

2.3 種群分解

種群分解選擇過程如算法3 所示.首先,通過將每個解與最近的參考向量聯系起來,把種群At分解為一組子種群.角度可以衡量解和參考向量之間的空間關系,如果一個解和參考向量之間的角度最小,那么就會被分配到這個參考向量所代表的子種群中.

算法3.種群分解

經過種群分解以后,適應度值將作為每個子種群內的選擇標準進行精英選擇,適應度值計算公式如下:

適應度計算同時衡量了解的多樣性和收斂性,利用對解與向量的夾角進行標準化,角度標準化過程使得適應度值對解和向量之間的夾角變得敏感,采用z是考慮了在不同目標存在不同量化范圍的情況,這就可以使適應度值計算對多樣性敏感,能夠有益于解的選擇.在每個子種群中,適應度值最小的解會被選作是精英進入下一代,組成解集合

2.4 R2 排序

R2 指標可以用來評估兩個集合的相關質量,分別由一個給定的近似集合A、一組權重向量WWW以及效用函數構成,R2 指標定義如下:

i=1,···,N,WWW=(w1,w2,···,wn) 是權重向量.關于等級的正式定義源于式(5),提出如下等式:

Bk=是最低等級解的集合.而當兩個解的效用值相同時,其中具有較低歐氏距離的解將會被選出,這能夠有效地消除松弛的Pareto 解.

在R2-RVEA 中,選擇ASF 作為R2 排序的效用函數.首先,利用式(6) 計算所有解的函數值,獲得能夠優化效用函數的解,將這些解放在頂層,這樣就獲得了第一等級(最優等級);然后,移除第一等級的解,以同樣的方式識別剩下的解,獲得第二等級;整個排序過程將一直持續,直到所有的解都被排序.R2 排序過程在算法4 中給出.種群分解淘汰的解通過R2 排序以后,從排序后的集合中選出前k個最好的解組成集合Rt.

算法4.R2 排序

3 實驗仿真及分析

在這個部分,提出的算法主要和當前較好的6 個MOEAs 進行實驗對比,分別是NSGAIII[18]、RVEA[16]MOEA/DD[36]、MOMBI-II[33]、KnEA[12]和TS-R2EA[34],實驗取自DTLZ 測試集和WFG 測試集.首先,進行實驗設置;然后,DTLZ 測試集中各個測試問題的實驗結果和對比分析;接下來,WFG 整個測試集的實驗結果以及對比分析;最后,算法性能分析.

在實驗中,采用了DTLZ[37]測試集中的測試問題DTLZ1-DTLZ7 以及WFG[38]測試集中的測試問題WFG1-WFG9.在DTLZ 的一個給定的M目標測試問題中,每一個目標函數都有n=k+M ?1個決策變量,在DTLZ1 中k設置為5,DTLZ2-DTLZ6 中k設置為10,以及在DTLZ7 中k設置為20.此外,WFG 基準測試套件中每一個給定測試問題的每個目標函數都有n=k+l個決策變量,k設置為(M ?1) 以及l設置為10.本文算法基于MATLAB2016a 實現,并采用多目標進化算法平臺PlatEMO[39]進行算法對比.

3.1 實驗設置

1) 交叉和變異算子設置:采用傳統的二進制交叉[40]和多項式變異[41]適用于所有的多目標進化算法.在本文中,交叉概率和變異概率分別設置為1.0 和1/n(n代表決策變量數目).而SBX 和多項式變異的分布指標都設置為20.

2) 種群規模:R2-RVEA、NSGA-III[18]、RVEA[16]、MOEA/DD[36]、MOMBI-II[33]、KnEA[12]和TS-R2EA[34]的種群規模取決于參考向量的數量.而這些參考向量采用單網格設計系統[18]生成.為了對比的公平,KnEA[12]設置與其他算法相同的種群規模.詳細配置列在表1 中.

表1 種群規模設置Table 1 Setting of population size

3) 終止條件:每一次運行的終止條件是最大代數.對于所有測試問題,在不同目標上的最大代數設置不同.在3 目標和5 目標的最大代數設置為1000,在10 目標上設置為1300,而15 目標的最大代數設置為1500.

4) 評價指標:算法的性能由HV[23]指標和IGD+[42]指標來評估.在計算HV 之前,所有目標值都要通過PF 值進行標準化.然后,HV 值就利用參考點(1,1,···,1) 和標準化后的目標值計算得來.此外,一旦目標數目大于等于5,Monte Carlo[20]評估方式采用1000000 個樣點進行更有效的計算.在IGD+指標計算中,對于每個測試實例,利用Das 和Dennis 方法在PF 上采樣大約5000 個均勻分布的點.此外,對于10 目標和15 目標問題,則采用雙層Das 和Dennis 方法生成采樣點.

5) 統計方法:每個算法在每個測試問題上都獨立運行30 次,然后采用Wilcoxon 秩和檢驗方法比較R2-RVEA 與其他對比算法獲得的結果,其中均值分析的顯著性水平設置為0.05.根據Wilcoxon 秩和檢驗方法,‘+’表示對比算法要優于R2-RVEA,‘?’表示對比算法獲得的結果比R2-RVEA 的結果差,‘≈’表示對比算法和R2-RVEA 獲得的結果沒有明顯的差異.

6) 對比算法參數設置:對于RVEA 和TSR2EA,在對比實驗中頻率參數fr和指標α分別設置為2 和0.1.在MOEA/DD 中,鄰域規模T和懲罰參數θ分別設置為20 和5,臨近選擇概率設置為δ=0.9.對于MOMBI-II,差異門限α,公差門限?和最小向量的記錄規格分別設置為0.5,0.001 和5.KnEA 的參數設置參考文獻[12].

3.2 算法在DTLZ1-DTLZ7 上對比分析

該節給出了7 個算法在DTLZ 測試集上的實驗結果,表2 和表3 分別匯總了對比算法所獲得的HV 值和IGD+值的均值和標準差(括號內為標準差).其中,突出最好的結果.

表2 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在DTLZ1?DTLZ7 上獲得的HV 值的統計結果(均值和標準差).最好的結果已突出Table 2 The statistical results (mean and standard deviation) of the HV values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on DTLZ1 to DTLZ7.The best results are highlighted

表2 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在DTLZ1?DTLZ7 上獲得的HV 值的統計結果(均值和標準差).最好的結果已突出(續表)Table 2 The statistical results (mean and standard deviation) of the HV values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on DTLZ1 to DTLZ7.The best results are highlighted(Continued table)

表3 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在DTLZ1 DTLZ7 上獲得的IGD+值的統計結果(均值和標準差).最好的結果已突出Table 3 The statistical results (mean and standard deviation) of the IGD+values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on DTLZ1 to DTLZ7.The best results are highlighted

表3 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在DTLZ1 DTLZ7 上獲得的IGD+值的統計結果(均值和標準差).最好的結果已突出(續表)Table 3 The statistical results (mean and standard deviation) of the IGD+values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on DTLZ1 to DTLZ7.The best results are highlighted(Continued table)

綜合HV 和IGD+的統計數據分析結果.DTLZ1-DTLZ4 具有規則形狀的PF,雖然R2-RVEA 沒有在所有測試實例中獲得最具競爭力的性能,但總體上獲得了良好的性能,由圖2 可以看到各個算法獲得的非支配解在DTLZ4 上15 目標實例中的分布情況.DTLZ5-DTLZ7 具有不規則形狀的PF,對于DTLZ5 和DTLZ6,R2-RVEA 主要在DTLZ5 的3 目標和DTLZ6 的3 目標上獲得了最好的性能,而在其他目標上的最好性能主要由MOEA/DD 獲得,由圖3 中可以看到各個算法獲得的非支配解在DTLZ5 上3 目標實例中的分布情況.在DTLZ7 上,綜合兩個指標的統計數據得出R2-RVEA 獲得了一般的性能,NSGA-III 性能相對穩定,總體性能相對較好,圖4 是各個算法獲得的非支配解在DTLZ7 上5 目標實例中的分布情況.綜合統計結果可以看出,R2-RVEA 在DTLZ 測試集上雖然沒有在每個測試實例上獲得最優的結果,但總體性能良好.

圖2 DTLZ4 問題15 目標上獲得的非支配解Fig.2 Nondominated solutions obtained on 15-objective DTLZ4

圖3 DTLZ5 問題3 目標上獲得的非支配解Fig.3 Nondominated solutions obtained on 3-objective DTLZ5

圖4 DTLZ7 問題5 目標上獲得的非支配解Fig.4 Nondominated solutions obtained on 5-objective DTLZ7

3.3 算法在WFG1-WFG9 上對比分析

該節給出了7 個算法在WFG 測試集上的實驗結果,表4 和表5 分別匯總了對比算法所獲得的HV 值和IGD+值的均值和標準差(括號內為標準差).其中,突出最好的結果.

表4 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在WFG1-WFG9 上獲得的HV 值的統計結果(均值和標準差).最好的結果已突出Table 4 The statistical results (mean and standard deviation) of the HV values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on WFG1 to WFG9.The best results are highlighted

表4 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在WFG1-WFG9 上獲得的HV 值的統計結果(均值和標準差).最好的結果已突出(續表)Table 4 The statistical results (mean and standard deviation) of the HV values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on WFG1 to WFG9.The best results are highlighted(Continued table)

表5 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在WFG1-WFG9 上獲得的HV 值的統計結果(均值和標準差).最好的結果已突出Table 5 The statistical results (mean and standard deviation) of the IGD+values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on WFG1 to WFG9.The best results are highlighted

表5 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在WFG1-WFG9 上獲得的HV 值的統計結果(均值和標準差).最好的結果已突出(續表)Table 5 The statistical results (mean and standard deviation) of the IGD+values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on WFG1 to WFG9.The best results are highlighted(Continued table)

表5 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在WFG1-WFG9 上獲得的HV 值的統計結果(均值和標準差).最好的結果已突出(續表)Table 5 The statistical results (mean and standard deviation) of the IGD+values obtained by R2-RVEA,NSGA-III,RVEA,MOEA/DD,MOMBI-II,KnEA and TS-R2EA on WFG1 to WFG9.The best results are highlighted(Continued table)

綜合HV 和IGD+的統計數據分析結果.WFG1 的設計是帶有偏見和混合結構的PF,R2-RVEA 的總體性能良好,要明顯優于對比算法.WFG2 是一種帶有斷開的PF,R2-RVEA 在這個測試問題上表現了不錯的性能,在5 目標數和10 目標上要明顯優于對比算法.WFG3 是一種比較難處理的問題,具有退化的PF 且決策變量不可以分離,在這個問題上,R2-RVEA 的HV 值要優于所有的對比算法,但是在15 目標上所有對比算法的HV 值都是0,因此在這一目標上無法進行性能對比.

WFG4-9 都被設計為凸面的PF,但在決策空間上具有不同的難度.從表4 和表5 中可以看出,R2-RVEA 在WFG4 測試問題獲得了最優的性能.在WFG5 問題上,R2-RVEA 獲得了較好的性能,相較于其他對比算法性能穩定.對于WFG6 測試問題,所有對比算法性能相似,R2-RVEA 的性能略優于其他算法.在WFG7 上,R2-RVEA 僅在15 目標上獲得了最好的性能,而TS-R2EA 總體性能要明顯 優 于R2-RVEA.并 且R2-RVEA 在WFG8 測 試問題上的性能和NSGA-III、RVEA 和TS-R2EA 相似,但明顯優于其他對比算法.在WFG9 測試問題上,除了RVEA 和TS-R2EA,R2-RVEA 在所有目標上要明顯優于其他對比算法.綜合統計結果可以看出,R2-RVEA 在WFG 測試集上總體性能優越.

3.4 算法性能分析

從上面兩個測試集得出的實驗結果可以看出,提出的R2-RVEA 在DTLZ 測試集中展現了比較不錯的性能,在WFG 測試集上性能非常優異.表6 總結了所有算法在64 個測試實例中的實驗對比,可以看出本文所提出的算法性能優越.

表6 R2-RVEA 與其他算法的測試對比Table 6 Comparison between R2-RVEA and other algorithms

當然,提出的算法仍然存在不足之處,經過實驗分析可知算法在指導進化種群的時候,存在收斂到局部PF 而無法有效管理多樣性的情況,使得算法性能急劇下降.

算法前期僅考慮收斂性,僅當整個種群收斂到PF 以后才管理多樣性,可能導致整個種群都收斂到局部的PF 上,后面再采用種群分解和R2 排序也無法有效管理多樣性.在多次實驗過程中發現R2-RVEA 會出現穩定和不穩定這兩種情況,具體可見圖6 中R2-RVEA 在3 維DTLZ7 上的實驗,對于GD 指標,GD 值越小說明收斂性越好,兩種情況GD 指標進化軌跡基本相同,這說明兩種情況的收斂性基本相同;對于DM 指標,DM 值越大說明多樣性越好,可以看出R2-RVEA 在不穩定情況時DM隨著進化過程數值驟減,最終DM 明顯小于穩定情況的DM 值,說明了多樣性要明顯比穩定情況時候的差.通過圖5 可以直觀地看到R2-RVEA 在不穩定情況時種群收斂到局部PF,這時候DM 值驟減到比較小的水平,也是導致多樣性較低的主要原因.

圖5 R2-RVEA 在3 維DTLZ7 上獲得的不同結果Fig.5 Different results obtained by R2-RVEA on 3-objective DTLZ7

圖6 R2-RVEA 在3 維DTLZ7 上GD 和DM 指標的進化軌跡Fig.6 Evolutionary trajectories of GD and DM for R2-RVEA on 3-objective DTLZ7

4 結束語

本文提出了一個基于R2 指標和參考向量的高維多目標進化算法.這個算法致力于處理具有不同PF 形狀的MOPs 以及MaOPs.在算法中,為了讓種群可以快速地收斂到PF 上,采用了Pareto 支配選取當前種群非支配解的方式來指導整個種群優化.而當整個種群都收斂到PF 上以后,采用種群分解和R2 排序進一步管理種群的收斂性和多樣性.

實驗結果表明了提出的R2-RVEA 在處理具有不同PF 形狀的MOPs 以及MaOPs 時,能夠很好地平衡收斂性和多樣性.當然,算法的初期階段僅采用Pareto 支配選取最優解的方式有可能導致種群收斂到局部PF 的情況發生,這使得種群分解和R2 排序已經無法有效地管理種群的多樣性.因此,在保證種群穩定地收斂到PF 上,如何更好地管理種群的多樣性仍然是未來工作的一個方向.