一種帶變異算子的PSO算法*

余仁波　趙修平　孟凡磊

(海軍航空工程學(xué)院飛行器工程系　煙臺(tái)　264001)

?

一種帶變異算子的PSO算法*

余仁波趙修平孟凡磊

(海軍航空工程學(xué)院飛行器工程系煙臺(tái)264001)

論文在基本PSO算法基礎(chǔ)上，引入了遺傳算法的變異算子。通過(guò)變異算子的控制函數(shù)，將PSO算法的訓(xùn)練過(guò)程分為前期和后期。在算法訓(xùn)練的前期，變異率取較大的值，以選擇較多的粒子進(jìn)行變異操作，目的是增強(qiáng)種群內(nèi)部粒子的多樣性，使得PSO算法能夠在解空間的較大范圍內(nèi)進(jìn)行搜索，以避免算法過(guò)早陷入局部最優(yōu)解；在訓(xùn)練的后期，變異率取較小的值，以選擇較少的粒子進(jìn)行變異操作，目的是減弱種群內(nèi)部粒子的多樣性，使得PSO算法能夠在解空間的較小范圍內(nèi)進(jìn)行搜索，以提高算法的收斂精度。仿真研究表明，論文的算法具有較高的收斂精度，并且解決局部極小問(wèn)題也相當(dāng)成功。

PSO算法; 遺傳算法; 變異算子; 控制函數(shù); 局部極小值

Class NumberTP301.6

1　引言

Kennedy J和Eberhart R于1995年提出了粒子群算法(PSO)[1]。作為一種快速仿生進(jìn)化算法，PSO算法目前已廣泛應(yīng)用在工業(yè)領(lǐng)域中的優(yōu)化問(wèn)題[2]。本文稱文獻(xiàn)[1]提出的算法為基本PSO算法。基本PSO算法具有算法簡(jiǎn)單易用的優(yōu)點(diǎn)，缺點(diǎn)是容易陷入優(yōu)化問(wèn)題的局部最優(yōu)解。針對(duì)這個(gè)問(wèn)題，人們對(duì)基本PSO算法進(jìn)行了諸多改進(jìn)，提出了不少改進(jìn)的PSO算法。這些改進(jìn)算法一般是對(duì)基本PSO算法的一些參數(shù)進(jìn)行優(yōu)化，難以解決基本PSO算法容易陷入局部最優(yōu)解的矛盾[3～4]。遺傳算法是一種全局搜索的優(yōu)化算法，搜索的精度低。PSO算法的精度高，早期容易陷入局部最優(yōu)解。PSO算法與遺傳算法相結(jié)合的混合優(yōu)化算法，能夠利用遺傳算法的全局搜索能力解決經(jīng)典PSO算法容易陷入局部最優(yōu)解的矛盾，同時(shí)也能解決遺傳算法搜索精度低的問(wèn)題。人們?cè)谶@方面已經(jīng)做出了不少工作[5～6]。文獻(xiàn)[7]通過(guò)引進(jìn)遺傳操作的控制函數(shù)，在算法訓(xùn)練的早期主要由PSO算法進(jìn)行搜索，在算法訓(xùn)練的后期遺傳算法以接近于1的概率進(jìn)行操作，避免算法陷入問(wèn)題的局部解。

如上所述，PSO算法是一種局部?jī)?yōu)化“群智能”算法，通過(guò)種群內(nèi)部粒子之間的競(jìng)爭(zhēng)來(lái)搜索最優(yōu)解，容易陷入局部最優(yōu)解[8]。陷入局部最優(yōu)解的原因是：在算法訓(xùn)練過(guò)程中，種群內(nèi)部的粒子過(guò)早趨于一致，使得算法的搜索空間變得非常小。有效的解決方案是：在算法訓(xùn)練的前期，保持種群內(nèi)部粒子的多樣性，使得算法在解空間的較大范圍內(nèi)進(jìn)行搜索；在算法訓(xùn)練的后期，縮小搜索范圍，利用PSO的局部搜索能力向最優(yōu)解方向進(jìn)行搜索。這樣能夠避免PSO算法過(guò)早陷入局部最優(yōu)解，同時(shí)也能夠獲得較高的收斂精度。

