譚 瑋，邱啟倉(cāng)，俞 維，王麗萍

1(浙江工業(yè)大學(xué) 管理學(xué)院，杭州 310023)2(之江實(shí)驗(yàn)室，杭州 310023)3(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)

1 引 言

解決多目標(biāo)優(yōu)化問(wèn)題的主要目的是為了實(shí)現(xiàn)目標(biāo)值的最小化.一般情況下，多目標(biāo)優(yōu)化問(wèn)題可以描述為:

minf(x)=(f1(x),f2(x),…,fm(x))Tsubjecttox∈Ω?Rn

(1)

其中Ω是決策空間，f:Ω→Θ?Rm是m維的目標(biāo)向量，x=(x1,x2,…,xn)T是決策空間中的一個(gè)n維決策向量.

多目標(biāo)優(yōu)化問(wèn)題的求解算法有多目標(biāo)進(jìn)化算法[1]、多目標(biāo)粒子群算法[2]、模擬退火算法等[3].多目標(biāo)進(jìn)化算法可以有效求解多目標(biāo)優(yōu)化問(wèn)題.近年來(lái)，國(guó)內(nèi)外學(xué)者提出了大量多目標(biāo)進(jìn)化算法，根據(jù)選擇機(jī)制，主要可分為以下3類：1)基于傳統(tǒng)Pareto支配關(guān)系，通過(guò)Pareto支配關(guān)系指導(dǎo)解集的選擇[4]；2)基于指標(biāo)函數(shù)，該類算法通過(guò)性能評(píng)價(jià)指標(biāo)來(lái)引導(dǎo)算法的搜索方向[5]；3)基于分解，通過(guò)將多目標(biāo)優(yōu)化問(wèn)題分解為若干單目標(biāo)優(yōu)化子問(wèn)題從而進(jìn)行求解[6].

自Zhang等人[7]2007年提出基于分解的多目標(biāo)進(jìn)化算法MOEA/D，基于分解的多目標(biāo)進(jìn)化算法逐漸成為眾多學(xué)者處理多目標(biāo)優(yōu)化問(wèn)題的首選算法框架，得到了廣泛應(yīng)用，并涌現(xiàn)出大量研究.在分解方法方面，Zheng等人[8]提出了一種結(jié)合加權(quán)和法和切比雪夫的分解方法，提高了算法的求解性能.在權(quán)重向量生成方面，Qi等人[9]通過(guò)分析切比雪夫分解方案下權(quán)向量與最優(yōu)解之間的幾何關(guān)系，提出了一種新的權(quán)向量初始化方法和自適應(yīng)權(quán)向量調(diào)整策略.對(duì)權(quán)重進(jìn)行周期性調(diào)整，使得子問(wèn)題的權(quán)重自適應(yīng)重新分布，從而獲得更好的解的均勻性.在算法資源分配上，Zhang等人[10]根據(jù)算法中每個(gè)子問(wèn)題的聚合函數(shù)值的提升率進(jìn)行資源分配.Lin等人[11]針對(duì)以往資源分配策略僅注重收斂性，提出了一種給個(gè)體稀疏區(qū)域分配較多計(jì)算資源的多樣性增強(qiáng)的資源分配策略IRA，使算法多樣性得到兼顧.此外，在考慮種群更新方面，Li等人[12]在2014年提出了一個(gè)穩(wěn)定匹配模型來(lái)協(xié)調(diào)MOEA/D中子問(wèn)題與解之間的相互選擇.在鄰域選擇機(jī)制方面，由于不同鄰域?qū)λ惴ㄐ阅芫哂酗@著影響，Wang等人[13]提出一種考慮全局替換的MOEA/D-GR算法，允許新解在全局范圍內(nèi)替換鄰域解，保證每個(gè)解都對(duì)應(yīng)其最合適的子問(wèn)題，然而該策略沒(méi)有限制新解替換解的個(gè)數(shù)，當(dāng)替換鄰域較大時(shí)可能導(dǎo)致解集多樣性的缺失.Yuan等人[14]提出基于距離更新的算法，利用解到子問(wèn)題的垂直距離維持目標(biāo)空間解集的均勻分布.

