龐 銳，高興寶

(陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710119)

0 引言

在許多實際問題中，往往需要同時優(yōu)化多個相互沖突的目標(biāo)函數(shù)，即多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problems，MOPs)。在MOPs中，一個目標(biāo)的優(yōu)化往往以另一些目標(biāo)的劣化為代價，所以其解集必為一組相互折衷的Pareto最優(yōu)解。由于MOPs的復(fù)雜性，往往難以使用傳統(tǒng)優(yōu)化算法求解。不同于傳統(tǒng)方法，進化算法(Evolutionary Algorithm，EA)是受自然界物種進化的啟發(fā)而形成的一種隨機優(yōu)化算法，它采用基于種群的遺傳進化產(chǎn)生后代個體，并通過優(yōu)勝劣汰的自然選擇進化種群。因此它具有更高的尋優(yōu)效率、魯棒性強、便于操作且為求解復(fù)雜優(yōu)化及多目標(biāo)優(yōu)化問題提供了新途徑。

上世紀(jì)末以來，許多學(xué)者通過模擬不同物種的行為提出了多種EA，如粒子群算法(Particle Swarm Optimization，PSO)[1]、蟻群算法(Ant Colony Optimization，ACO)[2]、人工蜂群算法(Artificial Bee Colony，ABC)[3]、差分進化算法(Differential Evolution，DE)[4]、免疫算法(Immune Algorithms，IA)[5]和螢火蟲算法(Firefly Algorithms，F(xiàn)A)[6]等。這些算法為解決復(fù)雜優(yōu)化問題提供了新思路并被廣泛用于求解調(diào)度問題、組合優(yōu)化和存貨控制等實際問題[7]。特別地，作為一種模擬鳥群覓食行為的自然模型，PSO由于操作簡單、收斂速度快，已被廣泛應(yīng)用于求解單目標(biāo)優(yōu)化問題，且對MOPs也有顯著優(yōu)勢[8-18]，因此基于PSO的多目標(biāo)EA已成為優(yōu)化領(lǐng)域的一個研究熱點[19]。

近年來，研究者們相繼提出了各種多目標(biāo)粒子群優(yōu)化算法(Multi-objective Particle Swarm Optimization，MPSO)。特別地，文獻[8]引入Pareto支配概念確定PSO中粒子的個體最優(yōu)和全局最優(yōu)位置，首次提出了多目標(biāo)粒子群優(yōu)化算法(MOPSO)?；贛OPSO，文獻[9]設(shè)計了一種新的變異算子。該算子在迭代初期讓所有的粒子均參與變異，而隨著迭代逐漸減小參與變異的粒子數(shù)，有效地增強了PSO的探索能力。為避免“群爆炸”，文獻[10]提出了一種基于速度約束的多目標(biāo)粒子群算法(SMPSO)。在進化過程中，該算法對所有粒子的速度加以限制，以防止粒子由于速度過快而集中涌向搜索邊界。文獻[11]將PSO與NSGA-Ⅱ[20]相結(jié)合，提出了非劣排序多目標(biāo)粒子群優(yōu)化算法(NSPSO)?；诜侵潢P(guān)系，文獻[12]提出了一種求解MOPs的多目標(biāo)綜合學(xué)習(xí)粒子群算法(MOCLPSO)。由于種群中個體的適應(yīng)度依賴于Pareto支配關(guān)系，上述算法可加快收斂速度，但仍需要設(shè)計相應(yīng)的多樣性保留機制來維持解集的多樣性和分布性，且收斂性和解的分布均勻性之間的平衡仍有待加強。

