自適應(yīng)慣性權(quán)重的粒子群優(yōu)化算法

張淵博,鄒德旋,張春韻,杜星瀚

(江蘇師范大學(xué)電氣工程及自動(dòng)化學(xué)院,江蘇 徐州 221116)

1 引言

群智能優(yōu)化算法[1]是模擬昆蟲、獸群、鳥群和魚群的群體行為,這些群體按照一種合作的方式尋找食物,群體中的每個(gè)成員通過學(xué)習(xí)它自身的經(jīng)驗(yàn)和其它成員的經(jīng)驗(yàn)來不斷地改變搜索的方向。群體智能優(yōu)化算法的突出特點(diǎn)就是利用了種群的群體智慧進(jìn)行協(xié)同搜索,從而在解空間內(nèi)找到最優(yōu)解。其中粒子群算法結(jié)構(gòu)簡(jiǎn)單、參數(shù)少、容易實(shí)現(xiàn),收斂速度較快。該算法已成功應(yīng)用于許多領(lǐng)域如圖像分割[2]、路徑規(guī)劃[3]、車間調(diào)度[4]、系統(tǒng)優(yōu)化[5]。

盡管粒子群優(yōu)化算法優(yōu)勢(shì)眾多,但粒子群算法容易陷入早熟收斂而找不到最優(yōu)解,存在收斂后期種群多樣性較差、速度較慢。因此學(xué)者們針對(duì)局部收斂、不變性、穩(wěn)定性、參數(shù)設(shè)置和拓?fù)浣Y(jié)構(gòu)進(jìn)行研究,對(duì)粒子群算法改進(jìn),并提出了許多算法的變體。文獻(xiàn)[6]提出了一種基于粒子群算法的自適應(yīng)變異差分進(jìn)化算法,在迭代早期,算法有效地利用改進(jìn)的DE/rand/1突變策略來探索較好的區(qū)域,從而提高逃離局部最優(yōu)的能力。在進(jìn)化的后期,利用粒子群算法的變異策略有效地加快了收斂速度。文獻(xiàn)[7]采用動(dòng)態(tài)自適應(yīng)慣性加權(quán)因子,并將遺傳算法(Genetic Algorithm,GA)[8]相關(guān)算子引入粒子群算法中,通過交叉和n點(diǎn)變異算子自適應(yīng)地選擇滿足遺傳算法選擇準(zhǔn)則且選擇概率隨時(shí)間變化的粒子群,更新其位置。文獻(xiàn)[9]提出全息粒子群算法采用了整體結(jié)構(gòu)和自相似結(jié)構(gòu)。將不同的粒子分為不同的組和級(jí),組內(nèi)之間粒子進(jìn)行信息交換,用一組中最好的粒子進(jìn)行不同級(jí)粒子的信息交換。該結(jié)構(gòu)提高了粒子群算法的速度和精度。廖星等[10]運(yùn)用線性遞減慣性權(quán)重與正態(tài)隨機(jī)數(shù)的隨機(jī)慣性權(quán)重提出了一種自適應(yīng)慣性權(quán)重粒子群優(yōu)化算法,并引入壓縮因子與變學(xué)習(xí)因子減小慣性權(quán)重的影響,最后使用GPU并行的運(yùn)行算法,加快運(yùn)行速度。

李龍澍等[11]針對(duì)PSO算法易陷入局部極值的缺陷,提出了一種新的自適應(yīng)慣性權(quán)重混沌PSO算法(New Adaptive Inertial Weight Chaotic Particle Swarm Optimizatio, CPSO-NAIW)。該算法首先采用新的權(quán)重自適應(yīng)方法,通過粒子與群體極值位置距離對(duì)權(quán)重進(jìn)行調(diào)整,使權(quán)重的調(diào)整與粒子的狀態(tài)位置狀態(tài)信息相結(jié)合,然后采用基于混沌優(yōu)化擺脫局部極值的方法,在算法陷入局部極值時(shí),對(duì)群體極值進(jìn)行混沌調(diào)整,以使各個(gè)粒子在追逐不同群體極值位置進(jìn)行更新時(shí),可以改變尋優(yōu)軌跡,提高了算法擺脫局部極值的能力。吳凡等[12]提出一種慣性權(quán)重曲線遞增策略的改進(jìn)算法(Curve Increment Particle Swarm Optimization, CIPSO),有效避免早熟問題,在處理“維度災(zāi)難”問題上,尋優(yōu)性能更強(qiáng),且具備良好的平衡全局與局部尋優(yōu)性能。以上現(xiàn)有方法都通過自適應(yīng)權(quán)重平衡全局與局部尋優(yōu)能力,但對(duì)于多峰測(cè)試函數(shù),算法仍陷入局部最優(yōu)。

