基于雙層協(xié)同進(jìn)化的多目標(biāo)粒子群算法

閆 李，李國森，瞿博陽，朱小培，馬佳慧

(中原工學(xué)院 電子信息學(xué)院，河南 鄭州 450007)

0 引 言

實(shí)際工程中大多數(shù)優(yōu)化問題屬于多目標(biāo)優(yōu)化問題(multi-objective optimization problems，MOPs)[1]。這類問題的優(yōu)化結(jié)果不是單一的，而是存在一組折衷解組成的帕累托最優(yōu)解集(Pareto-optimal set，PS)[2,3]。解決這類問題的目標(biāo)是獲得目標(biāo)空間中分布良好的帕累托前沿(Pareto front，PF)[4-6]。

在多目標(biāo)問題中，一些優(yōu)化問題具有多模態(tài)的特性。如路徑規(guī)劃問題[7]、背包問題[8]、車間調(diào)度問題[9]，這類問題屬于多模態(tài)多目標(biāo)優(yōu)化問題(multimodal multi-objective optimization problems，MMOPs)[10]，其特點(diǎn)是決策空間中的多個PS映射到目標(biāo)空間中相同的PF。解決這類問題的目標(biāo)是獲得決策空間中多個帕累托解集。

對此國內(nèi)外許多學(xué)者提出算法以解決多模態(tài)多目標(biāo)優(yōu)化問題。Liu等[11]利用雙保存集與重組策略提高解集在目標(biāo)與決策空間中的多樣性和收斂性。Xu[12]采用變異邊界處理方法以提高種群多樣性，并采用個體預(yù)選擇機(jī)制提高搜索精度。Ishibashi[13]使用決策空間中分布良好的個體優(yōu)化每個子問題，以保持決策空間中個體的多樣性。

上述研究在解決多模態(tài)多目標(biāo)問題上做出了很多工作，但仍然存在獲得的帕累托解集不完整、算法收斂性較差等不足。本文以多目標(biāo)粒子群算法(multi-objective particle swarm optimization algorithm，MOPSO)[14-16]為框架，提出基于雙層協(xié)同進(jìn)化的多目標(biāo)粒子群算法(DCMOPSO)。算法采用雙層協(xié)同進(jìn)化機(jī)制以定位更多的解，利用決策空間擁擠距離以保持解的多樣性。最后，通過對比實(shí)驗(yàn)驗(yàn)證DCMOPSO算法的性能。

1 基本概念

1.1 多模態(tài)多目標(biāo)優(yōu)化問題

如圖1所示，決策空間中的PS1、PS2對應(yīng)目標(biāo)空間同一個PF[7]。決策空間中A1和A2分別位于PS1、PS2，但在目標(biāo)空間中都對應(yīng)同一點(diǎn)A′。同時求出可行方案A1和A2，這給決策者選擇合適的方案提供了很大的靈活性[17]。

圖1 多模態(tài)多目標(biāo)優(yōu)化問題

1.2 粒子群算法描述

設(shè)一個由NP個粒子組成的種群在M維決策空間中進(jìn)行尋優(yōu)。在t時刻，第i個粒子從當(dāng)前位置xi(t) 以速度vi(t) 朝著其個體歷史最優(yōu)pbesti(t) 和全局最優(yōu)nbesti(t) 的方向飛行[18]。則在 (t+1) 時刻，該粒子的速度vi(t+1) 和位置xi(t+1) 分別定義為

vi(t+1)=wvi(t)+c1r1(pbesti(t)-xi(t))+
c2r2(nbesti(t)-xi(t))

(1)

xi(t+1)=xi(t)+vi(t+1)

(2)

其中，w為慣性權(quán)重，c1和c2為加速系數(shù)，r1和r2為[0，1]之間的隨機(jī)值。

2 基于雙層協(xié)同進(jìn)化的多目標(biāo)粒子群算法

2.1 雙層協(xié)同進(jìn)化機(jī)制