根據(jù)上述研究，可知在傳統(tǒng)MOEA/D算法中，鄰域大小對(duì)算法的性能會(huì)產(chǎn)生一定影響.對(duì)于不同目標(biāo)函數(shù)，每個(gè)子問(wèn)題的計(jì)算復(fù)雜度不盡相同.MOEA/D算法中采用固定鄰域?yàn)樽訂?wèn)題分配計(jì)算資源，資源分配不夠合理.本文基于算法總體流程的研究，進(jìn)一步分析了固定鄰域存在的缺陷，進(jìn)而提出了一種新的改進(jìn)方法，針對(duì)選擇鄰域和替換鄰域大小分別進(jìn)行適應(yīng)性調(diào)整，提出了改進(jìn)算法MOEA/D-INS.旨在為不同子問(wèn)題合理分配適當(dāng)大小的鄰域，平衡算法的收斂性和多樣性.

2 背景知識(shí)

2.1 分解方法

在MOEA/D框架[15,16]中，已研究出許多分解方法.其中常用的分解方法有加權(quán)和法、切比雪夫法、基于懲罰邊界交叉法.本文采用的是改進(jìn)切比雪夫分解方法，其公式如下:

(2)

式中，Z*為理想點(diǎn)，λ=(λ1,λ2,…,λk)為當(dāng)前子問(wèn)題在目標(biāo)空間中均勻分布的權(quán)重向量，若λi=0，則設(shè)置λi=10-6.

改進(jìn)切比雪夫分解方法相比原始切比雪夫分解方法主要有以下兩個(gè)優(yōu)勢(shì)[17]：1)均勻分布的權(quán)重向量能在目標(biāo)空間中產(chǎn)生均勻分布的搜索方向；2)每個(gè)權(quán)重向量均對(duì)應(yīng)位于Pareto前沿上的唯一解.這兩個(gè)優(yōu)勢(shì)對(duì)算法多樣性有所提升.

2.2 固定鄰域缺陷

MOEA/D算法中，對(duì)不同的子問(wèn)題設(shè)置固定鄰域，而后通過(guò)交叉變異產(chǎn)生新解，用于替換鄰域內(nèi)舊解.在生成新解和替換解過(guò)程中都采用固定鄰域，忽視了進(jìn)化過(guò)程中隨著解集的變化，生成新解會(huì)出現(xiàn)資源分配不均的問(wèn)題，以及雜交過(guò)程生成的新解與子問(wèn)題不協(xié)調(diào)的問(wèn)題.因此采用固定的選擇鄰域和替換鄰域不利于提升解集的多樣性和收斂性，若不考慮解集在進(jìn)化過(guò)程中迭代更新，容易導(dǎo)致MOEA/D算法陷入局部最優(yōu)，影響解的多樣性和收斂性.

圖1 MOEA/D固定鄰域分析示意圖Fig.1 MOEA/D fixed neighborhood analysis diagram

以二維ZDT1測(cè)試函數(shù)為例進(jìn)行說(shuō)明，取固定鄰域20，迭代300次后，其MOEA/D算法結(jié)果如圖1所示，小圓圈表示Pareto最優(yōu)解的位置.可以看出，固定鄰域下的進(jìn)化結(jié)果，一般在中間區(qū)域最優(yōu)解較多，邊緣區(qū)域最優(yōu)解較稀少.若只采用固定鄰域，則使邊緣區(qū)域最優(yōu)解多樣性下降，導(dǎo)致Pareto最優(yōu)解不能均勻分布在PF上，不利于提升算法性能.

3 改進(jìn)算法MOEA/D-INS

3.1 算法改進(jìn)策略描述

MOEA/D算法進(jìn)化過(guò)程中用到兩個(gè)不同的鄰域：選擇鄰域和替換鄰域[18].選擇鄰域用來(lái)進(jìn)行父代解的選擇，替換鄰域用來(lái)確定哪些舊解可能會(huì)被新解替換.選擇鄰域的大小會(huì)影響解在繁殖操作時(shí)選擇解的個(gè)數(shù)，選擇鄰域越大，可選擇參與繁殖的解集范圍越大，產(chǎn)生新解多樣性就大，收斂性較弱.替換鄰域的大小會(huì)影響解在替換操作時(shí)替換解的個(gè)數(shù)，替換鄰域越大，可替換的解個(gè)數(shù)就越多，就會(huì)產(chǎn)生較多相同的解副本，多樣性較弱.

