基于最小生成樹(shù)的粒子群優(yōu)化算法

李國(guó)森，閆 李，朱小培，柳琳娜

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

0 引 言

在科學(xué)與工程領(lǐng)域中，大多數(shù)優(yōu)化問(wèn)題由多個(gè)相互沖突的目標(biāo)組成，稱為多目標(biāo)優(yōu)化問(wèn)題。在對(duì)其進(jìn)行求解時(shí)，極難獲得一個(gè)能滿足所有目標(biāo)取得最優(yōu)的解。通常需要權(quán)衡相互沖突的目標(biāo)，得到一組折衷的Pareto最優(yōu)解集(pareto set，PS)[1]。PS對(duì)應(yīng)的目標(biāo)值組成Pareto前沿(pareto front，PF)。解決這類問(wèn)題的關(guān)鍵是在目標(biāo)空間中獲得分布性和收斂性好的PF。

另外一些多目標(biāo)優(yōu)化問(wèn)題具有多模態(tài)特性，稱為多模態(tài)多目標(biāo)問(wèn)題[2]，諸如稀疏網(wǎng)絡(luò)優(yōu)化[3]、建筑設(shè)計(jì)優(yōu)化[4]。這些問(wèn)題在決策空間中存在多個(gè)PS，對(duì)應(yīng)目標(biāo)空間中相同的PF，使算法在決策空間中有效找到多個(gè)分布性好的PS是研究該問(wèn)題的重要課題之一[5]。

學(xué)者們相繼提出各種多模態(tài)多目標(biāo)算法解決該類問(wèn)題。Tanabe等[6]采用基于分解的思想，對(duì)每個(gè)子問(wèn)題進(jìn)行尋優(yōu)，提高種群的多樣性。Qu等[7]在決策空間引入物種形成的方法。Li等[8]利用強(qiáng)化學(xué)習(xí)引導(dǎo)粒子動(dòng)態(tài)調(diào)整進(jìn)化方向，增強(qiáng)解在決策空間的多樣性。

盡管上述研究已經(jīng)取得一定成果，但仍存在算法多樣性丟失、獲得的PS不均勻等不足。本文提出基于最小生成樹(shù)的粒子群優(yōu)化算法。算法采用最小生成樹(shù)機(jī)制，提取種群的分布信息，構(gòu)建多個(gè)鄰域，引導(dǎo)粒子獨(dú)立進(jìn)化。同時(shí)使用擴(kuò)散策略和調(diào)和平均距離，擴(kuò)大種群搜索范圍，提高種群的分布性。

1 基本概念

1.1 多模態(tài)多目標(biāo)問(wèn)題

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

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

1.2 最小生成樹(shù)

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

1.3 粒子群算法

由NP個(gè)粒子組成的種群在D維的決策空間中以速度V從當(dāng)前位置X進(jìn)行迭代尋優(yōu)[11,12]。在第t次迭代，第i個(gè)粒子的速度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是慣性權(quán)重，C1、C2表示學(xué)習(xí)因子，rand為[0,1]內(nèi)的隨機(jī)變量。pbesti(t) 和nbesti(t) 分別為第t次迭代中第i個(gè)粒子的個(gè)體最優(yōu)和全局最優(yōu)。

2 基于最小生成樹(shù)的粒子群優(yōu)化算法

2.1 最小生成樹(shù)機(jī)制

標(biāo)準(zhǔn)粒子群算法在迭代后期種群多樣性降低，甚至出現(xiàn)停滯的現(xiàn)象[13]。鑒于此，本文提出最小生成樹(shù)機(jī)制?；舅枷胧歉鶕?jù)粒子分布構(gòu)造最小生成樹(shù)，構(gòu)建粒子的鄰域關(guān)系，引導(dǎo)粒子在鄰域內(nèi)進(jìn)化。算法1給出了最小生成樹(shù)機(jī)制的偽代碼。

首先，計(jì)算權(quán)重。每個(gè)粒子視為圖中的一個(gè)頂點(diǎn)，記為vi(i∈{1,2,3,…,NP})。 每?jī)蓚€(gè)粒子通過(guò)一條帶有權(quán)重的邊進(jìn)行連接。連接第i個(gè)和第j個(gè)粒子的邊的權(quán)重計(jì)算如下

(3)

算法1的步驟(1)～步驟(8)給出了初始化圖的頂點(diǎn)集V、邊集E和粒子的鄰域表N的過(guò)程。其中，鄰域表用于記錄與每個(gè)粒子相連的粒子下標(biāo)。初始化時(shí)，每個(gè)粒子的鄰域表中存儲(chǔ)本身粒子的下標(biāo)。

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

