一種動態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法

皮倩瑛，葉洪濤*

（1.廣西科技大學(xué)電氣與信息工程學(xué)院，廣西柳州545006；2.廣西汽車零部件與整車技術(shù)重點實驗室，廣西柳州545006）

一種動態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法

皮倩瑛1，2，葉洪濤*1，2

（1.廣西科技大學(xué)電氣與信息工程學(xué)院，廣西柳州545006；2.廣西汽車零部件與整車技術(shù)重點實驗室，廣西柳州545006）

針對使用經(jīng)典線性遞減策略來確定慣性權(quán)重的粒子群優(yōu)化算法在運算過程中與粒子尋優(yōu)的非線性變化特點不匹配的問題，提出一種動態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法.該算法對慣性權(quán)重引入隨機因子并基于粒子適應(yīng)度大小來動態(tài)調(diào)節(jié)慣性權(quán)重，更好地引導(dǎo)粒子進(jìn)行搜索，平衡了算法的全局搜索與局部搜索能力，提高了算法的收斂精度.為了驗證該算法的尋優(yōu)性能，通過8個經(jīng)典測試函數(shù)將標(biāo)準(zhǔn)粒子群算法、慣性權(quán)重遞減的粒子群算法及動態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法在不同維度下進(jìn)行測試比較.結(jié)果表明：提出的動態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法在尋優(yōu)精度和成功率方面都有所提升，算法性能更具優(yōu)越性.

粒子群算法；動態(tài)調(diào)節(jié)；慣性權(quán)重；隨機因子

0　引言

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法最早是由Kennedy和Eberhart于1995年提出的一種群體智能算法［1］，其基本思想起源于對鳥類群體捕食行為的研究，并將社會學(xué)中的競爭與合作引入到優(yōu)化問題的求解中.自PSO算法提出以來，由于它在多峰值、非線性和不可微等一系列優(yōu)化問題上有著良好的尋優(yōu)表現(xiàn)，引起了眾多學(xué)者的關(guān)注和研究；又因PSO算法程序簡潔易懂、可調(diào)參數(shù)少，出現(xiàn)了多種改進(jìn)PSO算法的方法，并被成功應(yīng)用于多個科學(xué)領(lǐng)域.文獻(xiàn)［2-3］將改進(jìn)后的PSO算法分別應(yīng)用到時變解耦模糊滑膜控制和光伏陣列系統(tǒng)中，拓寬了PSO算法的應(yīng)用領(lǐng)域.

對PSO算法中可調(diào)參數(shù)的研究，在目前的改進(jìn)技術(shù)中研究最多的是關(guān)于慣性權(quán)重因子ω的取值問題，它主要是種群在全局搜索和局部搜索能力之間的一種權(quán)衡.由Shi和Eberhart首次在文獻(xiàn)［4］中引入慣性權(quán)重的概念，為解決粒子爆炸問題取得了重大的進(jìn)展；后來，Shi等［5］提出了一種基于慣性權(quán)重ω線性遞減的粒子群優(yōu)化（linearly decreasing weight PSO，LWPSO）算法，其滿足了算法在搜索初期全局搜索能力強、在搜索后期局部搜索能力強的需求，對慣性權(quán)重的研究產(chǎn)生了深遠(yuǎn)的影響.陳貴敏等［6］在慣性權(quán)重線性遞減的基礎(chǔ)上，又提出了3種非線性的權(quán)值遞減策略；同時，自適應(yīng)策略［7］、模糊規(guī)則策略［8］、混沌策略［9］、指數(shù)型策略［10］等不同慣性權(quán)重的策略也相繼被提出.

受經(jīng)典線性遞慣性權(quán)重思想的啟發(fā)，為了更好地平衡全局搜索能力和局部搜索能力，本文提出一種動態(tài)調(diào)節(jié)慣性權(quán)重的策略，由隨機因子動態(tài)調(diào)節(jié)慣性權(quán)重，并通過適應(yīng)度函數(shù)的引導(dǎo)使粒子更好地進(jìn)行尋優(yōu)搜索.通過8個測試函數(shù)對標(biāo)準(zhǔn)PSO，LWPSO和該方法進(jìn)行仿真實驗，測試結(jié)果表明：該方法較前2種PSO算法有更優(yōu)越的尋優(yōu)性能.

1　PSO算法原理

