基于最小生成樹的粒子群優化算法

李國森，閆 李，朱小培，柳琳娜

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

0 引 言

在科學與工程領域中，大多數優化問題由多個相互沖突的目標組成，稱為多目標優化問題。在對其進行求解時，極難獲得一個能滿足所有目標取得最優的解。通常需要權衡相互沖突的目標，得到一組折衷的Pareto最優解集(pareto set，PS)[1]。PS對應的目標值組成Pareto前沿(pareto front，PF)。解決這類問題的關鍵是在目標空間中獲得分布性和收斂性好的PF。

另外一些多目標優化問題具有多模態特性，稱為多模態多目標問題[2]，諸如稀疏網絡優化[3]、建筑設計優化[4]。這些問題在決策空間中存在多個PS，對應目標空間中相同的PF，使算法在決策空間中有效找到多個分布性好的PS是研究該問題的重要課題之一[5]。

學者們相繼提出各種多模態多目標算法解決該類問題。Tanabe等[6]采用基于分解的思想，對每個子問題進行尋優，提高種群的多樣性。Qu等[7]在決策空間引入物種形成的方法。Li等[8]利用強化學習引導粒子動態調整進化方向，增強解在決策空間的多樣性。

盡管上述研究已經取得一定成果，但仍存在算法多樣性丟失、獲得的PS不均勻等不足。本文提出基于最小生成樹的粒子群優化算法。算法采用最小生成樹機制，提取種群的分布信息，構建多個鄰域，引導粒子獨立進化。同時使用擴散策略和調和平均距離，擴大種群搜索范圍，提高種群的分布性。

1 基本概念

1.1 多模態多目標問題

圖1給出了多模態多目標問題的示意圖[2,5]。在決策空間有兩條PS(分別為PS1和PS2)，均對應目標空間同一PF。PS1上的點A1和PS2上的點A2，均對應PF上的A′。將解決方案A1和A2均提供給決策者，有助于做出更合理的決策。

圖1 多模態多目標問題

1.2 最小生成樹

最小生成樹(minimum spanning tree，MST)是圖論中的一個概念[9]。圖可以表示為G=(V,E)， 其中集合V為頂點集，集合E為邊集[10]。對圖G中的邊，賦予一個實數w，稱為權。完全圖是指任意兩頂點均相鄰接的圖。最小生成樹是指各邊上權值之和最小的生成樹。

1.3 粒子群算法

由NP個粒子組成的種群在D維的決策空間中以速度V從當前位置X進行迭代尋優[11,12]。在第t次迭代，第i個粒子的速度Vi(t)和位置Xi(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)

其中，W是慣性權重，C1、C2表示學習因子，rand為[0,1]內的隨機變量。pbesti(t) 和nbesti(t) 分別為第t次迭代中第i個粒子的個體最優和全局最優。

2 基于最小生成樹的粒子群優化算法

2.1 最小生成樹機制

標準粒子群算法在迭代后期種群多樣性降低，甚至出現停滯的現象[13]。鑒于此，本文提出最小生成樹機制?；舅枷胧歉鶕Ｗ臃植紭嬙熳钚∩蓸洌瑯嫿Ｗ拥泥徲蜿P系，引導粒子在鄰域內進化。算法1給出了最小生成樹機制的偽代碼。

首先，計算權重。每個粒子視為圖中的一個頂點，記為vi(i∈{1,2,3,…,NP})。 每兩個粒子通過一條帶有權重的邊進行連接。連接第i個和第j個粒子的邊的權重計算如下

(3)

算法1的步驟(1)～步驟(8)給出了初始化圖的頂點集V、邊集E和粒子的鄰域表N的過程。其中，鄰域表用于記錄與每個粒子相連的粒子下標。初始化時，每個粒子的鄰域表中存儲本身粒子的下標。

其次，構造最小生成樹。最小生成樹的頂點集、邊集分別記為U、F。算法1的步驟(9)～步驟(16)描述了該構造過程。假設最小生成樹起點為v1。初始化時，頂點集U為v1，邊集F為空。選取具有最小權重的邊 (e,f)∈E(e∈U,f∈V-U)， 將頂點f和相連的邊(e,f)分別存儲在U、F中，同時更新相應粒子的鄰域表，重復上述步驟直至V-U=?。

