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

余仁波　趙修平　孟凡磊

(海軍航空工程學院飛行器工程系　煙臺　264001)

?

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

余仁波趙修平孟凡磊

(海軍航空工程學院飛行器工程系煙臺264001)

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

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

Class NumberTP301.6

1　引言

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

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

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

2　基本PSO算法

考慮優化問題：f(x)是一個D維連續函數，優化問題為

minf(x)

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

(1)

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

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

(2)

xid=xid+vid

(3)

其中：c1和c2為學習因子，r1和r2為[0，1]范圍內的均勻隨機數，w為慣性系數[11]。根據經驗，通常c1=c2=1.4962。i=1,2,…,D。對于慣性系數，本文采用動態遞減的策略，將在下文給出具體的方案。

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

第一步：初始化，包括群體規模N，學習因子c1和c2，慣性系數w，每個粒子的位置xi和速度Vi，最大迭代次數epochmax；

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

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

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

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

3　帶遺傳因子的PSO算法

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

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

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

(4)

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

圖1　五組不同控制系數時控制函數的曲線

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

μ=m·y(epoch)

(5)

其中，μ是變異算子的變異率，m是預設變異率，設定后不變。

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

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

M=[N·μ]

(6)

其中M是進行變異操作的粒子數。

隨機選擇M個粒子進行變異操作，采用實數編碼方案。考慮第k個粒子被選中進行變異操作，Xk=(xk1,xk2,…,xkD)，其中第j個元素發生了變異，則操作策略為

xkj=xkj+rand·y(epoch)

(7)

其中rand∈(-a,a)是隨機數。

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

本文采用動態遞減的慣性系數，動態慣性系數按式(8)計算

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

(8)

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

算法的步驟如下：

第一步初始化，包括群體規模N，學習因子c1和c2，慣性系數w，每個粒子的位置xi和速度Vi，最大迭代次數epochmax，預設變異率m；

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

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

第四步對每個粒子，按式(1)計算其適應度值fit[i]，并與其個體最優值pbest(i)比較，iffit[i]>pbest(i)thenpbest(i)=f[i]；

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

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

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

4　仿真研究

本文采用表1所示的函數對算法進行驗證，其中f1(x)是單峰值函數，其他是多峰值函數，搜索空間是整個實數空間。

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

仿真2：以f2(x)為目標函數對算法進行仿真，仿真參數改變如下：α=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組參數，每一組參數仿真100次，計算出最優性能指標的平均值，得圖4所示一組曲線。由圖可以看出，當參數α、β的值分別為1.7和10時，算法的收斂精度最高。

仿真3：分別以表1的函數為目標函數，參數N分別為20、30、40、50，其他參數與仿真1相同，每一組參數仿真100次，計算出最優性能指標的平均值，仿真結果如表2所示。通過與文獻[2]的仿真結果比較可以看出，本文的算法的尋優性能整體上比較高。

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

圖3　仿真1訓練結果

圖4　目標函數f2(x)仿真結果

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　結語

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

[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組合算法優化PID參數及可視化平臺設計[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] 李勇,吳敏,曹衛華,等.基于線性規劃和遺傳—粒子群算法的燒結配料多目標綜合優化方法[J].控制理論與應用,2011(12)：1740-1746.

[10] 周建新.基于GA-PSO的區域人力資本預測模型研究[D].成都:成都理工大學：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日

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

TP301.6

10.3969/j.issn.1672-9730.2016.10.008