基于改進(jìn)收縮因子的粒子群優(yōu)化算法

王鵬飛，任麗佳，高 燕

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院,上海 201620)

粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法[1-3]是一種生物啟發(fā)式進(jìn)化算法[4]，其運(yùn)行機(jī)制類似于模擬退火算法[5]，采用迭代尋優(yōu)的方式，從隨機(jī)解開始尋找最優(yōu)解[6-7]，其解的質(zhì)量根據(jù)適應(yīng)度函數(shù)值[8]來評價。該算法利用粒子朝向當(dāng)前最優(yōu)解的方式不斷迭代來尋找全局最優(yōu)解。和遺傳算法[9-11]相比，PSO不需要進(jìn)行生物學(xué)上的交叉、變異操作，較易實(shí)現(xiàn)，尋找最優(yōu)值的精度更高，收斂速度快，已被大量使用于工程實(shí)踐領(lǐng)域。

雖然PSO算法存在諸多的優(yōu)勢，但是在實(shí)際應(yīng)用中還是會出現(xiàn)早熟[12]、收斂差[13]等問題。為了減少這些問題對算法的影響，本文提出了一種基于改進(jìn)壓縮因子[14]的粒子群優(yōu)化(Fitness Particle Swarm Optimization，F(xiàn)PSO)算法。該算法引入新的壓縮因子方程，改進(jìn)速度迭代公式，減少了因?qū)W習(xí)因子設(shè)置不當(dāng)對算法造成的影響，可以有效規(guī)避過多粒子長時間處于某個局部范圍的現(xiàn)象，避免算法早熟，提升了算法的收斂速度與收斂性能。

1 傳統(tǒng)PSO算法

在原始PSO算法中，需要兩個N維的向量在一個N維的空間中進(jìn)行搜索。

第i個粒子的位置可表示為

xi=(xi1,xi2,…,xiN)T

(1)

速度為

vi=(vi1,vi2,…,viN)T

(2)

在找到兩個最優(yōu)解之后，PSO算法中粒子速度與位置的更新計算式為

(3)

(4)

2 FPSO算法流程

本文提出的FPSO優(yōu)化算法的基本原理是：速度優(yōu)化計算式有兩個重要的參數(shù)值c1和c2。c1代表粒子自身的經(jīng)驗(yàn)，c2代表其它粒子的經(jīng)驗(yàn)，兩者不僅影響粒子的運(yùn)動軌跡，還作為橋梁為粒子群之間進(jìn)行信息傳遞，并反映粒子群間信息的交流情況。粒子的尋優(yōu)范圍受c1的值影響較大，想要避免粒子過多地在局部范圍內(nèi)游走，c1的參數(shù)值不可過大。除此之外，c2影響著粒子的收斂速度。若c2設(shè)置過大，粒子容易陷入局部最優(yōu)，過早收斂于局部最優(yōu)點(diǎn)。為了讓算法的全局與局部搜索能力達(dá)到均衡的表現(xiàn)，需要合理控制粒子的飛翔速度[18]。本文引入改進(jìn)收縮因子φ來對c1和c2這兩個學(xué)習(xí)因子做出參數(shù)限制，使學(xué)習(xí)因子的值不會過大，均衡了算法收斂性能。

收縮因子為

(5)

利用其優(yōu)化后的新速度計算式為

(6)

其中，c=c1+c2，且c>2 。

新方法在不改變慣性權(quán)重對速度變化的影響效力下，通過引入新的壓縮因子改善了速度更新式。該方法通過提升分母的數(shù)值比重，使得收縮因子的收斂速度變快，針對過大的學(xué)習(xí)因子設(shè)置更快的調(diào)節(jié)能力，使c1和c2的值能夠被控制在合理范圍，提高了搜索空間的多樣性，增強(qiáng)了粒子向目標(biāo)逼近的搜索能力，防止過早收斂。本文將慣性權(quán)值的PSO與FPSO算法的w的變化情況進(jìn)行對比，結(jié)果如圖1和圖2所示。

圖1 慣性權(quán)值PSO算法w值迭代變化曲線Figure 1. Iterative change curve of w value of inertial weight PSO algorithm

圖2 FPSO算法w值迭代變化曲線Figure 2. Iterative change curve of w value of FPSO algorithm

由圖1和圖2可看出，慣性常數(shù)方法通常采用慣性權(quán)值隨更新代數(shù)增加而遞減的策略。在算法后期，由于慣性權(quán)值過小，會失去微粒探索新區(qū)域的能力，而FPSO算法則不存在此問題，因此相比于權(quán)重系數(shù)w，學(xué)習(xí)因子能更加有效地控制、約束微粒的飛行速度，增強(qiáng)算法的局部搜索能力。

FPSO的具體步驟如下：

步驟2利用各自測試函數(shù)的函數(shù)關(guān)系式作為測試函數(shù)，計算粒子i的適應(yīng)度值f(i)；

步驟3計算每個粒子的適應(yīng)度函數(shù)值f(i)，并將它和個體極值Pbest(i)比較。如果f(i)>Pbest(i)，則用f(i)替換Pbest(i)；

