參考點自適應調整下評價指標驅動的高維多目標進化算法

何江紅 李軍華 周日貴 ,

在現實生活中存在大量由多個相互沖突的目標組成的優化問題,這類問題稱為多目標優化問題(Multi-objective optimization problems,MOPs[1]);超過三個目標的MOPs 稱為高維多目標優化問題(Many-objective optimization problems,MaOPs[2]),這類問題廣泛存在于實際應用中,如自動發動機標定問題[3]、水資源分配系統設計[4]、航空發動機健康管理系統[5]、軟件重模塊化、軟件模塊聚類問題[6]等.

研究證明傳統的多目標進化算法(Multi-objective evolutionary algorithms,MOEAs)在處理MOPs 時能獲得較好的性能,然而在處理MaOPs時卻會出現一系列的問題[7],如:隨著目標數目的增加,種群中非支配解比例呈指數形式增加,算法的選擇壓力缺失;在高維空間中,部分性能評價指標(如超體積指標)的計算代價過大等.為了應對目標數目增加帶來的挑戰,提高MOEAs 在處理MaOPs時的能力,研究學者們提出一系列算法,大致可以分為3 類,分別為:基于松弛支配的算法、基于分解的算法、基于指標的算法.

1)基于松弛支配的算法:通過修改支配關系擴大解的支配區域,能在一定程度上緩解支配受阻現象;常見的松弛支配關系有:角度支配[8]、網格支配[9]、模糊支配[10]、基于參考點的支配[11]等.

2)基于分解的算法:利用一組參考向量將一個MOPs 分解為多個單目標優化問題(Single-objective optimization problems,SOPs) 或更為簡單的MOPs,隨后對這些子問題進行協同進化,這在一定程度上增加了種群的多樣性;此類經典算法有:MOEA/D[12]、MOEA/D-ANA[13]、RVEA[14]、MOEA/D-ROD[15]、NGSA-III[16]、MOEA-PPF[17].

3)基于指標的算法:通過構建適應度函數將候選解的目標值映射到一個確定的數值上,并將該值作為環境選擇中的選擇標準,該方法能夠區分具有相同目標和的解;此類經典算法有:SMS-EMOA[18]、MOMBI-II[19]、MaOEA-IPB[20]、R2-OSP[21]、MaOEA/IGD[22]等.

盡管上述算法能在一定程度上緩解傳統算法在處理高維優化問題時存在的不足,但面對具有不規則Pareto 前沿(Pareto front,PF)的優化問題時,常規方法可能無法獲得很好的性能,因此需要設計更先進的算法.目前處理不規則優化問題的算法可以分為四類,分別是采用固定參考向量與輔助選擇方法協同合作,在搜索過程中根據種群分布調整參考向量,用參考點同時衡量多樣性和保持收斂性,以及對群體進行聚類或劃分目標空間為子區域[23].其中參考向量的調整是非常重要的,Ma 等在文獻[24]中對單純性上的各種參考向量調整策略進行綜述,將其分為隨機調整、基于擬合的調整、局部種群指導的調整、局部檔案的調整、基于鄰域參考向量的調整和基于偏好的調整,并且詳細討論了每種方法的優缺點以及有待解決的問題.除此之外,近年來研究學者還結合不同的策略提出一些新型算法,如Yuan 等在文獻[25]中提出PREA,該算法基于平行距離進行個體選擇,與傳統的角度距離、徑向交叉距離相比,基于平行距離導出的點無論是在凹型、凸型,還是在不規則PF 上都是均勻分布的,這有利于提高算法在處理各種優化問題時的多樣性;Liu 提出FDEA[26],該算法利用模糊預測評估不同形狀PF 上解的相似性,并以此為依據對種群進行分割,有效地提高了算法的多樣性,同時提供一個共享權重向量加快收斂速度,兩者共同作用提高算法的性能.

