改進(jìn)慣性權(quán)重的簡化粒子群優(yōu)化算法

高　葦，平　環(huán)，張成剛，姜靜清

(1.內(nèi)蒙古民族大學(xué) 數(shù)學(xué)學(xué)院，內(nèi)蒙古 通遼028000;2.內(nèi)蒙古民族大學(xué) 計算機(jī)與科學(xué)學(xué)院,內(nèi)蒙古 通遼 028000)

?

改進(jìn)慣性權(quán)重的簡化粒子群優(yōu)化算法

高葦1，平環(huán)1，張成剛1，姜靜清2*

(1.內(nèi)蒙古民族大學(xué) 數(shù)學(xué)學(xué)院，內(nèi)蒙古 通遼028000;2.內(nèi)蒙古民族大學(xué) 計算機(jī)與科學(xué)學(xué)院,內(nèi)蒙古 通遼 028000)

摘要：針對傳統(tǒng)的粒子群優(yōu)化算法收斂速度慢、易陷入局部空間極值的缺點，提出一種基于簡化粒子群優(yōu)化算法同時改進(jìn)慣性權(quán)重的新算法.該算法首先去掉速度項，使算法更加簡便，然后改進(jìn)位移項，最后改進(jìn)慣性權(quán)重.對6個經(jīng)典函數(shù)分別采用傳統(tǒng)的粒子群優(yōu)化算法、簡化的粒子群優(yōu)化算法和該改進(jìn)的算法進(jìn)行比較，數(shù)值實驗表明，該改進(jìn)的粒子群優(yōu)化算法比其他兩個算法的性能好.

關(guān)鍵詞：速度項；慣性權(quán)重；經(jīng)典函數(shù)

1995年由Kennedy和Eberhart[1]提出的粒子群優(yōu)化算法(PSO)是一種由對鳥群研究而得到的智能優(yōu)化算法，粒子群優(yōu)化算法是通過對大量的鳥群、魚群、人類社會系統(tǒng)的研究證實了群體中個體之間信息的社會共享，有助于整體進(jìn)化.PSO提出后，由于過程簡單、原理易懂、收斂速度快，很快得到人們的關(guān)注.被運用于很多領(lǐng)域，例如圖像處理[2]、硬件加速器[3]、工業(yè)[4-5]、生物[6]、財務(wù)[7]等.

在粒子群優(yōu)化算法中參數(shù)是很重要的，尤其是慣性權(quán)重，它能夠影響算法的開發(fā)能力和探索能力，因此可以通過調(diào)節(jié)慣性權(quán)重的值來決定了粒子先前飛行速度對當(dāng)前速度的影響程度.當(dāng)慣性權(quán)重較大時，粒子速度也會增大，局部搜索的能力從而減弱，全局搜索的能力從而增強；當(dāng)慣性權(quán)重較小時，粒子速度也會降小，局部搜索的能力從而增強，全局搜索的能力從而減弱.因此恰當(dāng)?shù)母淖儜T性權(quán)重值可以很好地提高算法的性能.但是隨著研究的深入以及現(xiàn)實中的各種問題的出現(xiàn)如數(shù)學(xué)精確度[8]，逐漸暴露出傳統(tǒng)PSO算法的各種問題，主要有粒子易陷入局部空間最優(yōu)、后期粒子收斂速度過慢、搜索解的精度低等.為了增強粒子群優(yōu)化算法的性能，人們從很多方面進(jìn)行了改進(jìn).例如文獻(xiàn)[9]經(jīng)過反復(fù)實驗建議慣性權(quán)重采用從0.9線性遞減到0.4的策略.文獻(xiàn)[10]對粒子群算法更新公式進(jìn)行簡化，即去除掉速度項公式，通過位置公式進(jìn)行粒子更新.并通過隨機(jī)分布的方式獲取慣性權(quán)重從而提高粒子群算法的搜索能力，同時采用異步變化的學(xué)習(xí)因子的策略來改善粒子的學(xué)習(xí)能力.文獻(xiàn)[11]提出改進(jìn)的PSO算法不包含速度項參數(shù)，利用所有粒子的個體最優(yōu)位置信息，提高算法的性能.本文在文獻(xiàn)[11]的基礎(chǔ)上，為了更好的搜索到目標(biāo)函數(shù)值，對慣性權(quán)重進(jìn)行了改進(jìn)，通過粒子與粒子之間的影響，去掉速度項，同時利用迭代次數(shù)對慣性權(quán)重進(jìn)行動態(tài)改進(jìn)，從而增強粒子群優(yōu)化算法更新公式的收斂能力，并且改進(jìn)粒子群算法極易陷入局部搜索最優(yōu)的缺點.

