新的混合分解高維多目標進化算法

過曉芳,王宇平,代　才

(1. 西安電子科技大學 計算機學院,陜西 西安 710071；2.西安工業大學 理學院,陜西 西安 710032)

?

新的混合分解高維多目標進化算法

過曉芳1,2,王宇平1,代才1

(1. 西安電子科技大學 計算機學院,陜西 西安 710071；2.西安工業大學 理學院,陜西 西安 710032)

摘要:在基于分解技術求解高維多目標優化問題的思想啟發下,為了提高多目標優化問題非支配解集合的分布性和收斂性,提出新的基于個體支配關系的混合分解高維多目標進化算法.該算法采用分子種群的進化模式,設計新的基于有效階的個體支配關系用于個體的比較和更新操作,以便在增加個體選擇壓力的同時提高解集分布的多樣性.為了改善該算法的局部搜索性能,將Powell搜索作為局部搜索算子,采用傳統優化與進化算法相融合的混合進化策略.為了檢驗提出算法的性能,將提出算法用于求解5～20個目標的6類標準測試問題,與同類算法相比,該算法在收斂性和分布性方面均具有較大的改進和提高.

關鍵詞：多目標優化問題；進化算法；分子種群；個體支配關系

在科學研究和工程實踐領域,越來越多的多目標優化問題涉及到3個或3個以上目標對應的高維多目標優化問題[1](manyobjectiveoptimizationproblems,MAPs),而高維多目標進化算法的研究已經成為進化算法領域的一個研究熱點和難點.

隨著多目標優化問題的目標個數不斷增多,基于Pareto支配的個體排序策略會使種群中的大部分個體具有相同的排序值,此時,進化過程由于缺乏選擇壓力導致算法的搜索能力急劇下降[2-4].為了增加算法對非支配個體的排序和選擇能力,各國學者相繼提出兩類不同的策略對種群個體進行排序.1)基于松散Pareto支配關系的個體排序策略[5-9]；2)基于評價指標的個體適應度賦值[10-12].這兩種方法雖然在一定程度上能夠增加個體的選擇壓力,但是在目標數目較多的問題中有一定的局限性.同時,基于分解技術的多目標進化算法[13](multi-objectiveevolutionaryalgorithmsbasedondecomposition,MOEA/D)的提出為求解高維多目標優化問題提供了一個全新的思路.它將傳統的數學規劃方法與進化算法相結合,通過聚合函數把一個多目標優化問題分解為若干個單目標優化子問題并行求解.采用該算法有效地求解了具有多個目標的優化問題,得到了越來越多研究者的廣泛關注并提出了許多改進方法[14-17].

基于分解的技術在本質上存在一些局限性,在實施子問題解的更新操作中,新產生個體能否被舊個體取代完全取決于其在所屬子問題中聚合函數的取值,但未考慮新個體實際所在目標空間的位置,在一定程度上會影響種群的分布性[18-19].Liu等[19]提出新的基于分解思想求解多目標優化問題的算法MOEA/D-M2M,將多目標優化問題分解成相對簡單的若干個多目標優化的子問題,然后以并行的方式分別執行進化算法求出每個子問題的非支配解集合,并構成整個的Pareto最優解集合.采用該方法較好地解決了MOEA/D算法中個體更新策略所帶來的多樣性性能下降的不足,但是在子種群內部所采用的進化策略在某種程度上導致了算法的搜索效率較低.

在基于利用分解的思路求解高維多目標優化問題的思想啟發下,為了在改善非支配解集分布性的同時進一步提高算法的收斂性能,本文提出新的基于個體支配關系的混合分解高維多目標進化算法(hybriddecompositionmanyobjectiveevolutionaryalgorithmbasedonnewdominancerelation,HDMOEA-NDR).在HDMOEA-NDR中,首先針對MOEA/D中所采用的權向量設計方法無法任意設置其大小數目的不足,采用均勻設計[19]的方法將目標空間劃分成若干個子空間,并利用每個子空間對應的子種群分別實施進化操作,然后挑選出每個子種群的最佳非支配個體作為算法的非支配解集合.在每個子種群中,為了在提高個體選擇壓力的同時改善種群分布的多樣性,設計基于有效階的個體支配關系用于個體的選擇和更新操作.為了提高算法的局部搜索和全局搜索的性能,算法采用傳統優化Powell搜索法和進化算法相融合的混合進化策略參與進化操作.