遺傳算法是一種全局搜索的優(yōu)化算法，缺陷是難以獲得較高的收斂精度。遺傳算法的全局搜索能力源于種群內(nèi)部個(gè)體的多樣性。在遺傳算法訓(xùn)練過(guò)程中，算法主要通過(guò)變異操作和交叉操作保持種群內(nèi)部個(gè)體的多樣性，使得算法始終在解空間的較大范圍內(nèi)進(jìn)行搜索。在采用實(shí)數(shù)編碼時(shí)，操作變異算子更容易保持種群內(nèi)部個(gè)體的多樣性[9]。本文在經(jīng)典PSO算法的基礎(chǔ)上，通過(guò)一種變異算子控制函數(shù)，引入了遺傳算法的變異算子。在算法訓(xùn)練的前期，變異算子采用比較大的變異率，以保持種群內(nèi)部粒子的多樣性，使得PSO算法能夠在解空間的較大范圍內(nèi)進(jìn)行搜索，以減小算法陷入局部最優(yōu)解的概率；在訓(xùn)練的后期，變異算子采用比較小的變異率，使得PSO算法能夠在解空間的較小范圍內(nèi)進(jìn)行搜索，以提高算法的收斂精度。

2　基本PSO算法

考慮優(yōu)化問(wèn)題：f(x)是一個(gè)D維連續(xù)函數(shù)，優(yōu)化問(wèn)題為

minf(x)

X=[x1,x2,…,xD]s.t.xi∈[ai,bi]

(1)

其中：f(x)為目標(biāo)函數(shù)，在PSO算法中稱為適應(yīng)度函數(shù)，[ai,bi]為xi搜索范圍。設(shè)種群由N個(gè)粒子組成，每個(gè)粒子代表目標(biāo)函數(shù)的一個(gè)候選解。Xi=(xi1,xi2,…,xiD)為第i個(gè)粒子在D維解空間的位置，Vi=(vi1,vi2，…,viD)為第i個(gè)粒子的速度，pbest=(pi1,pi2,…,piD)為第i個(gè)粒子當(dāng)前最優(yōu)位置，gbest=(pg1,pg2,…,pgD)為全體粒子當(dāng)前最優(yōu)位置[10]。則粒子根據(jù)式(2)和(3)來(lái)更新自己的速度和位置：

vid=w*vid+c1r1(pid-xid)+c2r2(pgd-xid)

(2)

xid=xid+vid

(3)

其中：c1和c2為學(xué)習(xí)因子，r1和r2為[0，1]范圍內(nèi)的均勻隨機(jī)數(shù)，w為慣性系數(shù)[11]。根據(jù)經(jīng)驗(yàn)，通常c1=c2=1.4962。i=1,2,…,D。對(duì)于慣性系數(shù)，本文采用動(dòng)態(tài)遞減的策略，將在下文給出具體的方案。

則基本PSO算法的步驟如下：

第一步：初始化，包括群體規(guī)模N，學(xué)習(xí)因子c1和c2，慣性系數(shù)w，每個(gè)粒子的位置xi和速度Vi，最大迭代次數(shù)epochmax；

第二步：對(duì)每個(gè)粒子，按式(1)計(jì)算其適應(yīng)度值fit[i]，并與其個(gè)體最優(yōu)值pbest(i)比較，iffit[i]>pbest(i)thenpbest(i)=f[i]；

第三步：尋找全局最優(yōu)值gbest，即ifpbest(i)>gbest(i)thengbest=pbest(i)；

第四步：根據(jù)式(2)、(3)更新粒子的速度vi和位置xi；

第五步如果滿足結(jié)束條件，退出算法，否則返回第二步。

3　帶遺傳因子的PSO算法

