1. 粒子群算法思想起源
粒子群優化算法 ( P a r t i c l e S w a r m o p t i m i z a t i o n , P S O ) (Particle Swarm optimization,PSO) (ParticleSwarmoptimization,PSO)又稱為粒子群算法。它是通過模拟鳥群覓食行為而發展起來的一種基于群體協作的随機搜尋算法。
1987年，生物學家Craig Reynolds提出了一個非常有影響的鳥群聚集模型，在他的仿真中，每一個個體都遵循：
- 避免與鄰域個體相沖撞；
- 比對鄰域個體的速度；
- 飛向鳥群中心，且整個群體飛向目标。
- 仿真中僅利用上面三條簡單的規則，就可以非常接近地模拟出鳥群飛行的現象。
1990年，生物學家Frank Heppner也提出了鳥類模型，它的不同之處在于：
- 鳥類被吸引飛到栖息地。
- 在仿真中，一開始每一隻鳥都沒有特定的飛行目标，隻是使用簡單的規則确定自己的飛行方向和飛行速度，
- 當有一隻鳥飛到栖息地時，它周圍的鳥也會跟着飛向栖息地，最終整個鳥群都會落在栖息地。
1995 年，美國社會心理學家 James Kennedy 和電氣工程師Russell Eberhart 共 同 提 出 了 粒 子 群 算 法 （ Particle Swarm Optimization，PSO），該算法的提出是受對鳥類群體行為進行模組化與仿真的研究結果的啟發。
- 他們的模型和仿真算法主要對Frank Heppner的模型進行了修正，以使粒子飛向解空間并在最優解處降落。
- 粒子群算法一經提出，由于其算法簡單，容易實作，立刻引起了進化計算領域學者們的廣泛關注
2. 算法原理
2.１ 算法政策
粒子群優化算法源自對鳥群捕食行為的研究：
- 一群鳥在區域中随機搜尋食物，所有鳥知道自己目前位置離食物多遠，
- 那麼搜尋的最簡單有效的政策就是搜尋目前離食物最近的鳥的周圍區域。
- 粒子群算法利用這種模型得到啟示并應用于解決優化問題。
2.2 算法模組化
- 粒子群算法首先在給定的解空間中随機初始化粒子群，待優化問題的變量數決定了解空間的維數。
- 每個粒子有了初始位置與初始速度，然後通過疊代尋優。
- 在每一次疊代中，每個粒子通過跟蹤 兩個“極值” 來更新自己在解空間中的空間位置與飛行速度：
- 一個極值： 就是單個粒子本身在疊代過程中找到的最優解粒子，這個粒子叫作個體極值；
- 另一個極值： 是種群所有粒子在疊代過程中所找到的最優解粒子，這個粒子是全局極值。
2.3 模組化
假設在一個 D D D維的目标搜尋空間中，有 N N N 個粒子組成一個群落，其中第 i i i 個粒子表示為一個 D D D 維的向量：
第 i i i 個粒子的 “飛行”速度 也是一個 D D D 維的向量，記為
第 i i i 個粒子迄今為止搜尋到的最優位置稱為個體極值，記為
整個粒子群迄今為止搜尋到的最優位置為全局極值，記為
在找到這兩個最優值時，粒子根據如下的式 （ 6.5 ） （6.5） （6.5）和式 （ 6.6 ） （6.6） （6.6）來更新自己的速度和位置：
- 其中： c 1 c_1 c1和 c 2 c_2 c2 為學習因子，也稱加速常數； r 1 r_1 r1和 r 2 r_2 r2 為 [ 0 ， 1 ] [0，1] [0，1]範圍内的均勻随機數， i = 1 , 2 , … , D i =1,2,…,D i=1,2,…,D；
- v i j v_{ij} vij 是粒子的速度 ， v i j ∈ [ − v m a x ， v m a x ] v_{ij} ∈[-v_{max}， v_{max}] vij∈[−vmax，vmax]， max 是常數，由使用者設定來限制粒子的速度。
式（6.5）右邊由三部分組成：
- 第一部分為“慣性”或“動量”部分，反映了粒子的運動“習慣”，代表粒子有維持自己先前速度的趨勢；
- 第二部分為“認知”部分，反映了粒子對自身曆史經驗的記憶或回憶，代表粒子有向自身曆史最佳位置逼近的趨勢；
- 第三部分為“社會”部分，反映了粒子間協同合作與知識共享的群體曆史經驗，代表粒子有向群體或鄰域曆史最佳位置逼近的趨勢。
3.标準粒子群算法流程
引入研究粒子群算法經常用到标的準兩粒個子群概算念法：
- 一是“探索”，指粒子在一定程度上離開原先的搜尋軌迹，向新的方向進行搜尋，展現了一種向未知區域開拓的能力，類似于全局搜尋；
- 二是“開發”，指粒子在一定程度上繼續在原先的搜尋軌迹上進行更細一步的搜尋，主要指對探索過程中所搜尋到的區域進行更進一步的搜尋。
- 探索能力是一個算法的全局搜尋能力。開發是利用一個好的解，繼續原來的尋優軌迹去搜尋更好的解，它是算法的局部搜尋能力。
3.1 标準粒子群算法
如何确定局部搜尋能力和全局搜尋能力的比例，對一個問題的求解過程很重要。1998年，Shi Yuhui等人提出了帶有慣性權重的改進粒子群算法，由于該算法能夠保證較好的收斂效果，是以被預設為标準粒子群算法
可以看出，式 （ 6.7 ） （6.7） （6.7）中慣性權重 w w w 表示在多大程度上保留原來的速度：
- w w w較大，則全局收斂能力較強，局部收斂能力較弱；
- w w w較小，則局部收斂能力較強，全局收斂能力較弱。
實驗結果表明：
- 在0.8～1.2之間時，粒子群算法有更快的收斂速度；
- 而當 1.2時,算法容易陷入局部極值。
3.1.1 動态慣性權重值
另外，在搜尋過程中可以對 w w w 進行動态調整：
- 在算法開始時，可給 w w w 賦予較大正值，随着搜尋的進行 ，可以線性地使 w w w 逐漸減小。
- 這樣可以保證算法開始時，各粒子能以較大的速度步長在全局範圍内探測較好的區域；
- 而在搜尋後期，較小的 w w w 值則保證粒子能夠在極值點周圍做精細的搜尋，
- 進而使算法有較大的機率向全局最優解位置收斂。
對 w w w 進行調整，可以權衡全局搜尋和局部搜尋能力。目前，采用較多的動态慣性權重值是Shi提出的線性遞減權值政策，其表達式如下：
式中：
- T m a x T_{max} Tmax表示最大進化代數；
- w m i n w_{min} wmin表示最小慣性權重；
- w m a x w_{max} wmax 表示最大慣性權重；
- t t t 表示目前疊代次數。
- 在大多數的應用中， w m a x = 0.9 ， w m a x = 0.4 w_{max}=0.9， w_{max}=0.4 wmax=0.9，wmax=0.4。
3.2 算法流程
4. 粒子群算法特點
實踐證明，它适合在動态、多目标優化環境中尋優，與傳統優化算法相比，具有較快的計算速度和更好的全局搜尋能力。
- 由于參數少而容易實作，對非線性、多峰問題均具有較強的全局搜尋能力
- 粒子群算法特有的記憶使其可以動态地跟蹤目前搜尋情況并調整其搜尋政策。
- 另外，粒子群算法對種群的大小不敏感，即使種群數目下降時，性能下降也不是很大。
- 該算法能以較大機率收斂于全局最優解。
參考
《智能優化算法及其Mtalab執行個體 第二版》