基于鄰域驅動的粒子群算法

2022-11-25 07:26:08李國森郭倩倩趙啟鳳岳彩通

計算機工程與設計 2022年11期

李國森，閆李，郭倩倩，趙啟鳳，岳彩通

(1.中原工學院電子信息學院，河南鄭州 450007；2.鄭州大學電氣工程學院，河南鄭州 450001；3.鄭州大學產業技術研究院，河南鄭州 450001)

0 引言

在實際科學和工程應用中，大多數優化問題包含多個彼此沖突的目標[1]。在進行優化時，需要找到使所有目標達到最優的一組Pareto最優解集(Pareto set，PS)。所有Pareto最優解映射至目標空間形成Pareto前沿(Pareto front，PF)。基于Pareto支配關系的多目標算法是解決多目標問題的經典方法，能在一次運行后得到逼近真實PF的解集[2,3]。

在多目標優化問題中，存在一種特殊的優化問題，即多模態多目標優化問題(multimodal multi-objective optimization problems，MMOPs)[4,5]。MMOPs在決策空間中包含多個PS對應于目標空間中同一PF。研究者關注的是Pareto最優解在決策空間中的分布情況，旨在在決策空間中找到更多的Pareto最優解[6]。

為求解多模態多目標問題，Li等[7]采用多種變異策略，動態調整種群的進化方向。Tanabe等[8]引入分解的思想，劃分多個子問題進行同時優化。Liu等[9]采用雙檔案重組策略提高決策空間的多樣性。Qu等[4]采用自組織機制提高種群的尋優速度。Yue等[10]提出多模態多目標遺傳算法，提高對決策空間的搜索能力。

上述研究在一定程度上提高了解在決策空間的分布性，但仍存在算法多樣性缺失、獲得的PS不完整等不足。本文提出基于鄰域驅動的粒子群算法。算法采用鄰域驅動策略，構建多個獨立的鄰域，引導種群開采多個解。同時采用吸收機制，借鑒鄰域粒子的搜索經驗，提高算法對鄰域空間的深度搜索能力。

1 基本概念

1.1 多模態多目標優化問題

圖1給出了多模態多目標問題示意圖[11,12]。在決策空間中存在兩個PS，分別為PS1和PS2。兩個PS均對應于目標空間中的PF。其中，位于PS1上的A1和位于PS2上的A2均對應于PF上的A′。在決策空間中找出多個最優方案(如A1和A2)，可為決策者提供多種選擇。

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

1.2 粒子群算法描述

在D維決策空間中，種群POP由N個粒子組成。其中第i個粒子的位置記為xi，飛行速度記為vi，該粒子通過跟蹤個體最優pbest和全局最優nbest更新自己的位置和速度[13,14]。在第t次迭代，其更新公式如下

vi(t+1)=w·vi(t)+c1·rand·(pbesti(t)-xi(t))+
c2·rand·(nbesti(t)-xi(t))

(1)

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

(2)

其中，c1、c2是學習因子，w是慣性權重；rand∈[0,1]。

2 算法設計

2.1 鄰域驅動策略

標準粒子群算法在迭代后期存在種群多樣性丟失，早熟收斂等問題，很難在決策空間找到多個最優解[15]。鑒于此，本文提出鄰域驅動策略。基本思想是根據相似度將整個種群劃分為多個鄰域，每個鄰域內的粒子共享最優信息，粒子獨立在自己的鄰域空間內獨立進化，推動整個種群獲得更多的最優解。具體方法為：

首先，計算粒子間距離。分別計算每個粒子與種群中其它粒子的距離。第i個粒子與第j個粒子的歐式距離定義如下

(3)