步驟4將步驟3中的每個粒子的f(i)和Gbest(i)比較。如果f(i)>Gbest(i)，則用f(i)替換Gbest(i)；

步驟6判斷是否執(zhí)行結(jié)束操作(誤差值達(dá)到理想范圍或者M(jìn)值達(dá)到最大)，如果滿足則結(jié)束程序運(yùn)行，否則返回步驟2繼續(xù)執(zhí)行。

FPSO的具體流程如圖3所示。

圖3 FPSO流程圖Figure 3. Flow chart of FPSO

3 實(shí)驗(yàn)結(jié)果分析

運(yùn)用兩個單峰函數(shù)和3個多峰函數(shù)來驗(yàn)證FPSO算法的性能，求函數(shù)的極值。

兩個單峰函數(shù)為Sphere函數(shù)和Quadric函數(shù)，如式(7)和式(8)所示。

(7)

(8)

多峰函數(shù)為Ackley函數(shù)、Griewank函數(shù)和Rastrigin函數(shù)，分別如式(9)～式(11)所示。

(9)

(10)

(11)

這5個函數(shù)[19]是常用的PSO算法測試函數(shù)，其尋找全局最優(yōu)解的難易程度逐漸加深，且均在xi=(0,0,…,0)的位置取得極值。利用本文改進(jìn)后的算法對這5個函數(shù)尋優(yōu)并與兩種常見的粒子群算法進(jìn)行對比，能夠較為直觀地反映FPSO的收斂性和時效性。

按如下方式進(jìn)行初始化參數(shù)：粒子維度M設(shè)置為20，種群規(guī)模size設(shè)置為50，最大迭代次數(shù)為1 000，慣性權(quán)重c1=c2采用線性衰減策略，初始值為0.8，線性衰減的最小值為0.3。為了驗(yàn)證收縮因子對算法全局收斂能力與尋優(yōu)時間縮短的提升，學(xué)習(xí)因子分別取值2、3、4來進(jìn)行實(shí)驗(yàn)，并與PSO算法及骨干粒子群算法(Bare Bones PSO，BBPSO)進(jìn)行對比。每種測試函數(shù)都進(jìn)行了50次實(shí)驗(yàn)，取平均值后的結(jié)果如表1所示。

表1 測試函數(shù)尋優(yōu)均值

從表1可以看出，相較于PSO及BBPSO算法， FPSO算法尋找到的各測試函數(shù)的最優(yōu)值更接近實(shí)際最優(yōu)值。為了更直觀地體現(xiàn)FPSO在尋優(yōu)上的性能提升，取5個函數(shù)在第30次、學(xué)習(xí)因子取值為2的實(shí)驗(yàn)結(jié)果及運(yùn)行時間進(jìn)行說明，如圖4～圖8及表2所示。

圖4 Sphere函數(shù)對比圖Figure 4. Comparison chart of Sphere function

圖5 Quadric函數(shù)對比圖Figure 5. Quadric function comparison chart

圖6 Ackley函數(shù)對比圖Figure 6. Comparison chart of Ackley function

圖7 Griewank函數(shù)對比圖Figure 7. Griewank function comparison diagram

圖8 Rastrigin函數(shù)對比圖Figure 8. Rastrigin function comparison diagram

表2 學(xué)習(xí)因子為2時的各方法運(yùn)行時間

從圖4～圖8及表2可以看出，在5種測試函數(shù)尋優(yōu)下，F(xiàn)PSO的表現(xiàn)均優(yōu)于另外兩種算法。FPSO收斂速度快，基本在100代內(nèi)就能快速收斂，且適應(yīng)度值平滑變化，未出現(xiàn)明顯陷入局部最優(yōu)的情況，耗時短于PSO及BBPSO算法，在全局和局部的尋優(yōu)上都能達(dá)到不錯的效果，體現(xiàn)了算法尋優(yōu)性能的均衡性。針對PSO尋優(yōu)效果不佳的Ackley函數(shù)，F(xiàn)PSO也能快速收斂并接近最優(yōu)解。根據(jù)表1可以發(fā)現(xiàn)，不同學(xué)習(xí)因子對FPSO尋優(yōu)的影響不大，學(xué)習(xí)因子較大時，F(xiàn)PSO依舊有不錯的表現(xiàn)。該結(jié)果表明FPSO能夠有效避免加速度系數(shù)及最大速度等參數(shù)過大導(dǎo)致粒子群錯過最優(yōu)解的情況，且算法不收斂的問題有了明顯改善，體現(xiàn)了算法的性能。

4 結(jié)束語

本文針對傳統(tǒng)PSO算法不收斂，可能會錯過全局最優(yōu)解的問題，提出了一種基于改進(jìn)壓縮因子的PSO優(yōu)化算法。通過引入新的壓縮因子方程，改進(jìn)速度迭代公式，減少了因?qū)W習(xí)因子設(shè)置不當(dāng)對算法造成的影響。在測試中，4個受測對象的尋優(yōu)結(jié)果表明優(yōu)化后的算法的收斂速度得到了提升，且其適應(yīng)度值好于傳統(tǒng)PSO算法，更接近于真實(shí)值，更符合實(shí)際工程應(yīng)用需求。