MOEA/D是典型的分解算法，它將MOPs分解成若干個標(biāo)量優(yōu)化子問題進行求解[21]。受該思想的啟發(fā)，文獻[13]用PSO代替MOEA/D中的交叉算子，并對粒子的個體最優(yōu)和全局最優(yōu)位置進行更新，提出了一種基于分解的MOPSO/D算法。文獻[14]引入一種重新初始化策略來維持種群的多樣性，且從當(dāng)前種群中選擇粒子的個體最優(yōu)和全局最優(yōu)位置以節(jié)約存儲資源，提出了dMOPSO算法。文獻[15]提出一種基于目標(biāo)空間分解的MPSO/D算法。該算法基于一組均勻分布的方向向量將目標(biāo)空間分解成若干個子區(qū)域，且在每一子區(qū)域中僅保留一個最優(yōu)解以保證所獲解分布的均勻性。然而在每次迭代中，由于每一子區(qū)域僅保留一個解，因此這種分解方法容易造成部分優(yōu)質(zhì)解性能的喪失，難以處理復(fù)雜MOPs，且利用擁擠距離作為個體適應(yīng)度的評價指標(biāo)，計算復(fù)雜、收斂速度慢。上述基于分解的MPSO，雖然對部分MOPs有效，且比基于Pareto支配的MPSO，降低了計算復(fù)雜性，但在處理具有不連續(xù)、退化或多峰的復(fù)雜Pareto前沿面問題時，很難找到可均勻覆蓋整個Pareto前沿面的解集。

此外，文獻[16]用分解方法簡化MOPs，并用非支配關(guān)系保證算法的收斂性，提出了D2MOPSO。文獻[17]設(shè)計了一種基于兩個局部最優(yōu)解的多目標(biāo)粒子群算法(2LB-MOPSO)。該算法從外部文檔的非支配精英解中選取粒子的個體最優(yōu)和全局最優(yōu)位置，提高了搜索效率。結(jié)合PSO與DE，文獻[18]提出了一種自適應(yīng)的混合進化算法(HMOEA-AMP)。該算法用PSO更新進化種群，DE更新外部文檔，但其計算復(fù)雜性高且收斂速度有待提升。

由以上分析，基于分解的更新策略更有利于維持種群多樣性和解的分布均勻性，而基于Pareto支配的策略可以加快種群的收斂速度，提高算法的搜索效率。因此本文結(jié)合分解策略和Pareto支配策略，提出一種基于分解的改進自適應(yīng)多目標(biāo)粒子群優(yōu)化算法(An Improved Self-adaptive Multi-objective Particle Swarm Optimization based on Decomposition，ISMPSO/D)。首先，在分解方法確保進化種群多樣性的前提下，設(shè)計了新的適應(yīng)度評價方法以自適應(yīng)地調(diào)整每個父代個體的適應(yīng)度值，讓適應(yīng)度值更高的個體盡可能多地產(chǎn)生后代，并將在競爭中獲勝的優(yōu)質(zhì)后代解添加到父代候選解集中，增強了算法的尋優(yōu)質(zhì)量，提高了算法的收斂性；其次，在更新粒子時，從當(dāng)前粒子的鄰居或鄰居外隨機選擇個體最優(yōu)和全局最優(yōu)位置，并對后代解進行變異，增強了種群多樣性，避免了算法陷入局部最優(yōu)；最后，引入外部文檔作為候選的輸出種群，并采用擁擠距離維持其多樣性，從而充分結(jié)合了分解方法和Pareto支配的優(yōu)勢，增強了算法處理復(fù)雜問題的能力。通過12個多目標(biāo)測試函數(shù)的仿真實驗，并與5種多目標(biāo)優(yōu)化算法的比較，說明了所提ISMPSO/D算法的有效性。

1 有關(guān)算法簡介

1.1 多目標(biāo)優(yōu)化問題

本文研究多目標(biāo)優(yōu)化問題(1)：

minF(x)=[f1(x),f2(x),…,fM(x)]T
s.t.x∈X

(1)

其中,x=(x1,x2,…,xn)T是n維決策向量，X?Rn是決策空間，F(xiàn)是M維目標(biāo)向量，fi(x)為n元實值函數(shù)。

下面給出多目標(biāo)優(yōu)化中的幾個重要定義[22]。

定義1Pareto支配。設(shè)u，v是多目標(biāo)優(yōu)化問題(1)的兩個可行解，若?i∈{1,2,…,M},fi(u)≤fi(v)∧?j∈{1,2,…,M}使fj(u)

定義2Pareto最優(yōu)解。u為Pareto最優(yōu)解(或非支配解)當(dāng)且僅當(dāng)?v∈X:vu。

定義3Pareto最優(yōu)解集。稱X中所有Pareto最優(yōu)解構(gòu)成的集合為Pareto最優(yōu)解集，記為PS，即PS={u|?v∈X:vu}。

