慣性權(quán)重矩陣下的自適應(yīng)粒子群算法分析

楊寶軍

(太原學(xué)院 應(yīng)用數(shù)學(xué)系，山西 太原 030012)

PSO是以群集智能為基礎(chǔ)的一種隨機(jī)搜索算法，由Kenedy與Eberhart在1995年首次推出。PSO具有方便易用、可調(diào)節(jié)參數(shù)不多等特征，廣泛應(yīng)用在神經(jīng)網(wǎng)絡(luò)權(quán)值的訓(xùn)練、函數(shù)優(yōu)化、控制系統(tǒng)參數(shù)優(yōu)化等[1]。然而，在實(shí)踐過(guò)程中，PSO存在出現(xiàn)局部極數(shù)、收斂效率低下等缺陷[2]。可以從下面幾個(gè)方面進(jìn)行改進(jìn)：1)利用粒子速度參數(shù)、CBPE、多元性等來(lái)進(jìn)行設(shè)置[3]；2)把GA算法和螞蟻算法與PSO進(jìn)行融合[4]；3)優(yōu)化粒子位置變化規(guī)律或者使用變異策略[5]。因此，尋找1種以慣性權(quán)重矩陣為基礎(chǔ)的自適應(yīng)粒子群算法極為重要?；诖?，本文從離散狀態(tài)空間表達(dá)式入手，得出算法穩(wěn)定使用時(shí)參數(shù)約束條件與粒子的運(yùn)作規(guī)律，引進(jìn)使算法每個(gè)步驟以較大概率收斂、較小概率發(fā)散的參數(shù)組合選取策略、慣性權(quán)重矩陣策略，以及按照粒子活躍度速度重置與歷史最優(yōu)值擾動(dòng)策略，以期獲得改進(jìn)后的RDR-PSO，初步解決當(dāng)前PSO存在的缺陷。

1 粒子群算法分析

1.1 基本粒子群算法

在PSO穩(wěn)定使用時(shí)，對(duì)于第i個(gè)粒子來(lái)說(shuō)，其后的位置序列xi(k+1)會(huì)被速度vi(k)、位置xi(k)、個(gè)體最優(yōu)位置pi(k)、群體最優(yōu)位置gi(k)這些特殊的信息序列和某些不穩(wěn)定原因的影響。其變化步驟如下：

關(guān)于速度信息更新的相關(guān)模型

vi(k+1)=ωvi(k)+c1r1(pi(k)-xi(k))+

c2r2(gi(k)-xi(k)).

(1)

關(guān)于位置信息更新的數(shù)學(xué)模型

xi(k+1)=xi(k)+vi(k+1).

(2)

式中：ω為慣性權(quán)重；k為目前迭代頻次；c1，c2為學(xué)習(xí)因素；r1，r2為0到1之間均衡分布的隨機(jī)值，表示粒子所處環(huán)境的隨機(jī)影響要素。

從PSO的運(yùn)動(dòng)情況進(jìn)行分析，大量學(xué)者對(duì)于這種算法的收斂性做出討論，為后續(xù)的改進(jìn)方式打下基礎(chǔ)，因此，從離散狀態(tài)表達(dá)式入手，明確這種算法的穩(wěn)定性，提出這種穩(wěn)定性條件下算法使用時(shí)的數(shù)值要求十分重要。

假設(shè)群體粒子數(shù)量是n個(gè)，尋找最優(yōu)解搜索空間是m維，φ1(k)=c1r1(k)，φ2(k)=c2r2(k)，則為了確保普適性，把式(1)、式(2)表示成

V(k+1)=ωV(k)+φ1(k)(P(k)-X(k))+

φ2(k)(G(k)-X(k))，

(3)

X(k+1)=X(k)+V(k+1).

(4)

式中：ω，φ1(k)，φ2(k)都是n×m維對(duì)角矩陣；X(k)，P(k)，G(k)，V(k)都是n×m維矩陣。

因此，有著下面的定義：

定義1：e1，e2屬于數(shù)值不變的常量，若?k≤Kmax，這時(shí)就有Vij(k)=e1∪Xij(k)=e2，說(shuō)明這個(gè)方法能夠在長(zhǎng)時(shí)間內(nèi)被較好地使用。

定理1： PSO算法可以長(zhǎng)期運(yùn)行的要求是