為了能夠更好地處理不規則MaOPs,提高算法的通用性,本文提出參考點自適應調整下評價指標驅動的高維多目標進化算法,該算法的具體步驟如下:1)為了有效地生成一組參考點,提出一個PF形狀監測基礎上的自適應參考點策略,該方法首先利用一條特定的輪廓曲線近似PF,其次在該曲線上找到所有非支配解對應的點,然后以對應點之間的距離作為多樣性選擇標準,最后利用該準則選擇一組多樣性好的解作為參考點,此外基于曲線參數對參考點的位置進行調整,以減少偏離種群的參考點所產生的影響;2)為了進一步提高算法性能,在匹配選擇中結合Pareto 支配和改進的Pareto支配以及鄰域關系,選擇一組有希望的解作為父代種群;3)為了最終生成一組接近PF 且分布廣泛的種群,在環境選擇中利用參考點計算基于指標的適應度函數,將其作為選擇標準進行精英選擇.

1 基礎知識和相關工作

1.1 基礎知識

一個具有n個決策變量和m個目標變量的最小化MOPs 可以表示為:

其中x=(x1,···,xn)T∈X是n維決策向量,X表示n維決策空間;y=(y1,···,ym)T∈Y是m維目標向量,Y是m維目標空間;f:X→Y構成m個相互沖突的目標函數,是一個從n維決策空間X到m維目標空間Y的映射.在決策空間中,若解xPareto 支配解y(x?y),則需滿足:

其中fi(x)為解x在第i個目標上的真實目標值.

若在決策空間中不存在x使得x?x*,則x*為Pareto 最優解,F(x*)為Pareto 最優向量;由于MOPs 目標之間相互沖突的性質,一個目標性能的提升通常會導致其他目標性能的下降,因此需要一組Pareto 最優解作為不同目標之間的權衡,這樣的一組解被稱為Pareto 解集(Pareto set,PS),對應的在目標空間中的Pareto 最優向量集被稱為PF.

1.2 自適應參考點策略

在一些進化算法中通常需要一組在PF 上均勻采樣的參考點用于指標值的計算,或一組均勻分布的參考向量用于劃分子種群,本文統一采用參考點代替參考向量以及權重向量.由于在大部分的優化問題中,真實PF 是不可知的,因此需要不斷地對參考點進行調整使其盡可能地近似PF;為了達到這個目的,研究學者們提出了一系列自適應參考點策略.

在RVEA 中,根據當前種群中目標值的范圍調整參考向量,實現目標函數在沒有被標準化到相同范圍的情況下,依然能得到一組均勻分布的參考點;NSGA-III 中提出基于候選解的分布位置增加和刪除參考點;MOEA/D 引入檔案對參考點進行管理,若候選解位于稀疏區域,則將其選入檔案并生成相應的參考點.

然而上述所提到的自適應參考點策略存在局限性,例如在一些優化問題中頻繁地更新參考點在一定程度上影響種群的收斂性,導致出現局部收斂現象;一些自適應參考點策略的有效性取決于用戶預先定義參數;某些自適應方法對不同PF 的優化問題普適性低等.因此本文提出一個新的自適應參考點策略,該策略基于PF 形狀設計多樣性評估準則,并根據該準則選擇一組分布廣泛的非支配解作為參考點,另外利用曲線參數調整參考點的位置,最終生成一組近似PF 的參考點用于指標值的計算.

1.3 IGD-NS 指標

研究學者提出許多性能指標,如世代距離(Generational distance,GD[27])、反世代距離(Inverted generational distance,IGD[28])、超體積(Hypervolume,HV[29-31])、R2[32-33]、純多樣性(Pure diversity,PD[34])、增強的反世代距離指標(Enhanced inverted generational distance,IGDNS[35-36])等,這些指標被廣泛用于評估種群的收斂性、多樣性,或同時評估收斂性和多樣性,下面具體介紹現存的性能指標:

1) GD 指標

其中P為非支配解集,P* 為從PF 上均勻采樣的參考點;GD 指標計算非支配解與參考點之間的最小歐氏距離的平均值,GD 值越小表明種群的收斂性越好;但該指標無法評估種群的多樣性,若所有的非支配解重合在同一個點,且該點與參考點之間的歐氏距離很小,則依然能得到一個較好的GD 值,然而此時種群不具有多樣性.

2) IGD 指標

其中P為非支配解集,P* 為從PF 上均勻采樣的參考點;IGD 指標與GD 指標相似,計算每個參考點與非支配解之間的最小歐氏距離的平均值,IGD值越小,種群質量越好;該指標利用歐氏距離評估收斂性,利用參考點的均勻分布保證多樣性,因此能夠同時評估種群的收斂性和多樣性.

3) HV 指標