在傳統(tǒng)粒子群算法中，粒子間幾乎沒有信息交流，且采用全局最優(yōu)解更新各個粒子的位置，這將導(dǎo)致許多粒子過早收斂而降低了全局尋優(yōu)能力和種群多樣性，因此很難在決策空間找到多個解。另外，在連續(xù)多目標(biāo)優(yōu)化問題中，其真實(shí)帕累托解集在決策空間中是一個分段連續(xù)流形。如果使種群中的粒子逐漸飛向這些帕累托解集周圍，那么將能夠獲得大量的帕累托解集。

基于此，本文提出雙層協(xié)同進(jìn)化機(jī)制，該機(jī)制采用上下兩層，并將整個種群均分成兩個子種群，即上層一個探測種群和下層一個跟隨種群。探測種群采用外部檔案EXA中的精英解以引導(dǎo)進(jìn)化，盡可能逼近帕累托解集，并較均勻地分布在帕累托解集的周圍。跟隨種群負(fù)責(zé)跟隨探測種群，并學(xué)習(xí)探測種群的歷史最優(yōu)信息，加強(qiáng)局部的開采能力。具體方法為：

然后探測種群、跟隨種群協(xié)同進(jìn)化。其基本思想是探測種群中每個粒子采用全局最優(yōu)引導(dǎo)以收斂到全局最優(yōu)，而跟隨種群中的每個粒子跟隨其伙伴的個體歷史最優(yōu)以增強(qiáng)開采能力。對于探測種群中第i個粒子 (i∈P)，其速度更新公式如下

vi(t+1)=wvi(t)+c1r1(EXA(k)-xi(t))

(3)

對于跟隨種群中第j個粒子 (j∈Q)，其速度更新公式如下

vj(t+1)=wvj(t)+c1r1(pi(t)-xj(t))

(4)

雙層協(xié)同進(jìn)化機(jī)制如圖2所示。整個種群劃分為探測種群和跟隨種群。跟隨種群中的粒子跟隨其在探測種群的伙伴，且不受其它粒子的影響，進(jìn)而形成若干個鄰域以提高種群的多樣性。而探測種群中的不同粒子跟隨不同的全局最優(yōu)nbest。探測種群中的粒子不斷改善其位置，并將歷史最優(yōu)信息反饋給跟隨種群，以協(xié)同進(jìn)化定位更多的解。

圖2 雙層協(xié)同進(jìn)化機(jī)制

2.2 決策空間擁擠距離

在多模態(tài)多目標(biāo)問題中，相距很遠(yuǎn)的多個解可能對應(yīng)目標(biāo)空間中同一點(diǎn)，導(dǎo)致在目標(biāo)空間中這些解的擁擠距離會很小。如果只考慮解在目標(biāo)空間的分布情況，這些解在選擇過程中會被刪除，即很難保留決策空間中的擁擠距離大的解。

因此本文引入基于決策空間的擁擠距離度量，以提高最優(yōu)解在決策空間的分布性。具體計算方法：首先將所有個體按照快速非支配排序的方法進(jìn)行分層。然后根據(jù)每個決策變量對該層所有個體按升序進(jìn)行排序以便計算每一層中的每個個體的擁擠距離。設(shè)決策變量維數(shù)為M，個體數(shù)為N，Ind(i).distance為第i個個體 (1≤i≤N) 在第m個變量 (1≤m≤M) 上的擁擠距離，Ind(i).m為個體i在第m個變量上的值。對于非邊界點(diǎn)個體，擁擠距離計算如下

(5)

其中，Indmin.m、Indmax.m分別為該層所有個體在第m個變量上的最小值和最大值。對于邊界點(diǎn)個體，擁擠距離計算如下

(6)

(7)

圖3 決策空間擁擠距離

2.3 算法具體流程

步驟1 設(shè)置算法的種群大小NP、學(xué)習(xí)因子(c1)、最大迭代次數(shù)MaxIter，初始化種群POP，外部檔案EXA=POP。

步驟2 根據(jù)雙層協(xié)同進(jìn)化機(jī)制劃分探測種群、跟隨種群。