最后，選擇鄰域最優nbest。每個粒子按照其對應的鄰域表，選出其相應的鄰域粒子，對鄰域粒子進行非支配排序，選擇最優的粒子作為nbest。

算法1：最小生成樹機制

(1) \*計算權重*\

(2)V←{};E←{};N←[];

(3) Fori=1 toNP

(4)V←V∪{vi};N(i)←i;

(5) Forj=1 toNP

(6)e←vi;f←vj;E←E∪{(e,f)we,f};

(7) EndFor

(8) EndFor

(9) \*構造最小生成樹*\

(10)U←{v1};F←{};

(11) WhileV-U≠?

(12) (vi,vj)←選取最小邊(e,f)∈E, 且e∈U,f∈V-U;

(13)U←U∪{vj};F←F∪{(vi,vj)};

(14) \*更新鄰域表*\

(15)N(i)←[N(i)j];N(j)←[N(j)i];

(16) EndWhile

(17) \*根據鄰域表選擇nbest*\

(18) Fork=1 toNP

(19)Temp←X(N(k),:); \*第k個粒子的鄰域解*\

(20)Sorted_Temp←對Temp采用非支配排序;

(21)nbestk←Sorted_Temp(1,:); \*選取鄰域最優*\

(22) EndFor

假設種群大小NP=5，種群包含5個粒子。圖2示例了一個最小生成樹機制的過程。

圖2 最小生成樹機制

如圖2(a)所示，圖中有5個頂點，分別為v1,v2,v3,v4,v5。每對不同的頂點通過一條帶有權重的邊進行連接，形成完全圖(圖2(b))。然后，在完全圖上建立最小生成樹(圖2(c))。同時每個粒子都維護一個鄰域表(圖2(d))。例如，在圖2(c)中，與頂點v1相連的只有頂點v3。對應的，在圖2(d)中，1號粒子的鄰域表大小為2，其鄰域是其自身和3號粒子。1號粒子只能與3號粒子進行信息交流，不能與其它粒子進行交流。換句話說，彼此相近的粒子可以互相交流信息，而距離較遠的粒子不會進行信息交流。因此整個種群劃分為多個子種群，每個子種群可以搜索相應鄰域內的最優解，有利于算法找到更多的解。

2.2 擴散策略

為了避免算法過早收斂，提高種群進化活力，本文提出擴散策略。一方面，在標準粒子群算法中，存在粒子的一部分維度逐漸逼近最優解，而另一部分維度逐漸遠離最優解的現象。另一方面，如果某個粒子的鄰域表過大，將導致粒子間信息交流過快，粒子快速收斂到某一最優解附近，喪失種群多樣性。因此，擴散策略的基本思想是：①學習鄰域粒子的維度信息，增強對鄰域開采能力；②采用萊維分布，使粒子擴散到更大的區域，提高種群多樣性。

Xi,d(t)=rnd·Xi,d(t)+(1-rnd)·Xj,d(t)+Levy(λ)·(2·rand-1)·(Xi,d(t)-Xj,d(t))

(4)

其中，rnd∈[0,1],j∈N(i),d∈{1,2,3,…,D},λ∈(1,3]。Levy(λ) 是服從萊維分布的隨機數[14]。在式(4)中，一方面，通過學習鄰域內粒子的維度信息，粒子的進化方向不再只受鄰域最優的影響，增強粒子對鄰域的深度搜索能力；另一方面，萊維分布具有長步長和短步長交替出現的特性[15]。其產生的長步長有助于粒子搜索更大的范圍，提高粒子對決策空間的廣度搜索能力。

2.3 調和平均距離

許多研究者提出了保持解在目標空間中多樣性的方法[16-18]。而在多模態多目標問題中，多個相距很遠的解所對應的目標值很接近。如果考慮解在目標空間中的擁擠程度，決策空間中多樣性好的解會被刪除。為了保證決策空間中解的分布性，本節引入基于決策空間的調和平均距離。

首先計算個體與其它k個個體間的歐式距離，記為d1，d2，…,dk。 然后計算該個體的調和平均距離dist，公式如下

(5)

2.4 算法步驟

輸入：種群大小NP，最大迭代次數MaxIter，學習因子C1、C2，問題維度D。

輸出：外部檔案EXA。

步驟1 初始化粒子群POP，建立外部檔案EXA=POP。

步驟2 根據最小生成樹機制建立鄰域，為每個粒子分配nbest。

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

