動態(tài)調(diào)整慣性權(quán)重的粒子群算法優(yōu)化①

吳 靜,羅 楊

(南華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,衡陽 421001)

1 引言

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是一種經(jīng)典元啟發(fā)式算法,是基于群體的智能隨機優(yōu)化算法.在1995年[1]被Kennedy J和Eberhart RC等提出,現(xiàn)今該算法已被許多學(xué)者關(guān)注并且在現(xiàn)實優(yōu)化問題上也受到廣泛運用[2,3],如神經(jīng)網(wǎng)絡(luò)、車輛控制等領(lǐng)域.粒子群算法設(shè)置的參數(shù)少、執(zhí)行速度較快、實現(xiàn)比較便捷[4],但是該算法也存在一些不足,比如較容易陷入局部最優(yōu)、后期收斂速度變慢或出現(xiàn)早熟收斂等問題.因此,許多研究學(xué)者對此想出了一些對策來優(yōu)化算法.Clerc[5]在把收縮因子的概念引入到粒子群算法中來更新算法的速度從而能更好的控制算法的收斂性.Taherkhani等[6]通過粒子歷史最佳位置以及距離得到不同慣性權(quán)重,提高粒子群算法在靜態(tài)、動態(tài)環(huán)境中最優(yōu)解的質(zhì)量和收斂速度.王永貴等[7]在算法中引入動態(tài)分裂算子以增加種群的多樣性避免陷入局部最優(yōu),而后采用指數(shù)衰減的慣性權(quán)重以平衡粒子的全局和局部的搜索.還有一些學(xué)者加入混沌搜索、混沌運動[8,9]的思想來優(yōu)化算法.通過對文獻[5-9]中粒子群算法改進思想研究的理解和對比,對粒子群基本原理理解的基礎(chǔ)上,本文提出了一種動態(tài)調(diào)整慣性權(quán)重的粒子群算法.

2 算法基礎(chǔ)理論

粒子群算法是從生物界鳥群捕食中獲得的靈感.模仿鳥類覓食的過程把每個粒子的運動過程比作小鳥,為了搜尋未知位置的食物即適應(yīng)值而逐步找尋最近的路線,即比作算法中尋找最優(yōu)解的過程.從一個隨機解出發(fā),通過迭代找到最優(yōu)解,以適應(yīng)度值來作為評判標準,屬于進化算法的一種,它的運作原理可以假設(shè)在一個N維搜索空間中,由m個粒子組成一個種群,每個粒子擁有位置和速度兩個屬性,設(shè)第i個粒子的位置表示為向量Xi=(xi1,xi2,…,xid),i=1,2,…,m；第i個粒子的速度可表示為向Vi=(vi1,vi2,…,vid),i= 1,2,…,m.隨著粒子位置和速度的不斷更新,全局最優(yōu)解和局部最優(yōu)解也不斷地更新,利用每個粒子屬性計算目標函數(shù)當前的適應(yīng)度,通過迭代更新從而找到最優(yōu)適應(yīng)值.算法中每個粒子的速度和位置更新公式：

式中,w表示的是慣性權(quán)重；j為當前迭代次數(shù)；c1,c2表示學(xué)習(xí)因子；r1,r2是隨機數(shù)在[0,1]范圍內(nèi)取值；pbesti表示局部最優(yōu)解；gbest表示全局最優(yōu)解[10].粒子群算法的終止條件一般為當前可達到的最大迭代次數(shù)或者在迭代結(jié)束之前達到了算法要求的精度.

算法的基本流程圖如圖1所示[11],算法的基本步驟如下：

Step 1.初始化算法中的各個固定有效參數(shù)值,包括種群大小MaxIt、最大迭代次數(shù)nPop等；

Step 2.初始化設(shè)置一個模型,用來存放粒子的速度、位置、適應(yīng)度值、最佳適應(yīng)度值和最佳位置,再從種群中挑選出某個粒子的最佳適應(yīng)度值以及其對應(yīng)的最佳位置；

Step 3.根據(jù)算法中每個粒子的速度和位置更新公式來更新粒子的位置和速度；

Step 4.計算出粒子的適應(yīng)度值,通過位置的不斷更新,找到每個粒子所能尋到的個體最優(yōu)pbest,每得到一個新的pbest來比較最優(yōu)值,哪個最優(yōu)就更新為全局最優(yōu)gbest,隨著一個個粒子的更新迭代來一步步更新全局最優(yōu)解gbest；