1傳統(tǒng)的粒子群優(yōu)化算法

首先PSO算法初始化產(chǎn)生一群沒有體積沒有質(zhì)量的隨機(jī)粒子，每個粒子都有位移項和速度項，可以把每個粒子當(dāng)作一個可行解，而真正好的可行解還要用適應(yīng)度函數(shù)來確定.一般情況下在解空間進(jìn)行搜索粒子都追隨所在種群最好的粒子，并不斷更新自身的位置，逐代搜索得到所要求的最優(yōu)解.

對于每個粒子i的第d維的速度和位置分別按下面公式進(jìn)行更新.

(1)

(2)

其中：t為當(dāng)前迭代次數(shù)，w為慣性權(quán)重，c1，c2為學(xué)習(xí)因子，r1，r2為[0，1]之間的隨機(jī)數(shù).

式(1)有三個成面構(gòu)成：第一個成面是當(dāng)代粒子對前代粒子速度的繼承學(xué)習(xí)，表現(xiàn)當(dāng)代粒子對前一代運動過程的認(rèn)可；第二個成面是當(dāng)代粒子對粒子自身的識別，表示粒子結(jié)合自身以往的經(jīng)歷思考學(xué)習(xí)的認(rèn)知；第三個成面是算法對全部粒子的辨識，表示各個粒子間的信息共享與相互合作.這個更新公式必須是合法的，更新完之后檢查位置是否合法.若不合法必須進(jìn)行修正，修正一般是重新隨機(jī)設(shè)定位置或限定在邊界，通常在搜索空間PSO算法終止條件是達(dá)到設(shè)定的迭代次數(shù)或者是達(dá)到目標(biāo)函數(shù)需要的精確度.

2粒子群優(yōu)化算法的改進(jìn)

1)去掉速度項.為了避免傳統(tǒng)粒子群優(yōu)化算法容易陷入局部極值，進(jìn)化后期的收斂速度慢和精度低等問題，文獻(xiàn)[11]對傳統(tǒng)的粒子群算法更新公式進(jìn)行了改進(jìn)，即去掉速度更新公式，在搜索過程僅由位置更行公式進(jìn)行迭代，從而得到更加簡單的結(jié)構(gòu)的粒子群優(yōu)化算法.在傳統(tǒng)PSO算法搜索過程中，粒子根據(jù)速度項來變換位移項，并沒有考慮粒子與粒子之間的影響.事實上，粒子之間是有影響的.通過去掉粒子速度項，迭代方程也由原來的兩個更新公式降為一個公式，同時利用了粒子最優(yōu)位置，得到簡化粒子群優(yōu)化算法.更新公式如下：

(3)

其中：pad為所有的個體最優(yōu)位置的平均值，pid為粒子自身個體最優(yōu)位置，pgd為粒子種群的全局最優(yōu)位置.這個方法使得粒子在迭代過程更簡便，比傳統(tǒng)的粒子群算法更快的得到最優(yōu)解.

2)改進(jìn)慣性權(quán)重.在去掉速度項的簡化粒子群優(yōu)化算法的基礎(chǔ)上，再對傳統(tǒng)PSO算法中的慣性權(quán)重進(jìn)行改進(jìn).在PSO算法中慣性權(quán)重很重要，通過改進(jìn)慣性權(quán)重能夠有效地提高PSO算法的搜索性能.一般固定情況下把w設(shè)為0.729對算法更有利[12]，非固定的有非線性的情況[13-14]和線性的情況[15]等.

