複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/粒子羣優化/1352052
複製
複製成功

粒子羣優化

鎖定
粒子羣優化（Particle Swarm Optimization, PSO），又稱微粒羣算法，是由J. Kennedy和R. C. Eberhart等於1995年開發的一種演化計算技術，來源於對一個簡化社會模型的模擬。其中“羣（swarm）”來源於微粒羣匹配M. M. Millonas在開發應用於人工生命（artificial life）的模型時所提出的羣體智能的5個基本原則。“粒子（particle）”是一個折衷的選擇，因為既需要將羣體中的成員描述為沒有質量、沒有體積的，同時也需要描述它的速度和加速狀態。
中文名
粒子羣優化
外文名
Particle Swarm Optimization
作    者
J. Kennedy和R. C. Eberhart

目錄

  1. 1 算法簡介
  2. 2 算法原理
  3. 3 算法參數
  4. 4 收斂性

粒子羣優化算法簡介

粒子羣優化（Particle Swarm Optimization,PSO），又稱微粒羣算法，是由J. Kennedy和R. C. Eberhart等於1995年開發的一種演化計算技術，來源於對一個簡化社會模型的模擬。其中“羣（swarm）”來源於微粒羣匹配M. M. Millonas在開發應用於人工生命（artificial life）的模型時所提出的羣體智能的5個基本原則。“粒子（particle）”是一個折衷的選擇，因為既需要將羣體中的成員描述為沒有質量、沒有體積的，同時也需要描述它的速度和加速狀態。
PSO算法最初是為了圖形化的模擬鳥羣優美而不可預測的運動。而通過對動物社會行為的觀察，發現在羣體中對信息的社會共享提供一個演化的優勢，並以此作為開發算法的基礎。通過加入近鄰的速度匹配、並考慮了多維搜索和根據距離的加速，形成了PSO的最初版本。之後引入了慣性權重w來更好的控制開發（exploitation）和探索（exploration），形成了標準版本。為了提高粒羣算法的性能和實用性，中山大學、（英國）格拉斯哥大學等又開發了自適應（Adaptive PSO）版本和離散（discrete）版本 [1] 

粒子羣優化算法原理

PSO算法是基於羣體的，根據對環境的適應度將羣體中的個體移動到好的區域。然而它不對個體使用演化算子，而是將每個個體看作是D維搜索空間中的一個沒有體積的微粒（點），在搜索空間中以一定的速度飛行，這個速度根據它本身的飛行經驗和同伴的飛行經驗來動態調整。第i個微粒表示為Xi= （xi1, xi2, …, xiD），它經歷過的最好位置（有最好的適應值）記為Pi= （pi1, pi2, …, piD），也稱為pbest。在羣體所有微粒經歷過的最好位置的索引號用符號g表示，即Pg，也稱為gbest。微粒i的速度用Vi= （vi1, vi2, …, viD）表示。對每一代，它的第d維（1 ≤ d ≤ D）根據如下方程進行變化：
vid = w∙vid+c1∙rand（）∙（pid-xid）+c2∙Rand（）∙（pgd-xid）  （1a）      
xid = xid+vid                            （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的算法流程如下：
  1. 初始化一羣微粒（羣體規模為m），包括隨機的位置和速度；
  2. 評價每個微粒的適應度；
  3. 對每個微粒，將它的適應值和它經歷過的最好位置pbest的作比較，如果較好，則將其作為當前的最好位置pbest；
  4. 對每個微粒，將它的適應值和全局所經歷最好位置gbest的作比較，如果較好，則重新設置gbest的索引號；
  5. 根據方程（1）變化微粒的速度和位置；
  6. 如未達到結束條件（通常為足夠好的適應值或達到一個預設最大代數Gmax），回到2）。 [1] 

粒子羣優化算法參數

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個單個微粒的運行。因而得到解的幾率非常小。

粒子羣優化收斂性

收斂性的數學證明幫助了PSO的發展和應用, 但此內分析具有很大的侷限性.為PSO加入正交學習後，算法的全局收斂、收斂精度及魯棒可靠性都得到了提高。 [1] 
參考資料
  • 1.    Zhan, Z-H.; Zhang, J.; Li, Y; Chung, H.S-H. Adaptive Particle Swarm Optimization (PDF). IEEE Transactions on Systems, Man, and Cybernetics. 2009, 39 (6): 1362–1381. doi:10.1109/TSMCB.2009.2015956.