定義4Pareto前沿面。稱PS中所有Pareto最優(yōu)解的目標(biāo)函數(shù)值所構(gòu)成的曲線(或曲面)為Pareto前沿面，記為PF，即PF={F(u)=[f1(u),f2(u),…,fM(u)]T|u∈PS}。

1.2 標(biāo)準(zhǔn)的粒子群算法

PSO是Kennedy等提出的一種簡單有效的微粒群智能優(yōu)化算法[1]。在PSO中，每個粒子代表搜索空間中的一個可能解，種群即為問題潛在解的集合。設(shè)種群中第i個粒子的速度向量為vi=(vi,1,vi,2,…,vi,n)，位置向量xi=(xi,1,xi,2,…,xi,n)(i=1,2,…,N，N為種群中的粒子個數(shù))，則其速度和位置按方式(2)-(3)進行更新：

(2)

(3)

不同于其它EA算法，PSO的形式簡潔、操作方便、收斂速度快并且不需要過多的參數(shù)調(diào)整，因此更適合求解MOPs。但其快速的收斂會使種群多樣性變差，容易導(dǎo)致算法陷入局部最優(yōu)和出現(xiàn)早熟收斂。

2 提出的算法

為提高粒子群算法的搜索效率及克服分解方法處理復(fù)雜多目標(biāo)問題的缺陷，本文提出一種改進的ISMPSO/D算法。首先，在進化種群中采用基于目標(biāo)空間分解的更新策略，在每個子區(qū)域中保留一個最優(yōu)解來維持解集的分布均勻性和多樣性。同時，為更好地評價個體性能，用個體產(chǎn)生后代解的優(yōu)劣設(shè)計了一種新的適應(yīng)度評價方法，且后代解產(chǎn)生后，在新老解之間執(zhí)行競爭操作，根據(jù)競爭結(jié)果自適應(yīng)地調(diào)整其父代個體的適應(yīng)度值，并把在競爭中獲勝的優(yōu)質(zhì)后代解添加到父代候選解集中，提高了算法的搜索效率。其次，在粒子更新時，從當(dāng)前粒子的鄰居或鄰居外隨機選擇個體最優(yōu)和全局最優(yōu)位置，增強種群多樣性，且對產(chǎn)生的新解進行變異，避免算法陷入局部最優(yōu)。最后，引入外部文檔A作為候選輸出解集，并基于Pareto支配和擁擠距離更新和維護A，且在迭代完成后，采用基于逆世代距離(Inverted Generational Distance，IGD)[23]的種群輸出策略，輸出具有最優(yōu)IGD值的POP(t)或A作為最優(yōu)解集。

2.1 初始群體的產(chǎn)生

為盡可能保證初始群體的隨機性和多樣性，本文將采用如下分解方法產(chǎn)生初始群體POP(0)。首先，隨機產(chǎn)生N個個體x1,x2,…,xN組成POP和一組均勻分布的方向向量λ1,λ2,…,λN，并利用MOEA/D[21]的方法，確定每個向量的T個鄰居(T為整數(shù))。其次，基于這組方向向量，將目標(biāo)空間分解成N個子區(qū)域，且使每個子區(qū)域中僅保留與對應(yīng)方向向量最為接近的非支配個體。記分類之后所有子區(qū)域中個體的集合為POP(0)，具體操作如下。

算法1初始群體的產(chǎn)生

1)隨機產(chǎn)生POP={x1,x2,…,xN}和一組均勻分布的方向向量λ1,λ2,…,λN；

2)為每個方向向量找到離它歐式距離最近的T個向量，并把這T個向量作為該向量的鄰居；

3)計算POP中個體xi的目標(biāo)值F(xi)，(i=1,2,…,N)確定參考點Z=(Z1,Z2,…,ZM)，其中

Zj=min{fj(x)|x∈POP},j=1,2,…,M

(4)

4)對每一個體xi(i=1,2,…,N)計算F(xi)-Z與λk(k=1,2,…,N)之間的夾角Δ(F(xi)-Z,λk)，并按式(5)將POP分解為sub1,sub2,…,subN：

(5)

即為xi找到與F(xi)-Z夾角最小的方向向量；