傳統(tǒng)的PSO算法一般采用線性減少的慣性權(quán)重，但是隨著搜索空間的范圍逐漸縮小，使得粒子容易收斂到局部鄰域的極值點，從而使得粒子群算法極易收斂到局部極值.

為了解決上述PSO算法的不足，本文在動態(tài)改變慣性權(quán)重的粒子群優(yōu)化算法基礎(chǔ)上，對慣性權(quán)重更進(jìn)一步改進(jìn).改進(jìn)的慣性權(quán)重如下：

(4)

前半部分e-αn/αn-1中，根據(jù)所得函數(shù)值αn指標(biāo)在每次迭代時都進(jìn)行變化.通過位置的改變使得w線性減小，從而使wn動態(tài)改變.在式(4)中慣性權(quán)重wn充分利用了目標(biāo)函數(shù)的信息，增強了搜索方向的啟發(fā)性.又因為αn較大，αn/αn-1在不同的迭代次數(shù)中變化也過大，因此式(4)以e為底來降低它們的變化幅值，改善wn的平滑性，從而使得e-αn/αn-1在[0，1]內(nèi)，但是還存在著一定的收斂速度過快和陷入局部極值的缺點.為了更接近基本PSO算法w的取值區(qū)間[0.4，0.9]，在后面添加了一個線性遞增的公式(wini-wfin)tn/tmax，此公式隨著每次迭代次數(shù)的增加而變化.用前半部分減去后半部分，使得整個慣性權(quán)重在動態(tài)遞減，而且更加接近[0.4，0.9].當(dāng)0<αn/αn-1<1時，說明在這次迭代中算法總體呈現(xiàn)收斂，當(dāng)αn/αn-1數(shù)值減小，wn將越來越接近0.9，迭代之間的步長增大；當(dāng)αn/αn-1>1時說明在這次迭代中算法總體呈現(xiàn)發(fā)散，αn/αn-1比值增大，wn將慢慢接近0.4，迭代之間步長減小.

在式(4)中前半部分不僅單調(diào)減小，而且與目標(biāo)函數(shù)緊密聯(lián)系，同時通過后半部分的調(diào)節(jié)，使慣性權(quán)重起伏不至于過大.這使得粒子群優(yōu)化算法改進(jìn)后不僅加快了收斂的速度，而且局部最優(yōu)問題得到很好的解決.

3改進(jìn)后的PSO算法的步驟

2)根據(jù)式(4)計算出慣性權(quán)重；

3)計算各個粒子的函數(shù)適應(yīng)度值，并進(jìn)行判斷最優(yōu)適應(yīng)度值；

4)根據(jù)式(3)對粒子的位置進(jìn)行更新；

5)若粒子群迭代達(dá)到搜索的終止條件，就輸出目標(biāo)函數(shù)的極值，若不然回到步驟3)再次根據(jù)步驟搜索.

4 函數(shù)測試

為了驗證改進(jìn)后PSO的效率，采用6個常用的目標(biāo)函數(shù)對其進(jìn)行測試，并對仿真結(jié)果的數(shù)據(jù)與標(biāo)準(zhǔn)的粒子群優(yōu)化算法[1]、簡化粒子群優(yōu)化算法進(jìn)行對比.所需的參數(shù)設(shè)置如下：粒子種群規(guī)模m=30，維數(shù)D=20，最大迭代次數(shù)50，學(xué)習(xí)因子c1=c2=2.05.

6個基準(zhǔn)測試函數(shù)[16-18]如下：

表1～3顯示對于Sphere函數(shù)，采用三種算法，分別迭代50次的適應(yīng)度值變化情況,結(jié)果見表1～3.