其中P為解集,q為目標空間中的預定義參考點,1H(P,q)為H(P,q)的特征函數;HV 指標計算種群到參考點所覆蓋的面積,HV 值越大種群質量越好;相比于GD 指標和IGD 指標,HV 的計算不需要PF 的先驗信息,然而隨著目標數目的增加,計算復雜度成指數形式增加.

4) R2 指標

其中P為種群,V為參考向量集,z*為當前理想點;R2 指標將候選解從目標空間映射到效用空間以計算種群的質量,R2 指標值越小說明種群質量越好;然而R2 指標對中間區域存在固有的偏好,尤其在凸型PF 的優化問題上,分布在中間區域的種群能得到一個較低的R2 指標值.

近年來,IGD-NS 指標受到研究學者們的廣泛關注,該指標是 Tian 等在MOEA/IGD-NS[35]中首次提出的,與IGD 指標相比,該指標可以區分對種群沒有貢獻的解.文獻[35]中對無貢獻解做了嚴格定義,即在計算指標值時由于不是任何參考點的最近鄰域而被忽略,從而對種群的指標值不產生貢獻的解.無貢獻解y′公式定義為:

根據無貢獻解的定義,可以得到IGD-NS 指標的定義:

其中P*為一組均勻分布的參考點,P為非支配解集,P′為無貢獻解集;由公式可知前半部分與IGD指標的計算方法一致,后半部分為無貢獻解到參考點的距離,只有同時滿足與參考點之間的距離小和無貢獻解的數量少兩個條件才能得到一個較好的指標值.

Tian 等[35]不但對無貢獻解進行公式定義,為了便于理解,還佐以圖例解釋.如圖1 所示,X、Y、Z為參考點,A、B、C、D、E為非支配解,根據上述無貢獻解的定義,B、E不屬于任意一個參考點的最近鄰域,為無貢獻解.若在環境選擇中選取4 個解作為下一代種群,則需要從當前非支配解集中刪除1個候選解,如果使用IGD 指標評估種群的質量,{A、D、C},{A、B、C、D、E},{A、D、C、B},{A、D、C、E} 4 個解集的IGD 指標值相同,無法區分最差解;而IGD-NS 指標由于能夠區分B、E兩個無貢獻解,因此能更準確地評估種群的質量.

圖1 二目標下的無貢獻解Fig.1 The noncontributed solutions under bi-objective

根據以上分析,IGD-NS 指標與GD 指標相比,可以同時評估種群收斂性和多樣性;與IGD 指標相比,可以區分無貢獻解;與HV 指標相比,在高維空間中計算代價小;與R2 指標相比,對邊界解或中心解不存在偏好.基于這些性質,IGD-NS 指標適合作為選擇標準用于進化算法中.

2 參考點自適應調整下評價指標驅動的高維多目標進化算法

2.1 算法基本框架

算法1 為MaOEA-IAR 的主要框架,首先輸入種群規模以及最大進化代數,隨機生成一個規模為N的初始種群P0;其次在主循環中,通過匹配選擇生成父代種群,進而生成子代種群,子代種群和初始種群合并,最后對合并種群進行環境選擇生成下一代種群.下面將著重介紹算法的4 個子部分,分別為匹配選擇、環境選擇、自適應參考點和確定輪廓曲線.

算法1.MaOEA-IAR 算法框架

2.2 匹配選擇

匹配選擇能夠從當前種群中選擇一組有希望的解作為父代種群加入交配池.在傳統的算法中,通常會利用Pareto 支配關系選擇父代種群;然而在高維空間中個體之間互不支配,難以選擇非支配解;因此本文采用改進的Pareto 支配,將目標值的比較替換成子空間位置的比較,對個體進行定量比較能夠增加選擇壓力,具體過程如算法 2 所示.

首先將目標空間劃分為多個子空間,并計算個體所處子空間的位置yindex,計算方法為:

其中yi為個體y在第i個目標上的目標值,Ti為第i個目標的鄰域范圍,z為理想點,z*為最低點;并且假設將整個目標空間分為rm個子空間,即將每個目標均分為r等分,將個體所在的子空間作為其所在的鄰域,鄰域范圍即為T.

其次從種群中隨機選取2 個個體,通過Pareto支配以及改進的Pareto 支配選擇非支配解加入交配池中,在改進的Pareto 支配中,若x支配y,則需要滿足:

