MOEA/D線性插入方向向量策略研究

林夢嫚,王麗萍,周 歡

(浙江工業(yè)大學 經(jīng)貿(mào)學院, 杭州 310023)

1 引 言

多目標問題(Multi-objective problems,MOPs)中目標函數(shù)之間一般是相互沖突的,沒有一個最優(yōu)解能夠同時優(yōu)化所有的目標.Pareto最優(yōu)解對于決策者來說是一種很好的選擇.由于進化算法一次運行能夠提供多個Pareto最優(yōu)解,且不受目標函數(shù)數(shù)學性質(zhì)的影響,因此利用進化算法求解多目標優(yōu)化問題成為近年來的研究熱點[1].

近年來,多目標進化算法(Multi-objective evolutionary algorithms,MOEAs)的應用極為廣泛.根據(jù)現(xiàn)有的研究,MOEAs分為以下3類:

1)基于Pareto支配的多目標進化算法[2，3],該類方法以Pareto支配選擇較優(yōu)的解,隨著目標個數(shù)的增多,非支配解的比例明顯增加,搜索能力明顯退化[4].

2)基于指標的多目標算法[5-7],該類算法以某些性能指標作為參考信息選擇較優(yōu)的解,然而計算性能指標的復雜度較高,耗時較長.

3)基于分解的多目標算法[8-10],該系列算法將多目標問題分解為多個單目標子問題協(xié)同優(yōu)化,該類算法求解效率高,解集性能較優(yōu),其中以Q.Zhang[11]提出的基于分解的多目標進化算法(Multi-objective evolutionary algorithm based on decomposition,MOEA/D)效果最為顯著.

基于分解的多目標進化算法有幾個顯著的優(yōu)點.與Pareto支配的進化算法相比,有著較強的搜索能力,能夠很好的處理組合優(yōu)化問題,計算簡單,求解效率高,能夠很好的處理復雜Pareto Sets[12]的多目標問題等優(yōu)點.MOEA/D獲得2009年進化計算“無限制多目標進化算法”的冠軍[13],并普遍應用于諸多實際問題中.

至今為止,為提高MOEA/D的性能,學者們已經(jīng)做了大量的研究,根據(jù)研究的主要內(nèi)容,大致分為兩大類.一類為生成均勻的權(quán)重向量,嘗試依靠均勻分布的權(quán)重向量獲取均勻分布的解集.另一類則為算法進化過程中,根據(jù)進化得出的解集,調(diào)整權(quán)重向量,維持解集較好的分布特性.為研究的方便,本文側(cè)重于后者.

