基于雙層協同進化的多目標粒子群算法

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

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

0 引 言

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

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

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

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

1 基本概念

1.1 多模態多目標優化問題

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

圖1 多模態多目標優化問題

1.2 粒子群算法描述

設一個由NP個粒子組成的種群在M維決策空間中進行尋優。在t時刻，第i個粒子從當前位置xi(t) 以速度vi(t) 朝著其個體歷史最優pbesti(t) 和全局最優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為慣性權重，c1和c2為加速系數，r1和r2為[0，1]之間的隨機值。

2 基于雙層協同進化的多目標粒子群算法

2.1 雙層協同進化機制

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

基于此，本文提出雙層協同進化機制，該機制采用上下兩層，并將整個種群均分成兩個子種群，即上層一個探測種群和下層一個跟隨種群。探測種群采用外部檔案EXA中的精英解以引導進化，盡可能逼近帕累托解集，并較均勻地分布在帕累托解集的周圍。跟隨種群負責跟隨探測種群，并學習探測種群的歷史最優信息，加強局部的開采能力。具體方法為：

然后探測種群、跟隨種群協同進化。其基本思想是探測種群中每個粒子采用全局最優引導以收斂到全局最優，而跟隨種群中的每個粒子跟隨其伙伴的個體歷史最優以增強開采能力。對于探測種群中第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)

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

圖2 雙層協同進化機制

2.2 決策空間擁擠距離

在多模態多目標問題中，相距很遠的多個解可能對應目標空間中同一點，導致在目標空間中這些解的擁擠距離會很小。如果只考慮解在目標空間的分布情況，這些解在選擇過程中會被刪除，即很難保留決策空間中的擁擠距離大的解。

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

(5)

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

(6)

(7)

圖3 決策空間擁擠距離

2.3 算法具體流程

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

步驟2 根據雙層協同進化機制劃分探測種群、跟隨種群。

步驟3 根據雙層協同進化機制為探測種群中的粒子分配nbest。

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

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

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

2.4 算法復雜度分析

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

3 實驗和分析

3.1 測試函數

本文采用12個經典的多模態多目標測試函數[20]，包括MMF1-MMF8[7]、Omni-test[12]、SYM-PART simple[21]、SYM-PART rot.+trans.[21]以及SYM-PART rotate[21]。

3.2 實驗設置

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

3.3 評價指標

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

3.4 實驗結果

3.4.1 各策略性能對比實驗

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

表1 各策略PSP指標統計

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

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

3.4.2 不同算法的性能對比實驗

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

表2 不同算法PSP指標統計

表3 不同算法Hv指標統計

圖4給出了SYM-PART rot.+trans的真實PS和PF，該函數具有9個PS。為了直觀比較算法性能，圖5和圖6分別給出了所有算法在測試函數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測試函數上都能夠獲得較好分布的PF，且差別不大。

圖4 SYM-PART rot.+trans的真實PS和PF

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

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

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

3.4.3 算法的收斂性比較

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

圖7 測試函數MMF4的PSs分布

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

圖8 各算法的收斂性對比

4 結束語

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