其中xindexi為個體x在第i個目標上的位置,yindexi為個體y在第i個目標上的位置.

算法2.匹配選擇

然后在無法判斷支配關系的情況下,計算個體所處鄰域內解的個數NUM,選擇多樣性好的個體加入交配池;最后若多樣性也相近,則隨機選取1個個體加入交配池中.

2.3 環境選擇

環境選擇的目的是從合并種群中獲得一組接近PF 且分布良好的解集.算法3 給出了環境選擇的基本步驟:首先對種群中的個體進行非支配排序,選擇前k-1 個等級中的個體作為下一代,再將第k個等級中的個體通過適應度值進行刪除操作,直到下一代種群中的個體數與初始種群相等(k值由每個等級中的個體數確定,為滿足的最小值,即其中N為初始種群中的個體數).當目標數較小時,能夠通過非支配排序選擇出部分解,再通過適應度值選擇剩下的解;當目標數增大時,種群中幾乎所有的解都為非支配解,此時算法主要通過基于IGD-NS 指標的適應度值選擇下一代種群,非支配解p的適應度為:

其中P*為一組多樣性好的參考點.

算法3.環境選擇

2.4 PF 形狀監測基礎上的自適應參考點策略

傳統基于角度距離的多樣性評估準則在處理非線性PF優化問題時存在偏差,尤其在凹型PF 中,相同大小的角度距離不能生成均勻分布的候選解,如圖2 所示,被選擇的候選解傾向于分布在中心區域.因此在生成參考點的過程中,利用基于PF 形狀的多樣性評估準則對參考點進行自適應,這在一定程度上可以減少這種偏差;由于單獨使用多樣性評估準則選擇參考點可能生成偏離種群的參考點,利用理想點或最低點對參考點的位置進行調整,能夠降低此類參考點的影響.

圖2 基于角度距離選擇參考點Fig.2 Select reference points based on angular distance

算法4.生成參考點

算法4 為自適應參考點的具體步驟,首先根據當前種群狀態,用一條特定的輪廓曲線近似PF 并得到曲線參數p;然后在該曲線上找到所有非支配解的對應點,基于對應點設置多樣性評估準則;之后將邊界解添加到參照點集合Q,以該準則計算剩余非支配解與參照點之間的差異,選擇差異最大的非支配解加入集合Q中,直到集合內個體的數量滿足N,將Q中的所有個體作為初始參考點,差異值的計算公式如下:

其中x為剩余非支配解,y為參照點;x＇、y＇分別為x、y在曲線上的對應點;fi(x＇)、fi(y＇)分別為x＇、y＇在第i個目標上的值.

最后由于只考慮了多樣性方面的差異,可能生成部分偏離種群的參考點,為了降低此類參考點的影響,在凸型PF 問題中,將初始參考點調整為所在鄰域內的理想點,在凹型PF 問題中,將初始參考點調整為所在鄰域內的最低點.調整之后的參考點如下:

其中y*為凸型PF 中調整之后的參考點,y**為凹型PF 中調整之后的參考點,y為初始參考點,z為理想點,z*為最低點,r為鄰域參數,T為鄰域范圍.

此外,由于鄰域參數r是用戶預先定義的參數,在一定程度上影響參考點的調整;若參數r過大,則可能出現多個參考點處于同一鄰域內;為了避免此類情況發生,本文還根據調整后的參考點數量動態改變參數r,直到每一個參考點處于不同的鄰域內.

為了更清楚地理解參考點自適應過程,圖3 給出一個兩目標優化問題的例子說明如何進行參考點自適應.圖3(a)為一組非支配解,根據非支配解的分布確定合適的輪廓曲線近似PF;在曲線上找到所有非支配解的對應點,即非支配解和原點之間的連線與曲線的交點,然后根據多樣性評估準則選擇一組分布廣泛且均勻的初始參考點,如圖3(b)所示,實心圓形即為初始參考點;由于PF 形狀為凸型,因此將初始參考點調整為所在鄰域的理想點,如圖3(c).

圖3 自適應參考點過程Fig.3 Adaptive reference point process

2.5 確定輪廓曲線以及曲線參數p