自Q.Zhang 2007年提出MOEA/D以來,很多學者已經(jīng)證明MOEA/D中預先設定的固定權(quán)重向量并不能夠保證解集均勻分布整個Pareto前端.2010年,Gu和Liu[14]根據(jù)當前權(quán)重向量集合周期性地更新權(quán)重向量,在此基礎(chǔ)上提出W-MOEA/D(A Novel Weight Design in Multi-objective Evolutionary Algorithm,W-MOEA/D)算法,相比原始的MOEA/D,該算法求出解集的整體質(zhì)量有所提高,然而W-MOEA/D算法依靠WS(Weighted Sum,WS)聚合方法,由于WS聚合方法本身存在不能處理非凸問題的缺陷,因此阻礙了該算法的適用性.2011年,Jiang et al[15]提出paλ-MOEA/D(Multi objective Optimization by Decomposition with Pareto-adaptive Weight Vectors,paλ-MOEA/D),該算法根據(jù)Pareto前端的幾何特性對權(quán)重向量進行調(diào)整,該算法能夠獲得收斂性和多樣性較好的解集,然而該算法要求求解的多目標優(yōu)化問題的PF(Pareto Front,PF)為四分之一圓形或者球形.實際求解過程中,待求解問題的PF都是未知的,因此,該算法存在一定的缺陷.2013年,Wang et al[16]提出使用預處理策略調(diào)整權(quán)重向量,為初始化的個體找到距離相對較近的權(quán)重向量,為敘述的簡便,本文將該算法簡記為MOEA/D-pre(An enhanced MOEA/D using uniform directions and a pre-organization procedure,MOEA/D-pre),該算法能夠提高解集的收斂性,然而初始化的個體隨機性較大,導致MOEA/D算法中引入預處理策略的效果較差.隨后Qi et al[17]提出MOEA/D-AWA(MOEA/D With Adaption Weight Adjust,MOEA/D-AWA)算法,MOEA/D-AWA提出一種新的權(quán)重向量初始化技術(shù),同時根據(jù)復雜的Pareto前端自適應調(diào)整權(quán)重向量,提高解集的均勻性.然而MOEA/D-AWA中需要維持一定數(shù)量的外部非支配解,根據(jù)這些非支配解的擁塞距離自適應調(diào)整權(quán)重向量,這種方法增加了計算的復雜性,并消耗一定的時間.隨后,Yuan et al[18]提出MOEA/D-DU(Balancing Convergence and Diversity in Decomposition-Based Many-Objective Optimizers,MOEA/D-DU),根據(jù)解與相關(guān)子問題之間的垂直距離,調(diào)整解集的分布.實驗證明,該算法在高維多目標優(yōu)化問題中效果顯著,然而持續(xù)性的計算解與子問題的垂直距離消耗的計算資源較多,同時對于復雜的PF,依舊難于處理.2016年,Jiang et al[19]分析Pareto前端為尖峰、低尾、不連續(xù)的情況,提出兩階段策略的MOEA/D-TPN(an improved MOEA/D with a two-phase strategy(TP)and a niche-guided scheme,MOEA/D-TPN)算法,實驗表明該算法通過分析運行過程中問題的難易程度,把多目標問題的優(yōu)化分為兩個階段,合理利用計算資源,能夠有效地求解具有復雜PF的問題.然而,該算法具有兩個缺陷:其一,該算法設計的參數(shù)較多,在PF未知的情況下,算法中一系列的參數(shù)難以確定.其二,該算法不易預測種群的擁塞程度.

本文,首先分析均勻分布的權(quán)重向量、均勻分布的搜索方向二者與均勻分布的解集之間的關(guān)系,提出一種新的權(quán)重向量設置方式;其次利用進化過程中解集的分布特性,提出不依賴于外部種群的線性插入搜索方向策略,并將其轉(zhuǎn)換為對應的權(quán)重向量,同時在MOEA/D中周期性使用該策略調(diào)整搜索方向,獲取分布均勻的解集,提出使用調(diào)整權(quán)重向量的MOEA/D-AW算法,為比較公正性,采用WFG多目標算法測試函數(shù)進行系列仿真試驗,并將該算法與原始的MOEA/D、使用均勻分布的搜索方向MOEA/D、使用預處理的MOEA/D、MOEA/D-DU進行性能比較.

2 背景知識

2.1 權(quán)重向量的生成

當決策者沒提供任何的偏好信息的時候,希望得到的結(jié)果是均勻分布在Pareto前端上.因此對于MOEA/D來講,使用相對均勻的權(quán)重向量的結(jié)果比不均勻的權(quán)重向量效果更好.為此,MOEA/D中生成權(quán)重向量的方法.描述如下:

λ1+λ2+…+λk=1

(1)

(2)

2.2 MOEA/D中均勻權(quán)重向量、均勻搜索方向、均勻Pareto最優(yōu)解三者之間的關(guān)系

圖1中標識為權(quán)重向量的線條代表原始的MOEA/D預先設定的權(quán)重向量,虛線表示與預先設定的權(quán)重向量對應的方向向量.根據(jù)對聚合函數(shù)的幾何特性分析可知,Pareto最優(yōu)點為方向向量與PF的交點,如圖中的圓圈,而不是預先設定的權(quán)重向量與PF的交點.因此,均勻分布的方向向量能盡可能地保證均勻分布的Pareto最優(yōu)解集,預先設定的均勻分布的權(quán)重向量卻并不能夠保證產(chǎn)生均勻分布的Pareto最優(yōu)解集.文獻[16]中也給出相關(guān)的證明.基于以上的分析,本文決定使用2.3小節(jié)中的方法生成目標空間中的搜索的方向向量,然后根據(jù)表達式(3)將其轉(zhuǎn)換為對應的權(quán)重向量.

