一種改進(jìn)的粒子群算法研究

董翠英，曹曉月

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

0 引言

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

1 PSO算法和差分進(jìn)化算法

1.1 PSO算法

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

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

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

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為當(dāng)前迭代次數(shù)；Vid為粒子速度；c1和c2為非負(fù)常數(shù)，稱為加速度因子，rand1和rand2為分布于[0，1]之間的隨機(jī)數(shù)。為防止粒子的盲目搜索，一般建議將其位置和速度限制在一定區(qū)間[-Xmax，Xmax]和[-Vmax，Vmax]。

1.2 差分進(jìn)化算法

1.2.1 變異操作

(3)

1.2.2 交叉操作

，

(4)

1.2.3 選擇操作

(5)

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

2 改進(jìn)的粒子群算法

2.1 算法的步驟

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

(6)

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

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

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

(7)

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

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

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

Step2：評(píng)價(jià)每個(gè)微粒的適應(yīng)度；

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

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

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

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

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

圖1 IPSO算法的流程

2.2 仿真與分析

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

F1：Ackley函數(shù)

F2：Griewank函數(shù)

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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