輪廓曲線與PF 的近似程度直接影響參考點的生成以及算法的性能,閔氏距離能夠覆蓋各種凹凸度的PF,因此本文利用閔氏距離預先估計PF 形狀.算法5 對如何確定一條特定的曲線做了具體描述,首先利用m個邊界解構建超平面;然后計算該超平面與原點之間的歐氏距離d,將所有候選解到原點的距離與距離d進行比較,根據種群與超平面之間的位置關系初步判斷PF 的凹凸性,并相應地確定曲線參數范圍,這一步的目的是縮小曲線參數的范圍,降低時間復雜度;最后對于每一個p值,計算所有解的閔氏距離方差,選擇方差最小時對應的p值作為曲線參數.此時輪廓曲線可以用公式表示:

圖4 為一個兩目標優化問題,若要判斷PF 的形狀,首先連接邊界點A、B構建超平面,如圖4(a)所示,從圖中可以看出,種群中的個體大部分位于超平面的上方,并且根據非支配解與原點之間的距離和超平面與原點之間的距離可以初步判斷PF 為凹型,從而確定p的取值范圍為{1,1.1,1.2,···,3};然后對于每一個p值,計算所有非支配解的閔式距離方差,如圖4(b)所示,方差越小,解之間的輪廓曲線越接近.

圖4 確定輪廓曲線以及曲線參數Fig.4 Determine the contour curve and curve parameter

算法5.輪廓曲線

2.6 算法的時間復雜度分析

算法MaOEA-IAR 主要在環境選擇中耗費時間,其中生成參考點的最大時間復雜度為O(MrN),M為目標數,r為鄰域參數,N為種群規模;確定輪廓曲線以及曲線參數的時間復雜度為O(CpN),Cp為曲線參數數量;計算指標值的時間復雜度為O(N);因此算法的時間復雜度為max(O(MrN)).

3 實驗研究與結果分析

在這一部分,將本文提出的算法與當前性能較好的先進算法進行實驗對比,對比算法分別為:MOEA-DD、NSGA-III、RVEA、MOMBI-II、ARMOEA,實驗取自DTLZ 測試集和WFG 測試集以及IDTLZ1、IDTLZ2.接下來首先介紹實驗設置,然后對測試集中具有規則PF 的測試問題的實驗結果和算法對比進行分析,之后對測試集中具有不規則PF 的測試問題的實驗結果和算法對比進行分析,最后對比同樣采用參考點自適應方法的算法AR-MOEA 和MaOEA-IAR 的運行時間,進一步增加算法性能的說服力.除此之外,為了說明參考點自適應策略的有效性,對比AR-MOEA 與MaOEA-IAR 在MaF 測試集上的性能.

3.1 實驗設置

1)基準測試問題:本文采用DTLZ 測試集中的測試問題DTLZ1～DTLZ7 和WFG 測試集中的測試問題WFG1～WFG9 以及IDTLZ1、IDTLZ2,這些測試問題的目標數目可以任意擴展,實驗重點研究目標數為5、10、15、25 的測試問題,表1 給出了每個測試問題的真實PF 形狀以及不同目標數目下各個測試問題對應的決策變量數.

表1 測試問題Table 1 Test questions

2)種群規模:對比算法MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 與MaOEA-IAR的種群規模取決于參考向量的數量,參考向量的數量由外層和內層的劃分數目H1、H2決定,表2 總結了不同目標數目下對應的種群規模.

表2 不同目標對應的種群規模Table 2 Population sizes corresponding to different objectives

3)交叉和變異算子:在本文用到的所有進化算法均采用二進制交叉[37]和多項式變異[38]生成子代,交叉概率和變異概率設置為1.0 和1/D(決策變量數目),分布指標都設置為20.

4)終止條件:每一次運行的終止條件是最大評價次數,評價次數為進化代數與種群規模的乘積,對于不同的目標數目所采用的進化代數不同,具體的設置如表3 所示.

表3 不同目標對應的終止條件Table 3 Termination conditions corresponding to different objectives

5)評價指標:算法性能由IGD 指標[22]和PD指標[34]評估.IGD 指標為同時衡量種群收斂性和多樣性的指標,在IGD 指標計算中,對于每個測試實例,利用Das 和Dennis 在[39]中提出的方法(在10 目標、15 目標和25 目標測試問題中,采用雙層參考點采用方法)在PF 上采樣大約5000 個均勻分布的參考點,計算距離每個參考點最近的解與參考點之間的歐氏距離的平均值;為了進一步證明本文提出的方法在生成均勻參考點方面的有效性,采用PD 指標單獨衡量種群的多樣性,PD 指標利用Lp標準距離計算解的差異,通過種群中解的差異性的累加衡量多樣性.