為了使算法在進(jìn)化前期鎖定較好區(qū)域,在進(jìn)化后期提高局部搜索能力,提出一種自適應(yīng)慣性權(quán)重的粒子群優(yōu)化算法(Stochastic Inertial-Weighted Particle Swarm Optimization, AIWPSO),算法主要是對(duì)慣性權(quán)重、學(xué)習(xí)因子進(jìn)行改進(jìn),并加入局部搜索策略。最后通過標(biāo)準(zhǔn)測(cè)試函數(shù)與其它算法對(duì)比,驗(yàn)證了該算法的有效性。

2 基本粒子群優(yōu)化算法

粒子群優(yōu)化算法是由Kennedy[13]和Eberhart[14]在1995年提出的一種啟發(fā)式的群體智能算法,是一種無梯度優(yōu)化算法,其靈感來自于移動(dòng)生物的社會(huì)行為,如鳥群的移動(dòng),來達(dá)到同樣的目標(biāo)。運(yùn)動(dòng)是基于粒子在搜索空間中最佳的位置(即局部最好的位置),以及整個(gè)搜索空間中最佳的位置群(即全局最佳)。假設(shè)搜索空間有d維(d= 1,2,…D)每個(gè)粒子i的位置和速度分別用Vi=(vid,…,viD),Xi=(xid,…,xiD)表示。對(duì)于每次迭代或時(shí)間步長(zhǎng)t,速度被用來更新的下一個(gè)位置,每個(gè)粒子的計(jì)算公式為

vid(t+1)=wvid(t)+c1r1(pgd-xid(t))+c2r2(pid-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1)

(2)

對(duì)于每個(gè)粒子i和維數(shù)d,通過以上方程(1)式更新粒子的速度vid和(2)式更新粒子的位置xid。在式(1)中,w是動(dòng)量的權(quán)重,它影響到前一個(gè)速度對(duì)下一個(gè)粒子運(yùn)動(dòng)的影響程度。群體的最佳位置記為pgd,用常數(shù)c1加權(quán),c1為個(gè)體學(xué)習(xí)因子。c2為社會(huì)學(xué)習(xí)因子,對(duì)每個(gè)粒子pid的最佳位置加權(quán)。r1、r2為r(0,1)的均勻隨機(jī)數(shù)樣本。

3 自適應(yīng)權(quán)重粒子群優(yōu)化算法

避免速度向量使粒子發(fā)散導(dǎo)致后期收斂變慢和低精度問題,胡旺[15]提出一種更簡(jiǎn)化的粒子群優(yōu)化算法(Simplified Particle Swarm Optimization, SPSO),舍去速度項(xiàng),簡(jiǎn)化為

(3)

本文為了平衡算法的全局搜索與局部搜索能力并加快搜索速度,將慣性權(quán)重ω與學(xué)習(xí)因子(c,c2)和隨機(jī)數(shù)(r1,r2)進(jìn)行改進(jìn),提出一種自適應(yīng)慣性權(quán)重的粒子群優(yōu)化算法,更新公式為

(4)

(5)

影響因子根據(jù)迭代次數(shù)來改變個(gè)體極值和全局極值對(duì)粒子位置的影響。前期受個(gè)體極值影響大,使粒子快速找到相對(duì)較好的位置,尋優(yōu)中期,一部分粒子向全局最優(yōu)值靠近,一部分粒子繼續(xù)搜尋更好的位置點(diǎn),迭代次數(shù)達(dá)到后期時(shí),所有粒子向全局最優(yōu)值靠近,使粒子得到更好的收斂。

固定的學(xué)習(xí)因子,在處理復(fù)雜問題時(shí),很有可能陷入局部最優(yōu)解;因此,本文根據(jù)慣性權(quán)重自適應(yīng)的更新認(rèn)知和社交因子,更新公式為

(6)

(7)