本文在對(duì)鄰域分析過(guò)程中考慮了解所在不同區(qū)域?qū)M(jìn)化的影響.通過(guò)表示子問(wèn)題距離中心區(qū)域的偏離程度，具體公式如下：

(3)

λmid={λp|p=argminwi}

(4)

λbou={λp|p=argmaxwi}

(5)

其中子問(wèn)題λ的最大值減去最小值來(lái)表示偏離程度wi，公式(4)中的λmid表示該權(quán)重向量位于種群中間位置，結(jié)合公式(3)此時(shí)wi取得最小值；公式(5)中的λbou表示該權(quán)重向量位于種群邊界位置，此時(shí)wi取得最大值.采用此方法獲取解所在區(qū)域信息與采用角度或距離公式計(jì)算方式相比，可減小算法計(jì)算量從而加快計(jì)算速度.

由圖1可知采用固定鄰域情況下，邊界區(qū)域最優(yōu)解稀疏，解多集中在中間區(qū)域.而在算法進(jìn)化過(guò)程中，初期應(yīng)注重種群的多樣性，避免陷入局部最優(yōu).中后期，應(yīng)注重算法的收斂性，使種群更好地收斂到Pareto前沿.

因此從均衡算法的多樣性、收斂性及節(jié)約計(jì)算資源的角度考慮，針對(duì)選擇鄰域，邊界區(qū)域子問(wèn)題鄰域應(yīng)該增大，擴(kuò)大子問(wèn)題的搜索方向范圍從而找到更多最優(yōu)解，提高解集的多樣性，中間區(qū)域反之適當(dāng)減小以節(jié)約計(jì)算資源，同時(shí)結(jié)合算法的進(jìn)化初期選擇鄰域Tm值應(yīng)較大以維持種群的多樣性，隨著進(jìn)化代數(shù)的增加，Tm逐漸減小以提升收斂速度，提出選擇鄰域公式(6)，其效果如圖2(a)所示，在算法初期，選擇鄰域較大，提升解集多樣性，隨著進(jìn)化代數(shù)的增加，中間區(qū)域鄰域變小，邊界區(qū)域鄰域較大.針對(duì)替換鄰域，中心區(qū)域應(yīng)適當(dāng)增大對(duì)應(yīng)子問(wèn)題的鄰域，加快算法的收斂更快的找到最優(yōu)解.邊界區(qū)域反之減小以保留更多邊界解，保證算法的多樣性.同時(shí)結(jié)合算法的進(jìn)化代數(shù)，初期替換鄰域Tr值應(yīng)較小以維持種群的多樣性，隨著進(jìn)化代數(shù)的增加，Tr逐漸增大以提升收斂速度，提出替換鄰域公式(7)，其效果如圖2(a)所示，在算法初期，替換領(lǐng)域較大，提升算法收斂性，隨著進(jìn)化代數(shù)的增加，中間區(qū)域鄰域較大，邊界區(qū)域鄰域較小.

(6)

(7)

T為一個(gè)最小鄰域，防止鄰域過(guò)小導(dǎo)致個(gè)體過(guò)少影響進(jìn)化，Tmax表示設(shè)計(jì)的最大的鄰域值，gen表示進(jìn)化代數(shù)，Maxgen表示對(duì)應(yīng)問(wèn)題進(jìn)化的最大代數(shù)，通過(guò)wi來(lái)表示子問(wèn)題相對(duì)中心區(qū)域的偏離程度.

圖2 鄰域分配示意圖Fig.2 Neighborhood allocation diagram

3.2 改進(jìn)算法流程

輸入:種群規(guī)模N；均勻分布的權(quán)重向量：W←{λ1,λ2,…,λN}；鄰域大小T，變異概率Pm，交叉概率Pc；最大進(jìn)化代數(shù)Maxgen

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

