【智能優化算法】粒子群優化算法（PSO）【附python實現代碼】

寫在前面：
首先感謝兄弟們的訂閱，讓我有創作的動力，在創作過程我會盡最大能力，保證作品的質量，如果有問題，可以私信我，讓我們攜手共進，共創輝煌。

路雖遠，行則將至；事雖難，做則必成。只要有愚公移山的志氣、滴水穿石的毅力，腳踏實地，埋頭苦干，積跬步以至千里，就一定能夠把宏偉目標變為美好現實。

歷史文章回顧：
灰狼優化算法：【智能優化算法】灰狼優化算法【附python實現代碼】
白鯨優化算法：【智能優化算法】白鯨優化算法【附python實現代碼】
【智能優化算法】粒子群優化KNN分類算法【附python實現代碼】
【智能優化算法】粒子群優化隨機森林分類算法【附python實現代碼】
【智能優化算法】粒子群優化LightGBM分類算法【附python實現代碼】
【模型參數優化】隨機搜索對隨機森林分類模型進行參數尋優【附python實現代碼】
【模型參數優化】網格搜索對隨機森林分類模型進行參數尋優【附python實現代碼】
【模型參數優化】網格搜索對KNN分類模型進行參數尋優【附python實現代碼】
【模型參數優化】網格搜索對XGBoost分類模型進行參數尋優【附python實現代碼】
【模型參數優化】網格搜索對GBDT分類模型進行參數尋優【附python實現代碼】
【模型參數優化】網格搜索對SVM分類模型進行參數尋優【附python實現代碼】
【模型參數優化】隨機搜索對SVM分類模型進行參數尋優【附python實現代碼】

1、介紹

1.1、PSO算法起源

1995年，受到鳥群覓食行為的規律性啟發，James Kennedy和Russell Eberhart建立了一個簡化算法模型，經過多年改進最終形成了粒子群優化算法(Particle Swarm Optimization, PSO) ，也可稱為粒子群算法。

1.2、PSO算法特點

粒子群算法具有收斂速度快、參數少、算法簡單易實現的優點（對高維度優化問題，比遺傳算法更快收斂于最優解），但是也存在陷入局部最優解的問題，因此依賴于良好的初始化。

1.3、PSO算法基本思想

粒子群算法的思想源于對鳥群覓食行為的研究，鳥群通過集體的信息共享使群體找到最優的目的地。如下圖，設想這樣一個場景：鳥群在森林中隨機搜索食物，它們想要找到食物量最多的位置。但是所有的鳥都不知道食物具體在哪個位置，只能感受到食物大概在哪個方向。每只鳥沿著自己判定的方向進行搜索，并在搜索的過程中記錄自己曾經找到過食物且量最多的位置，同時所有的鳥都共享自己每一次發現食物的位置以及食物的量，這樣鳥群就知道當前在哪個位置食物的量最多。在搜索的過程中每只鳥都會根據自己記憶中食物量最多的位置和當前鳥群記錄的食物量最多的位置調整自己接下來搜索的方向。鳥群經過一段時間的搜索后就可以找到森林中哪個位置的食物量最多（全局最優解）。

在這里插入圖片描述

2、算法基本原理

2.1 對應關系

將鳥群覓食行為和算法原理對應，如下表所示：

鳥群覓食	粒子群算法
鳥	粒子
森林	求解空間
食物的量	目標函數值（適應值）
每只鳥所處的位置	空間中的一個解（粒子位置）
食物量最多的位置	全局最優解

2.2 基礎知識

PSO的基礎：信息的社會共享
粒子的兩個屬性：速度和位置（算法的兩個核心要素）
速度表示粒子下一步迭代時移動的方向和距離，位置是所求解問題的一個解。
算法的6個重要參數
粒子群算法的流程圖
粒子群算法的偽代碼

3、速度更新公式

表述上叫速度，實際上就是粒子下一步迭代移動的距離和方向，也就是一個位置向量。
在這里插入圖片描述

3.1、速度更新公式的解釋

第1項：慣性部分
由慣性權重和粒子自身速度構成，表示粒子對先前自身運動狀態的信任。
第2項：認知部分
表示粒子本身的思考，即粒子自己經驗的部分，可理解為粒子當前位置與自身歷史最優位置之間的距離和方向。
第3項：社會部分
表示粒子之間的信息共享與合作，即來源于群體中其他優秀粒子的經驗，可理解為粒子當前位置與群體歷史最優位置之間的距離和方向。

3.2、速度更新公式的參數定義

在這里插入圖片描述

3.3、速度方向

粒子下一步迭代的移動方向 = 慣性方向 + 個體最優方向 + 群體最優方向
在這里插入圖片描述

4、位置更新公式

上一步的位置 + 下一步的速度
在這里插入圖片描述

5、PSO算法參數的詳細解釋

5.1、粒子群規模：N

一個正整數，推薦取值范圍：[20,1000]，簡單問題一般取20-40，較難或特定類別的問題可以取100-200。較小的種群規模容易陷入局部最優；較大的種群規模可以提高收斂性，更快找到全局最優解，但是相應地每次迭代的計算量也會增大；當種群規模增大至一定水平時，再增大將不再有顯著的作用。

5.2、粒子維度：D

粒子搜索的空間維數即為自變量的個數。

5.3、迭代次數：K

推薦取值范圍：[50,100]，典型取值：60、70、100；這需要在優化的過程中根據實際情況進行調整，迭代次數太小的話解不穩定，太大的話非常耗時，沒有必要。