PSO算法源于對鳥類捕食行為的研究.鳥類捕食時，最簡單有效的方式就是尋找距離食物最近的鳥的周圍區(qū)域.PSO首先在可行解中初始化一群粒子，每個粒子都代表該優(yōu)化問題的一個潛在最優(yōu)解，每個粒子對應(yīng)一個由適應(yīng)度函數(shù)決定的適應(yīng)度值，用速度、位置和適應(yīng)度值表示該粒子的特征.假設(shè)在一個D維的搜索空間中有m個粒子，其中第i個粒子的位置向量為Xi=（Xi1，Xi2，…，XiD），第i個粒子的速度向量為Vi=（Vi1，Vi2，…，ViD）.在PSO算法的進(jìn)化過程中，個體極值為個體所經(jīng)歷位置中計算得到的適應(yīng)度值最優(yōu)位置，記為Pi=（Pi1，Pi2，…，PiD），群體極值為種群中所有粒子尋找到的適應(yīng)度最優(yōu)位置，記為Pg=（Pg1，Pg2，…，PgD）.在迭代過程中，每個粒子都會根據(jù)個體極值、群體極值和自己前一時刻的速度狀態(tài)來更新自身的速度和位置，位置和速度更新公式如下［11］：

其中，i＝1，2，…，m；d＝1，2，…，D；ω為慣性權(quán)重，在標(biāo)準(zhǔn)PSO算法中一般設(shè)置為在區(qū)間［0.8，1.2］之間的一個常數(shù)；r1，r2是分布于［0，1］區(qū)間上的隨機數(shù)；c1，c2為加速因子，是2個非負(fù)的常數(shù)；Pid是第i個粒子的個體極值；Pgd是整個粒子群的群體極值是第i個粒子的當(dāng)前位置是第i個粒子的當(dāng)前速度.粒子速度更新公式（1）主要由記憶項、自我認(rèn)知項和社會認(rèn)知項3部分組成.其中為記憶項，反映了前一次粒子速度的方向、大小對本次速度更新的影響，粒子按原始方向飛行的趨勢,起到了局部開發(fā)與全局搜索的能力為自我認(rèn)知項，是由當(dāng)前粒子指向個體極值的一個矢量，反映了算法中的粒子本身記憶對尋優(yōu)結(jié)果的影響，使粒子具有全局搜索能力為社會認(rèn)知項，是由當(dāng)前粒子指向群體極值的一個矢量，群體信息對粒子個體的影響由此反映，它表示了算法中粒子向整個搜索空間中在迭代過程中曾經(jīng)找到的最優(yōu)位置進(jìn)行尋優(yōu)的趨勢，本質(zhì)上體現(xiàn)了粒子間協(xié)同合作［12］.

2　動態(tài)調(diào)節(jié)慣性權(quán)重的PSO算法

慣性權(quán)重ω是PSO優(yōu)化算法的可調(diào)參數(shù)中最重要的參數(shù)之一，其大小控制了迭代過程中歷史因素對當(dāng)前狀態(tài)的影響程度.PSO算法中慣性權(quán)重確定從最初的依賴經(jīng)驗到對各種策略的初步探索取得了一定的成效.在大多數(shù)PSO算法改進(jìn)中，學(xué)者偏向使用簡單、直觀的慣性權(quán)重線性減小的方法，即慣性權(quán)重隨著算法迭代次數(shù)的增加而線性減小.ω滿足公式：

這種方法自提出來雖被廣泛應(yīng)用于各類優(yōu)化問題之中，但由于在實際的尋優(yōu)過程中，算法迭代進(jìn)化是復(fù)雜且為非線性變化的，讓ω單純呈線性減小的方式并不能很好地與真實尋優(yōu)過程相匹配.假設(shè)將慣性權(quán)重設(shè)定為服從某種分布的隨機數(shù)，并根據(jù)粒子適應(yīng)度大小做出選擇，慣性權(quán)重受隨機因子影響而動態(tài)地調(diào)整，使算法不僅具有跳出局部最優(yōu)的機會，還能提高算法的全局搜索性能；因此，在一定程度上，隨機因子可以從2個方面來克服算法在進(jìn)化過中慣性權(quán)重隨迭代次數(shù)線性遞減所產(chǎn)生的影響.對比慣性權(quán)重線性遞減的方法來說：第一，隨機因子使得粒子能在搜索初期有機會取到較小的慣性權(quán)重，加速算法的收斂；第二，隨機因子又能在搜索后期有機會取到較大的慣性權(quán)重，提高算法收斂精度.若在搜索前期，粒子已在最優(yōu)解附近時，與線性遞減策略產(chǎn)生的權(quán)值相比較，隨機分布的慣性權(quán)重有機會產(chǎn)生相對小的值，在2種不同權(quán)值情況下，后者的粒子適應(yīng)度比前者的粒子適應(yīng)度小，算法會選擇隨機分布產(chǎn)生的慣性權(quán)重，此時相對小的慣性權(quán)重有利于增強算法的局部搜索能力，加快算法的收斂速度；如果隨機分布的慣性權(quán)重產(chǎn)生了相對大的值，計算函數(shù)的適應(yīng)度值時，算法則會將隨機分布產(chǎn)生的權(quán)值淘汰，并選擇線性遞減策略產(chǎn)生的權(quán)值.同理，若在搜索后期，粒子依然與最優(yōu)解的距離較遠(yuǎn)時，隨機分布的慣性權(quán)重有機會產(chǎn)生相對大的值，此時相對大的慣性權(quán)重有利于增強算法的全局搜索能力，提高算法的尋優(yōu)精度；如果隨機分布的慣性權(quán)重產(chǎn)生的值較小，算法則會將其淘汰.

