杜 江，袁中華，王景芹

(河北工業(yè)大學(xué) 電磁場(chǎng)與電器可靠性省部共建重點(diǎn)實(shí)驗(yàn)室，天津 300130)

近年來(lái)，各種智能仿生算法相繼被提出，1995年由Kennedy等[1]等提出的粒子群算法(particle swarm optimization，簡(jiǎn)稱(chēng)PSO)便是其中一種.粒子群算法是對(duì)鳥(niǎo)群和魚(yú)群捕食行為進(jìn)行抽象模擬的一種群智能優(yōu)化算法，具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)個(gè)數(shù)少、魯棒性強(qiáng)等優(yōu)點(diǎn)，一經(jīng)提出便在計(jì)算機(jī)領(lǐng)域和許多工程領(lǐng)域得到廣泛應(yīng)用[2-8].

然而，與其他智能算法一樣，粒子群算法也存在易陷入局部最優(yōu)、收斂精度不高、收斂速度較慢和收斂成功率低等問(wèn)題.針對(duì)這些不足，國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究與改進(jìn).文[9]提出一種新的控制慣性權(quán)重的方法，控制過(guò)程簡(jiǎn)單、易實(shí)現(xiàn)，但對(duì)算法性能的提升非常有限.文[10]根據(jù)每個(gè)粒子的適應(yīng)度值自適應(yīng)地改變每個(gè)粒子的速度權(quán)重，動(dòng)態(tài)調(diào)整每個(gè)種群粒子的活性，提高了算法的全局尋優(yōu)能力和收斂能力，但收斂速度卻有所下降.文[11]引入了動(dòng)態(tài)跟蹤?quán)徲蝽?xiàng)，改進(jìn)了慣性權(quán)重和學(xué)習(xí)因子的調(diào)整策略，顯著提高了算法全局收斂性能.文[12]將混合蛙跳算法中的排序和分組機(jī)制引入簡(jiǎn)化粒子群算法中，提高了算法的求解精度，同時(shí)降低了算法收斂于局部最優(yōu)解的可能性.

論文針對(duì)標(biāo)準(zhǔn)粒子群算法的不足，通過(guò)實(shí)時(shí)調(diào)整慣性權(quán)重和粒子飛行路線，構(gòu)建了一種新的改進(jìn)的粒子群算法(particle swarm optimization algorithm with dynamically changing inertia weight，簡(jiǎn)稱(chēng)DMPSO).通過(guò)4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)改進(jìn)后粒子群算法的性能進(jìn)行測(cè)試，證明了改進(jìn)算法求解復(fù)雜優(yōu)化問(wèn)題時(shí)具有更高的求解精度和求解成功率.

1 標(biāo)準(zhǔn)粒子群算法

粒子群算法是一種群智能優(yōu)化算法.假設(shè)粒子群由m個(gè)分布在D維空間的粒子個(gè)體組成，每個(gè)粒子個(gè)體的屬性均包含3個(gè)D維矢量：xi=(xi1,xi2,…,xiD)、vi=(vi1,vi2,…,viD)和pi=(pi1,pi2,…,piD)，其中xi、vi和pi分別為粒子i在解空間內(nèi)的位置、飛行速度和歷史最優(yōu)位置，且1≤i≤m.pg=(pg1,pg2,…,pgD)為整個(gè)粒子群搜索到的最優(yōu)位置.算法迭代過(guò)程中，每個(gè)粒子的位置按式(1)、(2)進(jìn)行更新

(1)

(2)

算法以適應(yīng)值的大小判斷其位置的優(yōu)劣，每次迭代均更新每個(gè)粒子的當(dāng)前位置、歷史最優(yōu)位置和整個(gè)粒子群搜索到的最優(yōu)位置.

2 粒子群算法的改進(jìn)

2.1 慣性權(quán)重的改變

慣性權(quán)重w是PSO算法最重要的參數(shù)之一.由公式(1)很容易看出，w的大小決定了粒子上次迭代中飛行速度對(duì)本次迭代中飛行速度的影響，即決定了全局和局部搜索能力.分析可知，w取較大值有利于全局搜索，但增大算法開(kāi)銷(xiāo)，降低算法效率；w取較小值有利于局部搜索，加速算法收斂，但容易陷入局部最優(yōu).所以，設(shè)置一個(gè)合適的w可以平衡全局和局部搜索能力，即兼顧算法收斂速度和收斂精度，降低陷入局部最優(yōu)解的可能性，提高算法的整體性能.

關(guān)于如何實(shí)時(shí)控制w的大小，國(guó)內(nèi)外學(xué)者進(jìn)行了大量研究.文[13]提出線性減小慣性權(quán)重的方法(linearly decreasing weight, 簡(jiǎn)稱(chēng)LDW)，如下式