基本PSO算法在算法訓(xùn)練的早期容易陷入局部最優(yōu)解。為了解決這個(gè)問(wèn)題，在上述PSO算法中引入了遺傳算法的操作算子，以保持算法種群內(nèi)部粒子的多樣性，進(jìn)而避免算法過(guò)早收斂到局部最優(yōu)解。具體做法是引入一個(gè)變異算子控制函數(shù)，用來(lái)控制變異算子的變異率。在算法訓(xùn)練的前期，控制變異率取較大的值，以保持種群內(nèi)部粒子的多樣性，使得PSO算法在解空間的較大范圍內(nèi)進(jìn)行搜索；在算法訓(xùn)練的后期，控制變異率取較小的值，根據(jù)PSO算法原理，此時(shí)種群內(nèi)部的粒子很快趨于一致，使得PSO算法在解空間的較小范圍內(nèi)進(jìn)行搜索。

變異控制函數(shù)如式(4)所示：

y(epoch)=(1-(epoch/epochmax)α)β

(4)

其中epoch表示當(dāng)前迭代次數(shù)，epochmax表示最大迭代次數(shù)，α、β表示控制系數(shù)。圖1是五組不同控制系數(shù)時(shí)控制函數(shù)的曲線，其中epochmax=3000，曲線1～曲線5的控制系數(shù)分別為(α,β)=(10,10)、(10,100)、(3,100)、(1.7,10)、(1.7,100)。如圖1所示，通過(guò)設(shè)置適當(dāng)?shù)目刂葡禂?shù)(α,β)可以使得：在算法迭代的前期，控制函數(shù)的值接近于1，在算法迭代的后期，控制函數(shù)的值非常小。

圖1　五組不同控制系數(shù)時(shí)控制函數(shù)的曲線

根據(jù)式(4)，變異算子的變異率由式(5)決定：

μ=m·y(epoch)

(5)

其中，μ是變異算子的變異率，m是預(yù)設(shè)變異率，設(shè)定后不變。

由式(4)和圖1可以看出，當(dāng)t∈[1,epochmax]時(shí)，控制函數(shù)y(epoch,α)是α的單調(diào)遞增函數(shù)，y(epoch,β)是β的單調(diào)遞減函數(shù)。這意味著，通過(guò)調(diào)節(jié)α和β的值，可以控制變異率μ相對(duì)迭代次數(shù)epoch的曲線。α越大，μ取較大值的迭代次數(shù)越多，β越大，μ取較小值的迭代次數(shù)越多。如前文所述，本文中的PSO算法要求在算法訓(xùn)練的前期，變異率取較大的值，在訓(xùn)練的后期，變異率取較小的值。因此，通過(guò)調(diào)節(jié)α和β的值，變異控制函數(shù)y(epoch)可以實(shí)現(xiàn)上述功能，并且可以實(shí)現(xiàn)變異率連續(xù)變化，而不是跳躍變化。

根據(jù)變異率，進(jìn)行變異操作的粒子數(shù)由式(6)決定：

M=[N·μ]

(6)

其中M是進(jìn)行變異操作的粒子數(shù)。

隨機(jī)選擇M個(gè)粒子進(jìn)行變異操作，采用實(shí)數(shù)編碼方案?？紤]第k個(gè)粒子被選中進(jìn)行變異操作，Xk=(xk1,xk2,…,xkD)，其中第j個(gè)元素發(fā)生了變異，則操作策略為

xkj=xkj+rand·y(epoch)

(7)

其中rand∈(-a,a)是隨機(jī)數(shù)。

由式(4)和式(7)可以看出，在算法訓(xùn)練的前期，變異后的粒子距離變異前的粒子比較遠(yuǎn)，變異后的粒子距離變異前的粒子比較近。對(duì)于算法也就意味著在訓(xùn)練的前期搜索空間相對(duì)比較大，減小了過(guò)早陷入局部最優(yōu)解的概率；在訓(xùn)練的后期搜索空間相對(duì)比較小，能夠集中資源向全局最優(yōu)解方向搜索，以提高算法的收斂精度。

本文采用動(dòng)態(tài)遞減的慣性系數(shù)，動(dòng)態(tài)慣性系數(shù)按式(8)計(jì)算

w=wmin+(wmax-wmin)y(epoch)

(8)

其中wmax表示最大慣性系數(shù)，wmin表示最小慣性系數(shù)。采用式(8)的目的是在算法訓(xùn)練的前期采用較大的慣性系數(shù)，算法能夠在較大空間搜索；在算法訓(xùn)練的后期采用較小的慣性系數(shù)，算法能夠在較小空間進(jìn)行精細(xì)搜索。