最后，選擇鄰域最優(yōu)nbest。每個(gè)粒子按照其對(duì)應(yīng)的鄰域表，選出其相應(yīng)的鄰域粒子，對(duì)鄰域粒子進(jìn)行非支配排序，選擇最優(yōu)的粒子作為nbest。

算法1：最小生成樹(shù)機(jī)制

(1) \*計(jì)算權(quán)重*\

(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) \*構(gòu)造最小生成樹(shù)*\

(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) \*根據(jù)鄰域表選擇nbest*\

(18) Fork=1 toNP

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

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

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

(22) EndFor

假設(shè)種群大小NP=5，種群包含5個(gè)粒子。圖2示例了一個(gè)最小生成樹(shù)機(jī)制的過(guò)程。

圖2 最小生成樹(shù)機(jī)制

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

2.2 擴(kuò)散策略

為了避免算法過(guò)早收斂，提高種群進(jìn)化活力，本文提出擴(kuò)散策略。一方面，在標(biāo)準(zhǔn)粒子群算法中，存在粒子的一部分維度逐漸逼近最優(yōu)解，而另一部分維度逐漸遠(yuǎn)離最優(yōu)解的現(xiàn)象。另一方面，如果某個(gè)粒子的鄰域表過(guò)大，將導(dǎo)致粒子間信息交流過(guò)快，粒子快速收斂到某一最優(yōu)解附近，喪失種群多樣性。因此，擴(kuò)散策略的基本思想是：①學(xué)習(xí)鄰域粒子的維度信息，增強(qiáng)對(duì)鄰域開(kāi)采能力；②采用萊維分布，使粒子擴(kuò)散到更大的區(qū)域，提高種群多樣性。

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(λ) 是服從萊維分布的隨機(jī)數(shù)[14]。在式(4)中，一方面，通過(guò)學(xué)習(xí)鄰域內(nèi)粒子的維度信息，粒子的進(jìn)化方向不再只受鄰域最優(yōu)的影響，增強(qiáng)粒子對(duì)鄰域的深度搜索能力；另一方面，萊維分布具有長(zhǎng)步長(zhǎng)和短步長(zhǎng)交替出現(xiàn)的特性[15]。其產(chǎn)生的長(zhǎng)步長(zhǎng)有助于粒子搜索更大的范圍，提高粒子對(duì)決策空間的廣度搜索能力。

2.3 調(diào)和平均距離

許多研究者提出了保持解在目標(biāo)空間中多樣性的方法[16-18]。而在多模態(tài)多目標(biāo)問(wèn)題中，多個(gè)相距很遠(yuǎn)的解所對(duì)應(yīng)的目標(biāo)值很接近。如果考慮解在目標(biāo)空間中的擁擠程度，決策空間中多樣性好的解會(huì)被刪除。為了保證決策空間中解的分布性，本節(jié)引入基于決策空間的調(diào)和平均距離。

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

(5)

2.4 算法步驟

輸入：種群大小NP，最大迭代次數(shù)MaxIter，學(xué)習(xí)因子C1、C2，問(wèn)題維度D。

輸出：外部檔案EXA。

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

步驟2 根據(jù)最小生成樹(shù)機(jī)制建立鄰域，為每個(gè)粒子分配nbest。

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

步驟5 維護(hù)外部存檔EXA=[POP;EXA]。 根據(jù)調(diào)和平均距離計(jì)算存檔內(nèi)個(gè)體的擁擠度，保留前NP個(gè)擁擠度小的解。

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

3 實(shí)驗(yàn)與結(jié)果分析

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

本文采用12個(gè)標(biāo)準(zhǔn)多模態(tài)多目標(biāo)測(cè)試函數(shù)和一個(gè)多模態(tài)多目標(biāo)實(shí)際優(yōu)化問(wèn)題[2,7],包括MMF1-MMF8、SYM-PART1、SYM-PART2、SYM-PART3、Omni-test和MPB。

3.2 實(shí)驗(yàn)設(shè)計(jì)及參數(shù)設(shè)置

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

算法參數(shù)設(shè)置如下：C1=C2=2.05，W=0.7298。種群大小NP=800，最大迭代次數(shù)MaxIter=100，獨(dú)立運(yùn)行25次[7]。此外,采用秩和檢驗(yàn)來(lái)比較所提算法和對(duì)比算法的顯著性差異。符號(hào)“+、-、=”表示在統(tǒng)計(jì)意義上所提算法分別優(yōu)于、差于、等于對(duì)比算法。

3.3 評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)算法的性能采用以下兩種指標(biāo)：

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

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

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

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

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

表1 各策略PSP性能結(jié)果對(duì)比