(3)

其中λij即為采用2.3小節(jié)中的方法生成的方向向量的分量.表達式(3)有如下的修訂,當λij為0時,修改為λij+ε,其中ε為0.000001,其他情況,不做任何修改.采用這一策略,盡可能在初始化時產(chǎn)生均勻分布的方向向量,提高算法求得解集分布的均勻性.

圖1 MOEA/D中權(quán)重向量、方向向量、Pareto最優(yōu)解三者之間的關(guān)系Fig.1 Relationship between weight vector,direction vector and Pareto optimal solution in MOEA/D

3 具有復雜Pareto前端的多目標問題及MOEA/D存在的缺陷分析

3.1 復雜Pareto前端的多目標問題

現(xiàn)實生活中,多目標問題的Pareto前端都是未知的.因此均勻分布的搜索方向只能盡可能地提高解集分布的多樣性,但對于復雜的Pareto前端的多目標問題,僅依靠預先設定的均勻分布搜索方向顯然是不夠的.

3.2 MOEA/D存在的缺陷

4 線性插入搜索方向策略

基于以上的分析,本文將使用k近鄰方法求出進化過程中算法解集的密集度,刪除解集中最密的個體,對于解集中最稀疏的區(qū)域,利用附近的個體對應的方向向量,線性插入搜索方向(如圖2所示),并利用附近的個體產(chǎn)生出新的個體,達到增強解集多樣性的效果.具體算法流程如下:

圖2 線性插入方向向量示意圖Fig.2 Linear insertion direction vector diagram

輸入:

1.多目標優(yōu)化問題;

2.停止條件;

3.N:MOEA/D分解的子問題個數(shù)即種群規(guī)模大小;

4.λ1,λ2,…,λN:采用2.3中方法構(gòu)造的N個方向向量并利用式子(3)將其轉(zhuǎn)換為對應的權(quán)重向量;

5.T:預定的鄰域大小;

6.Adjust_Gen:0.8*MaxGen開始使用線性插入策略的代數(shù);調(diào)整的周期為 delta.

輸出:PF:{F(x1),F(x2),…,F(xN)}.

Step 1.初始化:

Step 1.1.計算任意兩個權(quán)重向量之間的歐式距離,為每個權(quán)重向量選出最近的T個向量作為它的鄰域.設B(i)={i1,i2,…,iT},i=1,2,…,N,其中λi1,λi2,…,λiT為距離λi最近的T個權(quán)重向量.

Step 1.2.采用隨機或均勻設計方法初始化種群x1,x2,…,xN,設FVi=F(xi),i=1,2,…,N.

Step 2.更新:

i=1,2,…,N,執(zhí)行

Step 2.2.修正:應用問題特定的修正或啟發(fā)式的改進策略作用于y生成y′.

Step 2.3.更新z:若fj(y′)

Step 2.4.更新鄰域解:若gte(y′|λj,z)≤gte(xj|λj,z),j∈B(i),則xj=y′,FVj=F(y′).

Step 3.線性插入搜索方向并更新解集:若算法迭代次數(shù)大于或者等于Adjust_Gen,每隔delta代,使用線性插入搜索方向策略;具體步驟為,計算每個個體的k近鄰值,找出k近鄰最大的個體對應的子問題記為indexMax,找出k近鄰最小的個體對應的子問題記為indexMin.刪除indexMin對應的個體,找到indexMax對應的個體,計算方向向量與indexMax個體方向向量最近的兩個個體,序號記為addindex1和addindex2,假設addindex1個體對應的k近鄰值大于addindex2個體對應的k近鄰值,確定加入的搜索方向向量在indexMax與addindex1之間,反之為indexMax與addindex2之間.根據(jù)以上找出的兩個個體,對其方向向量求均值,線性插入一個方向向量,并轉(zhuǎn)換為權(quán)重向量,在以上的兩個個體中隨機復制某一個個體(僅復制x與f(x)值)給新增的個體.最后重新計算鄰域并更新z(示意圖如圖4所示).