算法的步驟如下：

第一步初始化，包括群體規(guī)模N，學(xué)習(xí)因子c1和c2，慣性系數(shù)w，每個(gè)粒子的位置xi和速度Vi，最大迭代次數(shù)epochmax，預(yù)設(shè)變異率m；

第二步按式(4)計(jì)算控制函數(shù)y(epoch)，按式(8)計(jì)算慣性系數(shù)w；

第三步根據(jù)式(5)計(jì)算變異率，隨機(jī)選擇M個(gè)粒子按式(7)進(jìn)行變異操作；

第四步對(duì)每個(gè)粒子，按式(1)計(jì)算其適應(yīng)度值fit[i]，并與其個(gè)體最優(yōu)值pbest(i)比較，iffit[i]>pbest(i)thenpbest(i)=f[i]；

第五步尋找全局最優(yōu)值gbest，即ifpbest(i)>gbest(i)thengbest=pbest(i)；

第六步根據(jù)式(2)，式(3)更新粒子的速度vi和位置xi；

第七步如果滿足結(jié)束條件，退出，否則返回第二步。

4　仿真研究

本文采用表1所示的函數(shù)對(duì)算法進(jìn)行驗(yàn)證，其中f1(x)是單峰值函數(shù)，其他是多峰值函數(shù)，搜索空間是整個(gè)實(shí)數(shù)空間。

仿真1：以f2(x)為目標(biāo)函數(shù)對(duì)算法進(jìn)行仿真，圖2～圖3是仿真結(jié)果，仿真參數(shù)為(epochmax,N,α,β,wmin,wmax,c1,c2)=(3000,30,1.7,10,0.1,0.7298,1.4692,1.4692)。圖2是種群中第一個(gè)粒子在解空間搜索的曲線，由圖2不難看出，在算法迭代過(guò)程的前期，第一個(gè)粒子的搜索區(qū)間相對(duì)比較大；在算法迭代過(guò)程的后期，第一個(gè)粒子的搜索區(qū)間相對(duì)比較小。并且在算法訓(xùn)練的兩個(gè)階段，搜索區(qū)間的過(guò)渡比較平滑。這與圖1中曲線4也基本吻合。

仿真2：以f2(x)為目標(biāo)函數(shù)對(duì)算法進(jìn)行仿真，仿真參數(shù)改變?nèi)缦拢害?0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9,2.0,5.0,10.0,20.0；β=10,20,50,100,200，共110組參數(shù)，每一組參數(shù)仿真100次，計(jì)算出最優(yōu)性能指標(biāo)的平均值，得圖4所示一組曲線。由圖可以看出，當(dāng)參數(shù)α、β的值分別為1.7和10時(shí)，算法的收斂精度最高。

仿真3：分別以表1的函數(shù)為目標(biāo)函數(shù)，參數(shù)N分別為20、30、40、50，其他參數(shù)與仿真1相同，每一組參數(shù)仿真100次，計(jì)算出最優(yōu)性能指標(biāo)的平均值，仿真結(jié)果如表2所示。通過(guò)與文獻(xiàn)[2]的仿真結(jié)果比較可以看出，本文的算法的尋優(yōu)性能整體上比較高。

圖2　粒子在解空間搜索曲線

圖3　仿真1訓(xùn)練結(jié)果

圖4　目標(biāo)函數(shù)f2(x)仿真結(jié)果

f1(x)f2(x)f3(x)f4(x)N=209.1341117e-240.63677385.6740390e-130.0003438N=301.5199802e-330.08954635.6843419e-140N=401.4920326e-420.03979834.5723425e-140N=504.0368056e-490.01989924.0785153e-140

5　結(jié)語(yǔ)

本文在基本PSO算法基礎(chǔ)上，引入了遺傳算法的變異算子。通過(guò)變異算子的控制函數(shù)，將PSO算法的訓(xùn)練過(guò)程分為前期和后期。在算法訓(xùn)練的前期，變異算子采用比較大的變異率，以保持種群內(nèi)部粒子的多樣性，使得PSO算法能夠在解空間的較大范圍內(nèi)進(jìn)行搜索，以減小算法陷入局部最優(yōu)解的概率；在訓(xùn)練的后期，變異算子采用比較小的變異率，使得PSO算法能夠在解空間的較小范圍內(nèi)進(jìn)行搜索，以提高算法的收斂精度。仿真研究表明，本文的算法具有較高的收斂精度，并且解決局部極小問(wèn)題也相當(dāng)成功。

