基于R2 指標(biāo)和參考向量的高維多目標(biāo)進(jìn)化算法

陳國(guó)玉 李軍華 黎明 陳昊

多目標(biāo)優(yōu)化問(wèn)題(Multi-objective optimization problems,MOPs)[1]是指多個(gè)目標(biāo)被同時(shí)優(yōu)化的問(wèn)題.在現(xiàn)實(shí)生活中,經(jīng)常遇到優(yōu)化問(wèn)題包含四個(gè)及以上目標(biāo),這類(lèi)問(wèn)題統(tǒng)稱(chēng)為高維多目標(biāo)優(yōu)化問(wèn)題(Many-objective optimization problems,MaOPs)[2?4].雖然一些經(jīng)典的多目標(biāo)進(jìn)化算法(Multi-objective evolutionary algorithms,MOEAs),NSGA-II[5]、SPEA2[6]等能夠很好地處理多目標(biāo)優(yōu)化問(wèn)題(兩個(gè)或三個(gè)目標(biāo)),但是在解決高維多目標(biāo)優(yōu)化問(wèn)題上效果較差.

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

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

1 相關(guān)工作

1.1 基于指標(biāo)的多目標(biāo)進(jìn)化算法

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

基于評(píng)價(jià)指標(biāo)的MOEAs 比較典型的算法有:IBEA[19]、HypE[20]、SMS-EMOA[21].Zitzler 等在2004 年提出IBEA[19],該算法首先用二進(jìn)制評(píng)價(jià)指標(biāo)來(lái)定義優(yōu)化目標(biāo),然后使用它作為選擇標(biāo)準(zhǔn).通過(guò)幾個(gè)MOPs 測(cè)試問(wèn)題的實(shí)驗(yàn),結(jié)果表明IBEA 的性能優(yōu)于NSGA-II[5]和SPEA2[6].同時(shí),IBEA 的主要貢獻(xiàn)是為基于評(píng)價(jià)指標(biāo)的MOEAs 提供了一個(gè)通用框架,它可以嵌入其他評(píng)價(jià)指標(biāo)設(shè)計(jì)算法.

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

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

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

1.2 基于分解的多目標(biāo)進(jìn)化算法

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

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

例如在一個(gè)3 目標(biāo)(M=3)問(wèn)題上,考慮到每個(gè)目標(biāo)有4 個(gè)網(wǎng)格(p=4),則生成總數(shù)為15 的參考向量如圖1 所示.

圖1 目標(biāo)問(wèn)題上展示的15 個(gè)參考向量Fig.1 15 reference vectors are shown on 3-objective problem

2 基于R2 指標(biāo)和參考向量的高維多目標(biāo)進(jìn)化算法

2.1 基于分解的多目標(biāo)進(jìn)化算法

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

算法1.R2-RVEA 算法框架

2.2 環(huán)境選擇

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

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

i ∈{1,···,M},分別表示第i個(gè)解的標(biāo)準(zhǔn)化前和標(biāo)準(zhǔn)化后的目標(biāo)值.

2.3 種群分解

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

算法3.種群分解

經(jīng)過(guò)種群分解以后,適應(yīng)度值將作為每個(gè)子種群內(nèi)的選擇標(biāo)準(zhǔn)進(jìn)行精英選擇,適應(yīng)度值計(jì)算公式如下:

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

2.4 R2 排序

R2 指標(biāo)可以用來(lái)評(píng)估兩個(gè)集合的相關(guān)質(zhì)量,分別由一個(gè)給定的近似集合A、一組權(quán)重向量WWW以及效用函數(shù)構(gòu)成,R2 指標(biāo)定義如下:

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

Bk=是最低等級(jí)解的集合.而當(dāng)兩個(gè)解的效用值相同時(shí),其中具有較低歐氏距離的解將會(huì)被選出,這能夠有效地消除松弛的Pareto 解.

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

算法4.R2 排序

3 實(shí)驗(yàn)仿真及分析