(5)

定理2：在標(biāo)準(zhǔn)PSO算法穩(wěn)定運(yùn)行的情況下，假設(shè)K→Kmax，全部粒子速度是0，并且位置收斂于一點(diǎn)。

1.2 慣性權(quán)重ω和中間量φ的影響

據(jù)前文，在定理2中，算法如果要長(zhǎng)期運(yùn)行，就需要任意k的ω(k)，φ(k)，也就是式(5)中曲面相交的地方，因?yàn)楸磉_(dá)式較為龐雜，變化成式(6)，通過(guò)圖形的方式給出各種參數(shù)組合下算法的穩(wěn)定運(yùn)行狀況。

(6)

以x軸作為ω，y軸作為φ，圖中黑色的部分是z≡0的部分，當(dāng)區(qū)間位于-1.5<ω<1.5，-1.5<φ<1.5的時(shí)候，如果進(jìn)行投影，就可以得到圖1。

圖1 算法的穩(wěn)定性關(guān)系

從圖1可以看出，在任一時(shí)刻k慣性權(quán)重ω，φ在黑色空間內(nèi)時(shí)該離散時(shí)間系統(tǒng)可以長(zhǎng)期使用。假設(shè)長(zhǎng)期運(yùn)作時(shí)要求-0.5<ω<1，ω為式(3)的相關(guān)矩陣，在不考量干擾的條件下，速度的運(yùn)行軌跡為

V(k)=ωkV(0).

(7)

式中：V(0)為速度的初始情況。

從上述分析能夠發(fā)現(xiàn)，確保系統(tǒng)穩(wěn)定使用時(shí)，即ω，φ在所有的時(shí)間范圍之內(nèi)，他們的k的取值都是在黑色的位置，式(3)的所有粒子速度的值都會(huì)變得比較小。如果基于理論角度出發(fā)來(lái)看，這其中的差異就在于0<ω<1時(shí)，速度V的響應(yīng)為單調(diào)衰減，符號(hào)不變；如果有-0.5<ω<1，那么V的響應(yīng)則會(huì)變成正負(fù)交替，在震蕩中呈現(xiàn)出衰減的趨勢(shì)。這么來(lái)看，基于某種角度進(jìn)行分析，當(dāng)ω在尋找最優(yōu)解環(huán)節(jié)中可正可負(fù)時(shí)拓展粒子的搜索空間與速度V狀態(tài)軌線的龐雜性，使得這種方式能夠更好地在迭代環(huán)節(jié)中發(fā)現(xiàn)最優(yōu)解。

2 標(biāo)準(zhǔn)粒子群算法的改進(jìn)

為了進(jìn)一步提升PSO算法的性能，主要從ω，v與歷史最優(yōu)值入手，闡述改進(jìn)方式及其因素，逐步使用本文指出的以慣性權(quán)重矩陣作為基礎(chǔ)的RDR-PSO算法。

2.1 隨機(jī)慣性權(quán)重矩陣的引入

本文提出使得粒子在所有步驟都有較強(qiáng)的概率收斂、較小的概率發(fā)散的參數(shù)組合選擇方式，此類形式不僅能夠確保所有粒子的廣泛分布，還能夠保證算法有較強(qiáng)的穩(wěn)定性。不過(guò)所有粒子的搜索路線還是有盲目性的特征，所以文中為所有粒子所有維速度在每一步驟獨(dú)立設(shè)計(jì)1個(gè)隨機(jī)性的ω，并且其權(quán)重能夠是正值或者負(fù)值。利用這種方式能夠?yàn)榱Ｗ拥乃俣扰c位置變化帶來(lái)隨機(jī)性，造成運(yùn)動(dòng)狀況更為龐雜，這是為了盡量減少擴(kuò)大搜索范圍而產(chǎn)生的盲目性。

這時(shí)式(3)表達(dá)為

V(k+1)=(ωmin+(ωmax-ωmin)rand(n,d))V(k)+

c1r1(P(k)X(k))-c2r2(G(k)X(k)).

(8)

