基于鄰域驅(qū)動的粒子群算法

(7)

圖3示例了吸收機(jī)制。鄰域1和鄰域2的搜索范圍用虛線給出。相比于鄰域2，鄰域1的搜索范圍較大?？梢圆捎檬?7)對鄰域內(nèi)的粒子進(jìn)行更新。一方面，式(7)對鄰域內(nèi)所有粒子的信息進(jìn)行了綜合學(xué)習(xí)，促進(jìn)鄰域中優(yōu)秀信息的流動，增強(qiáng)種群對鄰域的搜索能力；另一方面，萊維分布兼顧小范圍的開采和大范圍的勘探[17,18]，能夠更全面搜索整個鄰域，避免陷入局部區(qū)域。

圖3 吸收機(jī)制

2.3 算法流程

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

步驟2 根據(jù)鄰域驅(qū)動策略劃分鄰域，為每個粒子分配nbest。

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

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

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

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

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

步驟8 輸出外部檔案EXA。

3 實 驗

3.1 測試函數(shù)

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

(8)

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

測試函數(shù)F2的表達(dá)式如下

(9)

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

測試函數(shù)F3的表達(dá)式如下

(10)

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

圖4 測試函數(shù)F1、F2、F3的PS和PF

3.2 實驗設(shè)計及參數(shù)設(shè)置

本文采用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]。

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

3.3 性能指標(biāo)

本文選取兩個性能指標(biāo)對算法進(jìn)行評價：

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

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

3.4 實驗結(jié)果

3.4.1 策略性能對比

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

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

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

3.4.2 算法性能對比

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

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

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

為了直觀地比較算法的性能，圖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可以看出，所有算法在目標(biāo)空間中獲得的PF相差不大，且均能覆蓋到整個真實PF上?？傮w來說，所提NDPSO算法在決策空間中能夠獲得分布性良好的解集。

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

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

3.4.3 算法收斂性比較

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

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

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

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

3.4.4 實際應(yīng)用

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

圖8 不同算法在實際應(yīng)用上獲得的PS對比

4 結(jié)束語

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