圖3 WFG1的IGD指標對比Fig.3 Index comparison of IGD of WFG1

Step 4.停止判斷:若滿足停止條件,則算法停止,輸出PF,否則返回Step 2繼續(xù)執(zhí)行.

圖4 WFG2的IGD指標對比Fig.4 Index comparison of IGD of WFG2

對于步驟3中,在算法迭代次數(shù)大于一定值,周期性引入線性插入搜索方向向量的策略的解釋如下:算法在初期,解集隨機產(chǎn)生,并不具備任何代表性,此時解集的分布遠離真實的Pareto前端,因此需要在進化到一定的代數(shù)后,解集能夠顯示出Pareto前端大概分布的情況下開始嘗試調(diào)整搜索方向,達到均勻分布解集的效果.周期性的調(diào)整是為了使新增的個體有著一定的時間去使用種群的進化,有利于種群在進化過程中保留相對較好的解.

5 仿真實驗及結(jié)果分析

本文選擇典型的二維測試函數(shù)WFG1-WFG9[20],選擇算法為原始的MOEA/D,使用均勻分布的方向向量MOEA/D-US,使用預處理的MOEA/D-pre和MOEA/D-DU算法,與本文提出的MOEA/D-AW算法進行性能對比分析.與MOEA/D對比的原因在于,本文的算法是在其基礎(chǔ)上改進,而MOEA/D-US則是為了排除采用均勻搜索方向這一措施產(chǎn)生的影響,使得比較更加公正.至于后兩者都是復雜PF的算法類型,對比是為了驗證改進算法的性能.性能評價指標采用世代距離指標(GD)[21]、Spacing指標(SP)[22]、反向世代距離指標(IGD)[23]、超體積指標(HV)[24]對解集收斂性、多樣性及整體性能進行對比分析.各算法對每個測試函數(shù)獨立運行20次.

本次實驗采用的實驗條件如下:平臺為Intel(R)Core(TM)i3,4.00GB RAM,實驗環(huán)境為MATLAB2014a.算法的種群為100,迭代次數(shù)為800,目標維度為2,鄰域大小為20,單次替換最大個數(shù)為5,分別獨立運行20次,雜交算法為差分算子,雜交概率為0.9,F為0.5,CR為0.5,變異為多項式變異,變異位置為20,變異概率為1/n,其中n為測試函數(shù)的變量個數(shù).

5.1 算法的GD指標、S指標測試

為分析改進算法相比原始算法求得解集的收斂性及多樣性,本次實驗選擇以上給出的GD指標和S指標分別對算法的收斂性及多樣性進行比較.GD指標中,在標準的Pareto前端上采樣500個點,所得結(jié)果如表1所示.

表1 兩種算法的GD均值及S均值
Table 1 Mean value of GD and the mean value of S
of the two algorithms.

測試問題GD均值S均值MOEA/DMOEA/D-AWMOEA/DMOEA/D-AWWFG10.08780.06830.03510.0386WFG20.00140.00150.03880.0220WFG30.07560.05930.02380.0138WFG40.16340.13100.02530.0163WFG50.12760.10830.02510.0148WFG60.00890.00100.02580.0160WFG70.08760.07420.02460.0155WFG80.03040.03550.02630.0278WFG90.06720.06070.02230.0156

