林夢嫚,王麗萍,周 歡

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

1 引 言

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

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

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

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

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

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

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

自Q.Zhang 2007年提出MOEA/D以來,很多學(xué)者已經(jīng)證明MOEA/D中預(yù)先設(shè)定的固定權(quán)重向量并不能夠保證解集均勻分布整個(gè)Pareto前端.2010年,Gu和Liu[14]根據(jù)當(dāng)前權(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前端的幾何特性對(duì)權(quán)重向量進(jìn)行調(diào)整,該算法能夠獲得收斂性和多樣性較好的解集,然而該算法要求求解的多目標(biāo)優(yōu)化問題的PF(Pareto Front,PF)為四分之一圓形或者球形.實(shí)際求解過程中,待求解問題的PF都是未知的,因此,該算法存在一定的缺陷.2013年,Wang et al[16]提出使用預(yù)處理策略調(diào)整權(quán)重向量,為初始化的個(gè)體找到距離相對(duì)較近的權(quán)重向量,為敘述的簡便,本文將該算法簡記為MOEA/D-pre(An enhanced MOEA/D using uniform directions and a pre-organization procedure,MOEA/D-pre),該算法能夠提高解集的收斂性,然而初始化的個(gè)體隨機(jī)性較大,導(dǎo)致MOEA/D算法中引入預(yù)處理策略的效果較差.隨后Qi et al[17]提出MOEA/D-AWA(MOEA/D With Adaption Weight Adjust,MOEA/D-AWA)算法,MOEA/D-AWA提出一種新的權(quán)重向量初始化技術(shù),同時(shí)根據(jù)復(fù)雜的Pareto前端自適應(yīng)調(diào)整權(quán)重向量,提高解集的均勻性.然而MOEA/D-AWA中需要維持一定數(shù)量的外部非支配解,根據(jù)這些非支配解的擁塞距離自適應(yīng)調(diào)整權(quán)重向量,這種方法增加了計(jì)算的復(fù)雜性,并消耗一定的時(shí)間.隨后,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)整解集的分布.實(shí)驗(yàn)證明,該算法在高維多目標(biāo)優(yōu)化問題中效果顯著,然而持續(xù)性的計(jì)算解與子問題的垂直距離消耗的計(jì)算資源較多,同時(shí)對(duì)于復(fù)雜的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)算法,實(shí)驗(yàn)表明該算法通過分析運(yùn)行過程中問題的難易程度,把多目標(biāo)問題的優(yōu)化分為兩個(gè)階段,合理利用計(jì)算資源,能夠有效地求解具有復(fù)雜PF的問題.然而,該算法具有兩個(gè)缺陷:其一,該算法設(shè)計(jì)的參數(shù)較多,在PF未知的情況下,算法中一系列的參數(shù)難以確定.其二,該算法不易預(yù)測種群的擁塞程度.

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

2 背景知識(shí)

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

