參考維基
http://zh.wikipedia.org/wiki/%E7%B2%92%E5%AD%90%E7%BE%A4%E4%BC%98%E5%8C%96
粒子群優化(Particle Swarm Optimization, PSO),又稱微粒群演算法,是由J.Kennedy和R. C.Eberhart等於1995年開發的一種演化計算技術,來源於對一個簡化社會模型的模擬。其中「群(swarm)」來源於微粒群符合M. M.Millonas在開發應用於人工生命(artificial life)的模型時所提出的群體智能的5個基本原則。「粒子(particle)」是一個折衷的選擇,因為既需要將群體中的成員描述為沒有質量、沒有體積的,同時也需要描述它的速度和加速狀態。
PSO演算法最初是為了圖形化的模擬鳥群優美而不可預測的運動。而通過對動物社會行為的觀察,發現在群體中對信息的社會共享提供一個演化的優勢,並以此作為開發演算法的基礎。通過加入近鄰的速度匹配、並考慮了多維搜索和根據距離的加速,形成了PSO的最初版本。之後引入了慣性權重w來更好的控制開發(exploitation)和探索(exploration),形成了標準版本。
演算法原理PSO演算法是基於群體的,根據對環境的適應度將群體中的個體移動到好的區域。然而它不對個體使用演化算子,而是將每個個體看作是D維搜索空間中的一個沒有體積的微粒(點),在搜索空間中以一定的速度飛行,這個速度根據它本身的飛行經驗和同伴的飛行經驗來動態調整。第i個微粒表示為Xi = (xi1, xi2, …, xiD),它經歷過的最好位置(有最好的適應值)記為Pi = (pi1, pi2, …, piD),也稱為pbest。在群體所有微粒經歷過的最好位置的索引號用符號g表示,即Pg,也稱為gbest。微粒i的速度用Vi = (vi1, vi2, …, viD)表示。對每一代,它的第d維(1 ? d ? D)根據如下方程進行變化:
(1a)
(1b)
其中w為慣性權重(inertia weight),c1和c2為加速常數(acceleration constants),rand()和Rand()為兩個在[0,1]範圍里變化的隨機值。
此外,微粒的速度Vi被一個最大速度Vmax所限制。如果當前對微粒的加速導致它的在某維的速度vid超過該維的最大速度vmax,d,則該維的速度被限制為該維最大速度vmax,d。對公式(1a),第一部分為微粒先前行為的慣性,第二部分為「認知(cognition)」部分,表示微粒本身的思考;第三部分為「社會(social)」部分,表示微粒間的信息共享與相互合作。
「認知」部分可以由Thorndike的效應法則(law of effect)所解釋,即一個得到加強的隨機行為在將來更有可能出現。這裏的行為即「認知」,並假設獲得正確的知識是得到加強的,這樣的一個模型假定微粒被激勵著去減小誤差。
「社會」部分可以由Bandura的替代強化(vicarious reinforcement)所解釋。根據該理論的預期,當觀察者觀察到一個模型在加強某一行為時,將增加它實行該行為的幾率。即微粒本身的認知將被其它微粒所模仿。
PSO演算法使用如下心理學假設:在尋求一致的認知過程中,個體往往記住自身的信念,並同時考慮同事們的信念。當其察覺同事的信念較好的時候,將進行適應性地調整。
標準PSO的演算法流程如下:
a). 初始化一群微粒(群體規模為m),包括隨機的位置和速度;
b). 評價每個微粒的適應度;
c). 對每個微粒,將它的適應值和它經歷過的最好位置pbest的作比較,如果較好,則將其作為當前的最好位置pbest;
d). 對每個微粒,將它的適應值和全局所經歷最好位置gbest的作比較,如果較好,則重新設置gbest的索引號;
e). 根據方程(1)變化微粒的速度和位置;
f). 如未達到結束條件(通常為足夠好的適應值或達到一個預設最大代數Gmax),回到b)。
演算法參數PSO參數包括:群體規模m,慣性權重w,加速常數c1和c2,最大速度Vmax,最大代數Gmax。
Vmax決定在當前位置與最好位置之間的區域的解析度(或精度)。如果Vmax太高,微粒可能會飛過好解,如果Vmax太小,微粒不能進行足夠的探索,導致陷入局部優值。該限制有三個目的:防止計算溢出;實現人工學習和態度轉變;決定問題空間搜索的粒度。慣性權重w使微粒保持運動的慣性,使其有擴展搜索空間的趨勢,有能力探索新的區域。
加速常數c1和c2代表將每個微粒推向pbest和gbest位置的統計加速項的權重。低的值允許微粒在被拉回來之前可以在目標區域外徘徊,而高的值導致微粒突然的沖向或者越過目標區域。如果沒有後兩部分,即c1 = c2 = 0,微粒將一直以當前的速度飛行,直到到達邊界。由於它只能搜索有限的區域,將很難找到好的解。如果沒有第一部分,即w =0,則速度只取決於微粒當前的位置和它們歷史最好位置pbest和gbest,速度本身沒有記憶性。假設一個微粒位於全局最好位置,它將保持靜止。而其它微粒則飛向它本身最好位置pbest和全局最好位置gbest的加權中心。在這種條件下,微粒群將統計的收縮到當前的全局最好位置,更象一個局部演算法。
在加上第一部分後,微粒有擴展搜索空間的趨勢,即第一部分有全局搜索的能力。這也使得w的作用為針對不同的搜索問題,調整演算法全局和局部搜索能力的平衡。如果沒有第二部分,即c1 = 0,則微粒沒有認知能力,也就是「只有社會(social-only)」的模型。在微粒的相互作用下,有能力到達新的搜索空間。它的收斂速度比標準版本更快,但是對複雜問題,比標準版本更容易陷入局部優值點。
如果沒有第三部分,即c2 = 0,則微粒之間沒有社會信息共享,也就是「只有認知(cognition-only)」的模型。因為個體間沒有交互,一個規模為m的群體等價于m個單個微粒的運行。因而得到解的幾率非常小。
=======================================================================================
一些原始碼, 來自 http://www.adaptivebox.net/CILib/code/psocodes_link.html
相關網站:
http://www.swarmintelligence.org/index.php
有趣的應用在robots, 下方有一些影片:
http://tecfa.unige.ch/perso/yvan/ModularWalkers/index.html
MATLAB 的 PSO 工具箱:
http://www.mathworks.com/matlabcentral/fileexchange/7506
- Dec 12 Sun 2010 07:17
Particle swarm optimization - 粒子群優化
close
全站熱搜
留言列表