粒子群最佳化

粒子群最佳化Particle Swarm Optimization, PSO),又稱粒子群演算法微粒群演算法,是由 J. Kennedy 和 R. C. Eberhart 等[1]於1995年開發的一種演化計算技術,來源於對一個簡化社會模型的類比。其中「群(swarm)」來源於微粒群符合 M. M. Millonas 在開發應用於人工生命(artificial life)的模型時所提出的群體智慧型的5個基本原則。「粒子(particle)」是一個折衷的選擇,因為既需要將群體中的成員描述為沒有品質、沒有體積的,同時也需要描述它的速度和加速狀態。

PSO 演算法最初是為了圖形化地類比鳥群優美而不可預測的運動。而通過對動物社會行為的觀察,發現在群體中對資訊的社會共享提供一個演化的優勢,並以此作為開發演算法的基礎[1]。通過加入近鄰的速度匹配、並考慮了多維搜尋和根據距離的加速,形成了 PSO 的最初版本。之後引入了慣性權重w來更好的控制開發(exploitation)和探索(exploration),形成了標準版本。為了提高粒群演算法的效能和實用性,中山大學、(英國)格拉斯哥大學等又開發了自適應(Adaptive PSO)版本[2]和離散(discrete)版本[3]

PSO 演算法屬於一種萬能啟發式演算法,能夠在沒有得知太多問題資訊的情況下,有效的搜尋具有龐大解空間的問題並找到候選解,但同時不保證其找到的最佳解為真實的最佳解。

演算法原理

PSO 演算法是基於群體的,根據對環境的適應度將群體中的個體移動到好的區域。然而它不對個體使用演化算子,而是將每個個體看作是 D 維搜尋空間中的一個沒有體積的微粒(點),在搜尋空間中以一定的速度飛行,這個速度根據它本身的飛行經驗和同伴的飛行經驗來動態調整。第 i 個微粒表示為 Xi =(xi1, xi2, …, xiD) ,它經歷過的最好位置(有最好的適應值)記為 Pi = (pi1, pi2, …, piD),也稱為 pbest。在群體所有微粒經歷過的最好位置的索引號用符號 g 表示,即 Pg,也稱為 gbest 。微粒 i 的速度用 Vi = (vi1, vi2, …, viD) 表示。對每一代,它的第 d+1 維(1 ≤ d+1 ≤ D)根據如下方程式進行變化:

       vid+1 = w∙vid+c1∙rand()∙(pid-xid)+c2∙Rand()∙(pgd-xid)        (1a)
       xid+1 = xid+vid+1				              (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)。

演算法參數

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 的發展和應用[4],但此類分析具有很大的局限性[5]。為 PSO 加入正交學習後,演算法的全域收斂、收斂精度及穩健可靠性都得到了提高[6]

外部連結

參考文獻

  1. ^ 1.0 1.1 Kennedy, J.; Eberhart, R. Particle swarm optimization. Neural Networks, 1995. Proceedings., IEEE International Conference on (IEEE). 1995, 4: 1942–1948. ISBN 0-7803-2768-3. doi:10.1109/ICNN.1995.488968. 
  2. ^ 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 [2014-02-02]. doi:10.1109/TSMCB.2009.2015956. (原始內容存檔 (PDF)於2017-05-17). 
  3. ^ Shen, Meie, Zhan, Zhi-Hui, Chen, Wei-Neng, Gong, Yue-Jiao, Zhang, Jun, and Li, Yun. Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks (PDF). IEEE Transactions on Industrial Electronics. 2014, (March): 1362–1381. doi:10.1109/TIE.2014.2314075. (原始內容 (PDF)存檔於2014-10-08). 
  4. ^ Clerc, M.; Kennedy, J. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation. 2002, 6 (1): 58–73. doi:10.1109/4235.985692. 
  5. ^ Pedersen, M.E.H.; Chipperfield, A.J. Simplifying particle swarm optimization (PDF). Applied Soft Computing. 2010, 10 (2): 618–628 [2014-02-02]. doi:10.1016/j.asoc.2009.08.029. (原始內容 (PDF)存檔於2014-01-24). 
  6. ^ Zhan, Z-H.; Zhang, J.; Li, Y; Shi, Y-H. Orthogonal Learning Particle Swarm Optimization (PDF). IEEE Transactions on Evolutionary Computation. 2011, 15 (6): 832–847 [2014-02-02]. doi:10.1109/TEVC.2010.2052054. (原始內容存檔 (PDF)於2020-08-06).