參考點自適應(yīng)調(diào)整下評價指標(biāo)驅(qū)動的高維多目標(biāo)進化算法

何江紅 李軍華 周日貴 ,

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

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

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

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

3)基于指標(biāo)的算法:通過構(gòu)建適應(yīng)度函數(shù)將候選解的目標(biāo)值映射到一個確定的數(shù)值上,并將該值作為環(huán)境選擇中的選擇標(biāo)準(zhǔn),該方法能夠區(qū)分具有相同目標(biāo)和的解;此類經(jīng)典算法有:SMS-EMOA[18]、MOMBI-II[19]、MaOEA-IPB[20]、R2-OSP[21]、MaOEA/IGD[22]等.

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

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

1 基礎(chǔ)知識和相關(guān)工作

1.1 基礎(chǔ)知識

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

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

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

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

1.2 自適應(yīng)參考點策略

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

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

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

1.3 IGD-NS 指標(biāo)

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

1) GD 指標(biāo)

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

2) IGD 指標(biāo)

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

3) HV 指標(biāo)

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

4) R2 指標(biāo)

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

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

根據(jù)無貢獻解的定義,可以得到IGD-NS 指標(biāo)的定義:

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

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

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

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

2 參考點自適應(yīng)調(diào)整下評價指標(biāo)驅(qū)動的高維多目標(biāo)進化算法

2.1 算法基本框架

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

算法1.MaOEA-IAR 算法框架

2.2 匹配選擇

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

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

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

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

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

算法2.匹配選擇

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

2.3 環(huán)境選擇

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

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

算法3.環(huán)境選擇

2.4 PF 形狀監(jiān)測基礎(chǔ)上的自適應(yīng)參考點策略

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

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

算法4.生成參考點

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

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

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

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

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

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

圖3 自適應(yīng)參考點過程Fig.3 Adaptive reference point process

2.5 確定輪廓曲線以及曲線參數(shù)p

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

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

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

算法5.輪廓曲線

2.6 算法的時間復(fù)雜度分析

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

3 實驗研究與結(jié)果分析

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

3.1 實驗設(shè)置

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

表1 測試問題Table 1 Test questions

2)種群規(guī)模:對比算法MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 與MaOEA-IAR的種群規(guī)模取決于參考向量的數(shù)量,參考向量的數(shù)量由外層和內(nèi)層的劃分?jǐn)?shù)目H1、H2決定,表2 總結(jié)了不同目標(biāo)數(shù)目下對應(yīng)的種群規(guī)模.

表2 不同目標(biāo)對應(yīng)的種群規(guī)模Table 2 Population sizes corresponding to different objectives

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

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

表3 不同目標(biāo)對應(yīng)的終止條件Table 3 Termination conditions corresponding to different objectives

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

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

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

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

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

表4 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9上獲得IGD 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記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 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記 (續(xù)表)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)

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

表5 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9上獲得PD 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記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 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記 (續(xù)表)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 目標(biāo)WFG5 上獲得的非支配解的分布情況,在平行坐標(biāo)系中,可以從收斂性、覆蓋性、均勻性和擴展性4 個方面來衡量種群質(zhì)量[40].從圖5 可知6個算法都達(dá)到PF 的范圍,無法準(zhǔn)確地評估種群的收斂性;MOEA-DD、NSGA-III、RVEA、ARMOEA、MaOEA-IAR 的覆蓋率較好,MOMBI-II在1～7 目標(biāo)軸上嚴(yán)重缺失解集,覆蓋率差;在均勻性方面,6 個算法的平行坐標(biāo)系下的折線都分布不均勻,這并不意味著生成的種群不均勻,因此在平行坐標(biāo)系下無法比較種群的均勻性;最后可以觀察到6 個算法目標(biāo)值范圍均為0～18,可擴展性較好.圖6 為6 個算法在5、10、15、25 目標(biāo)的DTLZ4 上獲得的IGD 指標(biāo)軌跡,從圖中觀察到算法MaOEAIAR 在5 目標(biāo)時與其他算法的性能相似,隨著目標(biāo)數(shù)目的增加,MaOEA-IAR 能夠較快收斂到一個穩(wěn)定且較低的IGD 指標(biāo)值.

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

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

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

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

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

圖8 WFG1 問題15 目標(biāo)上獲得的非支配解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 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記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 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記 (續(xù)表)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)

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

表7 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上獲得PD 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記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 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記 (續(xù)表)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 算法的運行時間分析

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

表8 AR-MOEA 和MaOEA-IAR 在DTLZ1～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG9 上運行時間的統(tǒng)一結(jié)果(均值).最好的結(jié)果已被標(biāo)記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 參考點自適應(yīng)策略的有效性分析

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

表9 AR-MOEA 和MaOEA-IAR 在MaF1～MaF7 上獲得IGD 值的統(tǒng)一結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已被標(biāo)記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 鄰域參數(shù)r 的分析和討論

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

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

4 總結(jié)

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

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