[1] Kennedy J, Eberhart R C.Particle swarm optimization [C]//Perth: Proceedings of the 4th IEEE International Conference on Neural Networks,1995:1942-1948.

[2] 高浩,冷文浩,須文波.一種全局收斂的PSO算法及其收斂分析[J].控制與決策，2009(2):196-201.

[3] Kalyan Veeramachneni，Lisa O，Ganapathi K.Probabilistically driven particle swarms for optiomization of multi valued discrete problems：Design an analysis[C]//Honolulu: Proc of IEEE Swarm Intelligence Symposium (SIS),2007:141-149.

[4] Paul S Andrew.An investigation into mutation operators for particle swarm optimization[J].IEEE Congress on Evolutionary Computation，Vancouver,2006,16(21)：1044-1051.

[5] 范晉偉,梅欽,李海涌,等.PSO-GA組合算法優(yōu)化PID參數(shù)及可視化平臺(tái)設(shè)計(jì)[J].機(jī)械設(shè)計(jì)與制造,2013(8)：8-11.

[6] M.Senthil A，M.V.C.Rao，Aarthi C.A new improved version of particle swarm optimization algorithm with global-local best parameters[J].Knowledge and Information Systems,2008,16(3)：331-357.

[7] Gandelli A，Grimaccia F，Mussetta，et al.Development and validation of different hybridization strategies between GA and PSO[J].IEEE Congress on Evolutionary Computation,2007,25(28)：2782-2785.

[8] Dong Hwa Kim, Kaoro Hirota.Vector control for loss minimization of induction motor using GA-PSO[J].Applied Soft Computing 8,2008:1692-1702.

[9] 李勇,吳敏,曹衛(wèi)華,等.基于線性規(guī)劃和遺傳—粒子群算法的燒結(jié)配料多目標(biāo)綜合優(yōu)化方法[J].控制理論與應(yīng)用,2011(12)：1740-1746.

[10] 周建新.基于GA-PSO的區(qū)域人力資本預(yù)測(cè)模型研究[D].成都:成都理工大學(xué)：2009:15-16.

[11] Hui Liu, Hong-qi Tian, Chao Chen, Yan-fei Li.An experimental investigation of two Wavelet-MLP hybrid frameworks[J].Electrical Power and Energy Systems,2013,52:161-173.

A PSO Algorithm with Mutation Operator

YU RenboZHAO XiupingMENG Fanlei

(Department of Airborne Vehicle Engineering, Naval Aeronautical and Astronautical University, Yantai264001)

In this paper, the mutation operator, which is used in Genetic Algorithm, is introduced into the basical PSO algorithm. By mutation operator control function, the training process of the PSO algorithm is divided into early phase and late phase. In the early phase of the algorithm train, the mutation rate is larger, so the more particles are chosen to take the mutation operation, in order to enhance the diversity of the population’s particles, and the PSO algorithm can hunt in a large solution space to avoid being trapped in the local optimal solution too early. In the late phase of the algorithm train, the mutation rate is smaller, so the less particles are chosen to take the mutation operation, in order to attenuate the diversity of the population’s particles, therefore the PSO algorithm can hunt in a smaller solution space to improve the convergence accuracy of the algorithm. Simulation results show that, the convergence precision of this algorithm is higher, and solution of the local minimum problem is quite well.

PSO algorithm, genetic algorithm, mutation operator, control function, local minimum

2016年4月17日,

2016年5月31日

余仁波,男,講師,研究方向：兵器發(fā)射理論與技術(shù)、裝備綜合保障理論與技術(shù)。趙修平,男,教授,研究方向：兵器發(fā)射理論與技術(shù)。孟凡磊,男,講師,研究方向：兵器發(fā)射理論與技術(shù)。

TP301.6

10.3969/j.issn.1672-9730.2016.10.008