5)當(dāng)subi=?時，隨機產(chǎn)生一個體放入subi中；當(dāng)subi中有多個個體時，根據(jù)Pareto支配關(guān)系找到其中的非支配解；若有多個非支配解，則保留與λi夾角最小的個體，并刪除其它個體，即

(6)

2.2 種群的進化

2.2.1 適應(yīng)度評價與個體競爭

在EA中，個體適應(yīng)度值是反映個體性能優(yōu)劣的重要指標(biāo)。在進化過程中將根據(jù)適應(yīng)度值的大小對種群中的個體進行優(yōu)勝劣汰，適應(yīng)度值大的優(yōu)質(zhì)個體將有機會繁衍更多的后代，而適應(yīng)度值小的個體將會逐漸被淘汰。適應(yīng)度評價方法對個體的影響類似于自然界中“物競天擇，適者生存”的自然準(zhǔn)則，因此設(shè)計合理的適應(yīng)度評價方法對EA性能有至關(guān)重要的影響。盡管已有的適應(yīng)度評價方法，如目標(biāo)函數(shù)值的大小和個體對目標(biāo)函數(shù)的影響程度[7]、非支配排序[20]、Tchebycheff方法[21]和擁擠度距離[15]等，能將個體的適應(yīng)度值與目標(biāo)函數(shù)值相聯(lián)系實現(xiàn)擇優(yōu)操作，但在迭代過程中無法自適應(yīng)地調(diào)整個體的適應(yīng)度值并且由于過多的函數(shù)評估，易浪費計算資源。

本文設(shè)計了一種新的自適應(yīng)適應(yīng)度評價方法。在進化過程中，該方法根據(jù)產(chǎn)生后代解的優(yōu)劣自適應(yīng)地調(diào)整父代個體的適應(yīng)度值，淘汰在競爭中失敗的個體，而將獲勝的后代解添加到父代候選解集中。所提方法在父代個體適應(yīng)度值和子代解的質(zhì)量之間建立了自適應(yīng)的動態(tài)聯(lián)系，操作簡單；不僅加快了后代解信息的利用率，而且提高了粒子的學(xué)習(xí)能力和算法的收斂，有效節(jié)省了計算資源。

通常，在EA中適應(yīng)度值大的優(yōu)質(zhì)個體會比一般個體更容易產(chǎn)生好的后代解。為提高后代解的質(zhì)量，自然期望這些優(yōu)質(zhì)個體盡可能多地被選擇為父代個體參與進化，從而產(chǎn)生更高質(zhì)量的后代。事實上，若個體在進化中產(chǎn)生了好的后代解，則可認為它在下一次進化中仍具有產(chǎn)生好的后代解的潛力。因此，本文將每一個體所產(chǎn)生后代解的優(yōu)劣作為反映該個體適應(yīng)度的指標(biāo)，即個體產(chǎn)生的優(yōu)質(zhì)后代數(shù)目越多，它的適應(yīng)度值就會越高，被選擇為父代個體的概率就越大。

在進化前，對POP(0)中每一個體的適應(yīng)度值進行初始化。為使非支配個體更多參與進化，將非支配個體的初始適應(yīng)度值設(shè)為1，受支配個體的初始適應(yīng)度值設(shè)為0，即個體xi的初始適應(yīng)度值

(7)

在第t次迭代中，執(zhí)行以下操作。

6)執(zhí)行上述操作N次使每一代產(chǎn)生N個后代解。

圖1 子區(qū)域中的個體競爭Fig.1 The individual competition in the sub-region

本文ISMPSO/D每產(chǎn)生一個后代解，就對其進行分區(qū)，并與該區(qū)域原來的解進行競爭，且獲勝的優(yōu)質(zhì)后代可盡快參與到種群進化，從而使種群中非支配個體數(shù)不斷增多且越來越靠近對應(yīng)方向向量，但文獻[15]是先產(chǎn)生N個后代解，然后再進行分區(qū)。此外，由于增加了優(yōu)勝劣汰的競爭操作，因此ISMPSO/D在保證多樣性前提下有效提升了收斂速度。

2.2.2 粒子的更新

