基于動(dòng)態(tài)自適應(yīng)變參的粒子群優(yōu)化算法

李 眩，吳曉兵，童百利

（銅陵職業(yè)技術(shù)學(xué)院經(jīng)濟(jì)貿(mào)易系，安徽 銅陵 244061）

算法。該算法采用非線(xiàn)性遞減策略對(duì)慣性權(quán)重進(jìn)行調(diào)整,使其具有平衡PSO 算法的全局和局部搜索能力。仝秋娟等［5］、張曉莉等［6］提出一種基于適應(yīng)度的粒子群優(yōu)化算法，根據(jù)粒子的適應(yīng)度值動(dòng)態(tài)自適應(yīng)地調(diào)整算法中慣性權(quán)重和學(xué)習(xí)因子的取值，以平衡算法的全局搜索與局部搜索能力，從而避免算法陷入局部極值。楊巍等［7］對(duì)基本粒子群算法的更新迭代方式進(jìn)行了改進(jìn)，提出一種改進(jìn)的動(dòng)態(tài)權(quán)值自適應(yīng)粒子群優(yōu)化算法。采用動(dòng)態(tài)權(quán)值自適性?xún)?yōu)化局部搜索和全局搜索，達(dá)到合理搜索的目的。以上研究表明，通過(guò)對(duì)粒子群算法慣性權(quán)重的自適應(yīng)調(diào)整能改善算法的尋優(yōu)能力。上述基于粒子群算法的慣性權(quán)重自適應(yīng)改進(jìn)，是改進(jìn)粒子群算法提升算法效率的一條思路，為后續(xù)自適應(yīng)粒子群算法的研究提供了借鑒。

引 言

粒子群算法（PSO）是模擬鳥(niǎo)群覓食行為發(fā)展起來(lái)的集群體協(xié)作和信息共享的群體智能算法，具有操作簡(jiǎn)單、收斂速度快、魯棒性好的特點(diǎn)，且有深刻的智能背景，在科學(xué)研究和工程中應(yīng)用非常廣泛。粒子群算法的應(yīng)用從最初的函數(shù)優(yōu)化擴(kuò)展到現(xiàn)在的神經(jīng)網(wǎng)絡(luò)訓(xùn)練、圖像處理、工程領(lǐng)域的過(guò)程優(yōu)化、隨機(jī)優(yōu)化問(wèn)題的求解、最優(yōu)控制等領(lǐng)域［1］。隨著粒子群算法應(yīng)用研究的深入，傳統(tǒng)PSO 算法的局限也相繼被發(fā)掘，譬如存在早熟收斂或者不收斂、維數(shù)災(zāi)難、易陷入局部極值等問(wèn)題［2］。對(duì)粒子群算法進(jìn)行改進(jìn)可以提高尋優(yōu)能力。有學(xué)者從算法參數(shù)的設(shè)置來(lái)改進(jìn)算法。李艷等［3］、張娟芝等［4］以PSO算法為基礎(chǔ),提出一種新的自適應(yīng)調(diào)整慣性權(quán)重的PSO

由于粒子群算法涉及參數(shù)不僅有慣性權(quán)重還有加速因子，它們對(duì)算法的尋優(yōu)性能都存在影響。單獨(dú)調(diào)整其中某個(gè)參數(shù)，忽視其他參數(shù)對(duì)算法尋優(yōu)能力的影響，這樣的改進(jìn)存在局限性?；诖?，本文嘗試運(yùn)用動(dòng)態(tài)自適應(yīng)調(diào)整策略對(duì)傳統(tǒng)粒子群算法多個(gè)參數(shù)進(jìn)行調(diào)整，結(jié)合引入自適應(yīng)變化的控制因子，來(lái)改進(jìn)粒子群算法，以期提高算法執(zhí)行效率和全局尋優(yōu)能力。

1 粒子群算法原理

1.1 粒子群算法基本思想