表1給出兩種算法在WFG1-WFG9測試問題上的GD均值和S均值.觀察GD均值中的MOEA/D-AW算法一欄可知,除了WFG2和WFG8,其他的測試問題上,改進算法求出的解集的GD均值均比原始算法求出解集的GD均值小,WFG4測試問題上最明顯.表明采用均勻搜索方向和線性插入搜索方向策略后,可以改進算法求出解集的收斂性.原因在于,進化過程中,根據(jù)算法求出解集的分布性,適當調(diào)整搜索方向,進而調(diào)整對應的權(quán)重向量,可以有效地引導解集朝向真實的PF,避免部分個體陷入局部最優(yōu),提高算法的收斂性.至于WFG2和WFG8,改進算法的效果相對略差.觀察表1中S均值對應的兩列,可以得出,大部分的測試函數(shù),改進的算法的S均值相比原始的MOEA/D算法求出的解集的S均值小很多,說明采用線性插入方向向量,進化過程中根據(jù)解集的分布性,通過探測真實的PF,不斷調(diào)整搜索的方向,刪除密集區(qū)域的重復個體,稀疏區(qū)域增加個體,有利于提高算法的多樣性.以上兩組數(shù)據(jù)表明,改進的算法可以提高求出解集的收斂性與多樣性.

5.2 算法的IGD指標測試

為比較改進算法與原始算法求得解集收斂性與多樣性的整體性能.本次測試采取能夠評價算法整體性能的IGD指標,采樣點數(shù)為500點.為簡易直觀顯示出MOEA/D與MOEA/D-AW兩種算法的性能,以下將給出5種算法在9種測試問題上的箱須圖.

由圖3至圖11可知:在使用IGD指標對算法的整體性能進行測試時,結(jié)果顯示出MOEA/D-AW算法求出IGD的均值在以上的幾個測試問題均比MOEA/D等其它4個算法求出均值小;除了WFG9函數(shù),MOEA/D-AW算法求出的IGD均值與MOEA/D算法求出均值相差不大,但在該測試問題上,MOEA/D-AW算法求出IGD指標的方差比MOEA/D算法求出IGD指標的方差小很多(MOEA/D-AW算法的盒子長度比MOEA/D盒子長度小很多),說明MOEA/D-AW求解性能更加穩(wěn)定,其他的幾幅圖中也可觀測出穩(wěn)定性;在WFG1,WFG3-WFG7幾個測試問題上,可以看出MOEA/D-AW求出結(jié)果的IGD指標的均值,最小值,最大值均比原始的MOEA/D算法求出的指標值小很多,說明MOEA/D-AW中采用線性調(diào)整權(quán)重向量的策略能夠根據(jù)進化過程中求出的解集分布適當?shù)卣{(diào)整搜索向量,有效地解決稀疏區(qū)域甚至不連續(xù)區(qū)域搜索向量的資源浪費問題,極大地增加了算法求解的多樣性,同時使用更多的個體搜索解,增大算法求解的收斂性,從而極大地提高了算法的整體求解性能.

圖5 WFG3的IGD指標對比Fig.5 Index comparison of IGD of WFG3

圖6 WFG4的IGD指標對比Fig.6 Index comparison of IGD of WFG4

圖7 WFG5的IGD指標對比Fig.7 Index comparison of IGD of WFG5

圖8 WFG6的IGD指標對比Fig.8 Index comparison of IGD of WFG6

圖9 WFG7的IGD指標對比Fig.9 Index comparison of IGD of WFG7

圖10 WFG8的IGD指標對比Fig.10 Index comparison of IGD of WFG8

5.3 算法的HV指標測試

為進一步分析改進算法的求出解集的整體性能,本次實驗選擇更為精確的超體積(HV)指標度量,超體積即被非支配解集覆蓋的目標空間區(qū)域大小,其度量方法,在理論上具有良好的數(shù)學性質(zhì),即在所有的一元測度中,是一個能夠判定非支配解集比另一個非支配解集更優(yōu)的有效方法,其值越大,解集質(zhì)量越高.比較的算法有如下幾種:原始的MOEA/D,MOEA/D-US,MOEA/D-pre,MOEA/D-DU,MOEA/D-AW,HV指標中采樣點數(shù)為100000,參考點為1.2*F(max),其中F(max)為所求解集的各個分量的最大值.便于直觀地比較,以下分別給出5種算法在WFG1-WFG9測試問題上的HV指標的箱須圖.

圖11 WFG9的IGD指標對比Fig.11 Index comparison of IGD of WFG9

圖12至圖20分別為MOEA/D,MOEA/D-US,MOEA/D-pre,MOEA/D-DU和MOEA/D-AW在WFG1-WFG9測試函數(shù)上算法獨立運行20次,得到的超體積指標值對比圖.分析以上9幅圖可以得出如下幾點結(jié)論:

圖12 WFG1超體積指標對比Fig.12 Comparison of WFG1 hyper volume index

1)MOEA/D-US算法求出解集的HV指標值對應的盒須圖的中值基本上都略高于MOEA/D算法求出解集的HV指標值的中值,WFG1,WFG6,WFG9測試函數(shù)上顯示出MOEA/D-US算法求出解集的HV指標值分布相比原始的MOEA/D算法求出的HV指標值更為集中.表明采取均勻的搜索方向比均勻的權(quán)重向量略好.