在這個(gè)部分,提出的算法主要和當(dāng)前較好的6 個(gè)MOEAs 進(jìn)行實(shí)驗(yàn)對(duì)比,分別是NSGAIII[18]、RVEA[16]MOEA/DD[36]、MOMBI-II[33]、KnEA[12]和TS-R2EA[34],實(shí)驗(yàn)取自DTLZ 測(cè)試集和WFG 測(cè)試集.首先,進(jìn)行實(shí)驗(yàn)設(shè)置;然后,DTLZ 測(cè)試集中各個(gè)測(cè)試問(wèn)題的實(shí)驗(yàn)結(jié)果和對(duì)比分析;接下來(lái),WFG 整個(gè)測(cè)試集的實(shí)驗(yàn)結(jié)果以及對(duì)比分析;最后,算法性能分析.

在實(shí)驗(yàn)中,采用了DTLZ[37]測(cè)試集中的測(cè)試問(wèn)題DTLZ1-DTLZ7 以及WFG[38]測(cè)試集中的測(cè)試問(wèn)題WFG1-WFG9.在DTLZ 的一個(gè)給定的M目標(biāo)測(cè)試問(wèn)題中,每一個(gè)目標(biāo)函數(shù)都有n=k+M ?1個(gè)決策變量,在DTLZ1 中k設(shè)置為5,DTLZ2-DTLZ6 中k設(shè)置為10,以及在DTLZ7 中k設(shè)置為20.此外,WFG 基準(zhǔn)測(cè)試套件中每一個(gè)給定測(cè)試問(wèn)題的每個(gè)目標(biāo)函數(shù)都有n=k+l個(gè)決策變量,k設(shè)置為(M ?1) 以及l(fā)設(shè)置為10.本文算法基于MATLAB2016a 實(shí)現(xiàn),并采用多目標(biāo)進(jìn)化算法平臺(tái)PlatEMO[39]進(jìn)行算法對(duì)比.

3.1 實(shí)驗(yàn)設(shè)置

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

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

表1 種群規(guī)模設(shè)置Table 1 Setting of population size

3) 終止條件:每一次運(yùn)行的終止條件是最大代數(shù).對(duì)于所有測(cè)試問(wèn)題,在不同目標(biāo)上的最大代數(shù)設(shè)置不同.在3 目標(biāo)和5 目標(biāo)的最大代數(shù)設(shè)置為1000,在10 目標(biāo)上設(shè)置為1300,而15 目標(biāo)的最大代數(shù)設(shè)置為1500.

4) 評(píng)價(jià)指標(biāo):算法的性能由HV[23]指標(biāo)和IGD+[42]指標(biāo)來(lái)評(píng)估.在計(jì)算HV 之前,所有目標(biāo)值都要通過(guò)PF 值進(jìn)行標(biāo)準(zhǔn)化.然后,HV 值就利用參考點(diǎn)(1,1,···,1) 和標(biāo)準(zhǔn)化后的目標(biāo)值計(jì)算得來(lái).此外,一旦目標(biāo)數(shù)目大于等于5,Monte Carlo[20]評(píng)估方式采用1000000 個(gè)樣點(diǎn)進(jìn)行更有效的計(jì)算.在IGD+指標(biāo)計(jì)算中,對(duì)于每個(gè)測(cè)試實(shí)例,利用Das 和Dennis 方法在PF 上采樣大約5000 個(gè)均勻分布的點(diǎn).此外,對(duì)于10 目標(biāo)和15 目標(biāo)問(wèn)題,則采用雙層Das 和Dennis 方法生成采樣點(diǎn).

5) 統(tǒng)計(jì)方法:每個(gè)算法在每個(gè)測(cè)試問(wèn)題上都獨(dú)立運(yùn)行30 次,然后采用Wilcoxon 秩和檢驗(yàn)方法比較R2-RVEA 與其他對(duì)比算法獲得的結(jié)果,其中均值分析的顯著性水平設(shè)置為0.05.根據(jù)Wilcoxon 秩和檢驗(yàn)方法,‘+’表示對(duì)比算法要優(yōu)于R2-RVEA,‘?’表示對(duì)比算法獲得的結(jié)果比R2-RVEA 的結(jié)果差,‘≈’表示對(duì)比算法和R2-RVEA 獲得的結(jié)果沒(méi)有明顯的差異.

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