粒子群算法（PSO 算法）起源于對(duì)鳥(niǎo)群覓食行為的研究。由于鳥(niǎo)群覓食和優(yōu)化問(wèn)題求解在一些方面具有相似性，于是人們模擬鳥(niǎo)群覓食的生物原理進(jìn)行優(yōu)化決策和尋找問(wèn)題最優(yōu)解［8］。標(biāo)準(zhǔn)PSO 算法實(shí)現(xiàn)過(guò)程如下：假設(shè)在M 維（即有M 個(gè)函數(shù)自變量）搜索域中，有n 個(gè)粒子組成一個(gè)群體，n 代表種群規(guī)模。種群太小則不能保證粒子群體的多樣性，以致算法性能很差，種群太大盡管可以增加尋優(yōu)的效率，阻止早熟收斂的發(fā)生，但無(wú)疑會(huì)增加計(jì)算量，造成收斂時(shí)間太長(zhǎng)，表現(xiàn)為收斂速度緩慢［9］。Xi=(xi1,xi2,...,xiM)（i = 1,2,...,n），為粒子i的位置向量，粒子維數(shù)取決于待優(yōu)化函數(shù)的變量數(shù)。 其中，xik∈[ ]

L,U ，代表粒子i在第k 個(gè)自變量上的取值。在實(shí)際應(yīng)用中，X 每一維取值保證在一定的范圍內(nèi)，這在函數(shù)優(yōu)化問(wèn)題中相當(dāng)于自變量的定義域，L 表示第k 個(gè)自變量的取值下限，U 表示第k 個(gè)自變量的取值上限。Vi=(vi1,vi2,...,viM)為粒子i 的的速度向量，它們都是M 維的，vik∈[vmin,vmax]，vmin表示粒子在第k 維方向上的最小速度，vmax表示粒子在第k維方向上的最大速度。在每一代尋優(yōu)中，粒子將根據(jù)其自身找到的歷史最優(yōu)位置和群體找到的歷史最優(yōu)位置來(lái)調(diào)整自己的飛行方向和方位［10］。記Pi=( pi1,pi2,...,piM)為粒子i 自身找到的具有最佳適應(yīng)值的位置；記Pg=( pg1,pg2,...,pgM)為整個(gè)粒子群搜索到的最優(yōu)位置。

其中，w 為慣性權(quán)重，c1與c2為加速因子，r1與r2為隨機(jī)量。

每一維粒子速度和位置都會(huì)被約束在一個(gè)范圍內(nèi)，為了防止粒子逃遁出解空間，若超過(guò)邊界條件，采用如下方法進(jìn)行處理：

或者

1.2 參數(shù)對(duì)粒子群算法的影響分析

算法搜索性能對(duì)參數(shù)有較高的依賴(lài)性，算法涉及3個(gè)參數(shù)：慣性權(quán)重w、加速因子c1及c2。3 個(gè)參數(shù)若設(shè)置為定值或者線(xiàn)性變化，則會(huì)對(duì)算法尋優(yōu)及效率帶來(lái)不利影響［11］。3 個(gè)參數(shù)設(shè)置不當(dāng)可能會(huì)使粒子群算法演變成局部尋優(yōu)算法，或者粒子群在早期就喪失多樣性，造成算法早熟收斂［12］。另外，在優(yōu)化前期，為了粒子具有較大速度，可以提高搜索全局最優(yōu)解的能力。而在后期接近最優(yōu)解時(shí)，為了不使粒子速度過(guò)大而偏離最優(yōu)位置區(qū)域，錯(cuò)失全局最優(yōu)解而陷入局部最優(yōu)，因此，在后期接近全局最優(yōu)區(qū)域時(shí)，位置更新幅度不宜過(guò)大，應(yīng)該對(duì)粒子速度進(jìn)行有效調(diào)整和約束，不能忽視后期粒子可能因速度過(guò)大而導(dǎo)致俯沖脫離全局最優(yōu)區(qū)域的情況出現(xiàn)，從而可能造成算法不成熟收斂［13］。鑒于上述原因，在PSO計(jì)算中引入非線(xiàn)性變化的收縮因子ρ(t)，與慣性權(quán)重相比，其更能有效管束粒子的飛行速度改善算法的收斂能力。