步驟5 維護外部存檔EXA=[POP;EXA]。 根據調和平均距離計算存檔內個體的擁擠度，保留前NP個擁擠度小的解。

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

3 實驗與結果分析

3.1 測試函數

本文采用12個標準多模態多目標測試函數和一個多模態多目標實際優化問題[2,7],包括MMF1-MMF8、SYM-PART1、SYM-PART2、SYM-PART3、Omni-test和MPB。

3.2 實驗設計及參數設置

本文采用8個對比算法，包括DE_RLRF[8]、RVEA-ADA[6]、TriMOEATA&R[4]、SSMOPSO[7]、MO_Ring_PSO_SCD[2]、MMOGA[19]、DN-NSGAII[7]、Omni-optimizer[20]。

算法參數設置如下：C1=C2=2.05，W=0.7298。種群大小NP=800，最大迭代次數MaxIter=100，獨立運行25次[7]。此外,采用秩和檢驗來比較所提算法和對比算法的顯著性差異。符號“+、-、=”表示在統計意義上所提算法分別優于、差于、等于對比算法。

3.3 評價指標

為了評價算法的性能采用以下兩種指標：

(1)帕累托解集近似性(PSP)[2]：評估算法在決策空間中所獲得PS的多樣性和收斂性。其值越大，說明算法在決策空間的性能越好；

(2)超體積(HV)[21]：度量算法在目標空間中所獲得PF的收斂性。其值越大，說明算法得到的PF在目標空間中越接近真實PF。

3.4 實驗結果與分析

3.4.1 各策略性能對比實驗

為了考察所提策略的有效性，將MSTPSO與MOPSO(基本的粒子群算法)[2]、MSTPSO-I(僅采用最小生成樹機制的MOPSO算法)、MSTPSO-II(僅采用擴散策略的MOPSO算法)和MSTPSO-III(僅采用調和平均距離的MOPSO算法)進行比較。PSP性能指標的平均值和標準差見表1。

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

從表1中可知，MSTPSO-I在所有測試問題上優于MOPSO。表明最小生成樹機制能夠提高基本粒子群算法的性能。最小生成樹機制通過發現種群粒子的分布，進而構建多個鄰域，引導粒子在不同的鄰域內進化，有利于找到更多分布性好的解。其次，MSTPSO-II算法的性能優于MOPSO算法。表明擴散策略在提升粒子群算法的性能方面起到了積極作用。擴散策略通過學習鄰域其它粒子的信息，指導粒子的搜索方向，提高算法的搜索活力。再次，MSTPSO-III的性能略優于MOPSO。表明調和平均距離能夠改善算法尋優性能。調和平均距離可以度量粒子在決策空間的擁擠程度，通過保留多樣性好的粒子，保證了種群具有較好的分布。此外，MSTPSO算法的性能優于對比的4個算法，表明所提策略的結合提高了粒子群算法的尋優性能。

3.4.2 不同算法性能對比實驗

首先比較算法在決策空間中尋優性能。表2列出了所有算法在13個測試問題上的PSP指標的均值和標準差。從表2可以看出，相比于其它算法，MSTPSO在13個測試問題中獲得了較好的PSP值。其次是SSMOPSO算法，該算法采用物種形成的方法形成多個小生境，提高了算法在決策空間中獲得更多解的能力。然后是MO_Ring_PSO_SCD算法，該算法采用環形拓撲建立多個鄰域，提高了種群在決策空間的多樣性。DE_RLRF表現緊隨其后。該算法采用強化學習指導種群按照不同的策略進化尋優，有助于快速找到多個解。DN-NSGAII和Omni-optimizer表現接近，兩者均通過衡量解在決策空間的擁擠度，增強了種群在決策空間的分布性。然后依次是TriMOEATA&R、RVEA-ADA、MMOGA。TriMOEATA&R采用雙檔案策略保持多樣性和收斂性的解，改善了算法的求解能力。RVEA-ADA采用分解的方法保持解的多樣性，對定位更多的解起到了積極作用。MMOGA采用遺傳算法框架，將種群劃分多個小生境以引導粒子進化，在一定程度上提高了算法的性能。其次比較算法在目標空間中的尋優性能。表3給出了算法在測試問題上獲得的HV值。可以看出，所有算法在同一測試問題上獲得的HV值彼此接近。表明所有算法在目標空間中的性能相近。

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

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