Step 1.初始化:

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

Step 1.2.初始化種群P←{x1,x2,…,xN};

Step 1.3.初始化理想點(diǎn)Z*←{Z1,Z2,…,ZK}T;

Step 2.更新:Fori=1toN，do

Step 2.1.根據(jù)公式(6)在每代更新之前計(jì)算每代的選擇鄰域Bm(i),根據(jù)公式(7)計(jì)算替換鄰域Tr值，計(jì)算Br(i)；

Step 2.2.繁殖:從Bm(i)中隨機(jī)選擇兩個(gè)鄰居xk,xl,y←GenticOperators(xk,xl)進(jìn)行交叉變異生成新解；

Step 2.3.修正：應(yīng)用問(wèn)題特定的修正或啟發(fā)式的改進(jìn)策略作用于y生成y′；

Step 2.4.更新Z*:若Zj

Step 2.5.更新解：采用更新函數(shù)UpdateNeighborINS(Z*,Br(i),y,P,W)

Step 3.停止判斷：若滿足停止條件，則輸出PF，否則返回Step 2繼續(xù)執(zhí)行.

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

為驗(yàn)證本文提出算法的性能，本文選取的測(cè)試函數(shù)為二維ZDT[19]測(cè)試函數(shù)ZDT1-ZDT4、ZDT6和三-五維DTLZ1-4[20]系列測(cè)試函數(shù).將MOEA/D-INS與MOEA/D、MOEA/D-GR、MOEA/D-DRA和MOEA/D-DU這4種經(jīng)典算法，進(jìn)行仿真實(shí)驗(yàn)比較.仿真實(shí)驗(yàn)在IntelCorei5-7200UCPU-@2.50GHz的環(huán)境下進(jìn)行.

4.1 參數(shù)設(shè)置

種群大?。憾S測(cè)試問(wèn)題設(shè)置為100，三維設(shè)置為105，四維設(shè)置為120，五維設(shè)置為126.交叉變異算子：變異概率Pm=1/n，其中n為測(cè)試函數(shù)的決策變量個(gè)數(shù)，交叉概率Pc=0.99，選擇鄰域的概率δ=0.9.終止條件：ZDT系列測(cè)試函數(shù)的最大迭代次數(shù)設(shè)置為300代，DTLZ2、DTLZ4最大進(jìn)化代數(shù)為500，三維DTLZ1、DTLZ3測(cè)試函數(shù)的最大進(jìn)化代數(shù)為1000，四維DTLZ1、DTLZ3測(cè)試函數(shù)的最大進(jìn)化代數(shù)為2000，五維DTLZ1、DTLZ3測(cè)試函數(shù)的最大進(jìn)化代數(shù)為3000.算法在每個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行20次，以降低算法隨機(jī)性對(duì)實(shí)驗(yàn)結(jié)果的影響.

4.2 性能評(píng)價(jià)指標(biāo)

本文采用如下算法性能評(píng)價(jià)指標(biāo)，進(jìn)行算法性能對(duì)比：

IGD(Inverted Generational Distance，IGD)[21]是一種評(píng)價(jià)解集整體質(zhì)量的指標(biāo).通過(guò)測(cè)量理想Pareto前沿面PFknown上的子集P*和近似Pareto前沿面PFture上的子集P的趨近程度，PFknown與PFture越接近，算法求得的IGD值就越小，解集整體性能也就越優(yōu).

超體積指標(biāo)(hyper volume，HV)[22]是一種能夠同時(shí)衡量算法收斂性和多樣性的綜合性指標(biāo)，表示非支配解集覆蓋的目標(biāo)空間區(qū)域大小，算法求得的HV值越大，解集質(zhì)量也就越高.

4.3 改進(jìn)算法在ZDT系列測(cè)試函數(shù)性能對(duì)比分析

與傳統(tǒng)使用固定鄰域的MOEA/D算法在二維ZDT系列測(cè)試函數(shù)上進(jìn)行對(duì)比實(shí)驗(yàn)，檢驗(yàn)文中提出的MOEA/D-INS算法性能.表中黑色粗體數(shù)據(jù)表示對(duì)比實(shí)驗(yàn)結(jié)果中最優(yōu)值.