3.2 算法在DTLZ1-DTLZ7 上對(duì)比分析

該節(jié)給出了7 個(gè)算法在DTLZ 測(cè)試集上的實(shí)驗(yàn)結(jié)果,表2 和表3 分別匯總了對(duì)比算法所獲得的HV 值和IGD+值的均值和標(biāo)準(zhǔn)差(括號(hào)內(nèi)為標(biāo)準(zhǔn)差).其中,突出最好的結(jié)果.

表2 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在DTLZ1?DTLZ7 上獲得的HV 值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出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 值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出(續(xù)表)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+值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出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+值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出(續(xù)表)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+的統(tǒng)計(jì)數(shù)據(jù)分析結(jié)果.DTLZ1-DTLZ4 具有規(guī)則形狀的PF,雖然R2-RVEA 沒(méi)有在所有測(cè)試實(shí)例中獲得最具競(jìng)爭(zhēng)力的性能,但總體上獲得了良好的性能,由圖2 可以看到各個(gè)算法獲得的非支配解在DTLZ4 上15 目標(biāo)實(shí)例中的分布情況.DTLZ5-DTLZ7 具有不規(guī)則形狀的PF,對(duì)于DTLZ5 和DTLZ6,R2-RVEA 主要在DTLZ5 的3 目標(biāo)和DTLZ6 的3 目標(biāo)上獲得了最好的性能,而在其他目標(biāo)上的最好性能主要由MOEA/DD 獲得,由圖3 中可以看到各個(gè)算法獲得的非支配解在DTLZ5 上3 目標(biāo)實(shí)例中的分布情況.在DTLZ7 上,綜合兩個(gè)指標(biāo)的統(tǒng)計(jì)數(shù)據(jù)得出R2-RVEA 獲得了一般的性能,NSGA-III 性能相對(duì)穩(wěn)定,總體性能相對(duì)較好,圖4 是各個(gè)算法獲得的非支配解在DTLZ7 上5 目標(biāo)實(shí)例中的分布情況.綜合統(tǒng)計(jì)結(jié)果可以看出,R2-RVEA 在DTLZ 測(cè)試集上雖然沒(méi)有在每個(gè)測(cè)試實(shí)例上獲得最優(yōu)的結(jié)果,但總體性能良好.

圖2 DTLZ4 問(wèn)題15 目標(biāo)上獲得的非支配解Fig.2 Nondominated solutions obtained on 15-objective DTLZ4

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

圖4 DTLZ7 問(wèn)題5 目標(biāo)上獲得的非支配解Fig.4 Nondominated solutions obtained on 5-objective DTLZ7

3.3 算法在WFG1-WFG9 上對(duì)比分析

該節(jié)給出了7 個(gè)算法在WFG 測(cè)試集上的實(shí)驗(yàn)結(jié)果,表4 和表5 分別匯總了對(duì)比算法所獲得的HV 值和IGD+值的均值和標(biāo)準(zhǔn)差(括號(hào)內(nèi)為標(biāo)準(zhǔn)差).其中,突出最好的結(jié)果.