由PSO更新式(2)-(3)知，在pbest和gbest的引導(dǎo)下，種群可以快速朝真實PF方向逼近。但PSO的快速收斂容易使種群多樣性變差，不利于搜索。由于不同粒子具有不同的特征，且這些特征有助于搜索，所以在更新粒子時，首先產(chǎn)生一個隨機數(shù)，若該隨機數(shù)小于J，則從當(dāng)前粒子的鄰居中隨機選擇pbest和gbest以增強算法的局部開發(fā)能力；否則從鄰居外隨機選擇pbest和gbest以增強算法的全局探索能力，避免陷入局部最優(yōu)。

在標(biāo)準(zhǔn)PSO中，增加鄰域修正策略可以提高后代解的質(zhì)量、提升算法的收斂速度和增強PSO的局部搜索能力[15]。因此本文仍采用如下更新方式[15]：

(8)

(9)

其中,uj和lj分別為決策向量第j維分量的上下界，

(10)

在更新過程中，由于pbest和gbest均從當(dāng)前粒子的鄰居或鄰居外隨機挑選，避免了某一粒子信息被多次利用，從而既降低了后代解集中于某個區(qū)域的可能性，又平衡了種群的局部開發(fā)和全局探索能力；接著對后代解實施變異操作，進一步增強了種群的多樣性。因此兩種策略的結(jié)合，不僅提高了搜索群體的多樣性，而且有效增強了PSO的搜索能力，避免算法陷入局部最優(yōu)。此外，參數(shù)J的選擇對平衡算法的全局探索與局部開發(fā)有重要影響，根據(jù)3.1節(jié)中的實驗分析，本文中取J=0.9。

綜上所述，完整的種群進化過程如下。

算法2種群的進化

1)輸入POP(t)和Fiti(i=1,2,…,N)，令后代解集E=?，操作次數(shù)k=1；

6)若達到最大操作次數(shù)N，則輸出POP(t)，F(xiàn)iti和E；否則令k=k+1，返回2)繼續(xù)上述循環(huán)。

2.3 外部文檔的維護

用EA求解MOPs時，由于部分問題的PF分布較為復(fù)雜(如DTLZ5～7)，所以為使最終所獲解集具有更好的分布性和收斂性，應(yīng)在PF分布密集區(qū)域保留更多解，而在稀疏區(qū)域保留較少解。盡管ISMPSO/D算法在更新種群時，采用一組均勻分布的權(quán)向量將目標(biāo)空間分解成若干個子區(qū)域，且在每個子區(qū)域中僅保留一個最優(yōu)解，但均勻分布的權(quán)向量并不能保證最終獲得PF的均勻性，且每個子區(qū)域中僅保留一個最優(yōu)解，會造成密集區(qū)域優(yōu)質(zhì)解的嚴(yán)重喪失。因此基于目標(biāo)空間分解的更新策略并不適合求解所有優(yōu)化問題，尤其對具有不連續(xù)、退化或多峰PF的復(fù)雜問題。為克服這一不足，本文引入外部文檔A儲存進化過程中產(chǎn)生的歷史精英解，以獲得一組候選的高質(zhì)量解集。但隨著進化，文檔A中精英解數(shù)目就會急劇增加，故對它進行如下操作：1)采用Pareto支配關(guān)系保證收斂性，即每一次迭代后，將后代解集E與A合并，找出其中的非支配解；2)采用擁擠距離方法確保多樣性，即當(dāng)非支解數(shù)目超過預(yù)先設(shè)定的規(guī)模H時，計算它們在目標(biāo)空間中的擁擠度距離，刪去具有較小擁擠距離的多余解。迭代完成后，將外部文檔和進化種群都作為候選的輸出種群，充分結(jié)合了分解方法、Pareto支配和擁擠距離的優(yōu)勢，增強了算法處理復(fù)雜問題的能力。

2.4 種群的輸出

由以上分析，ISMPSO/D在迭代過程中會產(chǎn)生進化種群POP(t)和外部文檔A兩組解集。對POP(t)，采用了基于目標(biāo)空間分解的更新策略，而對A，采用了Pareto支配和擁擠距離的更新策略。由于不同優(yōu)化問題的最優(yōu)更新策略不同，因此本文采用基于IGD的種群輸出策略。對每個測試問題，迭代完成后，分別計算兩組解集的IGD值并進行比較，輸出具有較小IGD值的解集。