表1為MOEA/D-INS與MOEA/D在IGD指標(biāo)上的實(shí)驗(yàn)結(jié)果.由表1可知，在ZDT1、ZDT2、ZDT3、ZDT4這4個(gè)測(cè)試函數(shù)上，MOEA/D-INS的IGD指標(biāo)優(yōu)于MOEA/D，在ZDT6測(cè)試函數(shù)上，MOEA/D-INS所求解集的IGD指標(biāo)略劣于MOEA/D.由此可以看出在以上測(cè)試函數(shù)中，文中提出的MOEA/D-INS對(duì)算法整體性能的提升具有明顯的效果.

圖3為兩種算法在ZDT系列測(cè)試函數(shù)上的前沿效果圖.采用黑色實(shí)線表示對(duì)應(yīng)問(wèn)題中真實(shí)Pareto前沿，方形和圓圈分別對(duì)應(yīng)MOEA/D和MOEA/D-INS算法的Pareto最優(yōu)解值.從圖3改進(jìn)前后算法的Pareto前沿對(duì)比圖可看出，MOEA/D-INS算法求出的解集比MOEA/D求出的解集更貼近真實(shí)Pareto前沿面，且解集分布更均勻，在ZDT4測(cè)試問(wèn)題上尤其明顯，而MOEA/D的解集對(duì)應(yīng)真實(shí)Pareto前沿面距離較遠(yuǎn)，原因在于進(jìn)化的迭代次數(shù)不夠，未能很好的收斂.

表1 改進(jìn)前后算法在ZDT測(cè)試函數(shù)上指標(biāo)對(duì)比Table 1 Comparison of indicators on the ZDT test function before and after improvement

圖3 改進(jìn)前后算法在ZDT測(cè)試函數(shù)上Pareto前沿對(duì)比圖Fig.3 Comparison chart of Pareto front edge on ZDT test function before and after improvement

在ZDT1、ZDT2、ZDT3測(cè)試問(wèn)題上MOEA/D-INS均優(yōu)于MOEA/D，ZDT6測(cè)試問(wèn)題上，MOEA/D-INS與MOEA/D算法性能總體相當(dāng).可以看出，改進(jìn)算法MOEA/D-INS求解的整體質(zhì)量比MOEA/D更高.

4.4 改進(jìn)算法在DTLZ系列測(cè)試函數(shù)性能對(duì)比分析

為更深入驗(yàn)證本文提出算法的性能，對(duì)DTLZ1-4測(cè)試問(wèn)題進(jìn)行仿真測(cè)試，目標(biāo)維度分別為三、四、五維，并使用IGD和HV指標(biāo)對(duì)算法求出的解集進(jìn)行分析.選取對(duì)比算法MOEA/D、MOEA/D-GR、MOEA/D-DRA和MOEA/-DU.

表2為各算法求得的IGD指標(biāo)仿真實(shí)驗(yàn)結(jié)果，其中粗體表示對(duì)應(yīng)算法所得解集整體質(zhì)量?jī)?yōu)于其它四種算法.由表2可知，在實(shí)驗(yàn)結(jié)果中，在三維DTLZ1和五維DTLZ1中MOEA/D算法的均值雖然不是最優(yōu)，但具有最好的穩(wěn)定性，在四維DTLZ2中MOEA/D也具有最好的穩(wěn)定性.在五維DTLZ2中MOEA/D-DU求解的性能最穩(wěn)定，在五維DTLZ4中MOEA/D-DU算法IGD均值和MOEA/D-INS相同最優(yōu)，原因可能在于MOEA/D-DU算法在進(jìn)化更新過(guò)程中，考慮新解到權(quán)重向量的距離，避免過(guò)分強(qiáng)調(diào)聚合函數(shù)值而使得解偏離對(duì)應(yīng)權(quán)重向量，這種基于距離的更新策略能較好的維持解集的多樣性.從仿真實(shí)驗(yàn)結(jié)果整體上看MOEA/D-INS所得IGD指標(biāo)的均值最小，表明算法整體性能最優(yōu).原因在于，相比MOEA/D、MOEA/D-GR、MOEA/D-DRA和MOEA/-DU算法，MOEA/D-INS算法為不同位置的子問(wèn)題分配不同的選擇鄰域和替換鄰域，并根據(jù)算法進(jìn)化狀態(tài)而動(dòng)態(tài)調(diào)整鄰域，從而使算法求得解集的整體質(zhì)量更高.