表4 R2-RVEA、NSGA-III、RVEA、MOEA/DD、MOMBI-II、KnEA 和TS-R2EA 在WFG1-WFG9 上獲得的HV 值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出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 值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出(續(xù)表)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 值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出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 值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出(續(xù)表)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 值的統(tǒng)計(jì)結(jié)果(均值和標(biāo)準(zhǔn)差).最好的結(jié)果已突出(續(xù)表)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+的統(tǒng)計(jì)數(shù)據(jù)分析結(jié)果.WFG1 的設(shè)計(jì)是帶有偏見(jiàn)和混合結(jié)構(gòu)的PF,R2-RVEA 的總體性能良好,要明顯優(yōu)于對(duì)比算法.WFG2 是一種帶有斷開(kāi)的PF,R2-RVEA 在這個(gè)測(cè)試問(wèn)題上表現(xiàn)了不錯(cuò)的性能,在5 目標(biāo)數(shù)和10 目標(biāo)上要明顯優(yōu)于對(duì)比算法.WFG3 是一種比較難處理的問(wèn)題,具有退化的PF 且決策變量不可以分離,在這個(gè)問(wèn)題上,R2-RVEA 的HV 值要優(yōu)于所有的對(duì)比算法,但是在15 目標(biāo)上所有對(duì)比算法的HV 值都是0,因此在這一目標(biāo)上無(wú)法進(jìn)行性能對(duì)比.

WFG4-9 都被設(shè)計(jì)為凸面的PF,但在決策空間上具有不同的難度.從表4 和表5 中可以看出,R2-RVEA 在WFG4 測(cè)試問(wèn)題獲得了最優(yōu)的性能.在WFG5 問(wèn)題上,R2-RVEA 獲得了較好的性能,相較于其他對(duì)比算法性能穩(wěn)定.對(duì)于WFG6 測(cè)試問(wèn)題,所有對(duì)比算法性能相似,R2-RVEA 的性能略?xún)?yōu)于其他算法.在WFG7 上,R2-RVEA 僅在15 目標(biāo)上獲得了最好的性能,而TS-R2EA 總體性能要明顯 優(yōu) 于R2-RVEA.并 且R2-RVEA 在WFG8 測(cè) 試問(wèn)題上的性能和NSGA-III、RVEA 和TS-R2EA 相似,但明顯優(yōu)于其他對(duì)比算法.在WFG9 測(cè)試問(wèn)題上,除了RVEA 和TS-R2EA,R2-RVEA 在所有目標(biāo)上要明顯優(yōu)于其他對(duì)比算法.綜合統(tǒng)計(jì)結(jié)果可以看出,R2-RVEA 在WFG 測(cè)試集上總體性能優(yōu)越.

3.4 算法性能分析

從上面兩個(gè)測(cè)試集得出的實(shí)驗(yàn)結(jié)果可以看出,提出的R2-RVEA 在DTLZ 測(cè)試集中展現(xiàn)了比較不錯(cuò)的性能,在WFG 測(cè)試集上性能非常優(yōu)異.表6 總結(jié)了所有算法在64 個(gè)測(cè)試實(shí)例中的實(shí)驗(yàn)對(duì)比,可以看出本文所提出的算法性能優(yōu)越.

表6 R2-RVEA 與其他算法的測(cè)試對(duì)比Table 6 Comparison between R2-RVEA and other algorithms

當(dāng)然,提出的算法仍然存在不足之處,經(jīng)過(guò)實(shí)驗(yàn)分析可知算法在指導(dǎo)進(jìn)化種群的時(shí)候,存在收斂到局部PF 而無(wú)法有效管理多樣性的情況,使得算法性能急劇下降.

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

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

圖6 R2-RVEA 在3 維DTLZ7 上GD 和DM 指標(biāo)的進(jìn)化軌跡Fig.6 Evolutionary trajectories of GD and DM for R2-RVEA on 3-objective DTLZ7

4 結(jié)束語(yǔ)

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

實(shí)驗(yàn)結(jié)果表明了提出的R2-RVEA 在處理具有不同PF 形狀的MOPs 以及MaOPs 時(shí),能夠很好地平衡收斂性和多樣性.當(dāng)然,算法的初期階段僅采用Pareto 支配選取最優(yōu)解的方式有可能導(dǎo)致種群收斂到局部PF 的情況發(fā)生,這使得種群分解和R2 排序已經(jīng)無(wú)法有效地管理種群的多樣性.因此,在保證種群穩(wěn)定地收斂到PF 上,如何更好地管理種群的多樣性仍然是未來(lái)工作的一個(gè)方向.