(3)

其中：wmax、wmin分別為慣性權(quán)重的最大和最小值，die為當(dāng)前迭代次數(shù)，DIE為最大迭代次數(shù).

LDW方法控制直接、實(shí)現(xiàn)簡(jiǎn)單，但因?yàn)閷?duì)w的調(diào)整只考慮了算法所處的迭代階段，所以很難適應(yīng)復(fù)雜、非線性問(wèn)題的求解，對(duì)標(biāo)準(zhǔn)算法性能的提升非常有限.

事實(shí)上，想要減小求解復(fù)雜問(wèn)題時(shí)算法陷入局部最優(yōu)的可能性、提高收斂精度和收斂成功率，除了要考慮算法所處的迭代階段以外，還應(yīng)該考慮迭代過(guò)程中粒子的分布情況(集中或者分散)，即w的大小應(yīng)由迭代階段和粒子分布情況共同決定，如下式

(4)

其中：α為慣性權(quán)重變異算子，它的大小由粒子在解空間內(nèi)的分布情況決定；其他參數(shù)的含義與式(3)一致.

考慮實(shí)時(shí)檢測(cè)解空間內(nèi)粒子的分布情況，論文采用文[14]提出的分布熵來(lái)表示，如下式

(5)

其中：k=1,2,…，Q，m為粒子個(gè)數(shù)，Q為解空間被平均劃分的相等區(qū)域的個(gè)數(shù)，m1、m2、…、mQ分別為第die次迭代后每個(gè)區(qū)域內(nèi)的粒子個(gè)數(shù).

E(die)越小說(shuō)明粒子越集中，此時(shí)應(yīng)為α賦一較大值，即加強(qiáng)全局搜索；反之，E(die)越大說(shuō)明粒子越分散，此時(shí)應(yīng)為α賦一較小值，即加強(qiáng)局部搜索.α的具體調(diào)整方法如下式

(6)

其中：E1、E2分別為粒子分布熵的上、下門(mén)檻值(應(yīng)滿足E1

在算法迭代后期，粒子勢(shì)必會(huì)集中于全局最優(yōu)解附近，此時(shí)增大α來(lái)加強(qiáng)全局搜索勢(shì)必會(huì)影響算法最終的收斂性.所以，以分布情況調(diào)整w大小的方式僅適用于算法迭代前期和中期，即die

2.2 飛行模式的調(diào)整

合理地控制w的大小，可以改善算法的性能，除此之外，效仿其他智能優(yōu)化算法，合理利用種群其他粒子的經(jīng)驗(yàn)，無(wú)疑也可以從中受益[15].分析可知，每個(gè)粒子的歷史最優(yōu)位置pi的附近出現(xiàn)全局最優(yōu)解的可能性要遠(yuǎn)遠(yuǎn)大于其他位置(特別是在算法迭代中后期)，當(dāng)某一粒子連續(xù)多次不能更新其歷史最優(yōu)位置pi時(shí)，由式(2)可知，該粒子很有可能已經(jīng)遠(yuǎn)離了其歷史最優(yōu)位置pi，繼續(xù)迭代進(jìn)而得到更優(yōu)解的可能性非常小，此時(shí)應(yīng)該將該粒子 “拉回”其歷史最優(yōu)位置pi處，以其歷史最優(yōu)位置pi處為起點(diǎn)繼續(xù)飛行，即把式(2)修改為式(7)

(7)

此時(shí)種群其他粒子的狀態(tài)(歷史最優(yōu)位置)已經(jīng)改變，加之算法本身的隨機(jī)性，所以，被“拉回”的粒子不會(huì)延續(xù)上次“失敗”的路線飛行.綜上所述，如此調(diào)整之后減小了粒子搜索的盲目性，增加了粒子搜索到全局最優(yōu)解的可能性.

2.3 改進(jìn)后的算法流程

改進(jìn)后的粒子群算法流程描述如下：

步驟1初始化，包括隨機(jī)初始化每個(gè)粒子的位置xi、飛行速度vi、歷史最優(yōu)位置pi、全局最優(yōu)位置pg；

步驟2計(jì)算每個(gè)粒子的適應(yīng)值；

步驟3更新每個(gè)粒子的歷史最優(yōu)位置和種群最優(yōu)位置；

步驟4根據(jù)式(4)～(6)調(diào)整慣性權(quán)重w；

步驟5若某粒子連續(xù)s次不能改變其歷史最優(yōu)位置pi，且當(dāng)前迭代次數(shù)die

步驟6判斷算法是否滿足結(jié)束條件，即是否達(dá)到最大迭代次數(shù)或滿足最小誤差：若否，則跳轉(zhuǎn)至步驟2;若是，則結(jié)束迭代并輸出優(yōu)化結(jié)果.

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了測(cè)試改進(jìn)算法的有效性，對(duì)4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真試驗(yàn)，并與標(biāo)準(zhǔn)粒子群算法(PSO)、文[13]提出的線性減小慣性權(quán)重的方法(LDW)、文[9]提出的調(diào)整慣性權(quán)重的方法(MPSO)相對(duì)比.4個(gè)測(cè)試函數(shù)的名稱(chēng)、表達(dá)式等信息如表1所示.其中：f1為單峰函數(shù)，f2、f3、f4為多峰函數(shù).

實(shí)驗(yàn)的硬件環(huán)境為：Windows XP系統(tǒng)，AMD雙核2.5 GHz CPU，1.94 G內(nèi)存.通過(guò)VC++軟件進(jìn)行仿真實(shí)驗(yàn).在試驗(yàn)中，粒子個(gè)數(shù)m=50，c1=c2=2，慣性權(quán)重最大值wmax=0.7、最小值wmin=0.1，分布熵下門(mén)檻值E1=2、上門(mén)檻值E2=3.2，最大迭代次數(shù)DIE=1 000，粒子分布檢測(cè)結(jié)束標(biāo)志P=0.8.

實(shí)驗(yàn)從3個(gè)方面進(jìn)行測(cè)試[16]：

(1) 固定算法進(jìn)化代數(shù)，根據(jù)多次實(shí)驗(yàn)的平均最優(yōu)適應(yīng)值比較4種算法的求解精度；

(2) 通過(guò)多次試驗(yàn)的平均進(jìn)化曲線比較4種算法的收斂速度；

(3) 固定收斂精度，比較4種算法的收斂成功率.

表1 測(cè)試函數(shù)信息

3.2 仿真結(jié)果及分析

3.2.1 算法求解精度對(duì)比

每一種算法對(duì)每一個(gè)測(cè)試函數(shù)在不同維度下均進(jìn)行20次仿真試驗(yàn)，表2給出了20次試驗(yàn)的平均最優(yōu)適應(yīng)值.

由表2可以看出，在簡(jiǎn)單問(wèn)題(單峰函數(shù)f1)求解時(shí)，LDW、MPSO(new model particle swarm optimization)和DMPSO的求解精度均低于PSO，這是因?yàn)楦倪M(jìn)后算法通過(guò)對(duì)慣性權(quán)重的調(diào)整，使之更側(cè)重于全局搜索，而在一定程度上削弱了局部搜索.在復(fù)雜問(wèn)題(高維度多峰函數(shù)f2、f3、f4)求解時(shí)，DMPSO與其他3種算法相比，具有更高的求解精度.