圖4是IGD指標(biāo)走勢(shì)圖，圖中三角形、星形、圓形、矩形、菱形分別對(duì)應(yīng)MOEA/D-INS、MOEA/D、MOEA/D-DRA、MOEA/D-GR和MOEA/D-DU 5種算法.在DTLZ1和DTLZ3測(cè)試函數(shù)上MOEA/D-DRA算法在進(jìn)化的前期曲線下降速度最快，因?yàn)樵撍惴◤拿總€(gè)子問(wèn)題的聚合函數(shù)值相對(duì)提升率來(lái)分配計(jì)算資源，提升率高的子問(wèn)題接下來(lái)也更容易被選擇參與進(jìn)化，因此在算法進(jìn)化初期具有較好的收斂性.MOEA/D-INS算法對(duì)應(yīng)的IGD值在算法進(jìn)化前期也有著較快的收斂速度，在進(jìn)化后期數(shù)值更是逐漸減小至小于其它4種對(duì)比算法.在DTLZ2和DTLZ4測(cè)試函數(shù)上，MOEA/D-INS算法對(duì)應(yīng)的IGD數(shù)值在進(jìn)化中始終小于其它4種對(duì)比算法，且隨著進(jìn)化代數(shù)的增加變化趨勢(shì)穩(wěn)定平緩，可見(jiàn)MOEA/D-INS針對(duì)這類測(cè)試函數(shù)具有較好的表現(xiàn).結(jié)合表2,圖4通過(guò)5種算法在DTLZ系列測(cè)試函數(shù)上的表現(xiàn)，發(fā)現(xiàn)MOEA/D-INS具有較好的整體性能.這主要是因?yàn)镸OEA/D-INS將選擇鄰域和替換鄰域分開(kāi)考慮，分別提出不同的鄰域規(guī)模，在確保算法進(jìn)化收斂性的同時(shí)，也有助于提高算法的多樣性，因此較好提升算法整體性能.對(duì)于具有復(fù)雜性質(zhì)的測(cè)試問(wèn)題，MOEA/D-INS仍具有較大提升空間.

表2 5種算法在三-五維DTLZ測(cè)試函數(shù)的IGD指標(biāo)測(cè)試結(jié)果Table 2 IGD value test results of five algorithms in 3-5 D DTLZ test function

圖4 5種算法在三-五維DTLZ測(cè)試函數(shù)的IGD指標(biāo)走勢(shì)圖Fig.4 Change of IGD value on DTLZ3-5 D by five different algorithms

表3為各算法求得的HV指標(biāo)均值和標(biāo)準(zhǔn)差.從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，MOEA/D-DRA在五維DTLZ3測(cè)試函數(shù)上表現(xiàn)優(yōu)于其它算法，MOEA/D-DU、MOEA/D-INS次之.MOEA/D-DU在三、四維DTLZ3及五維DTLZ4測(cè)試函數(shù)上的表現(xiàn)最優(yōu)，MOEA/D-INS、MOEA/D-DRA次之.MOEA/D-GR在五維DTLZ1測(cè)試函數(shù)上性能最優(yōu).而在其余測(cè)試函數(shù)上，MOEA/D-INS算法求得指標(biāo)HV值優(yōu)于其它算法.已知，測(cè)試函數(shù)DTLZ1的最優(yōu)解前沿是一個(gè)線性超平面，較難收斂到全局的復(fù)雜多模態(tài)問(wèn)題.DTLZ2是一個(gè)相對(duì)簡(jiǎn)單的測(cè)試問(wèn)題，通常用于研究算法在大量目標(biāo)中性能提升的能力.DTLZ3是一個(gè)多峰問(wèn)題，在解集收斂到Pareto前沿之前，易陷入局部最優(yōu).DTLZ4是簡(jiǎn)單連續(xù)的單模態(tài)測(cè)試函數(shù)，研究算法保持解集的分布性的能力.MOEA/D-INS在求解DTLZ2、DTLZ4測(cè)試函數(shù)上表現(xiàn)嚴(yán)格優(yōu)于其它算法，因此在求解算法分布性上有著較強(qiáng)的優(yōu)勢(shì)，能夠得到收斂性好，分布廣的解集.