當(dāng)決策者沒提供任何的偏好信息的時(shí)候,希望得到的結(jié)果是均勻分布在Pareto前端上.因此對(duì)于MOEA/D來講,使用相對(duì)均勻的權(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中標(biāo)識(shí)為權(quán)重向量的線條代表原始的MOEA/D預(yù)先設(shè)定的權(quán)重向量,虛線表示與預(yù)先設(shè)定的權(quán)重向量對(duì)應(yīng)的方向向量.根據(jù)對(duì)聚合函數(shù)的幾何特性分析可知,Pareto最優(yōu)點(diǎn)為方向向量與PF的交點(diǎn),如圖中的圓圈,而不是預(yù)先設(shè)定的權(quán)重向量與PF的交點(diǎn).因此,均勻分布的方向向量能盡可能地保證均勻分布的Pareto最優(yōu)解集,預(yù)先設(shè)定的均勻分布的權(quán)重向量卻并不能夠保證產(chǎn)生均勻分布的Pareto最優(yōu)解集.文獻(xiàn)[16]中也給出相關(guān)的證明.基于以上的分析,本文決定使用2.3小節(jié)中的方法生成目標(biāo)空間中的搜索的方向向量,然后根據(jù)表達(dá)式(3)將其轉(zhuǎn)換為對(duì)應(yīng)的權(quán)重向量.

(3)

其中λij即為采用2.3小節(jié)中的方法生成的方向向量的分量.表達(dá)式(3)有如下的修訂,當(dāng)λij為0時(shí),修改為λij+ε,其中ε為0.000001,其他情況,不做任何修改.采用這一策略,盡可能在初始化時(shí)產(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 具有復(fù)雜Pareto前端的多目標(biāo)問題及MOEA/D存在的缺陷分析

3.1 復(fù)雜Pareto前端的多目標(biāo)問題

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

3.2 MOEA/D存在的缺陷

4 線性插入搜索方向策略

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

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

輸入:

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

2.停止條件;

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

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

5.T:預(yù)定的鄰域大小;

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

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

Step 1.初始化:

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

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

Step 2.更新:

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

Step 2.2.修正:應(yīng)用問題特定的修正或啟發(fā)式的改進(jìn)策略作用于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代,使用線性插入搜索方向策略;具體步驟為,計(jì)算每個(gè)個(gè)體的k近鄰值,找出k近鄰最大的個(gè)體對(duì)應(yīng)的子問題記為indexMax,找出k近鄰最小的個(gè)體對(duì)應(yīng)的子問題記為indexMin.刪除indexMin對(duì)應(yīng)的個(gè)體,找到indexMax對(duì)應(yīng)的個(gè)體,計(jì)算方向向量與indexMax個(gè)體方向向量最近的兩個(gè)個(gè)體,序號(hào)記為addindex1和addindex2,假設(shè)addindex1個(gè)體對(duì)應(yīng)的k近鄰值大于addindex2個(gè)體對(duì)應(yīng)的k近鄰值,確定加入的搜索方向向量在indexMax與addindex1之間,反之為indexMax與addindex2之間.根據(jù)以上找出的兩個(gè)個(gè)體,對(duì)其方向向量求均值,線性插入一個(gè)方向向量,并轉(zhuǎn)換為權(quán)重向量,在以上的兩個(gè)個(gè)體中隨機(jī)復(fù)制某一個(gè)個(gè)體(僅復(fù)制x與f(x)值)給新增的個(gè)體.最后重新計(jì)算鄰域并更新z(示意圖如圖4所示).

圖3 WFG1的IGD指標(biāo)對(duì)比Fig.3 Index comparison of IGD of WFG1

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

圖4 WFG2的IGD指標(biāo)對(duì)比Fig.4 Index comparison of IGD of WFG2

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

5 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

5.1 算法的GD指標(biāo)、S指標(biāo)測試

為分析改進(jìn)算法相比原始算法求得解集的收斂性及多樣性,本次實(shí)驗(yàn)選擇以上給出的GD指標(biāo)和S指標(biāo)分別對(duì)算法的收斂性及多樣性進(jìn)行比較.GD指標(biāo)中,在標(biāo)準(zhǔn)的Pareto前端上采樣500個(gè)點(diǎn),所得結(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,其他的測試問題上,改進(jìn)算法求出的解集的GD均值均比原始算法求出解集的GD均值小,WFG4測試問題上最明顯.表明采用均勻搜索方向和線性插入搜索方向策略后,可以改進(jìn)算法求出解集的收斂性.原因在于,進(jìn)化過程中,根據(jù)算法求出解集的分布性,適當(dāng)調(diào)整搜索方向,進(jìn)而調(diào)整對(duì)應(yīng)的權(quán)重向量,可以有效地引導(dǎo)解集朝向真實(shí)的PF,避免部分個(gè)體陷入局部最優(yōu),提高算法的收斂性.至于WFG2和WFG8,改進(jìn)算法的效果相對(duì)略差.觀察表1中S均值對(duì)應(yīng)的兩列,可以得出,大部分的測試函數(shù),改進(jìn)的算法的S均值相比原始的MOEA/D算法求出的解集的S均值小很多,說明采用線性插入方向向量,進(jìn)化過程中根據(jù)解集的分布性,通過探測真實(shí)的PF,不斷調(diào)整搜索的方向,刪除密集區(qū)域的重復(fù)個(gè)體,稀疏區(qū)域增加個(gè)體,有利于提高算法的多樣性.以上兩組數(shù)據(jù)表明,改進(jìn)的算法可以提高求出解集的收斂性與多樣性.

5.2 算法的IGD指標(biāo)測試

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

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

圖5 WFG3的IGD指標(biāo)對(duì)比Fig.5 Index comparison of IGD of WFG3

圖6 WFG4的IGD指標(biāo)對(duì)比Fig.6 Index comparison of IGD of WFG4

圖7 WFG5的IGD指標(biāo)對(duì)比Fig.7 Index comparison of IGD of WFG5

圖8 WFG6的IGD指標(biāo)對(duì)比Fig.8 Index comparison of IGD of WFG6

圖9 WFG7的IGD指標(biāo)對(duì)比Fig.9 Index comparison of IGD of WFG7

圖10 WFG8的IGD指標(biāo)對(duì)比Fig.10 Index comparison of IGD of WFG8

5.3 算法的HV指標(biāo)測試

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

圖11 WFG9的IGD指標(biāo)對(duì)比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ù)上算法獨(dú)立運(yùn)行20次,得到的超體積指標(biāo)值對(duì)比圖.分析以上9幅圖可以得出如下幾點(diǎn)結(jié)論:

圖12 WFG1超體積指標(biāo)對(duì)比Fig.12 Comparison of WFG1 hyper volume index

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

圖13 WFG2超體積指標(biāo)對(duì)比Fig.13 Comparison of WFG2 hyper volume index

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

圖14 WFG3超體積指標(biāo)對(duì)比Fig.14 Comparison of WFG3 hyper volume index

圖15 WFG4超體積指標(biāo)對(duì)比Fig.15 Comparison of WFG4 hyper volume index

圖16 WFG5超體積指標(biāo)對(duì)比Fig.16 Comparison of WFG5 hyper volume index

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

圖17 WFG6超體積指標(biāo)對(duì)比Fig.17 Comparison of WFG6 hyper volume index

圖18 WFG7超體積指標(biāo)對(duì)比Fig.18 Comparison of WFG7 hyper volume index

圖19 WFG8超體積指標(biāo)對(duì)比Fig.19 Comparison of WFG8 hyper volume index

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

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

圖20 WFG9超體積指標(biāo)對(duì)比Fig.20 Comparison of WFG9 hyper volume index

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

6 結(jié) 論

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