1問題背景

1.1多目標優化問題

定義1多目標優化問題和高維多目標優化問題高維多目標優化問題建立在多目標優化問題的基礎上.不失一般性,多目標優化問題(multi-objectiveoptimization,MOP)可以表述為

(1)

定義2Pareto支配對于決策空間中的兩個向量xA,xB,xAPareto支配xB(記為xAxB)當且僅當滿足

(?i)(fi(xA)≤fi(xB))∧

(?j)(fj(xA)

(2)

定義3Pareto最優解或非支配解一個解x*被稱為Pareto最優解當且僅當在決策空間中x*不會被其他解x所Pareto支配,其中,表示解個體之間的Pareto支配關系.決策空間中所有的Pareto最優解集合構成了Pareto最優解集(Pareto set, PS),Pareto最優解集中的所有Pareto最優解在目標空間中的像構成了Pareto最優前沿(Pareto front, PF).

(3)

在利用進化算法求解多目標優化問題的過程中,進化算法使用適應度函數引導群體向Pareto最優前沿收斂.在設計算法時需要求出的非支配解集合不斷逼近真正的Pareto最優解集,并盡可能均勻且寬廣地分布在目標函數空間中.

1.2基于分解的MOEA/D算法的基本思想

MOEA/D是Zhang等[13]提出的一種基于分解思想求解多目標優化問題的算法.它結合傳統的數學規劃方法與進化算法,將一個多目標優化問題(1)分解為若干個單目標優化子問題,然后用進化算法同時求解這些子問題的最優解作為多目標優化問題的Pareto最優解集合.其中,每一個單目標優化子問題的目標函數對應一個有關特定權向量的聚合函數,MOEA/D利用一組權向量集合來設置不同的搜索方向,不同的權向量將引導算法朝著目標空間的不同區域進行搜索.MOEA/D采用切比雪夫分解方法將多目標優化問題分解成若干個如下式所示的單目標優化的子問題：

(4)

2基于新個體支配關系的混合分解高維多目標進化算法

在基于分解思想求解高維多目標優化問題的思想啟發下,為了在進一步提高子問題內部個體向真正Pareto前沿收斂能力的同時改善非支配解集合的分布性,提出新的基于個體支配關系的混合分解高維多目標進化算法(hybrid decomposition many objective evolutionary algorithm based on new dominance relation, HDMOEA-NDR).按照MOEA/D-M2M的進化模式,提出算法首先通過一組均勻分布的方向向量將目標空間劃分成若干個子目標空間,與此同時,初始種群被這組方向向量分解成若干個子種群.在每個子種群中,針對高維多目標優化問題中個體之間由于缺乏選擇壓力而導致收斂性下降的不足,設計新的個體支配關系用來比較非支配個體間的優劣關系,并將該支配關系用于子種群內部個體的選擇和更新操作.另外,為了在保證算法全局收斂的同時提高局部搜索性能,提出算法根據進化的前、后階段自適應地選擇不同區域的個體參與新個體的生成,設計一種將傳統優化Powell搜索法和進化算法相融合的混合進化策略.

2.1子種群的劃分以及個體的更新策略

分子種群的進化策略將高維多目標優化問題劃分成若干個子問題同時進化.首先,它利用均勻設計的思想[14]并通過一組均勻分布的方向向量λ1,λ2,…,λN將目標空間劃分為若干個子空間,同時,將初始種群POP中的每個個體分配到離其最近的權向量所屬的子種群中,從而將初始種群劃分為若干個子種群,記為P1,P2,…,PN.子種群的劃分規則可以通過下式來實現：

Pi={x|x∈POP,<(F(x)-Z),λi> ≤

<(F(x)-Z),λj>}.

(5)

式中：Z為參考點,Z=[z1,z2,…,zm]T,其中 zi=min{fi(x)|x∈Ω};F(x)-Z為個體x的目標向量與參考點連線的方向向量；<>表示個體的方向向量與權向量的夾角,其取值越小,表示該個體離權向量越靠近.算法1描述了子種群的劃分策略.

算法1子種群的分配策略

輸入：初始種群POP和方向向量集合λ1,λ2,…,λN.

輸出：子種群P1,P2,…PN.

1)按照式(5)將種群中的每個個體并入所對應的子種群P1,P2,…,PN中.

