一種改進的粒子群算法研究

董翠英，曹曉月

(唐山學院 智能與信息工程學院，河北 唐山 063000)

0 引言

粒子群算法(Particle Swarm Optimization，簡稱PSO)是一種基于群體的隨機優化技術[1]，是Kennedy和Eberhart于1995年提出的一種基于群體智能的進化優化算法，其思想來源于人工生命和進化計算理論。PSO算法具有的復雜度低、運算精度高、收斂速度快、需要設置和調整的參數較少等優點引起了學術界的重視，并在解決實際問題中展示了其優越性，如在函數優化、非線性系統的辨別、神經網絡訓練等領域有了很好的應用。但是，對PSO的研究還不完善，基本PSO還存在一些缺陷[2-5]，如收斂精度不高，迭代后期收斂速度慢，容易陷入局部優化。自適應粒子群算法[6]在傳統粒子群的基礎上加入了按照非線性動態調整的慣性因子W，加速了算法的收斂速度，但加入非線性因子使得種群多樣性喪失。本文提出將差分進化算法中的交叉算子用于保持種群多樣性，以跳出局部尋優。差分進化算法(Differential Evolution，簡稱DE)是一種新興的群體進化算法，它通過模仿生物群體的個體間的合作與競爭所產生的啟發式群體智能來指導搜索。1995年，R.Storn和K.Price提出差分進化算法，主要用于解決切比雪夫多項式問題，后來研究出DE也可以解決復雜優化問題。差分進化算法是一種高效的全局優化算法，具有較強的收斂能力，可解決復雜的優化問題，如用于求解多目標、約束、高維、非凸非離散的數值優化問題。本文將結合粒子群算法和差分進化算法得到一種改進的粒子群優化算法。

1 PSO算法和差分進化算法

1.1 PSO算法

PSO算法首先在可解空間初始化一群粒子，每個粒子都代表極值優化問題的一個潛在最優解，然后用位置、速度和適應度三項指標表示該粒子特征，適應度值由適應度函數計算得到，其值的好壞表示粒子的優劣。粒子在解空間中運動，通過跟蹤個體極值pbest和群體極值gbest得以更新。個體極值pbest是指個體所經歷位置中計算得到的適應度值最優位置，群體極值gbest是指種群中的所有粒子搜索到的適應度最優位置。粒子每更新一次位置，就計算一次適應度值，并且通過比較新粒子的適應度值和個體極值、群體極值的適應度值，來更新個體極值pbest和群體極值gbest位置。

假設在一個D維的搜索空間中，有n個粒子組成的種群X=(X1，X2，…Xn)，其中第i個粒子表示為一個D維的向量Xi=[Xi1，Xi2，…，XiD]T，代表第i個粒子在D維搜索空間中的位置，亦代表問題的一個潛在解。根據目標函數即可計算出每個粒子位置Xi對應的適應度值。第i個粒子的速度為Vi=[Vi1，Vi2，…，ViD]T，其中個體極值為Pi=[Pi1，Pi2，…，PiD]T，種群的全局極值為Pg=[Pg1，Pg2，…，PgD]T。

在每一次迭代過程中，粒子通過個體極值和全局極值更新自身的速度和位置，更新公式如下列公式所示：

vidk+1=w*Vidk+c1*rand1*(pbestijk-xijk)+c2*rand2*(gbestjk-xijk)，

(1)

xidk+1=xidk+vidk+1。

(2)

在(1)(2)式中，w為慣性權重；d=1，2，…，D；i=1，2，…，n；k為當前迭代次數；Vid為粒子速度；c1和c2為非負常數，稱為加速度因子，rand1和rand2為分布于[0，1]之間的隨機數。為防止粒子的盲目搜索，一般建議將其位置和速度限制在一定區間[-Xmax，Xmax]和[-Vmax，Vmax]。

1.2 差分進化算法

1.2.1 變異操作

(3)

1.2.2 交叉操作

，

(4)

1.2.3 選擇操作

(5)

其中，finess()為適應度函數，一般以所要優化的目標函數為適應度函數。

2 改進的粒子群算法

2.1 算法的步驟

