張浩然
責任編輯：蘇向陽
文章發表于微信公衆号【運籌OR帷幄】：優化 | 粒子群算法介紹
編者按：
粒子群算法是計算數學中用于解決最優化的搜尋算法，也是最為經典的智能算法之一。應用主要是在工程和計算機科學還有行為管理研究科學裡面。通過閱讀這篇文章，你将了解粒子群算法的概念，優缺點以及發展方向。
1、簡介
粒子群算法(Particle Swarm Optimization,簡稱PSO)是1995年Eberhart博士和Kennedy博士一起提出的[1]。粒子群算法是通過模拟鳥群捕食行為設計的一種群智能算法。區域内有大大小小不同的食物源，鳥群的任務是找到最大的食物源(全局最優解)，鳥群的任務是找到這個食物源。鳥群在整個搜尋的過程中，通過互相傳遞各自位置的資訊，讓其他的鳥知道食物源的位置最終，整個鳥群都能聚集在食物源周圍，即我們所說的找到了最優解，問題收斂。學者受自然界的啟發開發了諸多類似智能算法，如蟻群算法[2]、布谷鳥搜尋算法[3]、魚群算法[4]、捕獵算法等等[5]。有興趣的讀者可以深入了解一下。
2、算法政策
粒子群算法的目标是使所有粒子在多元超體(multi-dimensional hyper-volume)中找到最優解。首先給空間中的所有粒子配置設定初始随機位置和初始随機速度。然後根據每個粒子的速度、問題空間中已知的最優全局位置和粒子已知的最優位置依次推進每個粒子的位置。随着計算的推移，通過探索和利用搜尋空間中已知的有利位置，粒子圍繞一個或多個最優點聚集或聚合。該算法設計玄妙之處在于它保留了最優全局位置和粒子已知的最優位置兩個資訊。後續的實驗發現，保留這兩個資訊對于較快收斂速度以及避免過早陷入局部最優解都具有較好的效果。這也奠定了後續粒子群算法改進方向的基礎。
3、算法步驟
基礎粒子群算法步驟較為簡單。粒子群優化算法是由一組粒子在搜尋空間中運動，受其自身的最佳過去位置pbest和整個群或近鄰的最佳過去位置gbest的影響。每次疊代粒子i的第d維速度更新公式為:
粒子i的第d維位置更新公式為：
其中
-第k次疊代粒子i飛行速度矢量的第d維分量
-第k次疊代粒子i位置矢量的第d維分量
c1,c2-加速常數，調節學習最大步長
r1,r2-兩個随機函數，取值範圍[0,1],以增加搜尋随機性
w-慣性權重，非負數，調節對解空間的搜尋範圍
粒子群算法流程圖如下：
通過速度更新公式我們可以看出，若需要算法快速收斂，我們需要将加速度常數調大。但是這麼做可能會導緻算法出現“早熟”。若把慣性權重調大，可增加粒子探測新位置的“積極性”，避免過早陷入局部最優，但也會降低算法的收斂速度。對于有些改進算法，在速度更新公式最後一項會加入一個随機項，來平衡收斂速度與避免“早熟”。并且根據位置更新公式的特點，粒子群算法更适合求解連續優化問題。
4、執行個體計算
這裡，我們選用一個非常經典的測試函數Rastrigin方程作為執行個體計算，來觀察粒子群算法的收斂過程。Rastrigin方程的表達式為：
A=10,xiϵ[−5.12,5.12]。當x為0時，方程值達到最小f(x)=0。
在二維變量下，這個方程是長這個樣子的：
我們可以看到，方程具有很強的非凸性(密集恐懼症)。當維數增加時，随機搜尋算法很容易陷入某個局部最優解中。我們利用粒子群算法求解了該測試函數。收斂過程如下圖所示(為了更好地表現收斂，我們特意加大了随機項系數，使得收斂過程緩慢一些)：
疊代次數1, 5, 10, 20, 50, 和100
這些粒子(藍點)很快就找到了全局最優解的位置(圖中心)。由于有随機項的存在，有些粒子即使在收斂後也不斷跳出(不用太在意這些細節)。當然如果讀者想避免這種情況，可以将随機項系數設為動态值，即随着疊代次數增加，該值越小。經驗表明當随機項系數随疊代次數成指數速度減小時，可增加搜尋全局最優解的機率，并提高計算速度。
5、評價标準
目前評價(改進)粒子群算法的标準已經非常成熟。業内大牛已經整理出了許多不同次元的标準測試函數。需要從準确率(與最優解的偏差)，成功率(計算到最優解的機率)，計算速度以及穩定性(均值，中位數，方差)等方面對算法進行考量。IEEE演化計算大會更是提出了一個完整的benchmark庫和評價計算方法(http://www.ntu.edu.sg/home/epnsugan/index_files/cec-benchmarking.htm)。同時每年也會組織演化計算競賽。有興趣的讀者可以查找一些近些年獲獎的論文深入研究一下。
6、改進方向
粒子群算法雖然自提出以來就吸引了大量學者的目光，但粒子群算法也存在諸多弊端，如局部搜尋能力差，容易陷入局部極值，搜尋精度低等。針對這些問題，粒子群算法有如下三類的改進方向：
第一類改進方法為改變粒子關系的拓撲結構。我們之前說粒子群設計玄妙之處在于它保留了全局最優位置和粒子已知的最優位置兩個資訊。然而曆史最優位置(為友善我們稱為位置A)和粒子已知的全局最優位置(為友善我們稱為位置B)我們可以稍加改動。最經典的改進為master-slave算法。首先，我們可以将問題分解為諸多的master粒子和slave粒子，根據适應值的不同挑選master粒子。每個master粒子下有不同數量的slave粒子，master粒子1所在區域的位置A1為master和slave所有粒子的曆史最優位置。同理，我們可以得到對應的A2和A3等粒子的最優位置，對比不同最優位置的數值，得出全局最優位置B。這種算法的好處是，如果master粒子1所屬粒子陷入局部最優或者無法找尋到最優解的情況，master粒子2、master粒子3及其它master粒子所在區域仍繼續搜尋，一定程度上保證了解的最優性。
master社群粒子的位置A為master社群和slave社群所有粒子的最優過去位置。而slave社群粒子的位置A僅僅為該slave社群所有粒子的最優過去位置。這樣，當劃分出多個slave社群時，即使有一個slave社群粒子收斂陷入局部最優，仍能保證master社群粒子有較大的機率跳出這個局部最優位置。
第二類改進方法為引入新的機制。通過引入新的控制粒子的機制來加快收斂速度，并且避免陷入局部最優。這類改進方法的一個例子為捕獵算法。在粒子群算法計算中，當出現收斂趨勢時，将會有大量的低速度粒子聚集。這些低速的聚集粒子并不會加速算法收斂也不會探測新的位置增加跳出局部最優的機率。是以我們稱這些粒子為“懶惰粒子”。在疊代過程中，這些“懶惰粒子”仍會占用計算量。于是，如果能加入一種删除機制，删除這些“懶惰粒子”并生成出一些活躍的粒子，那麼就可以在加快計算速度的同時減少收斂陷入局部最優的機率。這裡引入了老鷹捕食兔子的機制，删除老弱病殘的“懶惰”兔子，并增加新的“活躍”兔子。
第三類改進方法為耦合其他算法。由于不同的算法有不同的優點，如何将不同算法耦合以克服算法自身缺陷一直是研究的熱點。目前進行耦合計算的熱點算法有模拟退火，蟻群算法，遺傳算法等等。
結語
粒子群算法是一個簡潔且強大的優化算法。它可以嵌套非凸模型、邏輯模型、複雜模拟模型、黑箱模型、甚至實際實驗來進行優化計算，是一個讓人欲罷不能的算法。雖然粒子群算法在諸多領域均有不錯表現，如電力系統，生物資訊，物流規劃等，但對于一些特定問題的求解，粒子群并不能保證解的品質。是以，粒子群算法的發展仍在繼續，其研究仍有許多未知領域，如粒子群理論的數學驗證等等。期待着各位讀者大佬為粒子群算法的發展增磚加瓦。
參考文獻：
[1] A new optimizer using particle swarm theory, in: MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Ieee, 1995, pp. 39-43.
[2] Ant colony optimization: a new meta-heuristic, in: Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406), IEEE, 1999, pp. 1470-1477.
[3] Cuckoo search via Lévy flights, in: 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), IEEE, 2009, pp. 210-214.
[4] An optimizing method based on autonomous animats: fish-swarm algorithm, Systems Engineering-Theory & Practice, 22 (2002) 32-38.
[5] A novel particle swarm optimization based on prey–predator relationship, Applied Soft Computing, 68 (2018) 202-218.
相關文章推薦
我們還有其他演化計算介紹文章。歡迎大家閱讀。
點選藍字标題，即可閱讀《【優化】遺傳算法介紹》。
其他
【優化】優化理論科普叢書專題征稿之群體智能算法理論
溫馨提示
可以在 本公衆号背景 回複關鍵詞：“ 捕獵算法源代碼 ”獲得捕獵算法中文注解matlab源代碼，如果覺得有用， 請勿吝啬你的留言和贊哦！~