在算法搜索過(guò)程中，慣性權(quán)重值的變化應(yīng)該滿(mǎn)足如下要求：前期減少的速度比較慢，慣性權(quán)重值較大且減少幅度較小利于全局探索；后期較小且減少的速度較快，利于粒子展開(kāi)精細(xì)的局部搜索，這樣在保證收斂速度的同時(shí)又平衡了全局和局部搜索能力，有效避免陷入局部最優(yōu)［14］。另外，算法兩個(gè)加速因子的變化應(yīng)滿(mǎn)足c1先大后小、c2先小后大的要求［15］，這樣算法能較好兼顧局部和全局搜索。

2 動(dòng)態(tài)自適應(yīng)的粒子群算法

隨著PSO 算法研究的不斷深入，人們考慮到粒子群算法參數(shù)對(duì)其尋優(yōu)能力和效率有很大影響，開(kāi)始關(guān)注運(yùn)用自適應(yīng)變化的參數(shù)提升粒子群算法性能。通常從慣性權(quán)重的動(dòng)態(tài)調(diào)整入手來(lái)優(yōu)化粒子群算法，較大的慣性權(quán)重有利于展開(kāi)全局搜索，而較小的慣性權(quán)重則有利于局部尋優(yōu)，可以運(yùn)用慣性權(quán)重的自適應(yīng)調(diào)整來(lái)協(xié)調(diào)PSO算法的全局和局部尋優(yōu)能力［16］。但僅從單一參數(shù)的調(diào)整來(lái)進(jìn)行優(yōu)化，其提升算法的性能相對(duì)有限，不僅要對(duì)算法的慣性權(quán)重和加速因子進(jìn)行動(dòng)態(tài)時(shí)變調(diào)整，同時(shí)引入動(dòng)態(tài)時(shí)變的控制因子來(lái)約束粒子的位置更新幅度。因?yàn)閰?shù)值的非線(xiàn)性變化能比線(xiàn)性變化獲得更佳的算法性能［17］，李丹提出運(yùn)用非線(xiàn)性調(diào)整的慣性權(quán)重來(lái)提升算法的探索和開(kāi)發(fā)能力，以獲得全局最優(yōu)的目的。3 項(xiàng)參數(shù)的調(diào)整皆采取非線(xiàn)性的動(dòng)態(tài)自適應(yīng)時(shí)變調(diào)整策略，其隨著迭代次數(shù)呈非線(xiàn)性變化。慣性權(quán)重的動(dòng)態(tài)非線(xiàn)性調(diào)整，在此以反正切函數(shù)來(lái)構(gòu)建慣性權(quán)重調(diào)整公式如下：

式中，反正切函數(shù)是一個(gè)遞減的函數(shù)，隨著自變量的增加，函數(shù)值遞減的步長(zhǎng)逐漸減少。自變量等于1.56 時(shí)，函數(shù)值等于1，經(jīng)過(guò)反正切函數(shù)改進(jìn)的慣性權(quán)重變化正好符合PSO 算法的要求。本文中，wstart=0.9，wend=0.4。當(dāng)t=1 時(shí)，w(t) = wstart= 0.9，當(dāng)達(dá)到最大迭代次數(shù)tmax時(shí)，w(t) = wend= 0.4。k 為控制因子，控制w 隨t 變化曲線(xiàn)的平滑度, k取0.3，算法能取得較好的穩(wěn)定性。

