動態(tài)改變慣性權重的新模式粒子群算法

杜 江，袁中華，王景芹

(河北工業(yè)大學 電磁場與電器可靠性省部共建重點實驗室，天津 300130)

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

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

論文針對標準粒子群算法的不足，通過實時調整慣性權重和粒子飛行路線，構建了一種新的改進的粒子群算法(particle swarm optimization algorithm with dynamically changing inertia weight，簡稱DMPSO).通過4個標準測試函數(shù)對改進后粒子群算法的性能進行測試，證明了改進算法求解復雜優(yōu)化問題時具有更高的求解精度和求解成功率.

1 標準粒子群算法

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

(1)

(2)

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

2 粒子群算法的改進

2.1 慣性權重的改變

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

關于如何實時控制w的大小，國內外學者進行了大量研究.文[13]提出線性減小慣性權重的方法(linearly decreasing weight, 簡稱LDW)，如下式

(3)

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

LDW方法控制直接、實現(xiàn)簡單，但因為對w的調整只考慮了算法所處的迭代階段，所以很難適應復雜、非線性問題的求解，對標準算法性能的提升非常有限.

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

(4)

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

考慮實時檢測解空間內粒子的分布情況，論文采用文[14]提出的分布熵來表示，如下式

(5)

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

E(die)越小說明粒子越集中，此時應為α賦一較大值，即加強全局搜索；反之，E(die)越大說明粒子越分散，此時應為α賦一較小值，即加強局部搜索.α的具體調整方法如下式

(6)

其中：E1、E2分別為粒子分布熵的上、下門檻值(應滿足E1

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

2.2 飛行模式的調整

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

(7)

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

2.3 改進后的算法流程

改進后的粒子群算法流程描述如下：

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

步驟2計算每個粒子的適應值；

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

步驟4根據(jù)式(4)～(6)調整慣性權重w；

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

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

3 仿真實驗

3.1 實驗設計

為了測試改進算法的有效性，對4個標準測試函數(shù)進行仿真試驗，并與標準粒子群算法(PSO)、文[13]提出的線性減小慣性權重的方法(LDW)、文[9]提出的調整慣性權重的方法(MPSO)相對比.4個測試函數(shù)的名稱、表達式等信息如表1所示.其中：f1為單峰函數(shù)，f2、f3、f4為多峰函數(shù).

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

實驗從3個方面進行測試[16]：

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

(2) 通過多次試驗的平均進化曲線比較4種算法的收斂速度；

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

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

3.2 仿真結果及分析

3.2.1 算法求解精度對比

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

由表2可以看出，在簡單問題(單峰函數(shù)f1)求解時，LDW、MPSO(new model particle swarm optimization)和DMPSO的求解精度均低于PSO，這是因為改進后算法通過對慣性權重的調整，使之更側重于全局搜索，而在一定程度上削弱了局部搜索.在復雜問題(高維度多峰函數(shù)f2、f3、f4)求解時，DMPSO與其他3種算法相比，具有更高的求解精度.

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

3.2.2 算法收斂速度對比

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

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

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

3.2.3 算法收斂成功率對比

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

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

每一種算法對每一個測試函數(shù)進行50次仿真試驗，迭代次數(shù)達到1 000次時仍未達到指定收斂精度，則認為此次試驗沒有收斂.記錄收斂成功次數(shù)，并計算收斂成功率如表4所示.其中：收斂成功率=收斂成功次數(shù)/50.

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

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

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

4 結束語

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

參考文獻：

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

[2] 溫濤, 盛國軍, 郭權, 等. 基于改進粒子群算法的Web服務組合[J]. 計算機學報, 2013, 36 (5): 1031-1046.

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

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

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

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

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

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

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

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

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

[12] 黃太安, 生佳根, 徐紅洋, 等. 一種改進的簡化粒子群算法[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] 邵增珍, 王洪國, 劉弘. 具有啟發(fā)式探測及自學習特征的降維對稱微粒群算法[J]. 計算機科學, 2010, 37 (5): 219-222.

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

[16] 敖永才, 師奕兵, 張偉, 等. 自適應慣性權重的改進粒子群算法[J]. 電子科技大學學報, 2014, 43 (6): 874-880.