基于以上分析，提出動態(tài)調(diào)節(jié)慣性權(quán)重ω的生成公式：

其中，ω0滿足式（3），n為服從正態(tài)分布，其均值為1，標(biāo)準(zhǔn)差為0.01.

本算法綜合考慮了粒子適應(yīng)度（Fitness）和隨機分布（Random distribution），簡稱為FRPSO算法.具體流程如下：

Step1先對粒子進(jìn)行隨機初始化，使每個粒子都具有初始速度Vid和初始位置Xid，其中i∈［1,m］，m為粒子個數(shù)，d∈［1,D］，D為粒子的維數(shù)，取值約束在設(shè)置范圍內(nèi)；

Step2將測試函數(shù)的函數(shù)值設(shè)置為粒子的適應(yīng)度值，根據(jù)測試函數(shù)計算初始粒子的適應(yīng)度值，并尋找個體極值Pi和群體極值Pg；

Step3根據(jù)式（3）、式（4）計算2種不同的慣性權(quán)重ω0和ω1；

Step4根據(jù)式（1）、式（2）更新不同慣性權(quán)重下的粒子位置和粒子速度，并檢查更新后的位置Xid和速度Vid是否越界；

Step5計算、比較2種新粒子的適應(yīng)度值fitness0和fitness1，若fitness0比fitness1好，則算法選擇隨機分布的慣性權(quán)重，并對新粒子進(jìn)行個體極值和群體極值的更新.反之，若fitness1比fitness0好，則算法淘汰隨機分布產(chǎn)生的慣性權(quán)重，選擇按式（3）計算的慣性權(quán)重，對粒子進(jìn)行個體極值和群體極值的更新；

Step6若運行次數(shù)達(dá)到預(yù)設(shè)最大迭代尋優(yōu)次數(shù)，算法停止并輸出全局最優(yōu)解.否則，返回Step3繼續(xù)搜索.

3　仿真實驗及分析

3.1測試函數(shù)

為了測試FRPSO算法對搜索性能的改善，采用8個典型測試函數(shù)進(jìn)行對比分析.測試函數(shù)的維數(shù)、變量取值范圍和目標(biāo)值如表1所示.8個測試函數(shù)的具體數(shù)學(xué)描述如下：

a）f1為Rastrgin函數(shù)

多峰函數(shù)，全局最優(yōu)點在xi=0，i=1，…，n，目標(biāo)函數(shù)最優(yōu)值是f1（x）=0.

b）f2為Griewankan函數(shù)

多峰函數(shù)，全局最優(yōu)點在xi=0，i=1，…，n，目標(biāo)函數(shù)最優(yōu)值是f2（x）=0.

c）f3為Sphere函數(shù)

單峰函數(shù)，全局最優(yōu)點在xi=0，i=1，…，n，目標(biāo)函數(shù)最優(yōu)值是f3（x）=0.

d）f4為Rosenbrock函數(shù)

單峰函數(shù)，全局最優(yōu)點在xi=1，i=1，…，n，目標(biāo)函數(shù)最優(yōu)值是f4（x）=0.

e）f5為Schaffer函數(shù)

表1　測試函數(shù)的維數(shù)、初值范圍、目標(biāo)值和期望值Tab.1 The dimension，initial value range，target value and expected value of the test function

多峰函數(shù)，全局最優(yōu)點在xi=0，i=1，…，n，目標(biāo)函數(shù)最優(yōu)值是f5（x）=-1.