從表1中可知，MSTPSO-I在所有測(cè)試問(wèn)題上優(yōu)于MOPSO。表明最小生成樹(shù)機(jī)制能夠提高基本粒子群算法的性能。最小生成樹(shù)機(jī)制通過(guò)發(fā)現(xiàn)種群粒子的分布，進(jìn)而構(gòu)建多個(gè)鄰域，引導(dǎo)粒子在不同的鄰域內(nèi)進(jìn)化，有利于找到更多分布性好的解。其次，MSTPSO-II算法的性能優(yōu)于MOPSO算法。表明擴(kuò)散策略在提升粒子群算法的性能方面起到了積極作用。擴(kuò)散策略通過(guò)學(xué)習(xí)鄰域其它粒子的信息，指導(dǎo)粒子的搜索方向，提高算法的搜索活力。再次，MSTPSO-III的性能略優(yōu)于MOPSO。表明調(diào)和平均距離能夠改善算法尋優(yōu)性能。調(diào)和平均距離可以度量粒子在決策空間的擁擠程度，通過(guò)保留多樣性好的粒子，保證了種群具有較好的分布。此外，MSTPSO算法的性能優(yōu)于對(duì)比的4個(gè)算法，表明所提策略的結(jié)合提高了粒子群算法的尋優(yōu)性能。

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

首先比較算法在決策空間中尋優(yōu)性能。表2列出了所有算法在13個(gè)測(cè)試問(wèn)題上的PSP指標(biāo)的均值和標(biāo)準(zhǔn)差。從表2可以看出，相比于其它算法，MSTPSO在13個(gè)測(cè)試問(wèn)題中獲得了較好的PSP值。其次是SSMOPSO算法，該算法采用物種形成的方法形成多個(gè)小生境，提高了算法在決策空間中獲得更多解的能力。然后是MO_Ring_PSO_SCD算法，該算法采用環(huán)形拓?fù)浣⒍鄠€(gè)鄰域，提高了種群在決策空間的多樣性。DE_RLRF表現(xiàn)緊隨其后。該算法采用強(qiáng)化學(xué)習(xí)指導(dǎo)種群按照不同的策略進(jìn)化尋優(yōu)，有助于快速找到多個(gè)解。DN-NSGAII和Omni-optimizer表現(xiàn)接近，兩者均通過(guò)衡量解在決策空間的擁擠度，增強(qiáng)了種群在決策空間的分布性。然后依次是TriMOEATA&R、RVEA-ADA、MMOGA。TriMOEATA&R采用雙檔案策略保持多樣性和收斂性的解，改善了算法的求解能力。RVEA-ADA采用分解的方法保持解的多樣性，對(duì)定位更多的解起到了積極作用。MMOGA采用遺傳算法框架，將種群劃分多個(gè)小生境以引導(dǎo)粒子進(jìn)化，在一定程度上提高了算法的性能。其次比較算法在目標(biāo)空間中的尋優(yōu)性能。表3給出了算法在測(cè)試問(wèn)題上獲得的HV值?？梢钥闯?，所有算法在同一測(cè)試問(wèn)題上獲得的HV值彼此接近。表明所有算法在目標(biāo)空間中的性能相近。

表2 不同算法PSP性能結(jié)果對(duì)比

表3 不同算法HV性能結(jié)果對(duì)比

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

3.4.3 算法收斂性對(duì)比實(shí)驗(yàn)

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

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

圖4 不同算法所獲得的PF對(duì)比

3.4.4 實(shí)際應(yīng)用

為了進(jìn)一步考察算法的性能，將所有算法應(yīng)用于一個(gè)實(shí)際優(yōu)化問(wèn)題-基于地圖的問(wèn)題(縮寫(xiě)為MPB)[7]。該問(wèn)題在決策空間有3個(gè)不連續(xù)的PS，如圖7所示。

圖5 測(cè)試函數(shù)MMF7的PSs分布

圖6 不同算法的收斂性對(duì)比

圖7 實(shí)際應(yīng)用MPB的PSs分布

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

圖8 算法獲得的PS情況對(duì)比

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

本文提出基于最小生成樹(shù)的粒子群優(yōu)化算法(MSTPSO)。算法采用最小生成樹(shù)機(jī)制、擴(kuò)散策略、調(diào)和平均距離。最小生成樹(shù)機(jī)制建立多個(gè)不同的鄰域，粒子在鄰域交流信息并獨(dú)立進(jìn)化，提高種群在決策空間的多樣性。擴(kuò)散策略可以綜合學(xué)習(xí)鄰域粒子的信息，促使粒子在更大的空間范圍內(nèi)搜索。調(diào)和平均距離用于度量解在決策空間的擁擠程度，提高解的分布性。通過(guò)對(duì)比8個(gè)算法，驗(yàn)證了MSTPSO在決策空間中具有很好的性能。下一步工作將提出更復(fù)雜的測(cè)試問(wèn)題。