吳 靜,羅 楊

(南華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,衡陽(yáng) 421001)

1 引言

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

2 算法基礎(chǔ)理論

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

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

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

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

Step 2.初始化設(shè)置一個(gè)模型,用來(lái)存放粒子的速度、位置、適應(yīng)度值、最佳適應(yīng)度值和最佳位置,再?gòu)姆N群中挑選出某個(gè)粒子的最佳適應(yīng)度值以及其對(duì)應(yīng)的最佳位置；

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

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

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

圖1 算法流程圖

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

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

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

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

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

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

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

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

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

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

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

4 算法結(jié)果分析

4.1 測(cè)試函數(shù)選擇

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

F1：Sphere 函數(shù)

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

F2：Rosenbrock 函數(shù)

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

F3：Ackley 函數(shù)

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

F4：Rastrigin 函數(shù)

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

F5：Griewank 函數(shù)

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

針對(duì)以上5個(gè)不同的函數(shù)進(jìn)行對(duì)比性測(cè)驗(yàn)來(lái)比較3個(gè)算法,以上5個(gè)函數(shù)的理論最優(yōu)值均為0.

4.2 測(cè)試結(jié)果分析

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

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

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

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

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

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

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

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

圖2 Sphere

圖3 Rosenbrock

圖4 Ackley

圖5 Rastrigin

圖6 Griewank