Step 5.判斷是否達到算法的終止條件,如果還未達到,就返回Step 3繼續(xù)；否則輸出結(jié)果.

圖1 算法流程圖

由于傳統(tǒng)的粒子群算法在后期比較容易陷入局部最優(yōu),多樣性減少且后期收斂速度過慢的問題,本文在下一章對粒子群算法進行了改進并進行對比實驗.

3 改進的粒子群算法

3.1 動態(tài)調(diào)整慣性權(quán)重的粒子群算法

慣性權(quán)重表示粒子的歷史速度對當前速度的影響,決定了新粒子對于歷史速度記憶的保持,具有平衡粒子偵察和開采的能力.慣性權(quán)重偏大時,表示對算法的全局搜索能力較強,而對于局部搜索則較弱,這對一些偏差較少的區(qū)域難以準確的找到極值；而當慣性權(quán)重偏小時,局部搜索能力則會有提高,而對全局搜索就會變?nèi)?這時粒子多樣性就會減少而導(dǎo)致對新的區(qū)域難以搜索[12].本文針對這一特點對慣性權(quán)重進行了優(yōu)化使算法能夠自適應(yīng).

將差分進化算法(DE)[13]的思想引用到粒子群算法中,該算法通過反復(fù)迭代進而將適應(yīng)度好的個體保留,不同于粒子群算法的是DE算法有自己的記憶能力,即可以動態(tài)地追蹤當前能夠搜索的情況來調(diào)整搜索策略,具有較好的全局收斂能力和魯棒性,利用此特性用來彌補粒子群算法后期容易陷入局部最優(yōu)的狀況.文獻[13]為了提升對短期電力負荷預(yù)測,對差分進化算法進行優(yōu)化,優(yōu)化其種群的變異算子,在防止種群多樣性減少的同時又能在后期加快收斂速度,最初的慣性只是一個固定取值,例如取值為1等,本文利用上述改進的差分進化算法引入到慣性權(quán)重參數(shù)中來實現(xiàn)對慣性權(quán)重的動態(tài)調(diào)整.

本文之所以將差分進化算法中改進后的變異算子加入到慣性權(quán)重中,是因為其引入了三角函數(shù)中的余弦函數(shù),余弦函數(shù)具有周期振蕩性,以總迭代次數(shù)為基礎(chǔ),使每個粒子在搜索時獲得振蕩擴大搜索空間增大種群多樣性,有助于粒子跳出局部最優(yōu),實驗證明用這種方法提高算法搜索效率能有效改善早熟現(xiàn)象.

優(yōu)化后的動態(tài)慣性權(quán)重如式(3)所示,其中nPop表示迭代的次數(shù),i則表示迭代次數(shù).

式中,a取值0.1,b取值0.2.

除了上述對慣性權(quán)重的改進,本文還加入了對邊界值[14]的處理,包括對速度的限制和位置邊界的限制,為了限制粒子的速度,設(shè)定有最大速度和最小速度,以搜索空間為基準設(shè)定速度,不同測試對應(yīng)不同速度,算法速度的最大值與最小值公式如式(4)和式(5)所示.

其中,VarMin表示最小搜索空間值,VarMax表示最大搜索空間值,k的取值為0.2.

為了防止粒子的搜索范圍會超出算法所規(guī)定的空間則對位置邊界也進行了設(shè)定,根據(jù)給定的搜索空間范圍,設(shè)定當前粒子的最大位置等同或者小于最大搜索空間值,同理當前粒子的最小值可以等同或者大于最小搜索空間值,但是兩者不能超過范圍之外.

4 算法結(jié)果分析

4.1 測試函數(shù)選擇

為了驗證優(yōu)化后的算法的有效性,將動態(tài)調(diào)整慣性權(quán)重的粒子群算法(PSO-I)與加入慣性系數(shù)阻尼比[15]的粒子群優(yōu)化算法(PSO-W)、文獻[5]中Clerc提出的帶收縮因子的粒子群算法(PSO-X)進行對比,在Windows 7旗艦版,MATLAB R2016a仿真軟件的條件下進行實驗.本文使用5個測試函數(shù)來驗證改進之后基于動態(tài)調(diào)整慣性權(quán)重的粒子群算法的有效性.基本參數(shù)設(shè)定為：c1取值為2,c2取值為2,種群數(shù)量MaxIt為50,種群維數(shù)為10,最大迭代次數(shù)nPop為200次.根據(jù)文獻[16]的測試研究選出以下幾個測試函數(shù)：