2)對于每個子問題i,執行

IF |Pi|≤K

在種群POP中隨機選擇(K-|Pi|)個個體放入子種群Pi中；

ELSE

在Pi中隨機選出兩個個體,根據2.2節提出的有效階支配關系去掉兩者之中的被支配個體,該過程重復(|Pi|-K)次,直到子種群Pi中具有K個個體.

END

2.2基于有效階的個體支配關系

在高維多目標優化問題中,隨著優化目標個數的不斷增多,非支配個體在種群中所占的比例迅速上升,甚至種群中的絕大部分個體都變成非支配個體.此時,傳統的Pareto支配關系已經無法比較非支配個體間的優劣關系.為了在子種群的進化操作中增加個體間的選擇壓力并將靠近Pareto前沿的優良個體挑出參與進化操作,設計一種新的基于有效階的個體支配關系.

定義4基于有效階的個體支配關系對于定義1給定的多目標優化問題,xA、xB是原始目標集合{f1,f2,…,fm}下基于Pareto支配關系的兩個非支配個體,在原始目標集{f1,f2,…,fm}中任取k個目標函數{fi1,fi2,…,fik}(ik∈{1,2,…,m})構成原始目標集的子集(稱為目標子集),所有含k個目標函數的目標子集構成的集合記為sk,即sk={P|P?{f1,f2,…,fm}∧|P|=k}.下面考慮給定k元目標子集所構成的集合sk中,個體xA與xB的Pareto支配關系.

對于固定的k,nb(xA,xB|k),ne(xA,xB|k)和nw(xA,xB|k)分別表示以sk中元素(fi1,fi2,…,fik)為目標集比較xA、xB支配關系時, 使xAParetoxB、xA和xB具有互不Pareto支配、xBParetoxA關系成立的k元素目標子集的數目,分別記為

nb(xA,xB|k)=|{i|xA{i}xB,?i∈sk}|,

(6)

ne(xA,xB|k)=|{i|(xA{i}xB)∧

(xB{i}xA),?i∈sk}|,

(7)

nw(xA,xB|k)=|{i|xB{i}xA,?i∈sk}|.

(8)

式中：xA{i}xB表示以sk中元素i作為目標集時, 個體xA支配個體xB.

對于在原始目標集合(f1,f2,…,fm)下的兩個互不支配的個體xA、xB來說,若滿足nb(xA,xB|k)+ne(xA,xB|k)>nw(xA,xB|k),則稱xAk階有效支配xB,記為xAkxB.例如,含有4個目標的2個互不支配Pareto的個體xA、xB在每個目標上的取值分別為(1 4 2 3)和(2 4 1 7).根據有效階支配關系的定義,分別考慮xA、xB在目標集合的4個3元目標子集下的Pareto支配關系,通過比較xA、xB分別在目標子集(f1,f2,f3)、(f1,f3,f4)和(f2,f3,f4)下是互不支配的,即ne(xA,xB|k)=3；xA在目標子集(f1,f2,f4)下Pareto支配xB,即nb(xA、xB|k)=1,而nw(xA,xB|k)=0,滿足xA3階有效支配xB的條件,即nb(xA,xB|3)+ne(xA,xB|3)>nw(xA,xB|3).

通常,首先取k=m-1,驗證兩個互不Pareto支配的個體xA、xB在m-1階的目標子集下是否滿足有效階支配關系.若無法滿足其中一個個體能夠有效階支配另一個個體,則考慮它們在m-2階的目標子集下是否滿足有效階支配關系,依次類推.

