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

鄧 浩，李均利，胡 凱

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

0 引 言

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

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

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

1 PSO

1.1 基本PSO算法

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

基本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為學習因子，分別調(diào)節(jié)對個體經(jīng)驗和群體經(jīng)驗的學習率，rand1、rand2為(0,1)之間的隨機變量。pbi,d、gbi,d、Xi,d分別表示第i個粒子歷史最優(yōu)值第d維、全局歷史最優(yōu)值第d維、第i個粒子位置第d維。

1.2 PSO算法

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

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

(3)

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

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

(4)

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

2 INVPSO

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

2.1 鄰域速度模仿策略

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

最優(yōu)鄰域粒子速度的選擇

(5)

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

速度模仿

(6)

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

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

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

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

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

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

2.2 鄰域策略

本文使用動態(tài)鄰居拓撲結(jié)構(gòu)，在每次迭代中根據(jù)各個粒子的位置，選擇離目標粒子最近的K個粒子作為其鄰居。

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

(7)

2.3 變異策略

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

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

(8)

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

2.4 模仿和變異發(fā)生條件

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

rand

(9)

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

2.5 邊界策略

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

(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 位置更新策略

比較位置更新前后的適應(yīng)度變化，若更新后適應(yīng)值沒有優(yōu)于原位置，則返回原位置

(12)

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

2.7 算法步驟

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

輸出：最優(yōu)解

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

步驟2 while(item

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

步驟4 更新全局最優(yōu)、個體歷史最優(yōu)、鄰居表、各粒子適應(yīng)值均值fmean；

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

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

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

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

1)

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

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

步驟10item++；

步驟11 END while；

步驟12 輸出最優(yōu)解。

3 實驗結(jié)果及分析

3.1 測試函數(shù)

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

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

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

表1 13個標準測試函數(shù)

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

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

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

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

表3 新舊速度模仿

3.4 鄰域大小對INVPSO的影響

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

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

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

表4 鄰域數(shù)1～30下獨立運行30次的平均結(jié)果

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

3.5 與其它算法對比

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

3.5.1 求解精度

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

3.5.2 收斂性能分析

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

3.5.3 顯著性檢驗

T檢驗：對INVPSO算法和對比算法在13個函數(shù)上的結(jié)果進行T檢驗，結(jié)果見表3，“+”、“-”、“=”表示INVPSO算法在均值結(jié)果上對相應(yīng)算法的均值結(jié)果在T檢驗下分別處于顯著優(yōu)于、顯著劣于、差異不顯著3種狀態(tài)。

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

4 結(jié)束語

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

表6 5種算法在測試集上的表現(xiàn)

圖1 在12個函數(shù)上各算法收斂曲線

表7 INVPSO算法對其它算法的T檢驗結(jié)果