其次，劃分鄰域。在種群規模為N的種群POP中，集合SP表示已加入鄰域的粒子，集合NLi表示第i個粒子的鄰域集合，nsize表示鄰域的大小。從種群POP中，先找出距離第1個粒子最近的nsize個粒子，將其加入SP和NL1中。接著找出距離第k(1

最后，分配最優nbest。第i個粒子的nbest選取方法為：對NLi中的粒子進行非支配排序，選取排在第一的粒子作為nbest。

圖2給出鄰域驅動策略示意圖。從圖2中可知，整個種群劃分成4個鄰域，每個鄰域內包含5個粒子，其中一個粒子是鄰域nbest，nbest指導鄰域內個體進化。根據歐式距離作為粒子間的相似度，相似的個體被劃分到同一鄰域內，鄰域中的個體在各自的空間內搜索。另外，鄰域隨著迭代次數動態更新，若某些粒子早熟停滯，在鄰域信息的牽引下跳出局部區域。按照這種方式，提高粒子在尋優時的活性，種群逐漸在決策空間能夠找到更多解。

圖2 鄰域驅動策略

2.2 吸收機制

在粒子群算法中，如果粒子僅被最優解引導，將快速收斂到最優解附近[16]。為了挖掘鄰域內的潛在解，提高算法的搜索活力，本文提出吸收機制。基本思想是吸收鄰域內所有粒子的搜索經驗，引導粒子在鄰域內充分開采。

假設第i個粒子的鄰域集合記為NLi，該鄰域的上邊界記為UBi，下邊界記為LBi，對角線距離記為Li。集合L記錄每個粒子對應的對角線距離。

首先，在d維，上邊界UBid和下邊界LBid計算如下

UBid=max(NLid)

(4)

LBid=min(NLid)

(5)

其中，NLid表示鄰域集合NLi中所有粒子的第d維。

其次，依據鄰域的上下邊界，計算對角線距離Li。公式如下

(6)

最后，如果滿足rand

(7)

圖3示例了吸收機制。鄰域1和鄰域2的搜索范圍用虛線給出。相比于鄰域2，鄰域1的搜索范圍較大。可以采用式(7)對鄰域內的粒子進行更新。一方面，式(7)對鄰域內所有粒子的信息進行了綜合學習，促進鄰域中優秀信息的流動，增強種群對鄰域的搜索能力；另一方面，萊維分布兼顧小范圍的開采和大范圍的勘探[17,18]，能夠更全面搜索整個鄰域，避免陷入局部區域。

圖3 吸收機制

2.3 算法流程

步驟1 隨機初始化粒子種群POP，外部檔案EXA=POP。

步驟2 根據鄰域驅動策略劃分鄰域，為每個粒子分配nbest。

步驟3 按照式(1)、式(2)更新粒子的位置和速度。

步驟4 按照式(4)、式(5)、式(6)計算每個鄰域的上下邊界和對角線距離。

步驟5 判斷是否采用式(7)更新粒子位置。

步驟6 更新外部檔案EXA=[POP;EXA]。

步驟7 重復步驟2～步驟6，直至滿足終止條件。

步驟8 輸出外部檔案EXA。

3 實驗

3.1 測試函數

為了檢驗算法的有效性，采用12個典型多模態多目標測試函數和1個多模態多目標實際問題[4,11]，分別為MMF1-MMF8、SYM-PART1、SYM-PART2、SYM-PART3、Omni-test、MPB。另外，為了進一步評估算法的性能，根據測試函數的設計方法[11]，設計3個具有不同難度的測試函數，其PS和PF分布情況如圖4所示。測試函數F1的表達式如下

(8)

該函數在決策空間的維度是2。決策變量x1和x2的取值范圍分別為-4≤x1≤4, -4≤x2≤4。在決策空間中存在4個不連續的PS。比具有連續PS的函數更難求解。同時，在目標空間中PF存在拐點(Knee point)，需要算法具有較高的收斂性。其PS和PF分布情況如圖4(a)、圖4(b)所示。

測試函數F2的表達式如下

(9)

該函數和測試函數F1在決策空間的維度、決策變量的取值范圍、PS個數均相同。在決策空間中PS分成15個片段，比函數F1多2個，因此增加了算法的尋優難度。其PS和PF分布情況如圖4(c)、圖4(d)所示。

測試函數F3的表達式如下

(10)

該函數在決策空間的維度是3。決策變量x1、x2、x3的取值范圍分別為-1≤x1≤1, 0≤x2≤1, 0≤x3≤1。在決策空間中存在8個PS。其PS和PF分布情況如圖4(e)、圖4(f)所示。該函數的變量維度和PS個數均增加，更具有挑戰性。

圖4 測試函數F1、F2、F3的PS和PF

3.2 實驗設計及參數設置

本文采用8個對比算法，分別為DE_RLRF[7]、RVEA-ADA[8]、TriMOEATA&R[9]、SSMOPSO[4]、MO_Ring_PSO_SCD[11]、MMOGA[10]、DN-NSGAII[7]、Omni-optimizer[19]。

對比算法參數保持與相應文獻一致的設置。所提算法參數設置如下：c1=c2=2.05，w=0.7298，nsize=5。所有算法種群規模N=800，最大迭代次數T=100，獨立運行30次[11]。此外，采用Wilcoxon秩和檢驗來判斷算法得到的結果是否具有顯著性差異。符號“+、=、-”分別表示所提算法顯著優于、相似于、差于對比算法。

3.3 性能指標

本文選取兩個性能指標對算法進行評價：

(1)帕累托解集近似性(PSP)[11]：衡量算法獲得的PS的多樣性和收斂性。PSP值越大，表明算法在決策空間中的性能越好。

(2)超體積(HV)[20,21]：評估算法獲得的PF的收斂性和多樣性。HV值越大，表明算法在目標空間中的性能越好。

3.4 實驗結果

3.4.1 策略性能對比

為了驗證所提策略的有效性，將所提算法與MOPSO(基本粒子群算法)[11]、NDPSO-I(僅采用鄰域驅動策略的MOPSO)和NDPSO-II(僅采用吸引機制的MOPSO)進行對比。表1顯示了不同策略下算法的平均值和標準差。

表1 各策略PSP性能結果對比

從表1可以看出，NDPSO-I和NDPSO-II的性能明顯優于MOPSO。原因是鄰域驅動策略通過構造多個不同的小生境，形成相對獨立的鄰域空間，引導粒子在鄰域內獨立進化，實現對多個最優解的同步搜索。吸收機制通過對鄰域信息的提取和利用，指導粒子向整個鄰域搜索，促進粒子對鄰域的深度開采，維持種群的進化動力。其次，NDPSO在所有測試函數上獲得較好的PSP值。從秩和檢驗上看，NDPSO的性能在統計意義上優于對比的算法。進一步表明所提策略的有機結合，協同地提高了粒子群算法的整體性能。

3.4.2 算法性能對比

本節從兩個角度對算法的性能進行比較。首先比較算法在決策空間中的性能。表2列出了不同算法在測試函數上的PSP值。如表2所示，NDPSO在所有測試函數上具有很高的PSP值，在決策空間中顯示出很好的性能。SSMOPSO的性能排第二。SSMOPSO根據物種形成原理，建立多個小生境，保持種群多樣性。MO_Ring_PSO_SCD的表現緊隨其后。MO_Ring_PSO_SCD采用環形拓撲結構和特殊擁擠距離，增強種群的開采能力。DE_RLRF在大多數測試函數上表現較好。DE_RLRF根據種群進化狀態，分配有效尋優策略，加快找到最優解的速度。Omni-optimizer和DN-NSGAII的性能接近，通過引入決策空間擁擠距離，提高解的分布性。TriMOEATA&R、RVEA-ADA、MMOGA的表現略差。TriMOEATA&R引入雙檔案重組機制，對維持解的多樣性起到促進作用。RVEA-ADA引導種群優化多個子問題，改善種群對最優區域的探索能力。MMOGA采用鄰域劃分策略，有利于找到更多的解。其次比較算法在目標空間中的性能。表3給出了不同算法在測試函數上的HV值。所提算法在MMF5函數上獲得了最優的HV值。RVEA-ADA在MPB上顯示較好的性能。TriMOEATA&R在SYM-PART1和F3上表現很好。MMOGA在2個測試函數上獲得了最高的HV值。DN-NSGAII在8個測試函數上獲得了最優的HV值。Omni-optimizer在F1和F2上性能較好。其實，所有算法在相同測試函數上獲得的HV值處于相同的數量級上，且接近于最優值。表明所有算法在目標空間中的表現相當。

表2 不同算法PSP性能結果對比

表3 不同算法HV性能結果對比

為了直觀地比較算法的性能，圖5和圖6分別給出了算法在F3上獲得的PS和PF。F3在三維決策空間中包含8個PS。從圖5可以看出，NDPSO能夠找到全部PS，且獲得的PS能夠均勻分布在真實PS上。DE_RLRF、TriMOEATA&R、SSMOPSO、MO_Ring_PSO_SCD找到的PS不完整，不能很好地使粒子布滿整個真實PS。RVEA-ADA、MMOGA、DN-NSGAII、Omni-optimizer獲得的PS分布性較差，基本上集中在PS的某一部分上。從圖6可以看出，所有算法在目標空間中獲得的PF相差不大，且均能覆蓋到整個真實PF上。總體來說，所提NDPSO算法在決策空間中能夠獲得分布性良好的解集。

圖5 不同算法所獲得的PS對比

圖6 不同算法所獲得的PF對比

3.4.3 算法收斂性比較

算法的收斂性是衡量算法性能的指標之一。選取F1來測試算法收斂性。F1在決策空間具有4個PS，每個PS是不連續的，優化難度較大。將決策空間劃分為4個面積相等的子區域，分別為區域1 {x1∈[-4,0],x2∈[0,4]}、區域2 {x1∈(0,4],x2∈[0, 4]}、區域3 {x1∈[-4,0],x2∈(-4,0]} 和區域4 {x1∈(0,4],x2∈[-4,0)}。每個子區域均包含一個PS。收斂性是指在每次迭代時種群分布在每個子區域中解的比例[11]。如果種群在每個子區域中解的比例均等于25%，表明算法具有良好的收斂性。

圖7為算法在每次迭代時的收斂性變化曲線。對于圖7(a)，隨著迭代次數越來越大，種群在每個區域中所的比例逐漸接近25%。在第50次迭代后，種群在每個區域中比例逐漸趨于平穩，最終穩定在25%。表明所提算法在收斂性能上表現良好。對于圖7(b)、圖7(f)，在第30次迭代后，區域1和區域3中解的比例大于區域2和區域4。表明DE_RLRF和MO_Ring_PSO_SCD在后期迭代中更側重于優化區域1和區域3。對于圖7(c)，在第80次迭代之后，區域3中解的比例略大于25%，而區域2中解的比例略小于25%。表明RVEA-ADA在后期優化中，更多的粒子在區域3中搜索最優解。對于圖7(d)、圖7(e)、圖7(h)、圖7(i)，每個區域的收斂曲線波動頻繁，且不穩定于25%。表明TriMOEATA&R、SSMOPSO、DN-NSGAII和Omni-optimizer的收斂性能較差。對于圖7(g)，在第40次迭代后，區域1和區域2中解的比例明顯大于區域3和區域4中解的比例。表明在迭代后期MMOGA更傾向于對區域1和區域2的探索。

圖7 不同算法的收斂性對比

基于以上分析，可得出所提算法的收斂性能優于其它比較算法。

3.4.4 實際應用

為了測試算法在工程問題上的求解能力，選擇一個經典的實際優化問題-基于地圖的優化問題(縮寫為MPB)進行實驗[4]。該問題在決策空間有3個不連續的PSs。將所提算法與其它8個算法進行對比。從表1的結果可以看出，所提算法在該問題上獲得PSP值高于其它對比算法。圖8給出了算法的獲得的PS情況。由圖8可見，所提算法在決策空間具有很好的多樣性，能夠獲得更多最優解。其它算法能夠找到一部分的解，但存在獲得的PS不完整。例如，MO_Ring_PSO_SCD能夠找到3個PS，但得到的最優解集在部分區域有缺失。MMOGA獲得的大多數最優解分布在真實PS的邊界處。綜上所述，所提算法在解決實際問題上是有效的。

圖8 不同算法在實際應用上獲得的PS對比

4 結束語

本文提出基于鄰域驅動的粒子群算法(NDPSO)。采用了鄰域驅動策略和吸收機制。鄰域驅動策略將整個種群劃分為多個不同的鄰域，粒子在自己的鄰域獨立進化，增強解在決策空間的分布。吸收策略通過學習鄰域潛在的有用信息，加強對鄰域最優解的開采能力，增大找到更高質量解的概率。同時為了全面評估算法性能，本文設計3個多模態多目標測試函數。通過和8個多模態多目標算法相比，表明NDPSO能夠提高解在決策空間的多樣性，且獲得的PS分布均勻。在未來的工作中，將MMOPs擴展到約束優化問題中，設計約束多模態多目標測試函數。