依次分析在Pareto支配關系和有效階支配關系下比較兩個個體優劣的時間復雜度,分別為O(mN2)和O(2mmN2),其中,m為目標數,N為進化種群規模.盡管后者的時間復雜度高于前者,但是基于有效階的個體支配關系能夠有效地區分出兩個個體的優劣關系.在一般情況下,只需考察個體在k=m-1階目標子集下的有效階支配關系便可以區分兩兩非支配個體間的優劣,因此時間復雜度遠遠達不到O(2mmN2).另外,與傳統的基于Pareto的個體支配關系相比,在每個子種群中采用基于有效階的個體支配關系的優越性如下.1)改善了高維多目標優化問題中個體之間由于缺乏選擇壓力而導致收斂性下降的不足；2)彌補了僅用聚合函數評估個體優劣導致種群多樣性下降的缺陷.

2.3混合進化策略

在每個子種群的進化操作中,為了提高算法的局部搜索和全局搜索的性能,融合進化算法和傳統優化算法,在進化的不同階段自適應地選擇不同區域的個體參與新個體的生成.在進化過程的前期,為了增強算法的全局搜索能力,以較大的概率選擇其他子種群的個體進行交叉操作；在進化過程的后期,將傳統優化的Powell搜索法作為局部搜索算子來產生新的個體,以此來提高算法的收斂速度.

Powell法是一類經典、簡單有效的直接搜索方法,它在函數尋優的過程中僅僅借助函數值本身的信息,在優化問題中很方便使用.Powell法反復利用3個點的切比雪夫目標函數信息進行二次插值來逼近函數真正的極小值點,計算量相對較小.Powell法非常適合作為一種啟發式局部搜索算子融入到MOEA/D的進化操作中,以提高解的精度.

在每個子種群內部,Powell局部搜索算子隨機選出其中的任意兩個個體和與該子種群內的當前最好個體構成3個初始點,分別記為x1、x2和xi,best,利用式(4)計算當前3個個體對應在所在子空間i中的切比雪夫函數值,并按照函數值的大小關系對三個個體予以重新排序x1′、x2′、x3′,其中g(x1′)

(9)

式中：過三點(x1′,g(x1′))、(x2′,g(x2′))和(x3′,g(x3′))作一個二次多項式,并用該二次多項式的極小值點作為原函數極小值點的近似.此時,根據多元函數極值點存在的必要條件,利用二次函數的導數為0作為原函數極小值點的近似,即為xi,best.將新產生的最優點xi,best和原先3個個體x1′、x2′、x3′的切比雪夫函數值進行比較,并去掉最差的一個點,利用余下的3個點繼續作二次插值,重新得到新的最小值點yi,best.如此繼續作二次插值,直到滿足一定的精度后停止.

2.4基于新的個體支配關系的分解高維多目標進化算法

在執行過程中,設置的參數有：子問題(權重向量)的個數N,每個子問題對應的子種群的規模K,每個權重向量的鄰居權向量的個數T,執行選擇操作時用到的參數J,函數總共的評估次數Ev.算法的具體描述如下.

算法2HDMOEA-NRS主流程

1)初始化.

a)采用均勻設計[11]的方式產生N個權重向量λ1,λ2,…,λN.

b)隨機產生一個規模為N×K的初始化種群,x1,x2,…,xN×K,并計算初始種群的參考點Z=[z1,…,zm]T.

c)利用算法1將初始種群劃分為N個子種群,并且每個子種群中包含K個解,例如第i個子種群的個體記為{xi(K-1)+1,xi(K-1)+2,…,xiK},計算每個子種群的最好個體并將其記錄在xNK上.

d)計算兩兩權向量間的歐氏距離,對于每個子問題i,將鄰居向量設置為B(i)=[i1,…,iT].

2)更新操作.對于每個子問題i對應的子種群,隨機產生一個隨機數r.根據隨機數與選擇操作參數J的大小關系,選擇位于不同區域的個體參與不同的交叉操作,以便增加算法的局部搜索和全局搜索能力.

3)選擇和交叉操作.若隨機數r

4)變異操作.對交叉操作后生成的新個體y執行變異操作,生成新個體y′.

