基于鄰域速度模仿策略的粒子群算法

鄧 浩，李均利，胡 凱

(四川師范大學 計算機科學學院，四川 成都 610101)

0 引 言

粒子群算法(PSO)是Kennedy和Eberhart提出的一種進化計算方法，是通過模仿鳥群在覓食過程中的遷徙和聚集提出的一種基于群體智能的全局隨機搜索算法。算法簡單、易于實現，沒有過多參數的調節，在科學研究和工程實踐中受到了廣泛關注以及成功應用。但和許多其它群智能優化算法類似，傳統的PSO算法存在易陷入局部最優、收斂速度慢等問題。

進化算法中的進化直接表現為個體位置的變化，而在PSO算法中粒子位置的更新依賴于粒子速度。因此，很多研究者對PSO算法中的粒子速度更新方式進行了深入的研究，大體可以分為3類：第一類是調整PSO的參數，如Tanweer等提出一種自調節PSO算法，利用對個體適應值優劣的感知來調整慣性權重w[1]。Liang等提出一種非線性動態改變慣性權重的策略[2],通過平均粒子間距更新慣性權重；第二類是改變粒子鄰域拓撲結構，如李文斌等提出鄰域結構為復雜網絡的粒子群算法[3]，在粒子與網絡節點間建立映射關系,并根據節點的鄰居集合獲得粒子的動態飛行鄰居；薛文等提出分群策略的混沌粒子群優化算法[4],將種群分為迭代分群和混沌機制迭代分群，依據早熟判定策略，對種群實行兩階段尋優；第三類是引入其它策略，如Ouyang等引入和聲搜索提出了具有全局選擇策略的和聲搜索粒子群算法[5],Cheng和Jin引入社會學習機制提出了一種社會學習粒子群算法[6]。

本文提出了一種基于鄰域速度模仿策略的粒子群算法(imitate neighborhood velocity PSO，INVPSO)，在標準PSO算法的基礎上，讓粒子以一定的概率直接模仿鄰域內最優粒子的速度，自適應地調整粒子收斂情況；然后，對排名靠后的粒子以一定的概率進行質心變異以增強算法跳出局部極值的能力。

1 PSO

1.1 基本PSO算法

1995年Kennedy和Eberhart提出了基本PSO算法。N個粒子組成的種群在大小為D維的空間中以速度V飛行，一個粒子位置代表一個潛在解。每個粒子在每次迭代過程中，通過速度來更新位置X，每個位置代表的坐標值輸入到目標函數中會得到一個函數值，由這個函數值可以得到粒子位置的適應值。在飛行的過程中，粒子利用個體經歷過的最優適應值pb和群體經歷過的最優適應值gb來調整自己的飛行速度，經過若干次迭代得到最終解。

基本PSO算法的速度和位置更新公式如下

Vi,d=Vi,d+c1rand1(pbi,d-Xi,d)+c2rand2(gbi,d-Xi,d)

(1)

Xi,d=Xi,d+Vi,d

(2)

其中,Vi,d表示第i個粒子的第d維，c1、c2為學習因子，分別調節對個體經驗和群體經驗的學習率，rand1、rand2為(0,1)之間的隨機變量。pbi,d、gbi,d、Xi,d分別表示第i個粒子歷史最優值第d維、全局歷史最優值第d維、第i個粒子位置第d維。

1.2 PSO算法

1998年Shi和Eberhart將慣性權重概念引入基本PSO算法，將粒子速度更新式(1)修正為

Vi,d=wVi,d+c1rand1(pbi,d-Xi,d)+c2rand2(gbi,d-Xi,d)

(3)

其中，w稱為慣性權重，用于調節粒子當前速度對新速度的影響，合適的w能夠使粒子在保持運動慣性的同時進一步擴展搜索空間。

隨著迭代次數線性減小，其更新公式如下

(4)

其中，wmax表示w的最大值，wmin表示w的最小值，t表示當前迭代的次數，tmax表示最大迭代次數。通常設置wmax=0.9，wmin=0.4。

2 INVPSO

