粒子群優(yōu)化算法(PSO)的詳細(xì)解讀
本文轉(zhuǎn)自知乎用戶@追夢(mèng)小公子，有刪改，著作權(quán)歸作者所有，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
關(guān)注微信公眾號(hào)：數(shù)學(xué)建模BOOM，回復(fù)“028”，獲取《MATLAB智能算法30個(gè)案例分析》，其中有粒子群算法的詳細(xì)講解與代碼實(shí)現(xiàn)。
一、背景知識(shí)
1995年，受到鳥(niǎo)群覓食行為的規(guī)律性啟發(fā)，James Kennedy和Russell Eberhart建立了一個(gè)簡(jiǎn)化算法模型，經(jīng)過(guò)多年改進(jìn)最終形成了粒子群優(yōu)化算法(Particle Swarm Optimization, PSO) ，也可稱為粒子群算法。
粒子群算法具有收斂速度快、參數(shù)少、算法簡(jiǎn)單易實(shí)現(xiàn)的優(yōu)點(diǎn)（對(duì)高維度優(yōu)化問(wèn)題，比遺傳算法更快收斂于最優(yōu)解），但是也會(huì)存在陷入局部最優(yōu)解的問(wèn)題。
粒子群算法的思想源于對(duì)鳥(niǎo)群覓食行為的研究，鳥(niǎo)群通過(guò)集體的信息共享使群體找到最優(yōu)的目的地。
如下圖，設(shè)想這樣一個(gè)場(chǎng)景：鳥(niǎo)群在森林中隨機(jī)搜索食物，它們想要找到食物量最多的位置。但是所有的鳥(niǎo)都不知道食物具體在哪個(gè)位置，只能感受到食物大概在哪個(gè)方向。
每只鳥(niǎo)沿著自己判定的方向進(jìn)行搜索，并在搜索的過(guò)程中記錄自己曾經(jīng)找到過(guò)食物且量最多的位置，同時(shí)所有的鳥(niǎo)都共享自己每一次發(fā)現(xiàn)食物的位置以及食物的量，這樣鳥(niǎo)群就知道當(dāng)前在哪個(gè)位置食物的量最多。
在搜索的過(guò)程中每只鳥(niǎo)都會(huì)根據(jù)自己記憶中食物量最多的位置和當(dāng)前鳥(niǎo)群記錄的食物量最多的位置調(diào)整自己接下來(lái)搜索的方向。
鳥(niǎo)群經(jīng)過(guò)一段時(shí)間的搜索后就可以找到森林中哪個(gè)位置的食物量最多（全局最優(yōu)解）。
二、算法的基本原理
將鳥(niǎo)群覓食行為和算法原理對(duì)應(yīng)，如下圖：
鳥(niǎo)群覓食與粒子群算法的對(duì)應(yīng)關(guān)系
（1）PSO的基礎(chǔ)：信息的社會(huì)共享
（2）粒子的兩個(gè)屬性：速度和位置（算法的兩個(gè)核心要素）
速度表示粒子下一步迭代時(shí)移動(dòng)的方向和距離，位置是所求解問(wèn)題的一個(gè)解。
（3）算法的6個(gè)重要參數(shù)
假設(shè)在 DD 維搜索空間中，有 NN 個(gè)粒子，每個(gè)粒子代表一個(gè)解，則：
① 第i個(gè)粒子的位置為：
② 第i個(gè)粒子的速度（粒子移動(dòng)的距離和方向）為：
③ 第i個(gè)粒子搜索到的最優(yōu)位置（個(gè)體最優(yōu)解）為：
④?群體搜索到的最優(yōu)位置（群體最優(yōu)解）為：
⑤ 第 ii 個(gè)粒子搜索到的最優(yōu)位置的適應(yīng)值（優(yōu)化目標(biāo)函數(shù)的值）為：
——個(gè)體歷史最優(yōu)適應(yīng)值
⑥ 群體搜索到的最優(yōu)位置的適應(yīng)值為：
——群體歷史最優(yōu)適應(yīng)值
（4）粒子群算法的流程圖
粒子群優(yōu)化算法流程圖
（5）粒子群算法的偽代碼
三、速度更新公式
表述上叫速度，實(shí)際上就是粒子下一步迭代移動(dòng)的距離和方向，也就是一個(gè)位置向量。
① 第一項(xiàng)：慣性部分
由慣性權(quán)重和粒子自身速度構(gòu)成，表示粒子對(duì)先前自身運(yùn)動(dòng)狀態(tài)的信任。
② 第二項(xiàng)：認(rèn)知部分
表示粒子本身的思考，即粒子自己經(jīng)驗(yàn)的部分，可理解為粒子當(dāng)前位置與自身歷史最優(yōu)位置之間的距離和方向。
③ 第三項(xiàng)：社會(huì)部分
表示粒子之間的信息共享與合作，即來(lái)源于群體中其他優(yōu)秀粒子的經(jīng)驗(yàn)，可理解為粒子當(dāng)前位置與群體歷史最優(yōu)位置之間的距離和方向。
（3）速度的方向
粒子下一步迭代的移動(dòng)方向 = 慣性方向 + 個(gè)體最優(yōu)方向 + 群體最優(yōu)方向
四、位置更新公式
上一步的位置 + 下一步的速度
五、算法參數(shù)的詳細(xì)解釋
（1）粒子群規(guī)模：N
一個(gè)正整數(shù)，推薦取值范圍：[20,1000]，簡(jiǎn)單問(wèn)題一般取20~40，較難或特定類別的問(wèn)題可以取100~200。較小的種群規(guī)模容易陷入局部最優(yōu)；較大的種群規(guī)?？梢蕴岣呤諗啃裕煺业饺肿顑?yōu)解，但是相應(yīng)地每次迭代的計(jì)算量也會(huì)增大；當(dāng)種群規(guī)模增大至一定水平時(shí)，再增大將不再有顯著的作用。
（2）粒子維度：D
粒子搜索的空間維數(shù)即為自變量的個(gè)數(shù)。
（3）迭代次數(shù)：K
推薦取值范圍：[50,100]，典型取值：60、70、100；這需要在優(yōu)化的過(guò)程中根據(jù)實(shí)際情況進(jìn)行調(diào)整，迭代次數(shù)太小的話解不穩(wěn)定，太大的話非常耗時(shí)，沒(méi)有必要。
（4）慣性權(quán)重：ω
1998年，Yuhui Shi和Russell Eberhart對(duì)基本粒子群算法引入了慣性權(quán)重(inertia weight)ω，并提出動(dòng)態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度，該算法被稱為標(biāo)準(zhǔn)PSO算法。
參數(shù)意義
慣性權(quán)重表示上一代粒子的速度對(duì)當(dāng)代粒子的速度的影響，或者說(shuō)粒子對(duì)當(dāng)前自身運(yùn)動(dòng)狀態(tài)的信任程度，粒子依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng)。
慣性權(quán)重使粒子保持運(yùn)動(dòng)的慣性和搜索擴(kuò)展空間的趨勢(shì)。ω值越大，探索新區(qū)域的能力越強(qiáng)，全局尋優(yōu)能力越強(qiáng)，但是局部尋優(yōu)能力越弱。
反之，全局尋優(yōu)能力越弱，局部尋優(yōu)能力強(qiáng)。較大的 ω有利于全局搜索，跳出局部極值，不至于陷入局部最優(yōu)；
而較小的ω有利于局部搜索，讓算法快速收斂到最優(yōu)解。當(dāng)問(wèn)題空間較大時(shí)，為了在搜索速度和搜索精度之間達(dá)到平衡，通常做法是使算法在前期有較高的全局搜索能力以得到合適的種子，而在后期有較高的局部搜索能力以提高收斂精度，所以 w不宜為一個(gè)固定的常數(shù)。
改善慣性權(quán)重 ω
在解決實(shí)際優(yōu)化問(wèn)題時(shí)，往往希望先采用全局搜索，使搜索空間快速收斂于某一區(qū)域，然后采用局部精細(xì)搜索以獲得高精度的解。
因此提出了自適應(yīng)調(diào)整的策略，即隨著迭代的進(jìn)行，線性地減小 ω\[\omega\] 的值。這里提供一個(gè)簡(jiǎn)單常用的方法——線性變化策略：隨著迭代次數(shù)的增加，慣性權(quán)重ω不斷減小，從而使得粒子群算法在初期具有較強(qiáng)的全局收斂能力，在后期具有較強(qiáng)的局部收斂能力。
ωmax——最大慣性權(quán)重；ωmin——最小慣性權(quán)重；
iter——當(dāng)前迭代次數(shù)；itermax——最大迭代次數(shù)。
（5）學(xué)習(xí)因子：?c1,c2
也稱為加速系數(shù)或加速因子（這兩個(gè)稱呼更加形象地表達(dá)了這兩個(gè)系數(shù)的作用）
c1表示粒子下一步動(dòng)作來(lái)源于自身經(jīng)驗(yàn)部分所占的權(quán)重，將粒子推向個(gè)體最優(yōu)位置的加速權(quán)重；
c2表示粒子下一步動(dòng)作來(lái)源于其它粒子經(jīng)驗(yàn)部分所占的權(quán)重，將粒子推向群體最優(yōu)位置的加速權(quán)重；
c1=0：無(wú)私型粒子群算法，"只有社會(huì)，沒(méi)有自我"，迅速喪失群體多樣性，易陷入局部最優(yōu)而無(wú)法跳出；
c2=0：自我認(rèn)知型粒子群算法，"只有自我，沒(méi)有社會(huì)"，完全沒(méi)有信息的社會(huì)共享，導(dǎo)致算法收斂速度緩慢；
c1,c2都不為0：完全型粒子群算法，更容易保持收斂速度和搜索效果的均衡，是較好的選擇。
六、算法的一些重要概念和技巧
（1）適應(yīng)值（fitness values）
即優(yōu)化目標(biāo)函數(shù)的值，用來(lái)評(píng)價(jià)粒子位置的好壞程度，決定是否更新粒子個(gè)體的歷史最優(yōu)位置和群體的歷史最優(yōu)位置，保證粒子朝著最優(yōu)解的方向搜索。
（2）位置限制
限制粒子搜索的空間，即自變量的取值范圍，對(duì)于無(wú)約束問(wèn)題此處可以省略。
（3）速度限制
為了平衡算法的探索能力與開(kāi)發(fā)能力，需要設(shè)定一個(gè)合理的速度范圍，限制粒子的最大速度,即粒子下一步迭代可以移動(dòng)的最大距離。
較大時(shí)，粒子飛行速度快，探索能力強(qiáng)，但粒子容易飛過(guò)最優(yōu)解；
（4）優(yōu)化停止準(zhǔn)則
一般有兩種：
① 最大迭代步數(shù)
② 可接受的滿意解：上一次迭代后最優(yōu)解的適應(yīng)值與本次迭代后最優(yōu)解的適應(yīng)值之差小于某個(gè)值后停止優(yōu)化
（5）初始化
粒子群算法優(yōu)化的結(jié)果受很多因素的影響，其中受粒子初始值的影響比較大，而且較難調(diào)控。
如果粒子初始值是隨機(jī)初始化的，在不改變?nèi)魏螀?shù)的情況下，多次優(yōu)化的結(jié)果不一定都收斂到一個(gè)全局或局部最優(yōu)解，也可能會(huì)得到一個(gè)無(wú)效解。所以粒子初始化是一個(gè)十分重要的步驟，它關(guān)系到整個(gè)優(yōu)化過(guò)程中優(yōu)化收斂的速度與方向。
如果粒子的初始化范圍選擇得好的話可以大大縮短優(yōu)化的收斂時(shí)間，也不易于陷入局部最優(yōu)解。
我們需要根據(jù)具體的問(wèn)題進(jìn)行分析，如果根據(jù)我們的經(jīng)驗(yàn)判斷出最優(yōu)解一定在某個(gè)范圍內(nèi)，則就在這個(gè)范圍內(nèi)初始化粒子。如果無(wú)法確定，則以粒子的取值邊界作為初始化范圍。
在北理工韓寶玲教授的"基于粒子群算法的四足機(jī)器人靜步態(tài)優(yōu)化方法論文中采用了拉丁方抽樣方法來(lái)解決粒子初始化問(wèn)題，大家可以嘗試一下這種初始化方法。