若僅對(duì)w 作出非線(xiàn)性調(diào)整會(huì)使得算法一旦陷入局部陷阱內(nèi)就很難跳出，極易收斂到局部極值點(diǎn)。為了改變這種局限性，考慮到加速因子c1，c2對(duì)算法全局和局部尋優(yōu)能力亦有重要影響，因此同時(shí)對(duì)兩個(gè)加速因子進(jìn)行非線(xiàn)性的時(shí)變動(dòng)態(tài)調(diào)整。以指數(shù)函數(shù)為基礎(chǔ)構(gòu)造變化關(guān)系式，使其分別呈現(xiàn)遞減和遞增變化，能讓算法獲得較好的全局尋優(yōu)性能。其調(diào)整函數(shù)如下：

其中，c1max，c2max都設(shè)為2.0，c1min，c2min都設(shè)為0.6，α 為常數(shù)，設(shè)為0.009。

在前期為了粒子能以較大速度接近最優(yōu)位置，在后期為了不使粒子速度過(guò)大造成俯沖脫離最優(yōu)位置區(qū)域，而錯(cuò)失全局最優(yōu)解從而陷入局部最優(yōu)，因此在后期接近全局最優(yōu)區(qū)域時(shí)，位置更新幅度不宜過(guò)大。對(duì)位置更新公式（2）引入動(dòng)態(tài)自適應(yīng)時(shí)變的控制因子ρ(t)，對(duì)算法后期粒子位置更新幅度進(jìn)行約束。其變化規(guī)律按照如下函數(shù)進(jìn)行調(diào)整：

其中，ρmax設(shè)為1.8，ρmin設(shè)為0.4，α 為常數(shù)，設(shè)為0.009。

如此，粒子位置更新公式調(diào)整如下：

各參數(shù)取值隨迭代變化曲線(xiàn)如圖1所示。

圖1 各參數(shù)變化曲線(xiàn)

3 動(dòng)態(tài)自適應(yīng)PSO算法性能分析

為驗(yàn)證提出的動(dòng)態(tài)自適應(yīng)變參優(yōu)化的PSO 算法的性能，用一些典型的復(fù)雜函數(shù)極值尋優(yōu)對(duì)算法進(jìn)行測(cè)試。第一個(gè)測(cè)試函數(shù)為一個(gè)三維函數(shù)：

該函數(shù)三維圖像及其初始粒子分布如圖2所示。

圖2 f1函數(shù)圖像及其初始粒子分布圖

在測(cè)試過(guò)程中，取粒子數(shù)為100，粒子維數(shù)為2 維，最大迭代次數(shù)為50 次。為了進(jìn)一步顯示這種改進(jìn)的有效性，將隨機(jī)變化權(quán)重PSO 算法記為PSO-RIW、慣性權(quán)重和加速因子線(xiàn)性動(dòng)態(tài)調(diào)整的粒子群算法PSO 算法記為PSO-PIW、非線(xiàn)性動(dòng)態(tài)自適應(yīng)變參PSO 算法記為PSO-AIW。對(duì)迭代過(guò)程的適應(yīng)度函數(shù)值變化曲線(xiàn)進(jìn)行了對(duì)比，f1函數(shù)3種算法適應(yīng)度函數(shù)值如圖3所示。

圖3 各PSO算法的適應(yīng)度值變化

從適應(yīng)度函數(shù)值的變化曲線(xiàn)可以看出，采用帶控制收縮的動(dòng)態(tài)自適應(yīng)變參優(yōu)化的粒子群算法，在整個(gè)尋優(yōu)過(guò)程中自適應(yīng)度值曲線(xiàn)變化順暢，能極快跳出局部極值的束縛，快速進(jìn)入全局收斂，并且收斂時(shí)間較短，收斂迭代次數(shù)約為5次，表明優(yōu)化后的算法性能較好。而PSORIW 算法在迭代過(guò)程中較易陷入局部極值且不容易跳出，最終沒(méi)有收斂于全局最優(yōu)，而且收斂時(shí)間長(zhǎng)，算法效率不高，全局尋優(yōu)能力不理想。而PSO-PIW 算法雖收斂于全局最優(yōu)值，但在迭代過(guò)程中陷入局部極值的頻次較動(dòng)態(tài)自適應(yīng)優(yōu)化的PSO 算法要高，算法性能沒(méi)后者理想。