6)統計方法:每個算法在每個測試問題上獨立運行30 次,采用Wilcoxon 秩和檢驗方法比較本文提出算法與現存算法之間的性能,均值分析的顯著性水平設置為0.05.

7)對比算法參數設置:對于MOEA-DD,選擇局部父代概率δ設置為0.9;對于RVEA,控制懲罰概率參數α設置為2,參考向量自適應的頻率fr設置為0.1;對于MOMBI-II,差異門限α設置為0.5,公差門限ε設置為0.001,最小向量記錄規格設置為5.

3.2 算法在規則PF 測試問題上的對比分析

根據表4 的數據分析,在具有規則PF 的測試問題中,雖然MaOEA-IAR 沒有在所有的測試問題上獲得最好的性能,但總體性能良好.DTLZ1 為線性PF,AR-MOEA 在該測試問題上指標值突出,這與AR-MOEA 采用的參考點更新方法有關,在線性PF 上,初始均勻分布的參考點不會被檔案中的候選解更新;DTLZ2 為凹型PF,MaOEA-IAR 在5 目標和25 目標上獲得最好性能,AR-MOEA 在其余目標上獲得最好性能;DTLZ3 為凹型PF,該測試問題測試算法能否收斂到Pareto 全局最優,在該測試問題中,AR-MOEA 表現最好;DTLZ4 依然為凹型PF,測試當PF 高度偏向的情況下算法能否確保最優解均勻分布,從表中可觀察到MaOEA-IAR 在10 目標、15 目標和25 目標上獲得最優性能,說明該算法在保持解均勻分布的能力上優于其他算法;WFG4～WFG9 為凹型PF,且與現實優化問題相似,在此類測試問題上,MaOEA-IAR 在大部分測試問題上能夠獲得最好性能,這是由于基于PF 形狀的多樣性評估準則能夠準確地評估解之間的多樣性.綜合統計結果,在具有規則PF 的測試問題中,雖然MaOEA-IAR 沒有在每一個測試問題上獲得最好的性能,但總體性能良好,尤其在WFG測試問題中的性能顯著.

表4 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9上獲得IGD 值的統一結果(均值和標準差).最好的結果已被標記Table 4 The statistical results (mean and standard deviation) of the IGD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ4,WFG4～WFG9.The best results are highlighted

表4 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9 上獲得IGD 值的統一結果(均值和標準差).最好的結果已被標記 (續表)Table 4 The statistical results (mean and standard deviation) of the IGD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ4,WFG4～WFG9.The best results are highlighted(continued table)

根據表5 的數據分析,在多樣性方面,本文提出的算法能在大部分問題中表現良好,尤其是在高維空間中,MaOEA-IAR 相較于其他算法而言性能顯著.MOEA-DD 在25 目標的DTLZ1 和10 目標的DTLZ4 上面獲得最好性能;NSGA-III 在5 目標和25 目標的DTLZ3 上獲得最好性能;MaOEAIAR 在剩余的所有目標的測試問題中獲得最好性能.可以看出在高維空間中,本文提出的自適應參考點方法所生成的參考點多樣性好,相應的種群多樣性也有一定提升.

表5 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9上獲得PD 值的統一結果(均值和標準差).最好的結果已被標記Table 5 The statistical results (mean and standard deviation) of the PD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ4,WFG4～WFG9.The best results are highlighted

表5 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9 上獲得PD 值的統一結果(均值和標準差).最好的結果已被標記 (續表)Table 5 The statistical results (mean and standard deviation) of the PD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ4,WFG4～WFG9.The best results are highlighted(continued table)