5)更新操作.用新個體y′更新參考點Z,并根據式(5)判斷新個體y′找到所屬的子種群Pl.比較y′與子種群Pl的最好個體xlK的有效階支配關系：當y′kxlK時,將新個體y′保留在子種群Pl中,并在子種群Pl中的其余K-1個個體中隨機刪除一個；當xlKky′時,將新個體y′舍棄.

3)判斷終止準則.

若終止條件滿足,則將每個子種群的最好個體作為最終種群輸出；否則,轉步驟2).

3實驗結果與分析

3.1實驗設計和參數設置

為了檢測HDMOEA-NRS算法的性能,將該算法用于求解5類目標數可擴展的測試問題,分別包括具有多個局部Pareto Front的測試問題DTLZ1、DTLZ2和DTLZ3[20]以及具有復雜Pareto Set的測試問題F1和F2[21].每個測試問題所求解的目標數分別為5、10、15和20,并將數值試驗的測試結果與三類的高維多目標進化算法,分別是采用分子種群的多目標進化算法MOEA/D-M2M[19]、均勻權向量設計的分解多目標進化算法UMOEA/D[14]和基于收縮和擴展支配域的多目標進化算法NSGAII-CE[22]所得到的實驗結果進行比較.

針對數值實驗中的每一個測試問題,4種算法(HDMOEA-NRS, MOEA/D-M2M,UMOEA/D和NSGAII-CE)采用相同的進化算子,個體均采用實數編碼,具體參數設置如下.1) 種群規模：HDMOEA-NRS、MOEA/D-M2M、UMOEA/D和NSGAII-CE的種群規模設置為N=200, HDMOEA-NRS采用Beume等[11]提出的均勻設計的方式產生權向量集合,鄰居向量|B(i)|=20,每個子種群中包含的個體數K=5.2)進化操作采用差分進化和多項式變異：在差分進化操作中,交叉概率為0.5,比例因子為0.5；在多項式變異操作中,分布指數為20,變異概率為0.1.3)4個算法對于每個測試問題的最大函數評估次數為400 000.4)選擇操作參數J為

式中：maxEv為函數的最大評估次數.

在該數值實驗中,采用IGD[23](inverted generational distance)指標來度量算法的性能.IGD指標可以同時度量算法所獲得非支配解集合的收斂性和分布性,其取值越小,算法的性能越好.每種算法對每個測試問題獨立運行20次,分別記錄IGD指標在20次運行后計算出的均值和方差.

為了驗證在基于子種群的分解多目標進化算法中引入個體新支配關系和局部搜索策略對于算法收斂性的影響,將提出算法HDMOEA-NRS和MOEA/D-M2M針對5、10、15、20目標的測試問題DTLZ2分別獨立運行20次,分別記錄GD (generational distance)指標在20次運行后計算出的均值和方差.其中,GD[23]指標是用來度量算法所獲得非支配解集合的收斂性能,取值越小,算法的收斂性越好.

3.2對比實驗結果

表1給出3種算法獨立運行20次計算出非支配解集合IGD指標的均值mean和方差std結果,對比同一測試問題在3種不同算法下的IGD指標均值,最優結果在表1中用黑體加粗顯示.為了驗證提出算法HDMOEA-NRS的性能與同類高維多目標進化算法相比的穩定性,依次對每種算法獨立運行20次后得到的IGD指標樣本數據進行顯著性水平為0.05的t檢驗,檢驗結果如表1所示.在每一行所對應的測試問題中,“+”,“-”,“=”分別表示提出算法HDMOEA-NRS的性能優于、劣于或者等于所比較算法.

表1　3種算法在不同測試函數時分別運行10次得到的IGD統計結果

圖1　2種算法針對5、10、15、20目標的測試問題DTLZ2的GD指標統計盒圖Fig.1　Statistical box diagram of two algorithms in DTLZ2 with 5,10,15,20 objectives