步驟3 根據(jù)雙層協(xié)同進(jìn)化機(jī)制為探測種群中的粒子分配nbest。

步驟4 探測種群中的粒子根據(jù)式(3)進(jìn)行速度位置更新，跟隨種群中的粒子根據(jù)式(4)進(jìn)行速度位置更新。

步驟5 更新外部檔案EXA=[POP;EXA]，對外部檔案進(jìn)行非支配排序以及決策空間擁擠距離的計算，選擇前NP個解存入EXA。

步驟6 若迭代次數(shù)達(dá)到最大迭代次數(shù)MaxIter，輸出外部檔案EXA，否則，返回步驟3。

2.4 算法復(fù)雜度分析

DCMOPSO算法的主要運(yùn)算是劃分上下層種群，分配最優(yōu)領(lǐng)導(dǎo)nbest和計算擁擠距離。假設(shè)NP表示種群以及外部存檔的規(guī)模，M表示決策變量的個數(shù)，N表示目標(biāo)函數(shù)的個數(shù)。劃分上下層種群和分配最優(yōu)領(lǐng)導(dǎo)nbest都需要計算每個個體與其它個體的距離，故其計算復(fù)雜度均為O(NP2)。擁擠距離的計算需要先判斷支配關(guān)系，其計算復(fù)雜度為O(M*NP2)。計算擁擠距離的復(fù)雜度為O(M*NP*logNP)。因此，整個DCMOPSO算法的計算復(fù)雜度為O(M*NP2)。而基本的MOPSO算法的計算復(fù)雜度為O(N*NP2)[19]，因此在計算復(fù)雜度上，當(dāng)決策變量的個數(shù)M和目標(biāo)函數(shù)的個數(shù)N相同時，DCMOPSO算法和基本MOPSO算法具有同樣的計算復(fù)雜度。

3 實(shí)驗(yàn)和分析

3.1 測試函數(shù)

本文采用12個經(jīng)典的多模態(tài)多目標(biāo)測試函數(shù)[20]，包括MMF1-MMF8[7]、Omni-test[12]、SYM-PART simple[21]、SYM-PART rot.+trans.[21]以及SYM-PART rotate[21]。

3.2 實(shí)驗(yàn)設(shè)置

本文將提出的DCMOPSO算法與6種多目標(biāo)算法進(jìn)行比較，包括MO_Ring_PSO_SCD[7]、DN-NSGAII[11]、Omni-optimizer[12]、NSGA-II[4]、MOEA/D[5]、PESA-II[6]。其中，DCMOPSO算法參數(shù)如下：c1=2.05，w=0.7298。其它算法的參數(shù)設(shè)置與相應(yīng)文獻(xiàn)保持相同。各算法的種群規(guī)模NP和最大迭代次數(shù)MaxIter分別為800和100[7]，外部檔案大小為800。每個算法在12個測試函數(shù)上獨(dú)立運(yùn)行25 次，結(jié)果取平均值。采用Matlab R2014b進(jìn)行仿真，運(yùn)行環(huán)境為Windows 7 操作系統(tǒng)，Intel(R) Core(TM) I7-4790 處理器，16 GB內(nèi)存。

3.3 評價指標(biāo)

本文采用帕累托解集近似性(PSP)[7]和超體積(Hv)[22,23]兩種指標(biāo)對比不同算法的性能。PSP用于評價算法所獲得PS的收斂性和多樣性。Hv主要反映算法所獲得PF的收斂性和多樣性[24]。PSP值越大說明獲得的PS在決策空間中更逼近真實(shí)的PS，且具有良好的分布性。Hv值越大說明獲得的PF在目標(biāo)空間中更具有多樣性且接近真實(shí)的PF。

3.4 實(shí)驗(yàn)結(jié)果

3.4.1 各策略性能對比實(shí)驗(yàn)