圖1和圖2是Rosenbrock和Shaffer′sf 6在三種粒子群優(yōu)化算法下性能的比較.分別采用三種算法各自計算50次，圖中所用數(shù)據(jù)是最好一次的適應(yīng)度值.從圖1中可以看出簡化后的PSO算法和本文提出的改進(jìn)PSO算法比標(biāo)準(zhǔn)的PSO算法收斂速度快，可以快速搜索到目標(biāo)函數(shù)的準(zhǔn)最優(yōu)解.但是這兩個圖不能明顯的看出簡化的PSO算法和本文的改進(jìn)PSO算法的性能差異，所以又單獨對兩種方法進(jìn)行比較.圖3和圖4是Rosenbrock和Shaffer′sf 6函數(shù)采用這兩種方法的性能比較.從這兩個圖可以明顯地看出本文改進(jìn)的PSO算法的性能優(yōu)于簡化的PSO算法的性能.改進(jìn)的慣性權(quán)重使得搜索前半部分位移變化速度快，后半部分位移變化速度慢，防止陷入局部最優(yōu)，能夠更好的搜索目標(biāo)函數(shù)的值.

表1　傳統(tǒng)粒子群算法下的適應(yīng)度值的變化

表2　簡化粒子群算法下的適應(yīng)度值的變化

表3　本文改進(jìn)的算法下的適應(yīng)度值的變化

圖5～7分別表現(xiàn)了三種算法對6個函數(shù)計算時適應(yīng)度值的變化.

5結(jié)論

針對傳統(tǒng)的粒子群優(yōu)化算法速度收斂較慢而且易陷入局部空間極值的缺點，本文提出一種對慣性權(quán)重進(jìn)行改進(jìn)的PSO算法.該算法首先去掉速度項，使算法更加簡便，然后利用例子之間的關(guān)系和迭代次數(shù)改進(jìn)位移項.最后改進(jìn)慣性權(quán)重，使算法在開始時權(quán)重變化較大，后期權(quán)重變化較小，有利于局部搜索.對6個經(jīng)典函數(shù)分別采用傳統(tǒng)的粒子群優(yōu)化算法、簡化的粒子群優(yōu)化算法和本文改進(jìn)的算法進(jìn)行比較，實驗結(jié)果表明，本文改進(jìn)的粒子群優(yōu)化算法的收斂速度快，同時避免了陷入局部極值，該算法性能優(yōu)于其他兩個算法.

參考文獻(xiàn):

[1]J Kennedy，R C Eberhart.Particle swarm optimization[J].Proc IEEE Int Conf Neural Networks，1995(4)：1942-1948.

圖1　Rosenbrock函數(shù)在三種算法中適應(yīng)度值的變化 圖2　Shaffer′s f 7函數(shù)在三種算法中適應(yīng)度值的變化

圖3　Rosenbrock函數(shù)在兩種算法中適應(yīng)度值的變化 圖4　Shaffer′s f 7 函數(shù)在兩種算法中適應(yīng)度值的變化

圖5　基本PSO算法中6個函數(shù)的適應(yīng)度值變化 圖6　簡化的PSO算法中、6個函數(shù)的適應(yīng)度值變化

圖7　本文改進(jìn)的PSO算法中6個函數(shù)的適應(yīng)度值變化Fig.7　The fitness of the improved PSO algorithm in six fitness function value changes

[2]SETAYESHh M，ZHANG Mengjie，JOHNSTON M.A novel particle swarm optimization approach to detecting continuous,thin and smooth edges in noisy images[J].Information Sciences，2013，246：28-51.

[3]CALAZAN R M，NEDJAH N，MOURELLE L M.A hardware accelerator for particle swarm optimization[J].Applied Soft Computing，2014，14：347-356.

[4]ECHEVARR L C，SANTIAGO O L，F(xiàn)AJARDO J A H,et al.A variant of the particle swarm optimization for the improvement of fault diagnosis in industrial systems via faults estimation[J].Engineering Applications of Artificial Intelligence，2014，212：1-16.

[5]孫志民，趙珺，王偉.基于高斯搜索的改進(jìn)粒子群優(yōu)化在磨礦預(yù)測控制中應(yīng)用[J].大連理工大學(xué)學(xué)報，2015，55(1):89-96.

[6]李娜，黃治國.改進(jìn)的小生物粒子群優(yōu)化算法[J].軟件導(dǎo)刊，2015，14(2):45-47.