從表1可以看出,前兩種算法HDMOEA-NRS和MOEA/D-M2M的IGD指標均值遠遠優于UMOEA/D和NSGAII-CE,說明通過采用分子種群分解技術的高維多目標進化算法HDMOEA-NRS和MOEA/D-M2M獲取的非支配解集合的收斂性和多樣性明顯優于采用均勻權向量的分解多目標進化算法UMOEA/D,也優于僅僅通過增加個體選擇壓力的方式來增加收斂性的算法NSGAII-CE.另一方面,對比HDMOEA-NRS和MOEA/D-M2M,提出算法HDMOEA-NRS的IGD均值在大多數測試問題中優于MOEA/D-M2M,表明算法提出的基于子種群內部的個體排序策略和Powell搜索在提高算法的收斂性能方面的有效性和合理性.

圖1 給出提出算法HDMOEA-NRS和MOEA/D-M2M針對5、10、15、20目標的測試問題DTLZ2分別獨立運行20次計算的GD指標的統計盒圖,它能夠完整地反映數據的離散分布的統計特性.圖中,盒子的上、下兩條邊界線分別表示樣本數據的上、下四分位數,盒子中間的水平線表示樣本的中位數.從圖1可以看出,當目標數為5時,2種算法的GD指標均值相差不大；但是當目標數較多時,算法HDMOEA-NRS的收斂性明顯優于MOEA/D-M2M.

3.3個體新支配關系和局部搜索策略對于算法性能的影響分析

為了驗證提出的基于有效階的個體支配關系對算法收斂性和分布性的影響,對提出算法HDMOEA-NRS進行調整,將基于Pareto支配關系用于子種群內部個體間優劣關系的比較和個體更新操作,而其他進化算子和參數設置保持不變.針對5、10、15、20個目標的測試問題DTLZ1,將HDMOEA-NRS與調整后的采用Pareto排序的算法分別獨立運行20次,將計算出的IGD指標均值進行比較,結果如圖2所示.可以看出,提出算法將基于有效階的個體支配關系用于子種群內部個體間優劣關系的比較和個體更新操作,獲得的Pareto非支配解集合的收斂性和分布性具有更強的優勢.

為了驗證采用的Powell局部搜索策略對于算法收斂性和分布性的影響,對提出算法HDMOEA-NRS進行調整,在子種群的進化操作中取消了Powell局部搜索,而其他進化算子和參數設置保持不變.針對5、10、15、20個目標的測試問題DTLZ1,將HDMOEA-NRS與調整后算法分別獨立運行20次,將計算出的IGD指標均值進行比較,結果如圖3所示.可以看出,當目標數為5時,是否采用局部搜素算子對算法性能的影響不大,但是當目標數較多時,采用局部搜索算子能夠較好地提高算法的收斂性能.

圖2　2種排序策略對于算法性能的影響Fig.2　Influence of performance with two ranking strategy

圖3　局部搜素算子的運用對于算法性能的影響Fig.3　Influence of performance with use of local search operator

3.4參數敏感性分析

為了測試不同的實驗參數設置對于算法性能的影響,針對測試問題DTLZ1(5),分別檢驗權向量的鄰居個數T和子種群的規模K對IGD性能指標的影響.首先,在保持其他參數不變的情況下,測試當T的取值分別為5、8、12、15、20、25、30時,分別獨立運行HDMOEA-NRS算法20次計算出IGD指標的均值結果進行比較,結果如表2所示.表2的數據表明,T的設置對IGD指標的擾動僅為4%,說明T對算法的性能影響不大.在算法的執行過程中,T的取值越大,表明算法的全局搜索能力越強,本文取T=20.

為了驗證不同的子種群規模K對算法性能的影響,在保持其他參數不變的情況下,測試當K的取值分別為5、7、9、11、13、15時,分別獨立運行HDMOEA-NRS算法20次計算出IGD指標的均值結果進行比較,結果如表3所示.表3的數據表明, K的設置對IGD指標的擾動僅為3.7%,說明K對算法的性能影響不大.子種群的規模越大,計算過程中函數的評估次數越多,從而增大了算法的計算量.取最小值K=5.

表2　不同的鄰域規模T的設置對IGD的影響

表3　不同的子種群規模K的設置對IGD的影響

4結語