為了更直觀地對比各個算法,圖5 為6 個算法在10 目標WFG5 上獲得的非支配解的分布情況,在平行坐標系中,可以從收斂性、覆蓋性、均勻性和擴展性4 個方面來衡量種群質量[40].從圖5 可知6個算法都達到PF 的范圍,無法準確地評估種群的收斂性;MOEA-DD、NSGA-III、RVEA、ARMOEA、MaOEA-IAR 的覆蓋率較好,MOMBI-II在1～7 目標軸上嚴重缺失解集,覆蓋率差;在均勻性方面,6 個算法的平行坐標系下的折線都分布不均勻,這并不意味著生成的種群不均勻,因此在平行坐標系下無法比較種群的均勻性;最后可以觀察到6 個算法目標值范圍均為0～18,可擴展性較好.圖6 為6 個算法在5、10、15、25 目標的DTLZ4 上獲得的IGD 指標軌跡,從圖中觀察到算法MaOEAIAR 在5 目標時與其他算法的性能相似,隨著目標數目的增加,MaOEA-IAR 能夠較快收斂到一個穩定且較低的IGD 指標值.

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

圖6 5、10、15、25 目標DTLZ4 問題上的IGD 進化軌跡Fig.6 Evolutionary trajectories of IGD on 5、10、15、25-objective DTLZ4

3.3 算法在不規則PF 測試問題上的對比分析

根據表6 的數據分析結果,在具有不規則PF的測試問題中,雖然MaOEA-IAR 沒有在所有的測試問題獲得最好的性能,但總體上性能良好.DTLZ5～DTLZ6 為退化PF,此類測試問題測試進化算法收斂到Pareto 最優曲線上的能力,從表中可觀察到,MaOEA-IAR 在5 目標、15 目標、25 目標的DTLZ5 和25 目標的DTLZ6 上獲得最好性能,MOEA-DD 在5 目標的DTLZ6 上獲得最好性能,AR-MOEA 在其余目標上獲得最好性能,因此MaOEA-IAR 雖然不能在所有目標的測試問題上得到最優性能,但與其他算法相比,該算法在處理具有退化PF 的問題時依然能夠得到較好的性能,同時為了更直觀地反應種群的分布情況,圖7 描繪了各個算法在3 目標DTLZ5 上獲得的非支配解的分布情況,從圖中可觀察到MaOEA-IAR 能夠生成一組均勻且分布廣泛的種群;DTLZ7 為斷開PF,該測試問題測試算法在不同Pareto 最優區域保持子種群的能力,可觀察到AR-MOEA 能夠在5 目標、10 目標和15 目標上獲得最好的性能,RVEA在25 目標上獲得最好性能,但與剩余算法相比,MaOEA-IAR 在不同區域保持子種群的能力更強;IDTLZ1～IDTLZ2 為翻轉PF,AR-MOEA 在5 目標的IDTLZ1 上獲得最好性能,MaOEA-IAR 在其余測試問題上獲得最好性能,因此對于翻轉的優化問題,PF 形狀監測基礎上的自適應參考點方法依然能發揮較好的作用;WFG1～WFG3 分別為混合、斷開、退化PF,MaOEA-IAR 在大部分測試問題上獲得最好性能,圖8 描繪了各個算法在15 目標WFG1上獲得的非支配解的分布情況,從圖中可觀察到本文提出的算法在覆蓋率和均勻性方面均優于其他算法.綜合統計結果,在具有不規則PF 的測試問題中,雖然MaOEA-IAR 沒有在每一個測試問題上獲得最好的性能,但總體性能良好;這是由于在不規則的PF 上,根據種群的分布生成參考點,在沒有個體分布的區域不設置參考點,避免在無效區域產生下一代種群.

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

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

表6 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上獲得IGD 值的統一結果(均值和標準差).最好的結果已被標記Table 6 The statistical results (mean and standard deviation) of the IGD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3.The best results are highlighted

表6 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上獲得IGD 值的統一結果(均值和標準差).最好的結果已被標記 (續表)Table 6 The statistical results (mean and standard deviation) of the IGD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3.The best results are highlighted (continued table)

根據表7 的數據分析,相對于具有規則PF 的測試問題,在不規則PF 的測試問題中,本文提出的算法在多樣性方面性能稍遜,但依然能在大部分問題中保持較好的性能.MOEA-DD 在5 目標和15 目標上的WFG1 上獲得最好性能;NSGA-III在5 目標的DTLZ6,10 目標和25 目標的WFG1上以及15 目標和25 目標的WFG3 上獲得最好性能;AR-MOEA 在5 目標的DTLZ5 和DTLZ7 上獲得最好性能;其余各個目標下的測試問題上,MaOEA-IAR 算法獲得最好性能.這在一定程度上證明了利用PF 形狀自適應參考點能夠有效地提升算法的多樣性.