f）f6為Schwefel’s Problem 2.21函數(shù)

單峰函數(shù)，全局最優(yōu)點在xi=0，i=1，…，n，目標(biāo)函數(shù)最優(yōu)值是f6（x）=0.

g）f7為Schwefel’s Problem 2.22函數(shù)

單峰函數(shù)，全局最優(yōu)點在xi=0，i=1，…，n，目標(biāo)函數(shù)最優(yōu)值是f7（x）=0.

h）f8為Schwefel’s Problem 1.2函數(shù)

單峰函數(shù)，全局最優(yōu)點在xi=0，i=1，…，n，目標(biāo)函數(shù)最優(yōu)值是f8（x）=0.

3.2算法測試及分析

將提出的FRPSO算法與標(biāo)準(zhǔn)PSO，LWPSO算法進(jìn)行比較.對算法的參數(shù)取值設(shè)置如下：粒子群的種群規(guī)模m＝20，學(xué)習(xí)因子c1＝c2＝1.494 45，最大迭代次數(shù)為300.在標(biāo)準(zhǔn)PSO算法中，慣性權(quán)重ω=1；在LWPSO算法與FRPSO算法中，ωstart＝0.9，ωend＝0.4.3種不同算法分別獨立運行50次，并對這50次所得結(jié)果進(jìn)行統(tǒng)計，計算3種算法的成功率（成功率為迭代尋優(yōu)結(jié)束時，結(jié)果值小于給定精度的次數(shù)與運行次數(shù)的百分比）和適應(yīng)度值的平均值.表2給出了不同維度下標(biāo)準(zhǔn)PSO，LWPSO和FRPSO算法的實驗結(jié)果數(shù)值.

表2　3種算法運行50次的平均適應(yīng)值與成功率Tab.2 Average fitness and success rate of 3 algorithm s running 50 times

從仿真結(jié)果不難看出，對函數(shù)f1來說，不管在二維還是十維函數(shù)下，LWPSO算法的尋優(yōu)結(jié)果都較標(biāo)準(zhǔn)PSO算法好，但兩者結(jié)果都不如FRPSO算法.對函數(shù)f2來說，不管在二維還是十維函數(shù)下，LWPSO算法的尋優(yōu)結(jié)果都較標(biāo)準(zhǔn)PSO算法差，且兩者結(jié)果遠(yuǎn)不如FRPSO算法.對函數(shù)f3~f8來說，在二維函數(shù)情況下，LWPSO算法的尋優(yōu)結(jié)果較標(biāo)準(zhǔn)PSO算法好；在十維函數(shù)情況下，標(biāo)準(zhǔn)PSO算法尋優(yōu)結(jié)果較LWPSO算法好.但在2種維度下，F(xiàn)RPSO算法的尋優(yōu)結(jié)果比標(biāo)準(zhǔn)PSO，LWPSO算法的尋優(yōu)結(jié)果都好.特別是對函數(shù)f3，f8來說，F(xiàn)RPSO算法的尋優(yōu)精度大大提高.由于篇幅限制，此處給出測試函數(shù)f1、測試函數(shù)f3分別在二維函數(shù)、十維函數(shù)下2種不同維度的收斂曲線圖，分別如圖1～圖4所示.從圖中可以明顯看出，本文提出的FRPSO算法在不同維度下對比另外2種PSO算法來說，具有更高的收斂精度.

圖1　二維Rastrgrin函數(shù)收斂結(jié)果對比Fig.1 Comparison of convergence results for 2 dimensional Rastrgrin functions

圖2　十維Rastrgrin函數(shù)收斂結(jié)果對比Fig.2 Comparison of convergence results for 10 dimensional Rastrgrin functions

圖3　二維Sphere函數(shù)收斂結(jié)果對比Fig.3 Comparison of convergence results for 2 dimensional Sphere functions

圖4　十維Sphere函數(shù)收斂結(jié)果對比Fig.4 Comparison of convergence results for 10 dimensional Sphere functions

4　結(jié)語

本文通過引入隨機因子對PSO算法的慣性權(quán)重進(jìn)行動態(tài)調(diào)節(jié)，取得了算法在全局搜索與局部搜索之間的平衡，提出一種動態(tài)調(diào)節(jié)慣性權(quán)重的PSO算法.該算法突破經(jīng)典慣性權(quán)重呈線性遞減的約束，使算法根據(jù)粒子適應(yīng)度大小來選擇慣性權(quán)重.仿真結(jié)果證明，本文提出的FRPSO算法相比標(biāo)準(zhǔn)PSO算法和LWPSO算法而言，F(xiàn)RPSO算法的尋優(yōu)性能有明顯改善，提高了算法的收斂精度.