粒子群算法中一個重要的問題是如何指導粒子向更優點運動，式(3)使用歷史速度、個體歷史最優點和全局歷史最優點信息來更新粒子速度。有研究指出，在進化算法中，差分方法提供了類似梯度的信息，在粒子間距較大時，更新前后適應度的變化并不能很好描述梯度信息來指導算法的搜索，但是在粒子距離較近時，這類信息就能給出很好的指導[7]。和差分方法類似，鄰域最優粒子的速度也提供類似于梯度的信息，在粒子間距較大時，因為粒子距離較遠，鄰域最優粒子的速度并不能很好描述梯度信息來指導算法的搜索，但是在粒子距離較近時，這類信息就能給出很好的指導。同時，相比于差分中粒子位置提供梯度信息，速度項本身還包含了更新速度時涉及到的個體歷史信息和全局最優的信息。

2.1 鄰域速度模仿策略

對鄰域內的鄰居粒子，比較位置更新前后的適應值，選擇向著更優方向前進最多的粒子按一定概率在各個維度模仿其速度。

最優鄰域粒子速度的選擇

(5)

這里可以模仿的速度可以是式(3)更新前的舊速度或者更新后的新速度，而因為新速度在更新的過程中，因為受到本輪迭代歷史速度、個體歷史最優、全局歷史最優的影響，所以包含更多的信息。

速度模仿

(6)

其中，Vi,d表示第i個粒子第d維速度，rand表示(0,1)之間的隨機數，Vbi,d表示第i個粒子鄰域最優粒子速度的第d維。

當模仿對象速度指向當前粒子適應值減方向，則模仿行為會加速粒子向當前局部極值運動。當模仿對象速度指向當前粒子適應值增方向，則模仿行為會使粒子遠離當前局部極值。為了說明鄰域速度模仿策略思想，以下針對求最小值問題進行分析，因為最大值問題取負即可變為最小值問題，所以以下分析對最大值問題同樣成立。

情況1：當前粒子如果和模仿目標在同一個單調區間，并且目標速度指向谷底(即當前局部極值)，則模仿行為會加速粒子向當前局部極值運動；如果目標速度指向谷底反方向，則模仿行為會使粒子遠離當前局部極值或者減弱趨向極值的速度。前一種情況更容易出現在求解后期，后一種情況更容易出現在求解前期。

情況2：當前粒子如果和模仿目標在不同單調區間，則不管在前期、后期，目標速度提供的梯度信息和當前粒子無關，模仿其行為相當于隨機變異。而在前期，粒子和目標在不同單調區間的概率大于后期粒子和目標在不同單調區間的概率。

粒子位置更新前后的適應值變化提供了一定的梯度信息，而與位置更新有關的速度項則提供了梯度方向信息。因為在前期，粒子均勻分布在搜索空間中，互相之間距離較大，在后期，粒子收斂到一些局部地區，互相之間距離較小，所以模仿速度這一策略，利用速度提供的梯度信息，在前期更容易出現情況1，粒子鄰域的速度提供了較大范圍內適應值的變化信息，模仿其速度使粒子在向全局最優方向前進的同時也保持種群的多樣性；在后期更容易出現情況2，粒子鄰域的速度提供了較小范圍內適應值的變化信息，模仿其速度使粒子向極值方向加速收斂，并且保持一定的種群多樣性。

綜上所述，鄰域速度模仿策略能根據鄰域粒子的情況自適應地調整粒子收斂情況。在前期粒子間距較大時更可能給粒子隨機的擾動，增強跳出局部極值的能力；在后期粒子間距較小時能加速粒子向最優點收斂。

2.2 鄰域策略

本文使用動態鄰居拓撲結構，在每次迭代中根據各個粒子的位置，選擇離目標粒子最近的K個粒子作為其鄰居。

粒子xi和粒子xj的距離di,j采用歐氏距離

(7)

2.3 變異策略

在質心法[8]的基礎上，采用質心變異策略，對當前粒子，另外隨機選取兩個粒子，將當前粒子遷移到3個粒子的質心周圍。

在具體計算時，針對目標粒子目標維度，與其它隨機兩粒子對應維度求和取平均，然后再乘以一個(0,1)之間的隨機數

(8)

其中，xr2，xr3表示另外隨機選取的兩個粒子。

2.4 模仿和變異發生條件

隨著算法的迭代，粒子向最優點收斂， 在前期，要讓粒子擴展搜索范圍以跳出局部極值點，在后期，要讓粒子加速收斂以提高收斂速度和精度。所以模仿和變異發生的概率要隨著迭代次數的增加而減小。本文以式(4)定義的線性慣性權重為參考，設計了隨著迭代次數增加而減小的模仿和變異發生概率條件

rand

(9)