2.5 算法流程

由2.1-2.4小節(jié)，ISMPSO/D算法的詳細步驟如下。

算法3ISMPSO/D算法

1)初始化:

(1)設(shè)置進化種群規(guī)模為N，外部文檔規(guī)模為H，最大函數(shù)評估次數(shù)為FES_max；初始權(quán)值為ω，加速度常數(shù)為c1和c2，常數(shù)為J，方向向量鄰居規(guī)模為T；

(2)根據(jù)算法1產(chǎn)生初始種群POP(0)并隨機產(chǎn)生一組速度向量V={v1,v2,…,vN}；

(3)根據(jù)式(7)初始化Fiti(i=1,2,…,N)，令外部文檔A=?，迭代次數(shù)t=0；

2)更新ω并執(zhí)行算法2；

3)將E中的解與A中的解合并，更新A；

4)若滿足終止條件，則計算進化種群POP(t)和外部文檔A的IGD指標(biāo)，輸出具有較小IGD值的解集；否則，令t=t+1返回步2)繼續(xù)循環(huán)。

3 仿真實驗

為驗證ISMPSO/D算法的有效性，本文選取ZDT[24]和DTLZ[25]測試集中的12個多目標(biāo)基準(zhǔn)函數(shù)進行數(shù)值實驗，并與5種多目標(biāo)優(yōu)化算法進行比較，12個測試函數(shù)為雙目標(biāo)優(yōu)化問題ZDT1～4和ZDT6和三目標(biāo)優(yōu)化問題DTLZ1～7；5種多目標(biāo)算法為兩種典型的多目標(biāo)進化算法NSGA-Ⅱ[20]和MOEA/D[21]以及3種具有代表性的多目標(biāo)粒子群優(yōu)化算法SMPSO[10]、dMPSO[14]和MPSO/D[15]。本文所有實驗均使用Matlab R2014a在Math-PC機(Inter(R) Core(TM)2 Quad CPU)上進行。

ISMPSO/D算法的參數(shù)設(shè)置如下：鄰居規(guī)模T=10，最大函數(shù)評估次數(shù)FES_max=100 000，分布指標(biāo)ηm+1=20，初始權(quán)值ω=0.9，權(quán)值采用MPSO/D中的更新方式；加速度常數(shù)c1=2和c2=2；J=0.9(具體說明見下文)；對三目標(biāo)問題，種群規(guī)模N=105，外部文檔規(guī)模H=105，而對于雙目標(biāo)問題，種群規(guī)模N=100，外部文檔規(guī)模H=100；ISMPSO/D的方向向量產(chǎn)生方式與MOEA/D的方向向量產(chǎn)生方式相同。

IGD值可以反映真實PF與近似PF之間的距離。IGD值越小，說明算法所獲解集與真實PF之間的距離越小，其收斂性和多樣性更好。為衡量各算法收斂性和解集多樣性，本文將IGD值作為各算法的性能評價指標(biāo)。

3.1 J值的選取

為探索不同J值對算法性能的影響，當(dāng)J取0，0.3，0.6，0.9時，表1給出了部分測試函數(shù)IGD的平均值和標(biāo)準(zhǔn)差(括號內(nèi)數(shù)據(jù)為標(biāo)準(zhǔn)差)，并用粗體標(biāo)出了在每個測試問題上的最好IGD值。從表1可以看出，當(dāng)J=0.9時，除ZDT3和DTLZ3的標(biāo)準(zhǔn)差稍差外，各測試問題的IGD值都是最好的；對ZDT1和DTLZ3，不同J值對算法性能影響不大；對ZDT3問題，J取0.3和0.9的IGD值優(yōu)于J取0和0.6時的IGD值；但對ZDT4、DTLZ5和DTLZ7，J值越大，IGD結(jié)果越?。灰虼嗽谙旅嫠袑嶒炛腥=0.9。

表1 6種測試函數(shù)在不同J值下的IGD結(jié)果Tab.1 The IGD results of 6 test functions with different J values

3.2 比較與分析

本小節(jié)將ISMPSO/D算法與其它5種算法進行實驗，為確保算法評價的公平客觀及具有統(tǒng)計意義，在顯著水平為0.05時，根據(jù)文獻[26]所提方法對各比較算法和本文算法做t-檢驗。