表2 各函數(shù)在不同算法、不同維度下的平均最優(yōu)適應(yīng)值

3.2.2 算法收斂速度對(duì)比

每一種算法對(duì)每一個(gè)測(cè)試函數(shù)進(jìn)行20次仿真試驗(yàn)，得到1 000次迭代平均最優(yōu)適應(yīng)值數(shù)據(jù)，繪制平均進(jìn)化曲線如圖1所示.其中：橫坐標(biāo)代表算法迭代次數(shù)，縱坐標(biāo)代表迭代過(guò)程中每一代的平均最優(yōu)解.同時(shí)為了較直觀地展示各算法的迭代趨勢(shì)，對(duì)其迭代數(shù)據(jù)取自然對(duì)數(shù).

圖1 各測(cè)試函數(shù)平均收斂曲線

由圖1可以看出，在大多數(shù)優(yōu)化問(wèn)題中，DMPSO的收斂速度僅僅高于MPSO而低于PSO和LDW，這是加強(qiáng)全局搜索能力的必然結(jié)果.另外，圖1也顯示出了DMPSO在復(fù)雜問(wèn)題(高維度多峰函數(shù)f2、f3、f4)求解時(shí)，具有求解精度方面的優(yōu)勢(shì).

3.2.3 算法收斂成功率對(duì)比

設(shè)定算法收斂精度如表3所示.其解空間維度D=10.

表3 各測(cè)試函數(shù)收斂精度

每一種算法對(duì)每一個(gè)測(cè)試函數(shù)進(jìn)行50次仿真試驗(yàn)，迭代次數(shù)達(dá)到1 000次時(shí)仍未達(dá)到指定收斂精度，則認(rèn)為此次試驗(yàn)沒(méi)有收斂.記錄收斂成功次數(shù)，并計(jì)算收斂成功率如表4所示.其中：收斂成功率=收斂成功次數(shù)/50.

表4 各測(cè)試函數(shù)收斂成功率

通過(guò)表4可以看出：相對(duì)于PSO、LDW和MPSO，DMPSO在簡(jiǎn)單問(wèn)題(單峰函數(shù)f1)求解時(shí)，其收斂成功率不具有優(yōu)勢(shì)；而在復(fù)雜問(wèn)題(高維度多峰函數(shù)f2、f3、f4)求解時(shí)，收斂成功率明顯高于其他3種算法.