表7 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上獲得PD 值的統一結果(均值和標準差).最好的結果已被標記Table 7 The statistical results (mean and standard deviation) of the PD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3.The best results are highlighted

表7 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上獲得PD 值的統一結果(均值和標準差).最好的結果已被標記 (續表)Table 7 The statistical results (mean and standard deviation) of the PD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3.The best results are highlighted (continued table)

3.4 算法的運行時間分析

為了增加實驗結果的說服力,對算法的運行時間進行對比.由于參考點自適應策略較為耗費時間,與傳統算法進行時間上的對比無太大意義,因此本節將同樣利用參考點自適應策略的算法AR-MOEA與MaOEA-IAR 進行對比.從表8 中可以觀察到,MaOEA-IAR 在大部分的測試問題中能在較短的時間內完成種群的進化,即在更短的時間內得到質量更好的種群,算法的性能較為優越.

表8 AR-MOEA 和MaOEA-IAR 在DTLZ1～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG9 上運行時間的統一結果(均值).最好的結果已被標記Table 8 The statistical results (mean) of the time obtained by AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG9.The best results are highlighted

3.5 參考點自適應策略的有效性分析

在本節中,為了驗證參考點自適應策略的有效性,對比AR-MOEA 與MaOEA-IAR 在測試問題MaF1～MaF7 上的性能.AR-MOEA 與MaOEAIAR 都采用了參考點自適應策略增加參考點的多樣性,并且在環境選擇中都利用IGD-NS 指標計算適應度值并將其作為選擇標準;MaF 測試集中包含更多類型的優化問題,并且增加了具有凹型PF 的優化問題,這一類優化問題對生成參考點的策略要求更高.表9 為算法獨立運行30 次的IGD 指標值,其余設置與上述實驗設置相同.從表中的數據可以觀察到MaOEA-IAR 在10 目標的MaF6 和5 目標的MaF7 上未能獲得最好性能,在其余測試問題上獲得最好性能,算法中使用到的參考點自適應策略適用于各種形狀的優化問題.

表9 AR-MOEA 和MaOEA-IAR 在MaF1～MaF7 上獲得IGD 值的統一結果(均值和標準差).最好的結果已被標記Table 9 The statistical results (mean and standard deviation) of the IGD values obtained by AR-MOEA and MaOEAIAR on MaF1～MaF7.The best results are highlighted

3.6 鄰域參數r 的分析和討論

鄰域參數在算法中起著重要作用,但由于該參數為用戶預先定義參數,雖然在參考點自適應策略中描述了如何調整參數,其初始值卻較難確定;因此在本節將算法中的鄰域參數r的初始值分別設置為5,7,9,11,13,對比不同取值下算法在測試問題DTLZ1、DTLZ5、IDTLZ1、WFG1、WFG2、WFG4 上獲得的IGD 指標值.從表10 中可觀察到在大部分的目標下,當r取值為9 時能獲得最好的指標值;在25 目標的DTLZ1 和10 目標、25 目標的WFG4上,雖然算法在r為11 時獲得最好性能,但r為9 時的性能與最好性能相似;因此,將9 作為鄰域參數r的初始值.

表10 不同參數下算法MaOEA-IAR 的性能Table 10 Performance of MaOEA-IAR under different parameters

4 總結

為了改善參考點的適應能力,提高算法在處理具有不同PF 形狀的優化問題上的通用性,本文提出參考點自適應調整下評價指標驅動的高維多目標進化算法(MaOEA-IAR),該算法設計一個PF 形狀監測基礎上的自適應參考點方法,通過種群分布狀態以輪廓曲線近似PF,結合曲線參數生成一組多樣性好的參考點;同時在匹配選擇中利用Pareto支配以及改進的Pareto 支配選擇一組有希望的父代種群;兩者結合共同指導種群進化.

實驗證明本文提出的算法在處理各種PF 的MaOPs 時能獲得較好的性能,同時在增強種群多樣性方面效果明顯;然而在判斷PF 形狀時,由于某些測試問題不是純粹的線性、凹型或凸型,因此對于這樣的測試問題可能會出現PF 形狀判斷錯誤的情況,這在一定程度上對結果造成偏差,因此下一步的工作計劃是繼續優化判斷PF 形狀的方法,增強算法在處理復雜PF 問題時的性能.