式中：d為待改進(jìn)函數(shù)自變量的數(shù)量;n為原始粒子數(shù)量;ωmin，ωmax為速度所有維允許的慣性權(quán)重的極值;X(k)，V(k)，P(k)，G(k)各自是n×d維位置、搜索速度、個(gè)體歷史最優(yōu)點(diǎn)、全局最優(yōu)位置矩陣，其中，G(k)中數(shù)值都相同，(ωmin+(ωmax-ωmin)rand(n,d))就是為了提升其性能，繼而運(yùn)用n×d的矩陣。

基于上文分析，具體數(shù)值為

(9)

式中：ω(k)為n×d維矩陣，此時(shí)各個(gè)環(huán)節(jié)k達(dá)到1個(gè)條件：P發(fā)散>P收斂，意味著該方式有著良好的收斂性。

為了更好地闡述對(duì)于各個(gè)步驟來(lái)說(shuō)，每個(gè)步驟都是其中各個(gè)維度的定義慣性權(quán)重參數(shù)，且是具有優(yōu)勢(shì)的，然后對(duì)其設(shè)定變量c1=c2=0.5∪ω遞減、c1=c2=2∪ω遞減以及c1=c2=2∪ω矩陣，然后對(duì)3種情況進(jìn)行分析，在這些狀態(tài)下，粒子的原始狀態(tài)為：X(0)=[5-5]，V(0)=[-32]。

2.2 定義粒子活躍度

速度在0的均衡點(diǎn)得到穩(wěn)定收斂，所以可以將全部的粒子在k時(shí)間里的活躍情況認(rèn)為是每個(gè)維度上的絕對(duì)速度的極值，也就是

Di(k)=max(|Vi(k)|).

(10)

式中：Di(k)代表在第k步時(shí)第i個(gè)粒子的活躍情況。

從式(10)可知，Di(k)數(shù)值越小，速度越慢，其搜索最優(yōu)解的性能越不好，越接近于局部最優(yōu)解。假設(shè)Di(k)較小時(shí)，其搜索范圍將會(huì)不斷縮小，這時(shí)有助于找到局部最優(yōu)解，不過(guò)無(wú)法提升全局搜索速度，就是均衡算法的全局尋優(yōu)性能與局部尋優(yōu)性能，為Di(k)設(shè)定一個(gè)極值Dmin，而且設(shè)置1個(gè)常數(shù)klimit，假設(shè)Di(k)在連續(xù)的相應(yīng)的次數(shù)比Dmin要低的時(shí)候，就說(shuō)明這個(gè)例子具有比較低下的活躍度。

3 基于慣性權(quán)重矩陣的自適應(yīng)粒子群算法

在上述的討論中，當(dāng)某一粒子的活躍程度不高時(shí)，說(shuō)明速度越低，這時(shí)粒子位置信息與速度信息不會(huì)變化，呈現(xiàn)早期收斂情況，算法無(wú)法使用。本次通過(guò)速度與位置更新，使得這種粒子再次進(jìn)到搜索環(huán)節(jié)，能夠確保在這種算法使用中全部粒子長(zhǎng)期處于尋優(yōu)狀態(tài)，從而提升粒子使用率。這時(shí)所有粒子的pi(k)≈G(k)，為了確保重置的粒子可以受到全局最優(yōu)位置與個(gè)體歷史最優(yōu)位置的共同作用，使用個(gè)體歷史最優(yōu)位置干擾方式，使其位置參數(shù)發(fā)生變化，進(jìn)而拓展尋找范圍。

從上述分析能夠發(fā)現(xiàn)，這種改進(jìn)的算法保留了原有算法方便易用的特征，其存在的差別如下：

1)速度更新公式由(1)變成(8)，其中的不同就是以慣性權(quán)重矩陣作為基礎(chǔ)。

2)在速度更新公式里面，上面一個(gè)步驟的速度v(k)和歷史當(dāng)中最優(yōu)序列p(k)在當(dāng)前的疊代過(guò)程中出現(xiàn)變化。推斷其有無(wú)出現(xiàn)變化的基礎(chǔ)是：第i個(gè)粒子的活躍程度Di(k)有無(wú)持續(xù)klimit次低于臨界值Dmin，“是”則代表v(k)中第i行參數(shù)更新，同樣地對(duì)于p(k)中第i行參數(shù)給出1個(gè)干擾作用。