為了驗(yàn)證所提策略的有效性，將DCMOPSO算法和MOPSO(基本的多目標(biāo)粒子群算法)[7]、DCMOPSO-I(僅采用雙層協(xié)同進(jìn)化機(jī)制的MOPSO算法)和DCMOPSO-II(僅采用決策空間擁擠距離的MOPSO算法)進(jìn)行比較。在不同策略下算法PSP的均值、標(biāo)準(zhǔn)差和秩和檢驗(yàn)的h值見表1。

表1 各策略PSP指標(biāo)統(tǒng)計

從表1可以看出，DCMOPSO-I的性能優(yōu)于MOPSO，DCMOPSO-II的性能略優(yōu)于MOPSO。因此，采用雙層協(xié)同進(jìn)化機(jī)制和決策空間擁擠距離度量能夠改善基本MOPSO算法的性能。此外，秩和檢驗(yàn)的結(jié)果進(jìn)一步表明，DCMOPSO 結(jié)合這兩種策略能夠顯著提升算法的性能。其原因在于雙層協(xié)同進(jìn)化機(jī)制使DCMOPSO算法能夠找到更多的最優(yōu)解。雙層協(xié)同進(jìn)化機(jī)制在決策空間中將種群劃分探測種群、跟隨種群，并選擇外部存檔中的最優(yōu)解為上層探測種群分配nbest，使探測種群不斷逼近真實(shí)帕累托解集；跟隨種群中的粒子不斷跟隨探測種群中其對應(yīng)的伙伴粒子，進(jìn)而形成若干鄰域，并在其鄰域內(nèi)進(jìn)化，以維持種群的多樣性。采用決策空間擁擠距離度量以評估解在決策空間的擁擠度，使得擁擠度小的解優(yōu)先被保留，而擁擠度大的解由于多樣性很差而優(yōu)先考慮被剔除，提高了解在決策空間的分布性。

綜上所述，雙層協(xié)同進(jìn)化機(jī)制和基于決策空間的擁擠距離度量能夠提高算法的性能。

3.4.2 不同算法的性能對比實(shí)驗(yàn)

本節(jié)將提出的DCMOPSO 算法與6種多目標(biāo)算法進(jìn)行比較。首先，比較所有算法在決策空間中獲得PS的能力。所有算法的PSP指標(biāo)值見表2，可以看出DCMOPSO在所有測試函數(shù)上顯示出較好的性能，明顯優(yōu)于其它6種算法。MO_Ring_PSO_SCD的表現(xiàn)次之。MO_Ring_PSO_SCD采用環(huán)形拓?fù)湟孕纬啥鄠€小生境，有助于找到更多最優(yōu)解。DN-NSGAII和Omni-optimizer的表現(xiàn)相似。DN-NSGAII和Omni-optimizer均考慮解在決策空間的擁擠度，這提高了算法的性能。NSGA-II、MOEA/D和PESA-II表現(xiàn)較差，原因在于這3個算法沒有考慮解在決策空間中的分布，不能保留決策空間中多樣性好的解。其次，評價所有算法在目標(biāo)空間中獲得的PF的性能。所有算法的Hv指標(biāo)值見表3，可以得出結(jié)論DCMOPSO算法在Hv性能指標(biāo)上的表現(xiàn)不是最好的。但是，所有算法在同一測試函數(shù)上的Hv指標(biāo)值彼此很接近。原因是所有算法均考慮了最優(yōu)解在目標(biāo)空間中的分布。

表2 不同算法PSP指標(biāo)統(tǒng)計

表3 不同算法Hv指標(biāo)統(tǒng)計

圖4給出了SYM-PART rot.+trans的真實(shí)PS和PF，該函數(shù)具有9個PS。為了直觀比較算法性能，圖5和圖6分別給出了所有算法在測試函數(shù)SYM-PART rot.+trans上得到的PS和PF。從圖5可以看出，DCMOPSO能夠找到9個PS。MO_Ring_PSO_SCD、DN-NSGAII和Omni-optimizer 找到的PS并不完整，且有缺失。NSGA-II、MOEA/D和PESA-II獲得的PS更少。從圖6可以看出，所有算法在SYM-PART rot.+ trans測試函數(shù)上都能夠獲得較好分布的PF，且差別不大。