第二測(cè)試函數(shù)是帶正弦的三維函數(shù)。該函數(shù)是一個(gè)復(fù)雜的多峰多谷函數(shù)，存在大量的局部最小值點(diǎn)和高大的障礙物，因?yàn)樽兞恐g的關(guān)系，優(yōu)化算法很容易陷入局部最優(yōu)。f2測(cè)試函數(shù)關(guān)系如下所示：

f2測(cè)試函數(shù)圖像及其初始粒子分布如圖4所示。

圖4 f2函數(shù)圖像及其初始粒子分布圖

為了進(jìn)一步揭示這種改進(jìn)的有效性，同樣將PSORIW、PSO-PIW、PSO-AIW 算法迭代過(guò)程的適應(yīng)度函數(shù)值變化曲線(xiàn)進(jìn)行了對(duì)比，f2函數(shù)3 種算法適應(yīng)度函數(shù)值如圖5所示：

圖5 各PSO算法的適應(yīng)度值變化

從適應(yīng)度值變化情況來(lái)看，PSO-RIW 算法、PSOPIW 算法容易陷入局部極值，尋優(yōu)收斂時(shí)間較長(zhǎng)，算法效率較低，且跳出局部最優(yōu)解的能力較弱。PSO-AIW算法全局收斂的速度極快，沒(méi)有陷入局部最優(yōu)，其綜合效率是比較高的，同時(shí)也說(shuō)明優(yōu)化帶來(lái)的尋優(yōu)性能的提高還是比較令人滿(mǎn)意的。

為進(jìn)一步探討改進(jìn)后的PSO算法在高維情況下的尋優(yōu)能力和效率，下面用一個(gè)高維函數(shù)來(lái)測(cè)試優(yōu)化粒子群算法性能。采用Sphere函數(shù)對(duì)其進(jìn)行測(cè)試，其表達(dá)式為：

這是一個(gè)多維函數(shù)，其簡(jiǎn)單性能有助于探究?jī)?yōu)化算法在問(wèn)題多維度上的尋優(yōu)效果。該函數(shù)最優(yōu)點(diǎn)位于x =(0,0,…,0)，全局最優(yōu)點(diǎn)的函數(shù)值為0［17］。在此自變量取10 維，即該函數(shù)取10 個(gè)自變量。PSO 算法適應(yīng)度函數(shù)值變化曲線(xiàn)如圖6 所示,優(yōu)化PSO 算法在進(jìn)化迭代過(guò)程中適應(yīng)度值曲線(xiàn)變化順暢，表明其在多維函數(shù)尋優(yōu)上也沒(méi)有陷入局部極值，能快速收斂于全局最優(yōu)值，說(shuō)明改進(jìn)的PSO算法在解決高維優(yōu)化問(wèn)題亦有出色的表現(xiàn)。

圖6 優(yōu)化PSO算法適用度值變化

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

對(duì)傳統(tǒng)的粒子群算法從慣性權(quán)重、加速因子方面進(jìn)行了動(dòng)態(tài)的自調(diào)整優(yōu)化，并加入動(dòng)態(tài)變化的控制因子來(lái)提升算法的效率。結(jié)果表明：多個(gè)參數(shù)的動(dòng)態(tài)自適應(yīng)調(diào)整給粒子群算法帶來(lái)的性能提升是很顯著的，改進(jìn)后的算法全局尋優(yōu)能力有了增強(qiáng)。改進(jìn)的粒子群算法能用于現(xiàn)實(shí)當(dāng)中非線(xiàn)性強(qiáng)、復(fù)雜度高的問(wèn)題（如路徑規(guī)劃、自動(dòng)化控制等）的求解。粒子群算法改進(jìn)及其應(yīng)用具有很大的價(jià)值和發(fā)展空間。