3)本次使用的歷史最優(yōu)值干擾方式就是(β1+β2-β1)×rand)+1)×pi(k)，其中，β1，β2為擾動(dòng)數(shù)值，而非(β1+β2-β1)×rand)×pi(k)，由于這時(shí)所有粒子歷史最優(yōu)位置會(huì)迅速減退至0 ，對(duì)于最優(yōu)解在0時(shí)的能力評(píng)估的函數(shù)還是比較有用的，但是這會(huì)讓算法的使用缺乏相應(yīng)的價(jià)值。

4)對(duì)于參數(shù)組合策略來(lái)說(shuō)，按照式(9)來(lái)進(jìn)行選擇。其中，具體步驟與上文提出的一樣，在這里不一一說(shuō)明。

4 算法測(cè)試

在對(duì)本次指出的RDR-PSO算法展開(kāi)仿真比較驗(yàn)證過(guò)程中，了解Dmin參數(shù)選擇的差異，將直接關(guān)系到算法性能，同樣地為了掌握本次算法的優(yōu)點(diǎn)，先是簡(jiǎn)要說(shuō)明6種基本測(cè)試函數(shù)，之后對(duì)RDR-PSO算法性能展開(kāi)仿真試驗(yàn)，具體如下。

4.1 基本測(cè)試函數(shù)及介紹

本文基于6個(gè)種類的函數(shù)來(lái)對(duì)文章提出的算法進(jìn)行測(cè)試，測(cè)試算法查詢最優(yōu)解的能力，這些函數(shù)有著不一樣的極數(shù)，其名稱、公式和最優(yōu)值具體見(jiàn)表1，其中，Sphere表示單峰函數(shù)，只有1個(gè)極數(shù)，尋找最優(yōu)解沒(méi)有太大難度。Rosenbrack函數(shù)是病態(tài)函數(shù)，其極數(shù)存在于1條縫隙中，而其它函數(shù)都是多峰函數(shù)，在搜索范圍內(nèi)有著若干極數(shù)，尋找最優(yōu)解比較困難。本文基于表1中的6種函數(shù)，對(duì)本文算法的能力進(jìn)行測(cè)試。

表1 6種測(cè)試函數(shù)及極值

4.2 不同Dmin參數(shù)對(duì)算法性能的影響

在本次仿真驗(yàn)證過(guò)程中，將初始粒子數(shù)量設(shè)定成80，klimit數(shù)值是2，慣性權(quán)重矩陣按照[-0.5，0.8]進(jìn)行取值，參數(shù)設(shè)置是10-1，10-2，10-3，10-4，10-5。最大疊代設(shè)定成2 000。所有測(cè)試函數(shù)搜索區(qū)間是[-10，10]，對(duì)于所有函數(shù)10維、20維、30維時(shí)RDR-PSO算法單獨(dú)運(yùn)作20次，其結(jié)果可見(jiàn)各種Dmin數(shù)值對(duì)于不同測(cè)試函數(shù)在同樣的其他情況下其結(jié)果準(zhǔn)確度存在差別，從總體結(jié)果能夠發(fā)現(xiàn)，在Dmin參數(shù)選取10-3或者10-4時(shí)算法對(duì)于各種測(cè)試函數(shù)都能實(shí)現(xiàn)良好的搜索效果，因此，在之后的比較研究中并未特別說(shuō)明，都將Dmin參數(shù)設(shè)置成10-4。

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

PSO隨機(jī)搜索算法因?yàn)榫哂幸壮霈F(xiàn)局部極數(shù)、收斂效率低的缺陷，本文從離散狀態(tài)空間表達(dá)式入手，探討粒子群算法的穩(wěn)定性，獲得改進(jìn)后的自適應(yīng)粒子群算法(RDR-PSO)，并對(duì)RDR-PSO進(jìn)行仿真驗(yàn)證。結(jié)果表明，改進(jìn)后的PSO算法與標(biāo)準(zhǔn)PSO算法性能進(jìn)行比較分析，得到RDR-PSO算法有著可以提升收斂準(zhǔn)確度與跳出局部極數(shù)的特征，說(shuō)明RDR-PSO有著收斂準(zhǔn)確性高、全局尋優(yōu)速度快、方便易用，發(fā)展前景廣闊。然而本文僅從離散狀態(tài)空間表達(dá)式入手來(lái)探討粒子群算法的穩(wěn)定性，結(jié)論并不全面，以后還需深入研究。