粒子群算法及其改進(jìn)算法

1、粒子群算法及其改進(jìn)算法標(biāo)準(zhǔn)粒子群算法及其改進(jìn)算法首先在這里介紹一下，這個(gè)里主要介紹粒子群算法以及一個(gè)改進(jìn)的二階振蕩粒子群算法。原理粒子群優(yōu)化(PSO)算法是Kennedy和Eberhart受鳥群群體運(yùn)動(dòng)的啟發(fā)于1995年提出的一種新的群智能優(yōu)化算法1。大概的意思就是一片森林里有一群鳥在找一塊食物，它們不知道食物具體在哪，但是可以通過感官(例如嗅覺)去察覺到自己當(dāng)前位置距離食物的遠(yuǎn)近。鳥可以記住自己走過的位置并且知道自己做過的最優(yōu)位置。這一群鳥的運(yùn)動(dòng)都是隨機(jī)的，這類似于一種窮舉法。標(biāo)準(zhǔn)粒子群算法粒子群算法一般用來找一個(gè)函數(shù)的最優(yōu)值。這個(gè)函數(shù)一般就是適應(yīng)度函數(shù)。函數(shù)中未知量的個(gè)數(shù)就是這個(gè)查找的空間

2、維度。假設(shè)有N個(gè)粒子組成一個(gè)種群SXi是代表粒子i所在的位置，i=1,2,，NVi代表粒子i在位置Xi處的速度，i=1,2,，Npi是記錄粒子i到走過的最優(yōu)位置，i=1,2，Npg是所有粒子走過的最優(yōu)的位置，i=1,2，Nw為慣性權(quán)重c1、c2為學(xué)習(xí)因子r1,r2為0,1之間均勻分布的參數(shù)接下來種群中每個(gè)粒子按照公式更新速度和位置：Vi(t+1)=w*Vi(t)+c1*r1*(pi-xi(t)+c2*r2*(pg-xi(t)(1)xi(t+1)=xi(t)+vi(t+1)(2)PS:這里的r1、r2是每一步迭代都需要更新的隨機(jī)數(shù)cl、c2和w=則是一開始給定的一些參數(shù)，至于參數(shù)的給定取決于你自

3、己每次測試這個(gè)程序所得到的經(jīng)驗(yàn)-即哪些參數(shù)你跑出的結(jié)果比較好就選擇哪些參數(shù)。在這里再插一句，在我的實(shí)踐中認(rèn)為沒有必要去限制迭代過程中速度和位置是否超過最大值，如果在給定區(qū)間內(nèi)存在最優(yōu)值那么最后還是會(huì)迭代回來。只需要在給定的區(qū)間內(nèi)初始化就OK了。在我最開始的測試過程中限制速度和位置是使程序變慢了的，但是我一開始的思路出了問題，到很后面才改正過來也么有再去測試這個(gè)，所以就不加評論了。算法流程N(yùn)Y是否達(dá)到最大迭代次數(shù)開始計(jì)算每個(gè)粒子的適應(yīng)度值初始化速度和位置更新plpg更新速度和位置輸出結(jié)果標(biāo)準(zhǔn)p算法代碼functionxm,fv=Pso(N,c1,c2,w,M,D)%c1:自我學(xué)習(xí)因子%c2:社會(huì)

4、學(xué)習(xí)因子%w:慣性權(quán)重%N:種群數(shù)量%M:最大迭代次數(shù)%D:維數(shù)%初始化種群、速度和位置ticfori=1:Nforj=1:Dx(i,j)=unifrnd(-10,10);v(i,j)=unifrnd(-10,10);endend%根據(jù)適應(yīng)度計(jì)算適應(yīng)度值,初始化pi和pgfori=1:Ny(i)=test(x(i,:);pi(i,:)=x(i,:);%y(i,:)為最優(yōu)位置endk=find(y=min(y);pg=x(k(1),:);%更新位置與速度fort=1:Mfori=1:Nv(i,:)=wv(i,:)+c1rand*(pi(i,:)-x(i,:)+c2rand(pg-x(i,:);x

5、(i,:)=x(i,:)+v(i,:);iftest(x(i,:)y(i)y(i)=test(x(i,:);pi(i,:)=x(i,:);endify(i)test(pg)pg=pi(i,:);endendpbest(t)=test(pg);end%輸出結(jié)果disp(最優(yōu)位置)；xm=pgdisp(最優(yōu)值)；fv=test(pg)plot(pbest)toctest函數(shù)-就是適應(yīng)度函數(shù)functiony=test(V)y=0;b=length(V);fori=1:by=y+i*V(i)A2;end標(biāo)準(zhǔn)粒子群算法的局限性為進(jìn)一步說明標(biāo)準(zhǔn)粒子群算法的局限性，做如下推理：設(shè)01=c1*r1,02=c

6、2r2,w=1,由式(1)、(2)可轉(zhuǎn)化為式(3)、(4):Vi(t+1)=Vi(t)+01(pi-xi(t)+02(pg-xi(t)(3)xi(t+1)=xi(t)+vi(t+1)(4)已知速度公式Vi+1=Vi+axAt，可得：a=01(pi-xi(t)+02(pg-xi(t)=xi(t)(5)化簡可得：xi(t)+(01+02)xi(t)-(01pi+02pg)=0(6)式(6)是二階微分方程，通過二階微分方程求解公式，求得搜索位置在t代的x(t)的位置路徑公式：xi(t)=C1cos(01+02t)+C2sin(01+02t)(7)由式(7)可知，xi(t)在一個(gè)固定區(qū)間內(nèi)波動(dòng)，即在該

7、區(qū)間中尋找每個(gè)粒子第t次迭代后的位置，位置函數(shù)xi(t)沒有振蕩收斂，算法容易陷入局部最優(yōu)。例如，令C1=1,C2=1,01+02=1，可得位置函數(shù)xi(t)=cos(t)+sin(t)的圖像，如圖1所示。在該圖像中，對于t巳-汽+兩,xi(t)始終在固定上下限卜2,2內(nèi)范圍波動(dòng)，沒有振蕩收斂，容易陷入局部最優(yōu)。因此，在算法中加入振蕩收斂，是跳出局部最優(yōu)解，提高粒子群算法搜索性能和精度較有效的方法。12010圖I標(biāo)準(zhǔn)粒子群算空儻謾孌化函數(shù)/(xj=5LU(X)+CO3(X)改進(jìn)標(biāo)準(zhǔn)粒子群算法的思想胡建秀，曾建潮通過在標(biāo)準(zhǔn)二階粒子群算法速度迭代方程中引入二階振蕩環(huán)節(jié)的方法改進(jìn)算法，來增加粒子的多

8、樣性，提高算法的全局搜索能力，是改進(jìn)位置函數(shù)搜索區(qū)域較好的改進(jìn)方法。使用二階振蕩環(huán)節(jié)后，算法前期具有較強(qiáng)的全局搜索能力，振蕩收斂；而在后期強(qiáng)局部搜索，漸近收斂。該粒子群算法的進(jìn)化方程如下：Vi(t+1)=wxVi(t)+01(pi-(1+=1)xi(t)+=1xi(t-1)+02(pg-(1+=2)xi(t)+=2xi(t-1)(8)xi(t+1)=xi(t)+vi(t+1)(9)算法振蕩收斂：G201-101,=2201-101,=2202-102(11)振蕩收斂和漸進(jìn)收斂示意圖如圖2和圖3所示。1y4-4ID03.1030田2撮蕩收斂示意圖f=exp(1/ICx工)x(sm)+j(x=ex

9、p(113x處一esp(-1/10 xx)改進(jìn)后二階振蕩粒子群算法的迭代公式Vi(t+1)=wxVi(t)+01(pi-(1+=1)xi(t)+=2xi(t-1)+02(pg-(1+=3)xi(t)+=4xi(t-1)(12)xi(t+1)=xi(t)+vi(t+1)這個(gè)公式的實(shí)在上面的二階振蕩粒子群算法的基礎(chǔ)上進(jìn)行的改進(jìn)，這里三雖然是隨機(jī)數(shù)但是取值是有限制的：設(shè)最大迭代次數(shù)為Gmax,0=21+=12,0=41+32,0=11,0=31當(dāng)tGmax/2時(shí)，=1=2-1,=3=4-1,0=21,0=4Gmax/2時(shí)這么做的意義在于可以時(shí)算法在迭代的前半段振蕩收斂；在迭代的后半段使其漸進(jìn)收斂。這

10、里的證明和上面的二階振蕩粒子群算法的類似，我這就不展開了，感興趣的可以自己去找我參考的文獻(xiàn)。PS:關(guān)于改進(jìn)算法的流程圖和標(biāo)準(zhǔn)算法的類似，無非就是加了一個(gè)迭代次數(shù)前一半和后一半?yún)?shù)的改變，這里就不加上去了。改進(jìn)二階振蕩粒子群算法代碼functionz,best=PSO_1(w,Gmax,lizishu,weidu,a,b)%這個(gè)測試函數(shù)的最小值是0,取值范圍是-10,10%z是最優(yōu)點(diǎn)的適應(yīng)值，best是記錄最優(yōu)位置的坐標(biāo)%lizishu輸入需要的粒子數(shù)%weidu函數(shù)的自變量個(gè)數(shù)%a下界%b界q=zeros(1,Gmax);ticp=inf*ones(1,lizishu);%初始的最優(yōu)解默認(rèn)為i

11、nf%pg=0;A=unifrnd(a,b,lizishu,weidu);%A矩陣是位置矩陣，用于儲(chǔ)存每一步計(jì)算出的位置B=unifrnd(a,b,lizishu,weidu);%B是速度矩陣，用于儲(chǔ)存每一布計(jì)算出的VC=A;%用于記錄每個(gè)粒子的最優(yōu)位置D=unifrnd(a,b,lizishu,weidu);%位置矩陣，用于記錄上一次迭代的位置c=2;%c通常取1.5,這是一個(gè)經(jīng)驗(yàn)值y=;%給丫申請空間fori=1:lizishuy=y,test(A(i,:);endfori=1:lizishuifp(i)y(i)C(i,:)=A(i,:);endp(i)=min(p(i),y(i);%更新局部最優(yōu)解end%初始化全局最優(yōu)解k=find(p=min(p);pg=C(k(1),:);q(i)=test(pg);fori=1:Gmaxir1=unifrnd(0,1);r2=unifrnd(0,1);u1=r1*c;u2=r2*c;ifi：=IV0：Ell0.063381稅f7=2、改進(jìn)的PSO算法:我們嘗試1000維:改進(jìn)的PSO算法結(jié)果如下:我也試過一些最小值是無窮的函數(shù)(XA3)，以及一些振蕩函數(shù)(sinx+cosx),都可以跑出結(jié)果，這里就不一個(gè)個(gè)的給出結(jié)果了。z=PSO110.6,100：,15,lOuO.-10.15)胴已過(LllZScl砂E桐已過0.4