圖4 SYM-PART rot.+trans的真實(shí)PS和PF

圖5 各算法所獲得的PS對比

圖6 各算法所獲得的PF對比

綜上所述，和其它算法相比，DCMOPSO在決策空間中表現(xiàn)出更好的性能，且能夠獲得更多的PS。

3.4.3 算法的收斂性比較

為了比較算法的收斂性[7]，將4個多目標(biāo)算法(DCMOPSO、MO_Ring_PSO_SCD、Omni-optimizer、DN-NSGAII)進(jìn)行比較。NSGA-II、MOEA/D和PESA-II在決策空間的性能很差(見表3)，故不再進(jìn)行比較。本次實(shí)驗(yàn)選擇在測試函數(shù)MMF4上進(jìn)行測試。MMF4是由4段曲線(PS)組成的PSs，每段曲線對應(yīng)同一個PF。如圖7所示，將決策空間劃分為4個區(qū)域，分別為區(qū)域1、區(qū)域2、區(qū)域3 和區(qū)域4。因此每個區(qū)域面積相等，且均有一個PS。算法的收斂性是指每次迭代種群分布在每個區(qū)域中解的比例[7]。理論上，如果算法在測試函數(shù)MMF4上具有良好的收斂性能，那么每個區(qū)域中解的比例應(yīng)等于0.25。

圖7 測試函數(shù)MMF4的PSs分布

圖8展示了算法在100次迭代過程中每個區(qū)域中解的比例變化曲線。從圖8(a)中可以看出，區(qū)域1、區(qū)域2中解的比例隨迭代次數(shù)增加而先上升后下降，而區(qū)域3、區(qū)域4所在的曲線呈先下降后上升趨勢。在迭代次數(shù)趨近于60時，4個區(qū)域解的比例基本上接近0.25。這反映了DCMOPSO算法的收斂性能良好。對于MO_Ring_PSO_SCD的收斂性(如圖8(b)所示)，每個區(qū)域解的比例最終能夠穩(wěn)定在0.25左右。但是區(qū)域1、區(qū)域2的解的比例略大于區(qū)域3、區(qū)域4的解的比例。這說明MO_Ring_PSO_SCD的收斂性略差于DCMOPSO。對于DN-NSGAII的收斂性(如圖8(c)所示)，在第30次迭代以后，區(qū)域1、區(qū)域4的解的比例低于區(qū)域2、區(qū)域3的解的比例，且未收斂到0.25。這說明更多的種群個體聚集到了區(qū)域2、區(qū)域3。對于Omni-optimizer的收斂性(如圖8(d)所示)，在第45次迭代以后，區(qū)域1、區(qū)域4的解的比例高于區(qū)域2、區(qū)域3 的解的比例，且不接近0.25。這意味著大多數(shù)的種群個體收斂到了區(qū)域1、區(qū)域4。同時，在圖8(c)、圖8(d)中，每個區(qū)域解的比例變化頻繁震蕩，且不穩(wěn)定。因此DN-NSGAII、Omni-optimizer算法的收斂性能很差。綜上所述，DCMOPSO算法具有更好的收斂性能。

圖8 各算法的收斂性對比

4 結(jié)束語

本文提出了一種基于雙層協(xié)同進(jìn)化的多目標(biāo)粒子群算法(DCMOPSO)。該算法采用了雙層協(xié)同進(jìn)化機(jī)制和決策空間擁擠距離度量。雙層協(xié)同進(jìn)化機(jī)制采用上層探測種群不斷地逼近帕累托解集，下層跟隨種群不斷地跟隨其探測種群中的伙伴粒子。決策空間擁擠距離度量用于評估粒子在決策空間的擁擠度來維持帕累托解集在決策空間的多樣性。通過和6個多目標(biāo)算法進(jìn)行比較，驗(yàn)證了DCMOPSO算法能夠獲得更多的帕累托解，且在決策空間具有很好的收斂性。下一步工作將應(yīng)用DCMOPSO算法解決實(shí)際工程問題。