5.4、慣性權重：w

1998年，Yuhui Shi和Russell Eberhart對基本粒子群算法引入了慣性權重(inertia weight)，并提出動態調整慣性權重以平衡收斂的全局性和收斂速度，該算法被稱為標準PSO算法（本文所介紹）【Shi Y . A Modified Particle Swarm Optimizer[C]// Proc of IEEE Icec Conference. 1998.】。

參數意義
慣性權重w表示上一代粒子的速度對當代粒子的速度的影響，或者說粒子對當前自身運動狀態的信任程度，粒子依據自身的速度進行慣性運動。慣性權重使粒子保持運動的慣性和搜索擴展空間的趨勢。w值越大，探索新區域的能力越強，全局尋優能力越強，但是局部尋優能力越弱。反之，全局尋優能力越弱，局部尋優能力強。較大的w有利于全局搜索，跳出局部極值，不至于陷入局部最優；而較小的w有利于局部搜索，讓算法快速收斂到最優解。當問題空間較大時，為了在搜索速度和搜索精度之間達到平衡，通常做法是使算法在前期有較高的全局搜索能力以得到合適的種子，而在后期有較高的局部搜索能力以提高收斂精度，所以w不宜為一個固定的常數。當w=0時，退化成基本粒子群算法，當w=1時，失去對粒子本身經驗的思考。推薦取值范圍：[0.4,2]，典型取值：0.9、1.2、1.5、1.8。
改善慣性權重
在解決實際優化問題時，往往希望先采用全局搜索，使搜索空間快速收斂于某一區域，然后采用局部精細搜索以獲得高精度的解。因此提出了自適應調整的策略，即隨著迭代的進行，線性地減小w的值。這里提供一個簡單常用的方法——線性變化策略：隨著迭代次數的增加，慣性權重w不斷減小，從而使得粒子群算法在初期具有較強的全局收斂能力，在后期具有較強的局部收斂能力。

5.5、學習因子：c1、c2

也稱為加速系數或加速因子（這兩個稱呼更加形象地表達了這兩個系數的作用）
在這里插入圖片描述

6、PSO算法的其他重要概念和技巧

6.1、適應值（fitness values）

即優化目標函數的值，用來評價粒子位置的好壞程度，決定是否更新粒子個體的歷史最優位置和群體的歷史最優位置，保證粒子朝著最優解的方向搜索。

6.2、位置限制

限制粒子搜索的空間，即自變量的取值范圍，對于無約束問題此處可以省略。

6.3、速度限制

為了平衡算法的探索能力與開發能力，需要設定一個合理的速度范圍，限制粒子的最大速度，即粒子下一步迭代可以移動的最大距離。
Vmax較大時，粒子飛行速度快，探索能力強，但粒子容易飛過最優解；
Vmax較小時，飛行速度慢，開發能力強，但是收斂速度慢，且容易陷入局部最優解；
Vmax一般設為粒子變化范圍的10％~20％，可根據實際情況調試，但不能大于粒子(解)的變化范圍。

6.4、優化停止準則

停止準則一般有兩種：

最大迭代步數：達到最大迭代次數停止
可接受的滿意解：上一次迭代后最優解的適應值與本次迭代后最優解的適應值之差小于某個值后停止優化

6.5、初始化

粒子群算法優化的結果受很多因素的影響，其中受粒子初始值的影響比較大，而且較難調控。如果粒子初始值是隨機初始化的，在不改變任何參數的情況下，多次優化的結果不一定都收斂到一個全局或局部最優解，也可能會得到一個無效解。所以粒子初始化是一個十分重要的步驟，它關系到整個優化過程中優化收斂的速度與方向。如果粒子的初始化范圍選擇得好的話可以大大縮短優化的收斂時間，也不易陷入局部最優解。需要根據具體的問題進行分析，如果根據經驗判斷出最優解一定在某個范圍內，則就在這個范圍內初始化粒子。如果無法確定，則以粒子的取值邊界作為初始化范圍。

7、Python代碼實現

使用scikit-opt庫實現PSO

先安裝

pip install scikit-opt

# -*- coding: utf-8 -*-
"""
Created on Sat May 25 09:37:28 2024@author: 63454
"""def demo_func(x):x1, x2, x3 = xreturn x1 ** 2 + (x2 - 0.05) ** 2 + x3 ** 2# %% Do PSO
from sko.PSO import PSOpso = PSO(func=demo_func, n_dim=3, pop=40, max_iter=100, lb=[0, -1, 0.5], ub=[1, 1, 1], w=0.8, c1=0.5, c2=0.5)
pso.run()
print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)# %% Plot the result
import matplotlib.pyplot as plt
plt.xlabel("iterators", size=11)
plt.ylabel("fitness", size=11)
plt.plot(pso.gbest_y_hist)
# plt.plot(pso.gbest_y_hist, color='b', linewidth=2)
plt.show()

在這里插入圖片描述

參考資料

https://github.com/TimePickerWang/MachineLearning/blob/master/MachineLearning/OptAlgorithm/PSO.py
https://blog.csdn.net/xyisv/article/details/79058574
https://zhuanlan.zhihu.com/p/346355572?utm_id=0&eqid=b544778f00000f69000000066527b08b
https://github.com/guofei9987/scikit-opt/blob/master/examples/demo_pso.py
https://scikit-opt.github.io/scikit-opt/#/zh/more_sa
https://www.omegaxyz.com/2017/05/04/introductionofpso/
https://zhuanlan.zhihu.com/p/63956652