其中c＿start和c＿end分別設(shè)置為1.5和1。當(dāng)慣性權(quán)重減小時(shí),說明上一代的粒子位置不理想,在更新下一代粒子時(shí)應(yīng)保留粒子少部分的信息,同時(shí)應(yīng)該適量增加認(rèn)知因子和社交因子,使粒子向自身歷史最佳位置和群體歷史最佳位置逼近。此學(xué)習(xí)因子加入余弦函數(shù),能夠產(chǎn)生振蕩,使粒子更好的尋優(yōu)。

3.1 自適應(yīng)慣性權(quán)重

慣性權(quán)重ω起到了一個(gè)平衡全局搜索能力和局部搜索能力的作用恰當(dāng)?shù)摩刂悼梢蕴岣咚惴ㄐ阅?提高尋優(yōu)能力,減少迭代次數(shù)。本文運(yùn)用雙曲線先下降后上升的特性和高斯函數(shù)與目標(biāo)函數(shù)值相結(jié)合,提出自適應(yīng)慣性權(quán)重,表示為

ω=α(f(x))*β(t)

(8)

(9)

(10)

其中f(x)為粒子的目標(biāo)函數(shù)值;f＿avg為所有粒子的平均目標(biāo)函數(shù)值;δ為方差,a,b為雙曲線參數(shù),分別為0.3,50,β取值范圍為[0.3,1.042]。目標(biāo)函數(shù)值越小說明粒子適應(yīng)度越大。當(dāng)粒子適應(yīng)度小于平均適應(yīng)度值時(shí),說明粒子處于較差的位置,慣性權(quán)重取得較小值,使下次粒子更新時(shí)獲得前代粒子較少信息;當(dāng)粒子適應(yīng)度值大于平均適應(yīng)度值時(shí),粒子處于好的位置,慣性權(quán)重取得較大值,使下次粒子更新時(shí)獲得較多前代粒子信息。然后通過雙曲線先下降后上升的特性,使粒子尋優(yōu)前期有很強(qiáng)的全局尋優(yōu)能力,中期有較強(qiáng)的局部尋優(yōu)能力,加快收斂,后期增強(qiáng)全局搜索能力,使粒子有能力跳出局部最優(yōu),提高尋優(yōu)精度。

圖1為一個(gè)粒子隨進(jìn)化次數(shù)的慣性權(quán)重分布,整體上呈現(xiàn)先下降后上升趨勢(shì),進(jìn)化前期,粒子通過自己的適應(yīng)度值與所有粒子適應(yīng)度值的平均值的比值得到自己的慣性權(quán)重,使每個(gè)粒子搜尋到適合自己的區(qū)域;進(jìn)化中期,慣性權(quán)重較小,粒子可以快速達(dá)到最優(yōu)解;進(jìn)化后期,粒子的慣性權(quán)重較大,有利于粒子逃出局部最優(yōu)。

圖1 慣性權(quán)重分布

3.2 隨機(jī)局部搜索

本文為了增加最優(yōu)解的精確度,引入交叉變異操作,隨機(jī)生成粒子的方向向量,根據(jù)粒子與粒子中心的平均距離,進(jìn)行隨機(jī)局部搜索,隨機(jī)局部搜索的公式為

xcid=rand*xjd+(1-rand)*xkd

(11)

(12)

xni,d=xqi,d+μUi

(13)

(14)

(15)

其中i,j,k分別表示為第i個(gè)、第j個(gè)、第k個(gè)粒子,且i≠j≠k,xcid為交叉后得到新粒子,xqid為突變后的粒子,κ為均勻分布在[-0.01,0.01]之間,ui、li分別為第i個(gè)粒子迭代過程中空間中的最大值與最小值,xni,d為逃脫局部最優(yōu)產(chǎn)生的新粒子,μ為距離中心位置最近的K個(gè)粒子的平均距離,Ri(i=1,…,m)為隨機(jī)生成的方向向量。

算法實(shí)現(xiàn)步驟如下:

Step1 設(shè)置最大迭代次數(shù)、種群數(shù)量、初始化種群位置、學(xué)習(xí)因子;

Step2 計(jì)算出每個(gè)粒子的適應(yīng)度值;

Step3 找出個(gè)體極值Pbest與全局極值Gbest;

據(jù)有關(guān)統(tǒng)計(jì)表明，項(xiàng)目投入資金的總量為876.459萬元，包含783.643萬元的營(yíng)林人工費(fèi)用以及232.432萬元的工程材料費(fèi)用等。

Step4 根據(jù)式(6-10)計(jì)算學(xué)習(xí)因子與慣性權(quán)重;