為實驗的公平性，對雙目標(biāo)ZDT問題，所有算法的種群規(guī)模設(shè)置為100，每個測試問題的最大函數(shù)評估次數(shù)為100 000；而對三目標(biāo)DTLZ問題，所有算法的種群規(guī)模設(shè)置為105，每個測試問題的最大函數(shù)評估次數(shù)為100 000。對比算法的其它參數(shù)與其原文獻的設(shè)置相同。每種算法均獨立重復(fù)運行30次。

對雙目標(biāo)ZDT3和三目標(biāo)DTLZ5～7問題，ISMPSO/D算法在外部文檔A上的IGD值較小，故將外部文檔A作為最終的輸出種群；而對其余8個問題，進化種群POP(t)的IGD值較小，因此輸出進化種群POP(t)。其原因在于外部文檔中采用了擁擠距離和Pareto支配的更新策略，而進化種群是基于目標(biāo)空間的分解維持多樣性的。ZDT3的PF是不連續(xù)的凸形曲線，DTLZ5和DTLZ6的PF非均勻且退化，DTLZ7的PF不連續(xù)且分簇。實際上，對應(yīng)不同優(yōu)化問題的最佳更新策略并不相同，基于分解的方法在求解具有規(guī)整PF的三目標(biāo)問題(如DTLZ1～4)時更具優(yōu)勢，而基于Pareto支配和擁擠距離的方法更適合求解具有退化且不連續(xù)PF的問題(如ZDT3及DTLZ5～7)。本文算法充分結(jié)合了分解方法、Pareto支配和擁擠距離的優(yōu)勢，因此更具競爭力。

表1列出了ISMPSO/D和其它5種對比算法在12個測試問題上IGD的平均值(Mean)和標(biāo)準(zhǔn)差(Std)。每個測試問題的最佳IGD值用黑色加粗表示，“+”、“≈”、“-”分別表示本文算法的IGD值在t-檢驗中分別優(yōu)于、相似于、劣于各對比算法在同一測試問題上的顯著性區(qū)分結(jié)果，表1的最后統(tǒng)計了ISMPSO/D分別優(yōu)于、相似于、劣于各對比算法的問題個數(shù)。

從表2可以看出，本文ISMPSO/D算法在2個雙目標(biāo)和3個三目標(biāo)問題上取得最好IGD值(其中在ZDT1和DTLZ1上輸出外部文檔，在其余問題上輸出進化種群)，MPSO/D獲得4個最優(yōu)值，MOEA/D在ZDT4和ZDT6上獲得最優(yōu)值，SMPSO在DTLZ5上取得最優(yōu)值，而dMPSO在12個測試問題上都未獲得最優(yōu)IGD值。

與MPSO/D相比，ISMPSO/D獲得最優(yōu)值的個數(shù)多于MPSO/D，且在三目標(biāo)DTLZ1和DTLZ3上，二者所獲IGD均值相同，但在DTLZ5～7以及除ZDT2之外的其它雙目標(biāo)問題上，ISMPSO/D比MPSO/D獲得的IGD值要小。對PF分布較為規(guī)整的雙目標(biāo)ZDT1、ZDT4和ZDT6，ISMPSO/D由于采用了自適應(yīng)適應(yīng)度評價方法以及后代個體的實時競爭策略，因此更具優(yōu)勢；而對PF分布較為復(fù)雜的DTLZ5～7，外部文檔的引入使得本文充分結(jié)合了分解方法、Pareto支配和擁擠距離的優(yōu)勢，從而取得了較好IGD結(jié)果。

表2 6種算法在12個測試函數(shù)上的IGD結(jié)果Tab.2 The IGD values of six algorithms on twelve test functions

與MOEA/D相比，ISMPSO/D在三目標(biāo)DTLZ1～7上以及雙目標(biāo)ZDT1～3問題上都取得最優(yōu)IGD值。與SMPSO、NSGA-Ⅱ以及dMPSO相比，所提算法除了在DTLZ5上的性能稍遜于SMPSO和NSGA-Ⅱ外，在其它問題上均有顯著優(yōu)勢。綜上，ISMPSO/D在總體上獲得最好的多樣性和收斂性。