對所有的粒子都按式(9)設定模仿行為發生的概率。對于適應值排名靠后粒子按式(9)設定變異發生的概率，適應值排名靠后以各粒子均值為參照，對適應值大于0.8倍均值的粒子施加變異。

2.5 邊界策略

當位置超過邊界時，采用隨機回退策略，讓粒子退回到超出的邊界附近1/4取值范圍內

(10)

其中，xi,d表示第i個粒子的第d維坐標，ld表示第d維的取值下限，ud表示第d維的取值上限。

當速度超過限制時，則速度保持在邊界

(11)

其中，Vi,d表示第i個粒子的第d維速度，Vmin表示速度的取值下限，取Vmin=-0.01(ud-ld)，Vmax表示速度的取值上限,取Vmax=0.01(ud-ld)。

2.6 位置更新策略

比較位置更新前后的適應度變化，若更新后適應值沒有優于原位置，則返回原位置

(12)

其中，f(xi)表示第i個粒子的位置的適應值，f(xi+vi)表示第i個粒子的位置加上其速度vi之后位置的適應值。

2.7 算法步驟

輸入：種群規模N，學習率c1、c2,慣性權重最大值最小值wmax、wmin,最大迭代次數M，維度D,搜索空間(l,u)，鄰域大小k。

輸出：最優解

步驟1 隨機初始化粒子群和速度，評估個體適應值，迭代器item=0；