[7]彭靜，彭勇，歐陽令南.基于粒子群算法和支持向量機(jī)的財務(wù)危機(jī)預(yù)警模式[J].上海交通大學(xué)學(xué)報，2008，42(4):615-620.

[8]華志強，張春生.長尾加權(quán)相依的隨機(jī)變量和的精度大偏差[J].湖北民族學(xué)院學(xué)報(自然科學(xué)版)，2015，33(2)：121-123.

[9]SHI Y，EBERHART R C.Fuzzy Adaptive Particle Swarm Optimization [C]// Proceedings of the Congress on Evolutionary Computation,Seoul,Korea,2001：101-106.

[10]趙志剛，黃樹運，王偉倩. 基于隨機(jī)慣性權(quán)重的簡化粒子群優(yōu)化算法[J].計算機(jī)應(yīng)用研究，2014，31(22)：361-363.

[11]胡旺，李志蜀.一種更簡化而高效的粒子群優(yōu)化算法[J].軟件學(xué)報，2007，18(4)：861-868.

[12]SHI Y，EBERHART R C.Empirical Study of Particle Swarm Optimization[C]// Proc IEEE Congr Evol Comput，1999：1945-1950.

[13]邵洪濤，秦亮曦.帶變異算子的非線性慣性權(quán)重PSO算法[J].計算機(jī)技術(shù)與發(fā)展，2012，22(8)：30-38.

[14]CHATTERJEE A，SIARRY P.Nonlinear Inertia Weight Variation for Dynamic Adaption in Particle Swarm Optimization [J].Comput Oper Res，2006，33：859-871.

[15]YANG Tang，WANG Zidong，F(xiàn)ANG Jianan.Feedback learning Particle Swarm Optimization[J].Appl Soft Comput，2011，11：4713-4725.

[16]紀(jì)震，廖惠連，吳青華.粒子群算法及應(yīng)用[M].北京：科學(xué)出版社，2009：87-98.

[17]劉金承,費佳慧.改進(jìn)的動物遷徒算法求解全局優(yōu)化問題[J].長春大學(xué)學(xué)報,2015,25(8)：42-49.

[18]谷志剛,孫鋒利.基于粒子群脊波神經(jīng)網(wǎng)絡(luò)的飛機(jī)目標(biāo)識別[J].延邊大學(xué)學(xué)報(自然科學(xué)版),2014,40(4)：346-351.

責(zé)任編輯：時凌

Simplified Particle Swarm Optimization Algorithm Based on Improved Inertia Weight

GAO Wei1，PING Huan1，ZHANG Chenggang1，JIANG Jingqing2*

1.College of Mathematics，Inner Mongolia University for the Nationalities，Tongliao 028000，China；2.College of Computer Science and Technology,Inner Mongolia University for the Nationalities，Tongliao 028000，China)

Abstract：For the shortcomings of the traditional particle swarm optimization algorithm,which is easy to fall into local extreme,a new algorithm based on the simplified particle swarm optimization algorithm is proposed.Firstly，it removes the speed term，so it makes the algorithm simple.And then it mproves the displacement term.Finally it improves the inertia weight.Six classical functions are used to compare the traditional particle swarm optimization algorithm,the simplified particle swarm optimization algorithm and the improved algorithm proposed in this paper.The experimental results show that the performance of the improved particle swarm optimization is better than the other two algorithms.

Key words：velocity term；inertia weight；classical functions

收稿日期：2015-11-16.

基金項目：國家自然科學(xué)基金項目(61373067，61163034)；內(nèi)蒙古自然科學(xué)基金項目(2013MS0910).

作者簡介：高葦(1991- )，女，碩士生，主要從事智能算法的研究；*通信作者：姜靜清(1968- )，女，博士，教授，主要從事計算智能、樓式識別、深度學(xué)習(xí)的研究.

文章編號：1008-8423(2016)01-0011-05

DOI:10.13501/j.cnki.42-1569/n.2016.03.003

中圖分類號：O224

文獻(xiàn)標(biāo)志碼：A