為直觀觀察各比較算法在測試問題上所獲得的近似PF，圖2給出了4種算法在7個較難測試問題上迭代1 000次的近似PF圖像。由圖2可以看出，對7個較難測試的函數(shù)，ISMPSO/D算法均能獲得分布均勻且完整的PF；對雙目標(biāo)ZDT1和ZDT6問題，各算法都表現(xiàn)出良好的收斂性和均勻性，但基于分解的ISMPSO/D、MPSO/D和MOEA/D算法所獲PF要比NSGA-Ⅱ均勻；對ZDT3問題，MPSO/D陷入局部最優(yōu)未能找到分布完整的PF，MOEA/D和NSGA-Ⅱ雖然能找到完整的PF，但所獲解集的分布性明顯差于ISMPSO/D；對三目標(biāo)的4個測試問題，ISMPSO/D獲得的PF更為完整；對DTLZ1和DTLZ3，ISMPSO/D和MPSO/D的分布性明顯優(yōu)于NSGA-Ⅱ和MOEA/D，且后兩種算法僅能找到部分PF且分布不佳，而在搜索邊界上MPSO/D的分布性稍遜于本文算法；對PF非均勻且退化的DTLZ6問題，本文算法所獲PF不僅收斂而且分布均勻，MOEA/D和NSGA-Ⅱ收斂性不好，MPSO/D所獲PF的收斂性和分布性均最差；對DTLZ7，ISMPSO/D和NSGA-Ⅱ能收斂到4個簇上，而MOEA/D的多樣性嚴(yán)重缺失，MPSO/D不收斂。因此，本文算法不僅可以搜索到7個測試問題的完整PF，而且收斂性和所獲PF的分布性最佳。

圖2 4種算法在7個較難測試問題上的近似PF Fig.2 Approximate PF of four algorithms on seven difficult test functions

綜上所述，ISMPSO/D的綜合性能明顯優(yōu)于其它算法。其原因在于：1)提出的新適應(yīng)度評價方法將父代解的適應(yīng)度值與子代解的優(yōu)劣相聯(lián)系，且一旦產(chǎn)生后代解就立即參與競爭，并根據(jù)競爭結(jié)果對進化種群和父代適應(yīng)度值進行更新，使得優(yōu)質(zhì)后代解的信息被快速利用，提升了進化種群的整體質(zhì)量，加速了算法收斂。在相同迭代次數(shù)下，對PF分布規(guī)整的問題(如ZDT1、DTLZ1和DTLZ3)，其IGD比較結(jié)果和PF圖像都說明了上述改進的有效性；2)外部文檔的引入以及pbest和gbest的隨機選擇，避免了種群多樣性的過早喪失，改進了分解方法處理具有復(fù)雜PF問題(如DTLZ6和DTLZ7)的不足。

4 結(jié)論

為提高粒子群算法的搜索效率及克服分解方法處理復(fù)雜多目標(biāo)問題的不足，通過考慮適應(yīng)度評價和種群更新對算法收斂性及解的分布均勻性的重要影響，本文基于目標(biāo)空間的分解提出一種求解MOPs的改進ISMPSO/D算法。首先，設(shè)計了一種自適應(yīng)適應(yīng)度評價方法，并根據(jù)競爭結(jié)果對父代適應(yīng)度值和進化種群進行更新，加快了算法的收斂速度；其次，在更新粒子時，從當(dāng)前粒子的鄰居或鄰居外隨機選擇個體最優(yōu)和全局最優(yōu)位置，增強了粒子的多樣性，且對產(chǎn)生的后代解立即進行變異，避免了算法陷入局部最優(yōu)；最后，引入外部文檔作為候選的輸出種群，并采用擁擠距離維持多樣性，克服了分解方法不利于求解復(fù)雜問題的缺陷。通過對12個基準(zhǔn)函數(shù)的數(shù)值實驗，并與5種多目標(biāo)算法的比較，表明了所提算法不僅改進了分解方法無法找到復(fù)雜PF的缺陷，而且能更好地維持算法收斂性和解集多樣性的平衡。

盡管ISMPSO/D算法在多目標(biāo)測試問題上的綜合性能有所提升，但對超多目標(biāo)優(yōu)化問題如何改進，其性能有待進一步研究。