2012年2月26日 星期日

粒子群最佳化(Particle Swarm optimization,PSO)

原始概念:


PSO的起源是來自於鳥類群體捕食的行為研究對於一個最佳化問題的研究,像是一隻在空間中飛行的鳥一樣,稱作「粒子(Particle)」,在空間中移動的所有粒子都有一個由目標函數所映射的適應值。另外,每個粒子本身都會有一個向量跟速度,利用核心運用模式產生一個速度來決定他們移動的方向與距離,一群粒子靠著個體本身的成功經驗與目前族群中最佳粒子的位置求得最佳解。PSO中的每個粒子獨立搜尋,當粒子個體遇到目標函數最佳值時,其最佳搜尋變數將被記錄在個體記憶中,亦即每個粒子都擁有本身最佳(pbest)的搜尋變數記憶,依照此個體最佳搜尋變數記憶去修正下一次的搜尋方向。每次搜尋均以這些個體最佳適應值與群體中最佳適應值的最佳化程度做比較,修正群體最佳函數值的變數記憶,同時每個粒子也依照群體最佳變數(gbest)記憶來修正下一次粒子的搜尋速度,經過如此疊代計算後,PSO根據粒子群中最佳適應值計算出問題的最佳解。 




核心運作模式:



此部分則為大家說明有關PSO的執行步驟以及內部的核心運作模式:
1.初始化:將每個粒子的各個維度進行位置(positon)的初始化,最基本的就是以隨機(random)的方式初始。
2.計算適應值:利用目標函數計算每個粒子的適應値
3.將粒子的適應值和pbest值作比較,假如優於pbest值,則更新pbest值及其位置
4.將粒子的適應值和gbest值作比較,如果優於gbest值,則更新gbest值及其位置
5.可依照以下兩個公式來更新粒子各個維度的速度(1)跟位置的移動(2)。








w:慣性權重 [0,1]
C1, C2:學習因子
Rand():為[0,1]的亂數
i:第i個粒子
d:第d個維度
V:向量
X:位置
Pid:本身粒子最佳的位置
Pgd:群體最佳粒子的位置


6.是否達到停止準則條件,若是,則印出最佳適應值及粒子位置,否則,跳至第二步驟。


重點整理:



粒子群最佳化(Particle Swarm optimization,PSO),他的概念來自於模擬社會的行為,是屬於群體智慧的其中一種,

群體智慧包括:螞蟻演算法、蜜蜂演算法、粒子群最佳化…等多種演算法。



PSO本身還具有方向性和記憶性,利用粒子群具有探測與開發的特色,在問題空間中搜尋全域的最佳解。


每一個粒子都代表在最佳化問題中的解,各自負責區域中的最佳搜尋,再藉由族群間的記憶分享, 粒子將受到群體間的約束,最後完成最佳化問題的搜尋。