F1：Sphere 函數(shù)

對Sphere設(shè)定的搜索空間為[-10,10]n.

F2：Rosenbrock 函數(shù)

對Rosenbrock設(shè)定的搜索空間為[-10,10]n.

F3：Ackley 函數(shù)

對Ackley函數(shù)設(shè)定的搜索空間為[-30,30]n.

F4：Rastrigin 函數(shù)

Rastrigin函數(shù)設(shè)定的搜索空間為[-5,5]n.

F5：Griewank 函數(shù)

對Griewank搜索空間設(shè)為[-600,600]n.

針對以上5個不同的函數(shù)進行對比性測驗來比較3個算法,以上5個函數(shù)的理論最優(yōu)值均為0.

4.2 測試結(jié)果分析

對以上5個測試函數(shù)進行200迭代尋優(yōu)[16]后,計算出200次的平均值和均方差如表1所示.

從表1可以看出,在對函數(shù)F1、F2、F4和F5的測試中相對于PSO-W和PSO-X而言,PSO-I的平均值有明顯的優(yōu)化,且PSO-I的均方差也有進一步提升,說明優(yōu)化算法PSO-I穩(wěn)定性相對的進步了.函數(shù)F3在均值方面雖然沒有明顯的提升,但是在均方差數(shù)據(jù)上卻有較好的提高,說明動態(tài)調(diào)整慣性權(quán)重的粒子群算法(PSO-I)針對此類函數(shù)在穩(wěn)定性上有所提升,而函數(shù)F3的測試值則顯示PSO-W、PSO-X和PSO-I 3個算法的均值和均方差的結(jié)果相似,并無過大的浮動,說明動態(tài)調(diào)整慣性權(quán)重的粒子群算法在對F3這類的函數(shù)上沒有過人之處.綜上所述,PSO-I算法對于F1、F2、F4和F5這類函數(shù)的改進是有意義的.

表1 3種算法的均值和均方差

表1中,Mean表示平均值,Std表示均方差.

為了讓讀者能更清楚地觀察到改進后的動態(tài)調(diào)整慣性權(quán)重的粒子群算法和其他兩種優(yōu)化算法相比的收斂效果,通過5個測試函數(shù)的實驗仿真結(jié)果來真實地反饋出PSO-W、PSO-X和PSO-I 3個粒子群優(yōu)化算法的收斂情況.其仿真結(jié)果如圖2～圖6所示.

從5個圖中可以看出,相較于PSO-X和PSO-W算法,PSO-I算法對5個函數(shù)的收斂性都有所提升,對于函數(shù)F4和函數(shù)F5的后期收斂效果有明顯的提高,對于函數(shù)F1和函數(shù)F3而言只是有略微的提高,而對于函數(shù)F2來看與帶有收縮因子的粒子群優(yōu)化算法(PSO-X)相比并沒有明顯的提升.

5 結(jié)束語

經(jīng)過上述實驗的分析與對比,考慮到了原本粒子群算法后期出現(xiàn)收斂過慢且易陷入局部收斂的問題,提出了能動態(tài)調(diào)整慣性權(quán)重的粒子群算法(PSO-I),將差分進化算法思想融入到粒子群算法中,改進慣性權(quán)重一貫的固定值,使其能夠進行動態(tài)的調(diào)節(jié)來適應(yīng)當前的適應(yīng)度.將動態(tài)調(diào)整慣性權(quán)重的算法(PSO-I)與另外2種粒子群算法PSO-X和PSO-W進行仿真對比測試,從最后得出的數(shù)據(jù)和圖形結(jié)果來看,優(yōu)化慣性權(quán)重后的粒子群算法在穩(wěn)定性和后期收斂速度上都有所提升,但是對于部分測試函數(shù)的提高不是很明顯,因此而言,該算法在后期的有效性上還是有待提高.

圖2 Sphere

圖3 Rosenbrock

圖4 Ackley

圖5 Rastrigin

圖6 Griewank