為了進一步改善高維多目標優化算法中非支配解集合的分布性和收斂性,在基于分解技術的思想啟發下,提出基于新個體支配關系的混合分解高維多目標進化算法.本文的主要貢獻在于設計新的基于有效階的個體支配關系用于子種群內部個體間優劣關系的比較和子種群的更新操作,在增加個體的選擇壓力的同時提高解集分布的多樣性；提出將Powell搜索作為局部搜索算子與進化算法相融合的混合進化策略,以提高基于分解算法的求解精度.實驗結果表明,HDMOEA-NRS算法在提高算法的收斂性和改善非支配解集分布的多樣性上是有效的.

參考文獻 (References):

[1]CHRISTIANVL.Asurveyonmulti-objectiveevolutionaryalgorithmsformany-objectiveproblems[J].ComputationalOptimizationandApplications, 2014, 58(3):707-756．

[2] 公茂果,焦李成,楊咚咚,等. 進化多目標優化算法研究[J]. 軟件學報,2009, 2(20): 271-289．

GONGMao-guo,JIAOLi-cheng,YANGDong-dong,etal.Researchonevolutionarymulti-objectiveoptimizationalgorithms[J].JournalofSoftware, 2009, 2(20): 271-289．

[3] 孔維健. 高維多目標進化算法研究綜述[J]. 控制與決策, 2010,25(3)：321-326．

KONGWei-jian.Surveyonlarge-dimensionalmulti-objectiveevolutionaryalgorithms[J].ControlandDecision, 2010, 25(3): 321-326．

[4] 鞏敦衛. 基于集合的高維多目標優化問題的進化算法[J]. 電子學報, 2014, 42(1): 77-83．

GONGDun-wei.Solvingmany-objectiveoptimizationproblemsusingset-basedevolutionaryalgorithms[J].ActaElectronicaSinica, 2014, 42(1): 77-83．

[5]PIERRODF,KHUST,SAVICDA.Aninvestigationonpreferenceorderrankingschemeformulti-objectiveevolutionaryoptimization[J].IEEETransactionsonEvolutionaryComputation, 2007, 11(1): 17-45．

[6]ZOUXiu-fen,CHENYu,LIUMin-zhong.Anewevolutionaryalgorithmforsolvingmany-objectiveoptimizationproblems[J].IEEETransactionsonSystems,Man,andCybernetics,partB-Cybernetics, 2008, 38(5): 1402-1412．

[7]MOLINAJ,SANTANAL,HERNANDEZ-DIAZA,etal.G-dominance:referencepointbaseddominanceformultiobjectivemetaheuristics[J].EuropeanJournalofOperationalResearch, 2009, 197(2): 685-692．

[8]DEBK,JAINH.Anevolutionarymany-objectiveoptimizationalgorithmusingreference-point-basednondominatedsortingapproach,parti:solvingproblemswithboxconstraints[J].IEEETransactionsonEvolutionaryComputation, 2014, 18(4): 577-601.

[9]YUANYuan,HUAXu,WANGBo.Anewdominancerelationbasedevolutionaryalgorithmformany-objectiveoptimization[J].IEEETransactionsonEvolutionaryComputation, 2016,20(1): 16-37．

[10]ZITZLERE,SIMONK.Indicator-basedselectioninmulti-objectivesearch[C]∥ConferenceonParallelProblemSolvingfromNature(PPSNVIII).UK:Springer, 2004: 832-842．

[11]BEUMEN,NAUJOKSB,EMMERICHM.SMS-EMOA:multiobjectiveselectionbasedondominatedhypervolume[J].EuropeanJournalofOperationalResearch, 2007, 181(3): 1653-1669．

[12]WHILEL,BRADSTREETL,BARONEL.Afastwayofcalculatingexacthypervolumes[J].IEEETransactionsonEvolutionaryComputation, 2012, 16(1): 86-95．

[13]ZHANGQ,LIH.MOEA/D:amultiobjectiveevolutionaryalgorithmbasedondecomposition[J].IEEETransactionsonEvolutionaryComputation, 2007, 11(6): 712-731．