Step5 根據(jù)式(11-15)進(jìn)行隨機(jī)局部搜索更新出新的粒子;

Step6 通過適應(yīng)度函數(shù)計(jì)算兩種粒子的適應(yīng)度值,更新個(gè)體極值Pbest和全局極值Gbest。

Step7 判斷是否滿足終止條件,若滿足執(zhí)行Step8,否則轉(zhuǎn)到Step4。

Step8 輸出全局極值Gbest。

算法流程圖如圖2。

圖2 算法流程圖

4 仿真研究

仿真的運(yùn)行環(huán)境的內(nèi)存為16G,Intel i5-9300H CPU 2.4GHz,Windows 10操作系統(tǒng),算法采用Matlab R2019b實(shí)現(xiàn)。為了驗(yàn)證算法的合理性,分別在30維和100維下運(yùn)行30次進(jìn)行實(shí)驗(yàn)對(duì)比與分析。最后對(duì)算法的局部搜索進(jìn)行驗(yàn)證。

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

為了檢驗(yàn)算法AIWPSO的有效性,本文用16個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真對(duì)比,其中f3、f4、f8、f10-f16為單峰測(cè)試函數(shù),f1、f2、f5、f6、f7、f9為多峰函數(shù),f7為病態(tài)的二次函數(shù),全局極小點(diǎn)被無數(shù)的局部極小點(diǎn)所圍繞,因此很難找到最優(yōu)解。本文的測(cè)試函數(shù)見表1。為了更好統(tǒng)一觀測(cè)算法搜尋測(cè)試函數(shù)的最優(yōu)解。以下測(cè)試函數(shù)可能在形式上略有變化,但并不影響其測(cè)試效果,測(cè)試函數(shù)的理論解都為0。

表1 測(cè)試函數(shù)

4.2 參數(shù)設(shè)置與實(shí)驗(yàn)結(jié)果分析

設(shè)計(jì)實(shí)驗(yàn)時(shí)最重要的環(huán)節(jié)是合理設(shè)置參數(shù)和仿真環(huán)境,如此才能保證算法比較過程的公平性與公正性。表2為四種算法參數(shù)設(shè)置。

表2 四種算法參數(shù)設(shè)置

4.3 實(shí)驗(yàn)結(jié)果

將本文算法,與近三年新算法CPSO、CISPO和基本粒子群算法PSO在30維下進(jìn)行仿真對(duì)比。算法的實(shí)驗(yàn)數(shù)據(jù)對(duì)比結(jié)果見表3。

表3 四種算法搜索30維函數(shù)結(jié)果

從實(shí)驗(yàn)結(jié)果表中可以看出對(duì)于16個(gè)測(cè)試函數(shù),雖然AIWPSO算法對(duì)于f8所搜索的最優(yōu)解不優(yōu),但是四種算法中最優(yōu)的解,對(duì)于其它測(cè)試函數(shù)AIWPSO算法都能搜尋到很好的解,而且AIWPSO算法搜尋的最優(yōu)解都比其它三種算法搜尋的解好,并且AIWPSO算法能過搜索到f5、f6、f7、f9的理論解,這主要因?yàn)樗惴ㄓ泻芎玫娜炙阉髂芰?。但是算法?duì)于多次搜尋f7測(cè)試函數(shù)的平均解和標(biāo)準(zhǔn)差不優(yōu)。表中的平均值代表算法的平均優(yōu)化性能,這也是重要的評(píng)價(jià)指標(biāo),AIWPSO算法不僅最小值搜尋到f5、f6、f9的理論解,而且平均值也為理論解,說明AIWPSO算法對(duì)這三個(gè)函數(shù)有很強(qiáng)的搜索能力。標(biāo)準(zhǔn)差也是衡量算法性能的重要物理量之一?？梢詮谋碇锌闯鰂1、f4、f5、f6、f9被搜索的方差為0,說明AIWPSO算法搜尋的解很穩(wěn)定,f8函數(shù)的方差較大,是因?yàn)榇撕瘮?shù)帶有噪音擾動(dòng),導(dǎo)致算法搜尋不穩(wěn)定。