綜上所述，論文改進(jìn)的粒子群算法(DMPSO)在復(fù)雜問(wèn)題求解時(shí)，在收斂精度和收斂成功率方面均有明顯的優(yōu)勢(shì).由于加強(qiáng)了算法的全局搜索能力，也就意味著一定程度上減弱了算法的局部搜索能力，所以在收斂速度方面則比較遜色于部分其他算法.

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

論文提出一種改進(jìn)的粒子群算法，根據(jù)算法所處的迭代階段和粒子在解空間的分布情況，動(dòng)態(tài)控制慣性權(quán)重的大??；根據(jù)粒子歷史最優(yōu)位置的更新情況，調(diào)整粒子的飛行起點(diǎn).通過(guò)4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真試驗(yàn)，證明了改進(jìn)后的粒子群算法在復(fù)雜問(wèn)題求解時(shí)的優(yōu)越性.

參考文獻(xiàn)：

[1] KENNEDY J, EBERHART R. Particle swarm optimization[C]//IEEE Int Conference on Neural Networks Piscataway: IEEE Service Center, 1995: 1942-1948.

[2] 溫濤, 盛國(guó)軍, 郭權(quán), 等. 基于改進(jìn)粒子群算法的Web服務(wù)組合[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36 (5): 1031-1046.

[3] 梅飛, 梅軍, 鄭建勇, 等. 粒子群優(yōu)化的KFCM及SVM診斷模型在斷路器故障診斷中的應(yīng)用[J]. 中國(guó)電機(jī)工程學(xué)報(bào), 2013, 33 (36): 134-141.

[4] 陳雁, 孫海順, 文勁宇, 等. 改進(jìn)粒子群算法在船舶電力系統(tǒng)網(wǎng)絡(luò)重構(gòu)中的應(yīng)用[J]. 電力自動(dòng)化設(shè)備, 2011, 31 (3): 29-34.

[5] 高昆侖, 劉建明, 徐茹枝, 等. 基于支持向量機(jī)和粒子群的信息網(wǎng)絡(luò)安全態(tài)勢(shì)復(fù)合預(yù)測(cè)模型[J]. 電網(wǎng)技術(shù), 2011, 35 (4): 176-182.

[6] 曾令全, 羅富寶, 丁金嫚. 禁忌搜索—粒子群算法在無(wú)功優(yōu)化中的應(yīng)用[J]. 電網(wǎng)技術(shù), 2011, 35 (7): 129-133.

[7] 王慶燕, 馬宏忠, 曹生讓. 多策略粒子群算法在磁懸浮承重裝置中的應(yīng)用[J]. 中國(guó)電機(jī)工程學(xué)報(bào), 2014, 34 (30): 5416-5424.

[8] 陳乃仕, 王海寧, 周海明, 等. 協(xié)同粒子群算法在電力市場(chǎng)ACE仿真中的應(yīng)用[J]. 電網(wǎng)技術(shù), 2010, 34 (2): 138-142.

[9] 張焱, 高興寶. 一種改進(jìn)的粒子群算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2009, 45 (26): 58-59.

[10] 陳金輝, 陳辰, 董飚. 基于自適應(yīng)策略的改進(jìn)粒子群算法[J]. 計(jì)算機(jī)仿真, 2015, 32 (3): 298-303.

[11] 張文成, 周穗華, 吳志東, 等. 改進(jìn)策略的粒子群算法及其實(shí)驗(yàn)測(cè)試[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2012, 33 (10): 3945-3949.

[12] 黃太安, 生佳根, 徐紅洋, 等. 一種改進(jìn)的簡(jiǎn)化粒子群算法[J]. 計(jì)算機(jī)仿真, 2013: 30 (2): 327-337.

[13] SHI Y, EBERHART R. A modified particle swarm optimizer[C]//IEEE World Congress on Computational Intelligence, 1998: 69-73.

[14] 邵增珍, 王洪國(guó), 劉弘. 具有啟發(fā)式探測(cè)及自學(xué)習(xí)特征的降維對(duì)稱(chēng)微粒群算法[J]. 計(jì)算機(jī)科學(xué), 2010, 37 (5): 219-222.

[15] 郭廣寒, 王志剛. 一種改進(jìn)的粒子群算法[J]. 哈爾濱理工大學(xué)學(xué)報(bào), 2010, 15 (3): 31-34.

[16] 敖永才, 師奕兵, 張偉, 等. 自適應(yīng)慣性權(quán)重的改進(jìn)粒子群算法[J]. 電子科技大學(xué)學(xué)報(bào), 2014, 43 (6): 874-880.