粒子群算法基本原理

1、4.1粒子群算法基本原理粒子群算法基本原理粒子群優(yōu)化算法[45]最原始的工作可以追溯到1987年Reynolds對鳥群社會系統(tǒng)Boids（Reynolds對其仿真鳥群系統(tǒng)的命名）的仿真研究。通常，群體的行為可以由幾條簡單的規(guī)則進(jìn)行建模，雖然每個個體具有簡單的行為規(guī)則，但是卻群體的行為卻是非常的復(fù)雜，所以他們在鳥類仿真中，即Boids系統(tǒng)中采取了下面的三條簡單的規(guī)則：（1）飛離最近的個體(鳥)，避免與其發(fā)生碰撞沖突；（2）盡量使自己與周圍

2、的鳥保持速度一致；（3）盡量試圖向自己認(rèn)為的群體中心靠近。雖然只有三條規(guī)則，但Boids系統(tǒng)已經(jīng)表現(xiàn)出非常逼真的群體聚集行為。但Reynolds僅僅實現(xiàn)了該仿真，并無實用價值。1995年Kennedy[4648]和Eberhart在Reynolds等人的研究基礎(chǔ)上創(chuàng)造性地提出了粒子群優(yōu)化算法，應(yīng)用于連續(xù)空間的優(yōu)化計算中。Kennedy和Eberhart在boids中加入了一個特定點，定義為食物，每只鳥根據(jù)周圍鳥的覓食行為來搜尋食物。Ke

3、nnedy和Eberhart的初衷是希望模擬研究鳥群覓食行為，但試驗結(jié)果卻顯示這個仿真模型蘊(yùn)含著很強(qiáng)的優(yōu)化能力，尤其是在多維空間中的尋優(yōu)。最初仿真的時候，每只鳥在計算機(jī)屏幕上顯示為一個點，而“點”在數(shù)學(xué)領(lǐng)域具有多種意義，于是作者用“粒子（particle）”來稱呼每個個體，這樣就產(chǎn)生了基本的粒子群優(yōu)化算法[49]。假設(shè)在一個D維搜索空間中，有m個粒子組成一粒子群，其中第i個粒子的空間位置為，它是優(yōu)化問題的一個潛在123(...)12..

4、.iiiiiDXxxxxim??解，將它帶入優(yōu)化目標(biāo)函數(shù)可以計算出其相應(yīng)的適應(yīng)值，根據(jù)適應(yīng)值可衡量ix的優(yōu)劣；第i個粒子所經(jīng)歷的最好位置稱為其個體歷史最好位置，記為，相應(yīng)的適應(yīng)值為個體最好適應(yīng)值Fi；同123(...)12...iiiiiDPppppim??時，每個粒子還具有各自的飛行速度。所有粒123(...)12...iiiiiDVvvvvim??子經(jīng)歷過的位置中的最好位置稱為全局歷史最好位置，記為在其后的研究中引入了慣性權(quán)值來改善

5、PSO算法的局部搜索能力，形成了目前常用的基本PSO算法形式。取較大的ω值使得粒子能更好地保留速度，從而能更快地搜索解空間，提高算法的收斂速度；但同時由于速度大可能導(dǎo)致算法無法更好地進(jìn)行局部搜索，容易錯過最優(yōu)解，特別是過大的ω會使得PSO算法速度過大而無法搜索到全局最優(yōu)。取較小的ω值則有利于局部搜索，能夠更好地搜索到最優(yōu)值，但因為粒子速度受其影響相應(yīng)變小從而無法更快地進(jìn)行全局搜索，進(jìn)而影響算法收斂速度；同時過小ω值更是容易導(dǎo)致算法陷入局

6、部極值。因此，一個合適的ω值能有效兼顧搜索精度和搜索速度、全局搜索和局部搜索，保證算法性能。加速系數(shù)c1和c2代表每個粒子向其個體歷史最好位置和群體全局歷史最好位置的移動加速項的權(quán)值。較低的加速系數(shù)值可以使得粒子收斂到其最優(yōu)解的過程較慢，從而能夠更好搜索當(dāng)前位置與最優(yōu)解之間的解空間；但過低的加速系數(shù)值則可能導(dǎo)致粒子始終徘徊在最優(yōu)鄰域外而無法有效搜索目標(biāo)區(qū)域，從而導(dǎo)致算法性能下降。較高的加速系數(shù)值則可以使得粒子快速集中于目標(biāo)區(qū)域進(jìn)行搜索，

7、提高算法效率；但過高的加速系數(shù)值則有可能導(dǎo)致粒子搜索間隔過大，容易越過目標(biāo)區(qū)域無法有效地找到全局最優(yōu)解。因此加速系數(shù)對PSO能否收斂也起重要作用，合適的加速系數(shù)有利于算法較快地收斂，同時具有一定的跳出局部最優(yōu)的能力。對于速度更新公式(41)中，若c1=c2=0，粒子將一直以當(dāng)前的速度進(jìn)行慣性飛行，直到到達(dá)邊界。此時粒子僅僅依靠慣性移動，不能從自己的搜索經(jīng)驗和其他粒子的搜索經(jīng)驗中吸取有用的信息，因此無法利用群體智能，PSO算法沒有啟發(fā)性，

8、粒子只能搜索有限的區(qū)域，很難找到全局最優(yōu)解，算法優(yōu)化性能很差。若c=0，則粒子沒有認(rèn)知能力，不能從自己的飛行經(jīng)驗吸取有效信息，只有社會部分，所以c又稱為社會參數(shù)；此時收斂速度比基本PSO快，但由于不能有效利用自身的經(jīng)驗知識，所有的粒子都向當(dāng)前全局最優(yōu)集中，因此無法很好地對整個解空間進(jìn)行搜索，在求解存在多個局部最優(yōu)的復(fù)雜優(yōu)化問題時比基本PSO容易陷入局部極值，優(yōu)化性能也變差。若c2=0，則微粒之間沒有社會信息共享，不能從同伴的飛行經(jīng)驗中吸