為了更加直觀的觀察和反應(yīng)四種算法的優(yōu)越性,圖3為四種算法分別對(duì)函數(shù)f1、f3和f4、f8、f10、f16的迭代曲線。從圖中可以看出,從算法迭代開始不久AIWPSO就比其它三種算法搜尋的解好,并且不斷地找更加準(zhǔn)確的解,其它三種算法始終無法在尋優(yōu)過程中下滑到低于AIWPSO尋優(yōu)曲線的位置,是由于CPSO產(chǎn)生混沌現(xiàn)象時(shí)只有單一的混沌策略,在粒子陷入局部最優(yōu)時(shí),通過混沌策略,逃出局部最優(yōu)的能力較弱,粒子會(huì)進(jìn)入另一個(gè)局部最優(yōu)解,減慢了找到更好解的速度。CIPSO的曲線遞增策略雖然滿足了前期慣性權(quán)重較小,加快了搜尋速度,后期慣性權(quán)重較大,增加了全局搜索能力,但尋優(yōu)前期,單一的慣性權(quán)重策略,使粒子陷入局部最優(yōu),在尋優(yōu)后期時(shí),粒子跳出局部能力較弱,所以搜尋的解沒有AIWPSO的優(yōu)秀。但對(duì)于函數(shù)f1、f8平均函數(shù)解中CIPSO算法比CPSO逃脫局部最優(yōu)能力強(qiáng)。

圖3 四種算法獲得的6個(gè)函數(shù)平均適應(yīng)度進(jìn)化曲線

多數(shù)智能算法在低維函數(shù)的計(jì)算中效果很好,而在高緯函數(shù)中效果不佳。為進(jìn)一步綜合評(píng)價(jià)AIWPSO算法在高維度下算法的性能,本文將四種算法在100維下進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果見表4。由結(jié)果可知,AIWPSO算法尋找的最優(yōu)解并沒有明顯增大,除了搜尋函數(shù)f12、f14、f15的最小值增大了一倍,其它并沒有隨著維度的增加而使算法降低了尋優(yōu)的精準(zhǔn)度,說明AIWPSO算法能較好的適應(yīng)解決高維度函數(shù)問題。相比較而言,其它三種算法,最優(yōu)解都有明顯增大,發(fā)生維度災(zāi)難。

表4 四種算法搜索100維函數(shù)結(jié)果

圖4為四種算法在100維下運(yùn)行30次的平均函數(shù)解,可以從圖中看出f3、f10的進(jìn)化曲線,AIWPSO算法隨著迭代次數(shù)仍平穩(wěn)的下降,搜尋著最優(yōu)解,而CPSO、CIPSO算法逃出局部最優(yōu)能力較差,下降緩慢,而且由于維數(shù)的增加,兩種算法找到的最優(yōu)解都有一定量的增大。對(duì)于f14進(jìn)化曲線,AIWPSO算法雖然在52代左右曲線不在下降,但仍搜尋到了較好的解。整體上看,四種算法AIWPSO平均函數(shù)解下降的最快,這除了自適應(yīng)慣性權(quán)重的原因外,隨機(jī)局部搜素影響下,使每代都有機(jī)會(huì)得到更優(yōu)的解。

圖4 四種算法獲得的3個(gè)函數(shù)平均適應(yīng)度進(jìn)化曲線

4.4 局部搜索效果驗(yàn)證

將有局部搜索策略(AIW)和無局部搜索策略(AIW2)兩種算法運(yùn)行10次的平均函數(shù)解進(jìn)行對(duì)比見圖5?？梢钥闯鼍植克阉鞑呗允钟行АＬ貏e是多峰函數(shù)f7、f8尤為明顯,分別在28代搜索到理論解和29代搜尋到更好的解。f3為單峰函數(shù),在25代左右逐漸產(chǎn)生效果。由此可以看出,局部搜索策略增強(qiáng)了算法局部的搜索能力,提高了算法的收斂的精度。

圖5 兩種算法獲得的3個(gè)函數(shù)平均適應(yīng)度對(duì)比曲線

5 結(jié)束語

本文針對(duì)粒子群優(yōu)化算法在迭代的后期會(huì)出現(xiàn)種群多樣性不足,導(dǎo)致陷入局部最優(yōu)的問題,做出三點(diǎn)改進(jìn),首先,提出自適應(yīng)慣性權(quán)重,其次,加入隨慣性權(quán)重而改變的學(xué)習(xí)因子,然后,通過交叉變異操作進(jìn)行隨機(jī)局部搜索。最后本文通過16個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真,將算法與近三年的兩種粒子群算法和標(biāo)準(zhǔn)粒子群算法分別在30維和100維下對(duì)比分析,結(jié)果表明,AIWPSO算法具有更好的尋優(yōu)能力。