閆 李，李國(guó)森，瞿博陽(yáng)，朱小培，馬佳慧

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

0 引 言

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

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

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

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

1 基本概念

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

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

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

1.2 粒子群算法描述

設(shè)一個(gè)由NP個(gè)粒子組成的種群在M維決策空間中進(jìn)行尋優(yōu)。在t時(shí)刻，第i個(gè)粒子從當(dāng)前位置xi(t) 以速度vi(t) 朝著其個(gè)體歷史最優(yōu)pbesti(t) 和全局最優(yōu)nbesti(t) 的方向飛行[18]。則在 (t+1) 時(shí)刻，該粒子的速度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)粒子群算法中，粒子間幾乎沒(méi)有信息交流，且采用全局最優(yōu)解更新各個(gè)粒子的位置，這將導(dǎo)致許多粒子過(guò)早收斂而降低了全局尋優(yōu)能力和種群多樣性，因此很難在決策空間找到多個(gè)解。另外，在連續(xù)多目標(biāo)優(yōu)化問(wèn)題中，其真實(shí)帕累托解集在決策空間中是一個(gè)分段連續(xù)流形。如果使種群中的粒子逐漸飛向這些帕累托解集周圍，那么將能夠獲得大量的帕累托解集。

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

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

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

(3)

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

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

(4)

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

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

2.2 決策空間擁擠距離

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

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

(5)

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

(6)

(7)

圖3 決策空間擁擠距離

2.3 算法具體流程

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

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

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

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

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

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

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

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

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

3.1 測(cè)試函數(shù)

本文采用12個(gè)經(jīng)典的多模態(tài)多目標(biāo)測(cè)試函數(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。每個(gè)算法在12個(gè)測(cè)試函數(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 評(píng)價(jià)指標(biāo)

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

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

3.4.1 各策略性能對(duì)比實(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值見(jiàn)表1。

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

從表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ī)制在決策空間中將種群劃分探測(cè)種群、跟隨種群，并選擇外部存檔中的最優(yōu)解為上層探測(cè)種群分配nbest，使探測(cè)種群不斷逼近真實(shí)帕累托解集；跟隨種群中的粒子不斷跟隨探測(cè)種群中其對(duì)應(yīng)的伙伴粒子，進(jìn)而形成若干鄰域，并在其鄰域內(nèi)進(jìn)化，以維持種群的多樣性。采用決策空間擁擠距離度量以評(píng)估解在決策空間的擁擠度，使得擁擠度小的解優(yōu)先被保留，而擁擠度大的解由于多樣性很差而優(yōu)先考慮被剔除，提高了解在決策空間的分布性。

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

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

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

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

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

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

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

圖5 各算法所獲得的PS對(duì)比

圖6 各算法所獲得的PF對(duì)比

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

3.4.3 算法的收斂性比較

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

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

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

圖8 各算法的收斂性對(duì)比

4 結(jié)束語(yǔ)

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