粒子群算法基本原理

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

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

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

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

5、PSO算法的局部搜索能力，形成了目前常用的基本PSO算法形式。取較大的ω值使得粒子能更好地保留速度，從而能更快地搜索解空間，提高算法的收斂速度；但同時(shí)由于速度大可能導(dǎo)致算法無(wú)法更好地進(jìn)行局部搜索，容易錯(cuò)過(guò)最優(yōu)解，特別是過(guò)大的ω會(huì)使得PSO算法速度過(guò)大而無(wú)法搜索到全局最優(yōu)。取較小的ω值則有利于局部搜索，能夠更好地搜索到最優(yōu)值，但因?yàn)榱Ｗ铀俣仁芷溆绊懴鄳?yīng)變小從而無(wú)法更快地進(jìn)行全局搜索，進(jìn)而影響算法收斂速度；同時(shí)過(guò)小ω值更是容易導(dǎo)致算法陷入局

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

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

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