［1］KENNEDY J，EBERHART R.Particle Swarm Optimization：IEEE International Conference on Neural Networks，1995［C］.Perth：IEEE，1995.

［2］李哲明，李春貴，呂少姣.基于混沌粒子群優(yōu)化的時變解耦模糊滑模控制［J］.廣西工學(xué)院學(xué)報，2013，24（3）：67－72.

［3］陳陽，唐培和，徐奕奕.結(jié)合混沌粒子群的分布式最大功率點跟蹤［J］.廣西科技大學(xué)學(xué)報，2015，26（2）：41－46.

［4］SHIY，EBERHART R.A Modified Particle Swarm Optimizer：IEEE World Congress on Computational Intelligence，1998［C］.Anchorage：IEEE，1998.

［5］SHIY，EBERHARTR.Empirical Study of Particle Swarm Optimization：Evolutionary Computation，1999［C］.Washington：IEEE，1999.

［6］陳貴敏，賈建援，韓琪.粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究［J］.西安交通大學(xué)學(xué)報，2006，40（1）：53－56，61.

［7］DONG C，WANG G，CHEN Z，et al.A Method of Self－Adaptive Inertia Weight for PSO：Computer Science and Software Engineering，2008 International Conference on，2008［C］.Wuhan：IEEE，2008.

［8］LIU C，OUYANG C，ZHU P，et al.An Adaptive Fuzzy Weight PSO Algorithm：International Conference on Genetic and Evolutionary Computing，2010［C］.Shenzhen：IEEE，2010.

［9］LIANG J，CAIQ，CHU ZL，etal.Bayesian Network Structure Learning Algorithm Using Particle Swarm Optimization［J］.Journal of Huazhong University of Science and Technology（Natural Science Edition），2012，40（12）：44－48.

［10］EMEMIPOUR J，NEJAD M，EBADZADEH M.Introduce a New Inertia Weight for Particle Swarm Optimization：Computer Sciences and Convergence Information Technology，2009［C］.Seoul：IEEE，2009.

［11］SHI Y，EBERHART R.Fuzzy Adaptive Particle Swarm Optimization：Evolutionary Computation，Proceedings of the 2001 Congress on，2001［C］.Seoul：IEEE，2001.

［12］趙遠(yuǎn)東，方正華.帶有權(quán)重函數(shù)學(xué)習(xí)因子的粒子群算法［J］.計算機應(yīng)用，2013，33（8）：2265－2268.

（學(xué)科編輯：黎婭）

Particle swarm optimization algorithm for dynamic adjustment of inertia weight

PI Qian-ying1，2，YE Hong-tao*1，2
(1.School of Electrical and Information Engineering,Guangxi University of Science and Technology, Liuzhou 545006,China;2.Guangxi Key Laboratory of Automobile Components and Vehicle Technology,Liuzhou 545006,China)

In PSO,the inertia weight is a critical parameter,its role is to balance algorithm global and local search capabilities.For the use of classical linear decreasing strategy to determine the inertia weight particle swarm optimization during operations and optimization of nonlinear changes in particle characteristics mismatch problem, a dynamic adjustment of inertia weight particle swarm algorithm is proposed.The algorithm introduces random inertia weight factor,dynamically adjusts inertia weight based on particle size fitness,better guides the particle search and balances global and local search capabilities so as to improve the convergence precision.In order to verify the performance of the optimization algorithm,by 8 classic test function PSO,decreasing inertia weight particle swarm algorithm and dynamic adjustment of inertia weight particle swarm algorithm were tested in comparison with different dimensions.The results show that the proposed dynamic adjustment of inertia weight particle swarm optimization algorithm in accuracy and success rates have improved,the performance of the algorithm is more advantageous.

particle swarm optimization;dynamic adjustment;inertia weight;random factor

TP301.6

A

2095-7335（2016）03-0026-07

10.16375/j.cnki.cn45-1395/t.2016.03.005

2016-04-13

廣西重點實驗室項目（14-045-44）；廣西教育廳科研項目（201202ZD071）；廣西工學(xué)院博士基金項目（院科博11Z09）資助.

葉洪濤，博士，教授，研究方向：智能優(yōu)化與控制，E-mail：yehongtao@126.com.