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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

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

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

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

(4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5結(jié)論

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

參考文獻(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個(gè)函數(shù)的適應(yīng)度值變化 圖6　簡(jiǎn)化的PSO算法中、6個(gè)函數(shù)的適應(yīng)度值變化

圖7　本文改進(jìn)的PSO算法中6個(gè)函數(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ù)測(cè)控制中應(yīng)用[J].大連理工大學(xué)學(xué)報(bào)，2015，55(1):89-96.

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

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

[8]華志強(qiáng)，張春生.長(zhǎng)尾加權(quán)相依的隨機(jī)變量和的精度大偏差[J].湖北民族學(xué)院學(xué)報(bào)(自然科學(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]趙志剛，黃樹(shù)運(yùn)，王偉倩. 基于隨機(jī)慣性權(quán)重的簡(jiǎn)化粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31(22)：361-363.

[11]胡旺，李志蜀.一種更簡(jiǎn)化而高效的粒子群優(yōu)化算法[J].軟件學(xué)報(bào)，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ì)算機(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]劉金承,費(fèi)佳慧.改進(jìn)的動(dòng)物遷徒算法求解全局優(yōu)化問(wèn)題[J].長(zhǎng)春大學(xué)學(xué)報(bào),2015,25(8)：42-49.

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

責(zé)任編輯：時(shí)凌

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.

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

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

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

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

中圖分類號(hào)：O224

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