為了更加直觀地比較算法的性能，圖3和圖4分別繪制了算法在Omni-test上得到的PS和PF情況。從圖3可知，MSTPSO能夠找到所有的27個PS。DE_RLRF、RVEA-ADA、SSMOPSO、MO_Ring_PSO_SCD能夠找到更多的解，但獲得的PS不完整。TriMOEATA&R能夠找到26個PS。MMOGA、DN-NSGAII、Omni-optimizer僅找到其中的幾個PS。從圖4可知，所有算法取得了分布性較好的PF。由此說明，在不影響目標空間性能的前提下，MSTPSO在決策空間能夠取得較好的結果。

3.4.3 算法收斂性對比實驗

為了考察算法的收斂性[2]，本節將所有算法在測試問題MMF7上進行比較。MMF7在決策空間有兩個PS，每個PS是不規則的形狀，求解難度較大。如圖5所示,將決策空間劃分為兩個面積相等的子區域，分別是區域1和區域2。每個子區域各有一個PS。收斂性是每一次迭代時種群分布在子區域中所占的比例。理論上，假設算法在該測試問題上收斂性好，則兩個子區域的解的比例相等，均為50%。

圖6繪制了在100次迭代過程中收斂性變化曲線。從圖6(a)可以看出，區域1中解的比例隨迭代次數逐漸增加，而區域2中解的比例逐漸降低。在迭代次數接近70時，區域1和區域2的解的比例接近0.5，而后逐漸穩定于0.5。表明MSTPSO能夠很好的收斂到每一個PS，具有較好的收斂性能。從圖6(b)可知，在迭代后期，區域1和區域2中的解的比例逐漸趨于0.5。但是在迭代結束時，區域1的解的比例略大于區域2的比例。說明DE_RLRF的收斂性略差于MSTPSO。從圖6(c)可觀察到，在第10次迭代后，區域1中解的比例基本上大于區域2的解的比例。表明RVEA-ADA在指導種群進化時，更傾向搜索區域1。對于圖6(d)，在迭代后期，區域1中解的比例小于區域2的解的比例。表明TriMOEATA&R的收斂性較弱。對于圖6(e)，在第90次迭代后，區域1的解的比例大于區域2的解的比例。表明SSMOPSO在該測試問題上收斂性能較差。從圖6(f)、圖6(h)可以看出，在第95次迭代后，區域2的解的比例大于區域1的解的比例。表明MO_Ring_PSO_SCD和DN-NSGAII的收斂性能較差。對于圖6(g)、圖6(i)，在第30次迭代后，區域1的解的比例大于區域2的解的比例。表明MMOGA和Omni-optimizer算法在優化過程中，種群更容易聚集在區域1。綜上，MSTPSO算法的收斂性較好。

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

3.4.4 實際應用

為了進一步考察算法的性能，將所有算法應用于一個實際優化問題-基于地圖的問題(縮寫為MPB)[7]。該問題在決策空間有3個不連續的PS，如圖7所示。

圖5 測試函數MMF7的PSs分布

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

圖7 實際應用MPB的PSs分布

首先，由表2可知，MSTPSO在該問題上能夠獲得較高的PSP值。其次，圖8給出了所有算法在該問題上獲得的PS情況。對于圖8(a)，MSTPSO能夠獲得3個PS，且獲得的PS較全面的覆蓋真實的PS。對于圖8(e)、圖8(f)，SSMOPSO、MO_Ring_PSO_SCD能夠找到更多的解。對于其它6個算法，算法獲得的解較少。特別地，DE_RLRF僅找到的一個PS。綜上，MSTPSO在求解實際問題上是有效的。

圖8 算法獲得的PS情況對比

4 結束語

本文提出基于最小生成樹的粒子群優化算法(MSTPSO)。算法采用最小生成樹機制、擴散策略、調和平均距離。最小生成樹機制建立多個不同的鄰域，粒子在鄰域交流信息并獨立進化，提高種群在決策空間的多樣性。擴散策略可以綜合學習鄰域粒子的信息，促使粒子在更大的空間范圍內搜索。調和平均距離用于度量解在決策空間的擁擠程度，提高解的分布性。通過對比8個算法，驗證了MSTPSO在決策空間中具有很好的性能。下一步工作將提出更復雜的測試問題。