[14]TANYan-yan,JIAOYong-chang,LIHong.MOEA/D+uniformdesign:anewversionofMOEA/Dforoptimizationproblemswithmanyobjectives[J].ComputersandOperationsResearch, 2013, 40(6): 1648-1660．

[15]JIANGS,CAIZ,ZHANGJ,etal.MultiobjectiveoptimizationbydecompositionwithPareto-adaptiveweightvectors[C]∥Proceedingof7thInternationalConferenceonNaturalComputation.Shanghai:IEEE, 2011: 1260-1264．

[16]LIH,ZHANGQ.MultiobjectiveoptimizationproblemswithcomplicatedParetosets,MOEA/DandNSGA-II[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(2): 284-302．

[17]ZHOUA,ZHANGQ,ZHANGG.Amultiobjectiveevolutionaryalgorithmbasedondecompositionandprobabilitymodel[C]∥IEEECongressonEvolutionaryComputation. [S.l.]:IEEE, 2012: 1-8.

[18]QIY.MOEA/Dwithadaptiveweightadjustment[J].EvolutionaryComputation, 2014, 22(2): 231-264．

[19]LIUHai-lin,GUFang-qing,ZHANGQing-fu.Decompositionofamulti-objectiveoptimizationproblemsintoanumberofsimplemulti-objectivesub-problems[J].IEEETransactionsonEvolutionaryComputation, 2014, 18(3): 450-455．

[20]DebK,THIELEL,LAUMANNSM,etal.Scalablemultiobjectiveoptimizationtestproblems[C]∥IEEECongressonEvolutionaryComputation(CEC’02). [S.l.]:IEEE, 2002: 825-830．

[21]ZHANGQ,ZHOUA,ZHAOS,etal.Multi-objectiveoptimizationtestinstancesfortheCEC2009specialsessionandcompetition[R].Clemson:UniversityofEssex, 2008．

[22] 代才. 基于分解的多目標進化算法研究[D]. 西安：西安電子科技大學,2014: 50-70．

DAICai.Researchonevolutionaryalgorithmsbasedondecompositionformany-objectiveoptimizationproblems[D].Xi’an:XidianUniversity, 2014: 50-70.

[23]ZITZLERE,LAUMANNSM,THIELEL.Performanceassessmentofmulti-objectiveoptimizers:analysisandreview[J].IEEETransactionsonEvolutionaryComputation, 2003, 7(2): 117-133.

收稿日期：2015-04-24.浙江大學學報(工學版)網址： www.journals.zju.edu.cn/eng

基金項目：國家自然科學基金資助項目(61472297，61272119，61402350，61502290);陜西省教育廳專項科研資助項目(16JK1381).

作者簡介：過曉芳(1981-)，女，博士，講師，從事多目標進化算法的研究. ORCID: 0000-0002-8944-3400. E-mail: gxfang1981@126.com

DOI:10.3785/j.issn.1008-973X.2016.07.013

中圖分類號：TP 301

文獻標志碼：A

文章編號：1008-973X(2016)07-1313-09

Newhybriddecompositionmany-objectiveevolutionaryalgorithm

GUOXiao-fang1,2,WANGYu-ping1,DAICai1

(1. School of Computer, Xidian University, Xi’an 710071, China;2. School of Science, Xi’an Technological University, Xi’an 710032, China)

Abstract:A hybrid decomposition many-objective evolutionary algorithm based on a new dominance relation was proposed inspired by many-objective evolutionary algorithms based on decomposition in order to improve the diversity and convergence of the non-dominated solution set in many-objective optimization problems. The sub-population evolutionary pattern was adopted, and a new efficiency order based dominance relation was designed to compare and update individuals inside each subpopulation, which helps to increase selective pressure and improve diversity. Powell search was used as the local search operator in order to improve the performance of local search. A hybrid evolution strategy combining traditional optimization method with evolutionary algorithm was adopted. Six standard benchmark problems with 5 to 20 objectives were tested to demonstrate the effectiveness of the algorithm. Experimental results showed that the algorithm performed better than other available algorithms in convergence and diversity．

Key words:many-objective optimization problem; evolutionary algorithm; subpopulation; dominance relation