鄧 浩，李均利，胡 凱

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610101)

0 引 言

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

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

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

1 PSO

1.1 基本PSO算法

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

基本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個(gè)粒子的第d維，c1、c2為學(xué)習(xí)因子，分別調(diào)節(jié)對(duì)個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)的學(xué)習(xí)率，rand1、rand2為(0,1)之間的隨機(jī)變量。pbi,d、gbi,d、Xi,d分別表示第i個(gè)粒子歷史最優(yōu)值第d維、全局歷史最優(yōu)值第d維、第i個(gè)粒子位置第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稱(chēng)為慣性權(quán)重，用于調(diào)節(jié)粒子當(dāng)前速度對(duì)新速度的影響，合適的w能夠使粒子在保持運(yùn)動(dòng)慣性的同時(shí)進(jìn)一步擴(kuò)展搜索空間。

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

(4)

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

2 INVPSO

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

2.1 鄰域速度模仿策略

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

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

(5)

這里可以模仿的速度可以是式(3)更新前的舊速度或者更新后的新速度，而因?yàn)樾滤俣仍诟碌倪^(guò)程中，因?yàn)槭艿奖据喌鷼v史速度、個(gè)體歷史最優(yōu)、全局歷史最優(yōu)的影響，所以包含更多的信息。

速度模仿

(6)

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

當(dāng)模仿對(duì)象速度指向當(dāng)前粒子適應(yīng)值減方向，則模仿行為會(huì)加速粒子向當(dāng)前局部極值運(yùn)動(dòng)。當(dāng)模仿對(duì)象速度指向當(dāng)前粒子適應(yīng)值增方向，則模仿行為會(huì)使粒子遠(yuǎn)離當(dāng)前局部極值。為了說(shuō)明鄰域速度模仿策略思想，以下針對(duì)求最小值問(wèn)題進(jìn)行分析，因?yàn)樽畲笾祮?wèn)題取負(fù)即可變?yōu)樽钚≈祮?wèn)題，所以以下分析對(duì)最大值問(wèn)題同樣成立。

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

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

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

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

2.2 鄰域策略

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

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

(7)

2.3 變異策略

在質(zhì)心法[8]的基礎(chǔ)上，采用質(zhì)心變異策略，對(duì)當(dāng)前粒子，另外隨機(jī)選取兩個(gè)粒子，將當(dāng)前粒子遷移到3個(gè)粒子的質(zhì)心周?chē)?/p>

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

(8)

其中，xr2，xr3表示另外隨機(jī)選取的兩個(gè)粒子。

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

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

rand

(9)

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

2.5 邊界策略

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

(10)

其中，xi,d表示第i個(gè)粒子的第d維坐標(biāo)，ld表示第d維的取值下限，ud表示第d維的取值上限。

當(dāng)速度超過(guò)限制時(shí)，則速度保持在邊界

(11)

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

2.6 位置更新策略

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

(12)

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

2.7 算法步驟

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

輸出：最優(yōu)解

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

步驟2 while(item

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

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

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

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

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

對(duì)該粒子的每個(gè)維度，如果rand(0,

1)

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

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

步驟10item++；

步驟11 END while；

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

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

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

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

3.2 有鄰域速度模仿和無(wú)鄰域速度模仿的對(duì)比

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

表1 13個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)

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

3.3 模仿更新后的速度與更新前的速度的對(duì)比

粒子模仿的速度可以是式(3)更新前的速度(舊速度)也可以是更新后的速度(新速度)。兩種方法重復(fù)30次的結(jié)果見(jiàn)表3。從結(jié)果可以看出，在各個(gè)測(cè)試函數(shù)上模仿新速度的結(jié)果全部?jī)?yōu)于或同于模仿舊速度，特別是在單峰函數(shù)上。模仿更新后的速度效果明顯優(yōu)于模仿更新前的速度。這可能是因?yàn)楦潞蟮乃俣劝嗟男畔ⅰ?/p>

表2 有鄰域速度模仿與無(wú)鄰域速度模仿的對(duì)比

表3 新舊速度模仿

3.4 鄰域大小對(duì)INVPSO的影響

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

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

由表5可以看出，鄰域大小取1～30時(shí)，在整個(gè)測(cè)試集上P=0.299>0.05,不存在顯著差異；在單峰函數(shù)上在P=0.081>0.05，不存在顯著差異；在多峰函數(shù)上P=0.997，不存在顯著差異?？梢哉f(shuō)，INVPSO算法對(duì)鄰域大小不敏感，具有較強(qiáng)的魯棒性。

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

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

3.5 與其它算法對(duì)比

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

3.5.1 求解精度

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

3.5.2 收斂性能分析

對(duì)各個(gè)算法在以下各個(gè)函數(shù)上取得最好成績(jī)的一次的收斂過(guò)程畫(huà)出曲線(xiàn)，比較其收斂速度的快慢。因?qū)12各函數(shù)均未正確求解且差距較大，所以給出f1到f11及f13的收斂曲線(xiàn)，如圖1所示，各函數(shù)收斂圖圖例同f1函數(shù)收斂圖圖例?？梢钥闯?，除了f4、f9和f13,在其它函數(shù)上，INVPSO的收斂性能均優(yōu)于其它對(duì)比算法，在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。通過(guò)在13個(gè)函數(shù)上的比較可以看出，INVPSO算法在單峰測(cè)試函數(shù)和多峰測(cè)試函數(shù)上均有較優(yōu)的收斂性能。

3.5.3 顯著性檢驗(yàn)

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

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

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

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

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

圖1 在12個(gè)函數(shù)上各算法收斂曲線(xiàn)

表7 INVPSO算法對(duì)其它算法的T檢驗(yàn)結(jié)果