圖13 WFG2超體積指標對比Fig.13 Comparison of WFG2 hyper volume index

2)對比MOEA/D,MOEA/D-US,MOEA/D-AW三個算法在以上九個測試函數(shù)上的HV指標值分布情況看,MOEA/D-AW算法求出解集的HV指標值的最小值(盒須圖的最下面的橫線)中值及最大值(盒須圖的最上面的橫線)均大于(高于)MOEA/D-US算法求出的HV指標對應的值,表明本文提出的線性插入方向向量的策略有利于提高算法求得解集的整體質(zhì)量.除了WFG2測試函數(shù)以外,其他的幾個測試函數(shù)對應的圖上顯示出, MOEA/D-AW算法求出解集的HV指標值的離散程度遠遠小于MOEA/D-US,MOEA/D算法的求出解集的HV指標值.表明引入線性插入搜索方向策略可以提高算法的求解的穩(wěn)定性.得出質(zhì)量相對較好的解集.

圖14 WFG3超體積指標對比Fig.14 Comparison of WFG3 hyper volume index

圖15 WFG4超體積指標對比Fig.15 Comparison of WFG4 hyper volume index

圖16 WFG5超體積指標對比Fig.16 Comparison of WFG5 hyper volume index

3) 以上9幅圖均顯示出MOEA/D-AW算法求出的解集的HV指標對應的盒須圖的最小值、中值、最大值都高于其他的四個算法求出的解集的HV指標對應的值,表明引入線性插入搜索方向策略,根據(jù)進化過程中解集的離散分布情況,適當調(diào)整搜索方向,通過減少密集區(qū)域的搜索方向,去除重復的個體,稀疏區(qū)域增加搜索方向,增加新的個體,引導解集均勻分布在Pareto前端,有利于提高算法求解的整體質(zhì)量,得到更優(yōu)的解.WFG6,WFG7測試函數(shù)上顯示出算法求出高質(zhì)量解集穩(wěn)定性更好(對應的盒須圖長度最短),WFG1,WFG4,WFG6,WFG9測試函數(shù)上的結(jié)果顯示出MOEA/D-AW求出解集的HV指標的中值遠遠大于其他的四種算法求出超體積指標的中值,再次驗證引入線性插入搜索方向策略,能夠求出質(zhì)量更好的解集.

圖17 WFG6超體積指標對比Fig.17 Comparison of WFG6 hyper volume index

圖18 WFG7超體積指標對比Fig.18 Comparison of WFG7 hyper volume index

圖19 WFG8超體積指標對比Fig.19 Comparison of WFG8 hyper volume index