表3 5種算法在三-五維DTLZ測(cè)試函數(shù)的HV指標(biāo)測(cè)試結(jié)果Table 3 HV indicator test results of five algorithms in 3-5D DTLZ test function

圖5 5種算法在三-五維DTLZ1-4測(cè)試函數(shù)上的HV盒圖Fig.5 HV box diagram of the five algorithms on the 3-5D DTLZ1-4 test function

由圖5可以看出，在四維DTLZ1上，MOEA/D-GR雖然有最大的HV均值，但是從盒子的長(zhǎng)度可以看出算法的穩(wěn)定性較差，這可能是因?yàn)镸OEA/D-GR注重收斂性，而DTLZ1是一個(gè)多峰的問(wèn)題，在進(jìn)化過(guò)程中新解替換鄰域內(nèi)多個(gè)舊解，使得算法陷入局部最優(yōu)，性能下降.在四維DTLZ3，五維DTLZ3上，MOEA/D-DRA的HV均值最大，但是算法性能不夠穩(wěn)定.MOEA/D-INS相較于其它4種對(duì)比算法所對(duì)應(yīng)的中位數(shù)位置即圖中盒子中間的橫線明顯高很多，并且從圖5中可以看出該算法的盒子長(zhǎng)度是最短即算法對(duì)應(yīng)的HV指標(biāo)四分位距離是最小的，即該算法的HV值的最大值和最小值相比相差不多指標(biāo)更為集中.表明了MOEA/D-INS相比其它4種對(duì)比算法求出的解集整體質(zhì)量更高，并且有更好的穩(wěn)定性即算法求解的性能更優(yōu).

綜上結(jié)合表2、表3、圖4、圖5通過(guò)5種算法在DTLZ系列測(cè)試函數(shù)上的表現(xiàn)，證明MOEA/D-INS具有較好的整體性能.這主要是因?yàn)镸OEA/D-INS將選擇鄰域和替換鄰域分開(kāi)考慮，提出不同的鄰域規(guī)模，在確保算法進(jìn)化過(guò)程中收斂性的同時(shí)，也有助于提高算法多樣性，因此較好提升算法的整體性能.對(duì)于簡(jiǎn)單連續(xù)的測(cè)試問(wèn)題，性能提升顯著，對(duì)于一些具有復(fù)雜性質(zhì)的測(cè)試問(wèn)題，仍具有較大提升空間.

5 總 結(jié)

本文從MOEA/D選擇鄰域和替換鄰域的角度分別進(jìn)行研究，針對(duì)不同區(qū)域子問(wèn)題分配不同鄰域的策略，并將其融入到多目標(biāo)進(jìn)化算法中提出MOEA/D-INS算法.該算法首先對(duì)不同區(qū)域子問(wèn)題分配不同的選擇鄰域和替換鄰域，再隨著進(jìn)化代數(shù)的迭代，動(dòng)態(tài)調(diào)整選擇鄰域和替換鄰域的大小，合理分配計(jì)算資源，提高算法的求解有效性.算法仿真實(shí)驗(yàn)結(jié)果表明，MOEA/D-INS與其他算法相比能更加有效的利用算法資源，在保證解集收斂性的情況下，提高解集分布均勻性，求解出整體質(zhì)量更高的解集，有效平衡了算法多樣性與收斂性之間的不平衡.在后續(xù)研究中，將關(guān)注高維多目標(biāo)優(yōu)化問(wèn)題和動(dòng)態(tài)多目標(biāo)優(yōu)化問(wèn)題，并將其應(yīng)用在車輛路徑規(guī)化、物流配送中心選址等實(shí)際應(yīng)用中.