標準粒子群算法初期收斂速度快，后期收斂速度慢，易陷入局部尋優的缺陷，基于此出現了自適應的粒子群算法[7]。所謂自適應粒子群算法，是加入慣性因子w。較大的w值有利于提高算法的收斂速度，而w較小時則有利于提高算法的收斂精度。對于w的控制經歷了從固定值到線性變化再到非線性變化的過程。不同的進化策略有不同的優點，在所有問題的解決上，并沒有哪一個進化策略能比其他進化策略更好。在一個算法中如果能夠結合不同的策略的優點，那么算法的性能能夠達到更優。本文提出一種改進的自適應粒子群算法(Improved adaptive PSO algorithm，簡稱IPSO)，采用的是非線性變化，其更新公式為：

(6)

其中，t是當前進化次數，tmax是最大進化次數，wmax為最大慣性權重。

但是因加入了非線性因子會使群多樣性下降，陷入局部尋優，故又加入了差分進化算法中的交叉算子來提高算法的全局探索能力，保持種群多樣性，利用DE算法的變異策略產生候選解，位置更新公式為：

xij=xr1j+F·(xr2j-xr3j)，j=1，2，…，D，

(7)

其中i=1，2，…，N；r1，r2，r3∈{1，2，…，N}，是隨機選取的3個個體，且r1≠r2≠r3≠i；F為[0，2]之間的變異因子，這里取0.5。

此算法既保證了算法的速度，又保證了算法的精度。算法的描述如下：

Step1：初始化一群微粒(群體規模為m)，包括隨機位置和速度；

Step2：評價每個微粒的適應度；

Step3：對每個微粒，將其適應值與其自身經過的最好位置作比較，如果較好，則將其作為當前的最好位置pbest；

Step4：對每個微粒，將其適應值與所有粒子經過的最好位置作比較，如果較好，則將其作為當前的最好位置gbest；

Step5：如果rand<變異率，采用差分交叉算子更新粒子位置，否則根據標準粒子群算法來調整微粒速度和位置；

Step6：未達到結束條件則轉Step2。

IPSO算法的流程如圖1所示。

圖1 IPSO算法的流程

2.2 仿真與分析

為證明該算法的性能，本文選擇了2個經典的函數進行測試。

F1：Ackley函數

F2：Griewank函數

(x∈[-500，500]，minf2(x)=0)。

為證明算法的性能，將本文算法與標準粒子群算法(PSO)、遺傳算法(GA)在精度、維度、收斂速度方面作對比試驗。其中參數設置為：群體規模均為30，在標準PSO算法中，慣性因子取值為0.5，學習因子c1=c2=2；在IPSO算法中，慣性因子從1.05非線性減到0.05，c1=c2=2，變異因子F=0.5；每種算法的最大迭代次數為2 000。每種算法的測試函數上隨機運行10次求其平均值。維度設置為2維、10維、30維。表1表2分別是函數f1，f2采用不同算法的實驗結果。

表1 函數f1的實驗結果

表2 函數f2的實驗結果

由表1可知，對于f1函數而言，在2維、10維、30維時，IPSO算法最優值均優于PSO，GA算法。

對于f2函數而言，在2維、10維、30維時，IPSO算法的最優值均優于PSO，GA算法。

這兩個函數的圖像和在3個算法下的適應度值進化曲線如圖2，圖3所示。

圖2 函數f1的進化曲線

圖3 函數f2的進化曲線

由圖2可以看出，PSO算法在迭代初期收斂速度比較快，在大約迭代200次便得到了最優值，精確度在10-15左右；IPSO算法初期迭代速度沒有PSO算法快，但最后精度和IPSO算法一樣。由圖3可知，IPSO算法迭代速度是最快的，在1 400次左右陷入局部尋優，但最后跳出了局部尋優，最后精度在10-14左右，說明對粒子群算法的改進是有效的。

3 結論

本文提出的一種改進的自適應粒子群算法，是在傳統自適應粒子群算法的基礎上，引入了差分進化算法中的交叉算子來提高算法的全局探索能力，利用DE算法的變異策略產生候選解，來克服種群多樣性的下降，從而跳出局部最優。通過對2個典型基準函數的優化問題測試了IPSO算法的性能，同時與標準粒子群算法(PSO)和遺傳算法(GA)算法進行了比較。仿真結果表明，本文提出的算法是一種收斂速度快、收斂精度高的全局尋優算法。