4) 以上的幾幅圖顯示出MOEA/D-pre,采用預處理的方式調(diào)整權(quán)重向量僅能略微提高算法的性能,MOEA/D-DU相比前面的三種略好,但是相比MOEA/D-AW,性能則差很多,原因在于,MOEA/D-DU僅注意到新產(chǎn)生的個體到子問題的垂直距離,并沒有考慮復雜Pareto前端帶來的影響.

以下給出5種算法在9種測試函數(shù)上的HV均值(HV最大值)的詳細數(shù)據(jù)(表2).

圖20 WFG9超體積指標對比Fig.20 Comparison of WFG9 hyper volume index

表2 4種算法對應的HV均值及HV最大值
Table 2 Mean value and maximum value of HV of the four algorithms

測試問題MOEA/DMOEA/D-USMOEA/D-preMOEA/D-DUMOEA/D-AWWFG10.5276(0.5494)0.5412(0.5900)0.5324(0.5709)0.5990(0.6486)0.6769(0.6982)WFG20.4575(0.4718)0.4588(0.4676)0.4566(0.4691)0.4627(0.4699)0.5478(0.6893)WFG30.6393(0.6475)0.6405(0.6465)0.6412(0.6470)0.6401(0.6467)0.6473(0.6503)WFG40.4244(0.4359)0.4266(0.4351)0.4258(0.4363)0.4271(0.4319)0.4494(0.4528)WFG50.4252(0.4294)0.4248(0.4291)0.4244(0.4271)0.4257(0.4279)0.4287(0.4310)WFG60.4066(0.4269)0.4098(0.4351)0.4087(0.4360)0.4082(0.4275)0.4509(0.4535)WFG70.4448(0.4528)0.4456(0.4533)0.4431(0.4549)0.4439(0.4546)0.4508(0.4539)WFG80.3721(0.4022)0.3150(0.4164)0.3052(0.4040)0.3452(0.4008)0.4204(0.4522)WFG90.4167(0.4445)0.4155(0.4359)0.4130(0.4352)0.4121(0.4381)0.4350(0.4419)

表2中給出5種算法在以上9個測試函數(shù)上的超體積指標均值及最大值的具體數(shù)值,結(jié)果顯示出對于所有的測試函數(shù),MOEA/D-AW算法求出的超體積指標的均值都大于其他四種算法求出解集的超體積指標對應的均值,表明引入線性插入搜索方向策略及均勻分布的搜索方向向量策略后,算法求解的性能極大地提高.在WFG1,WFG2,WFG6測試函數(shù)上,改進的算法性能提高的效果尤為顯著.至于改進算法MOEA/D-AW求出解集超體積指標值的最大值,除了WFG7和WFG9測試函數(shù)以外,基本上大于其他的四種算法,表明改進算法的具有求出更高質(zhì)量的解集.

6 結(jié) 論

本文首先通過分析均勻分布的權(quán)重向量,均勻分布的搜索方向向量及均勻分布的最優(yōu)解集之間的關(guān)系,提出MOEA/D中應采取均勻分布的搜索方向向量產(chǎn)生策略.進一步分析復雜Pareto前端的幾種情況,鑒于現(xiàn)實生活中的多目標測試問題的前端一般都是未知,提出了能夠獲得更為均勻的線性插入搜索方向的策略,并與原始的MOEA/D算法相結(jié)合,提出MOEA/D-AW的改進算法.通過對WFG1-WFG9多種典型的測試函數(shù)進行算法性能測試,仿真實驗結(jié)果采用GD指標,S指標分別度量解集的收斂性與多樣性.實驗證明,改進的算法能夠獲得收斂性更好,分布相對均勻的解集.最后,為驗證算法求出解集的整體質(zhì)量,采用更嚴格地,具有代表性的超體積指標度量MOEA/D-AW相比MOEA/D等四種算法的性能,結(jié)果證明改進的算法MOEA/D-AW求出解集的整體質(zhì)量有著顯著地提高.后續(xù)的研究中,將進一步研究在高維空間中如何動態(tài),并且準確的引入線性插入搜索方向,盡可能提高解集的多樣性,從而提高解集的整體質(zhì)量.