步驟2 while(item

步驟3 按式(4)更新權重w，按式(3)更新速度；

步驟4 更新全局最優、個體歷史最優、鄰居表、各粒子適應值均值fmean；

步驟5 比較每個粒子位置更新前后適應度的變化趨勢，按式(5)確定每個粒子在k鄰域大小內的最優鄰居粒子；

步驟6 對每個粒子的每個維度，如果rand(0,1)

步驟7 對每個粒子,如果f(xi)>0.8fmean，則：

對該粒子的每個維度，如果rand(0,

1)

步驟8 按式(10)和式(11)對位置和速度進行超限處理；

步驟9 按式(12)評估粒子適應度值，更新粒子位置；

步驟10item++；

步驟11 END while；

步驟12 輸出最優解。

3 實驗結果及分析

3.1 測試函數

實驗采用表1所示的函數，其中f1-f5是單峰函數，主要用來測試尋優精度，f6-f13為多峰函數，具有很多局部極值點，可以檢驗全局搜索性能和跳出局部極值的能力。所有函數的最優值都為0，搜索范圍為(-100，100)。

3.2 有鄰域速度模仿和無鄰域速度模仿的對比

本小節對比了有鄰域速度模仿策略和無鄰域速度模仿策略(即算法步驟6條件改為ifrand>1)，最大迭代次數M=1000，種群規模N=100，搜索空間維D=30,鄰域大小取k=10,重復30次結果見表2，結果“+”表示在該函數上有鄰域速度模仿策略優于無鄰域速度模仿策略，結果“-”表示有鄰域速度模仿策略劣于無鄰域速度模仿策略，結果“=”表示有鄰域速度模仿策略性能和無鄰域速度模仿策略相同。B、W、S分別表示對“+”、“-”、“=”的統計數量，B-W表示“+”個數和“-”個數之差。表中加粗數字表示：從均值上看，在該函數上該算法結果優于其它算法。T值中～表為對比的兩項均值和標準差均為0，T值計算出現除以0錯誤。

表1 13個標準測試函數

從結果可以看出，除了在f1、f10、f11上兩方法效果相同外，有鄰域速度模仿策略方法在其它測試函數上均顯著優于無鄰域速度模仿策略，說明鄰域速度模仿策略確實提高了算法性能。

3.3 模仿更新后的速度與更新前的速度的對比

粒子模仿的速度可以是式(3)更新前的速度(舊速度)也可以是更新后的速度(新速度)。兩種方法重復30次的結果見表3。從結果可以看出，在各個測試函數上模仿新速度的結果全部優于或同于模仿舊速度，特別是在單峰函數上。模仿更新后的速度效果明顯優于模仿更新前的速度。這可能是因為更新后的速度包含更多的信息。

表2 有鄰域速度模仿與無鄰域速度模仿的對比

表3 新舊速度模仿

3.4 鄰域大小對INVPSO的影響

鄰域速度模仿策略利用鄰域速度在不同階段的變化情況達到了對不同階段的自適應功能。這種能力和模仿的鄰域大小是否有關系？

本節比較了鄰域鄰居數量在1～30的情況下INVPSO算法的運行結果，具體情況見表4，對其進行Friedman檢驗分析，結果見表5，其中P值表示在“不同鄰域大小情況下算法性能相同”假設下該觀察結果或者更極端情況出現的概率。P值越小，算法間差異越顯著。當P<0.05時表明各算法存在顯著性能差異，當P>0.05時各算法不存在顯著差異。

由表5可以看出，鄰域大小取1～30時，在整個測試集上P=0.299>0.05,不存在顯著差異；在單峰函數上在P=0.081>0.05，不存在顯著差異；在多峰函數上P=0.997，不存在顯著差異。可以說，INVPSO算法對鄰域大小不敏感，具有較強的魯棒性。

表4 鄰域數1～30下獨立運行30次的平均結果

表5 鄰域數1～30的平均排名與Friedman檢驗分析

3.5 與其它算法對比

本文選取了4種算法與INVPSO比較，分別是標準PSO算法、混合螢火蟲算的粒子群算法HFPSO[9]、適應度依賴優化算法FDO[10]、基于多種群的自適應遷移PSO算法MSMPSO[11]。將這4種法所使用共同參數都設為相同，最大迭代次數M=1000，種群規模N=100，搜索空間維D=30。INVPSO算法鄰域大小取k=10，其它參數都與參考文獻持一致。

3.5.1 求解精度

從表6可以看出，INVPSO在10個函數上取得了最優的均值結果，特別在f8到f11上達到了最優點，其中f8函數其它算法均不能正確求解。PSO取得了一個最優均值結果，MSMPSO取得了兩個最優均值結果。對f6和f12，各個算法均未正確求解。從最優均值結果來看，在單峰函數和多峰函數上，INVPSO均有最優表現，明顯優于其它對比算法。

3.5.2 收斂性能分析

對各個算法在以下各個函數上取得最好成績的一次的收斂過程畫出曲線，比較其收斂速度的快慢。因對f12各函數均未正確求解且差距較大，所以給出f1到f11及f13的收斂曲線，如圖1所示，各函數收斂圖圖例同f1函數收斂圖圖例。可以看出，除了f4、f9和f13,在其它函數上，INVPSO的收斂性能均優于其它對比算法，在f4上，INVPSO和FDO優于HFPSO、MSMPSO和PSO。在f9上，10代以前HFPSO的收斂速度快于INVPSO算法，但是在10代到20代之間，INVPSO和HFPSO相近。在f13上，HFPSO收斂速度優于INVPSO，INVPSO優于MSMPSO和PSO。通過在13個函數上的比較可以看出，INVPSO算法在單峰測試函數和多峰測試函數上均有較優的收斂性能。

3.5.3 顯著性檢驗

T檢驗：對INVPSO算法和對比算法在13個函數上的結果進行T檢驗，結果見表3，“+”、“-”、“=”表示INVPSO算法在均值結果上對相應算法的均值結果在T檢驗下分別處于顯著優于、顯著劣于、差異不顯著3種狀態。

從表7可以看出，INVPSO算法其它對比算法的B-W得分均大于0，具有更好的綜合性能。在單峰函數f1～f5上，INVPSO和MSMPSO在T檢驗下性能相同，而在多峰函數f6～f13上，INVPSO算法對MSMPSO算法B-W分數為4分。在單峰函數上，INVPSO和MSMPSO有相同的性能，而在多峰函數上，INVPSO算法優于MSMPSO算法。

4 結束語

本文提出了一種鄰域速度模仿策略，并將這一策略引入粒子群優化算法，提出了基于鄰域速度模仿的粒子群優化算法(INVPSO)。通過模仿鄰域粒子的速度更新后的速度，利用了鄰域粒子包含的梯度變化信息，使得前期擴展了粒子的探索范圍，后期加速了粒子的收斂，實現了粒子群的自適應調整。同時采用三點質心變異，提高了粒子跳出局部極值的能力。實驗結果表明,鄰域模仿策略確實有效；模仿新速度效果優于模仿舊速度；鄰域速度模仿策略對于鄰域大小不敏感，具有較強的魯棒性；INVPSO具有較好的收斂性能和收斂精度，尤其在多峰函數上具有更好的收斂性能。

表6 5種算法在測試集上的表現

圖1 在12個函數上各算法收斂曲線

表7 INVPSO算法對其它算法的T檢驗結果