董翠英，曹曉月

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

0 引言

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

1 PSO算法和差分進化算法

1.1 PSO算法

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

假設(shè)在一個D維的搜索空間中，有n個粒子組成的種群X=(X1，X2，…Xn)，其中第i個粒子表示為一個D維的向量Xi=[Xi1，Xi2，…，XiD]T，代表第i個粒子在D維搜索空間中的位置，亦代表問題的一個潛在解。根據(jù)目標函數(shù)即可計算出每個粒子位置Xi對應(yīng)的適應(yīng)度值。第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為慣性權(quán)重；d=1，2，…，D；i=1，2，…，n；k為當前迭代次數(shù)；Vid為粒子速度；c1和c2為非負常數(shù)，稱為加速度因子，rand1和rand2為分布于[0，1]之間的隨機數(shù)。為防止粒子的盲目搜索，一般建議將其位置和速度限制在一定區(qū)間[-Xmax，Xmax]和[-Vmax，Vmax]。

1.2 差分進化算法

1.2.1 變異操作

(3)

1.2.2 交叉操作

，

(4)

1.2.3 選擇操作

(5)

其中，finess()為適應(yīng)度函數(shù)，一般以所要優(yōu)化的目標函數(shù)為適應(yīng)度函數(shù)。

2 改進的粒子群算法

2.1 算法的步驟

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

(6)

其中，t是當前進化次數(shù)，tmax是最大進化次數(shù)，wmax為最大慣性權(quán)重。

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

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：初始化一群微粒(群體規(guī)模為m)，包括隨機位置和速度；

Step2：評價每個微粒的適應(yīng)度；

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

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

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

Step6：未達到結(jié)束條件則轉(zhuǎn)Step2。

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

圖1 IPSO算法的流程

2.2 仿真與分析

為證明該算法的性能，本文選擇了2個經(jīng)典的函數(shù)進行測試。

F1：Ackley函數(shù)

F2：Griewank函數(shù)

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

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

表1 函數(shù)f1的實驗結(jié)果

表2 函數(shù)f2的實驗結(jié)果

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

對于f2函數(shù)而言，在2維、10維、30維時，IPSO算法的最優(yōu)值均優(yōu)于PSO，GA算法。

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

圖2 函數(shù)f1的進化曲線

圖3 函數(shù)f2的進化曲線

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

3 結(jié)論

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