鳥群的啟發(fā)--粒子群算法
看文章之前先看一個相關小視頻（55s, 2.86M）：
1. PSO的基本思想：
“自然界的蟻群、鳥群、魚群、羊群、牛群、蜂群等，其實時時刻刻都在給予我們以某種啟示，只不過我們常常忽略了大自然對我們的最大恩賜！”——馬良教授
粒子群算法的思想源于對鳥群捕食行為的研究．模擬鳥集群飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達到最優(yōu)目的。
設想這樣一個場景：一群鳥在隨機搜索食物
已知：
(1). 在這塊區(qū)域里只有一塊食物;??
(2). ??所有的鳥都不知道食物在哪里; ? ??
(3). 但它們能感受到當前的位置離食物還有多遠.???
那么:找到食物的最優(yōu)策略是什么呢？??
(1). 搜尋目前離食物最近的鳥的周圍區(qū)域 ．
(2). 根據(jù)自己飛行的經驗判斷食物的所在。
PSO正是從這種模型中得到了啟發(fā)：信息的社會共享
2. 算法介紹
(1)每個尋優(yōu)的問題解都被想像成一只鳥，稱為“粒子”。所有粒子都在一個D維空間進行搜索。
(2)所有的粒子都由一個fitness function 確定適應值以判斷目前的位置好壞。
(3)每一個粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。
(4)每一個粒子還有一個速度以決定飛行的距離和方向。這個速度根據(jù)它本身的飛行經驗以及同伴的飛行經驗進行動態(tài)調整。
粒子群優(yōu)化算法求最優(yōu)解在D維空間中，有N個粒子；
????粒子i位置：x_i=(x_i1,x_i2,…x_iD)，將xi代入適應函數(shù)f(x_i)求適應值；
????粒子i速度：v_i=(v_i1,v_i2,…v_iD)
????粒子i個體經歷過的最好位置：pbest_i=(p_i1,p_i2,…p_iD)
????種群所經歷過的最好位置：gbest=(g1,g2,…gD)
通常，最優(yōu)粒子第d（1≤d≤D）維的位置變化范圍限定在[X_min,d, X_max,d]?內，每個粒子的速度變化范圍限定在[-V_min,d, V_max,d]內（即在迭代中若相應粒子速度位置超出了邊界值，則該維的速度或位置被限制為該維最大速度或邊界位置）
粒子速度更新公式包含三部分：
???第一部分為粒子先前的速度
???第二部分為“認知”部分，表示粒子本身的思考，可理解為粒子i當前位置與自己最好位置之間的距離。
???第三部分為“社會”部分，表示粒子間的信息共享與合作，可理解為粒子i當前位置與群體最好位置之間的距離。
3. 算法流程圖
(1)Initial：
??初始化粒子群體（群體規(guī)模為n），包括隨機位置和速度。
(2)Evaluation：
? 根據(jù)fitness function ，評價每個粒子的適應度。
(3)Find the Pbest：
?? 對每個粒子，將其當前適應值與其個體歷史最佳位置（pbest）對應的適應值做比較，如果當前的適應值更高，則將用當前位置更新歷史最佳位置pbest。
(4)Find the Gbest：
??對每個粒子，將其當前適應值與全局最佳位置（gbest）對應的適應值做比較，如果當前的適應值更高，則將用當前粒子的位置更新全局最佳位置gbest。
(5)Update the Velocity：
??根據(jù)公式更新每個粒子的速度與位置。
(6)如未滿足結束條件，則返回步驟2
????通常算法達到最大迭代次數(shù)G_max或者最佳適應度值的增量小于某個給定的閾值時算法停止。
4. 算法舉例
求解如下四維Rosenbrock函數(shù)的優(yōu)化問題
種群的數(shù)量：m=5，
編碼：因為問題的維數(shù)是4，所以粒子的位置和速度都是四維實數(shù)向量
設定粒子的速度范圍（一般為位置的范圍）：V_max=60
對粒子群進行位置和速度的隨機初始化，如下：
至此，每個粒子的初始位置和初始速度都已確定，接下來根據(jù)目標函數(shù)f(x)計算每個粒子的適應值：
從適應值上我們可以得出群體歷史最優(yōu)解x_1,和個體歷史最優(yōu)解，每個解本身。接下來更新粒子位置和速度：設w=1,c_1=c_2=2，根據(jù)上面的速度位置更新函數(shù)，根據(jù)規(guī)則，每個粒子的速度和最優(yōu)粒子位置超過限制將強行拉回邊界，可以得到更新后的速度和位置如下：
然后，根據(jù)新位置繼續(xù)計算適應值，根據(jù)適應值替換全局歷史最優(yōu)粒子和個體歷史最優(yōu)粒子。直至達到最大迭代次數(shù)G_max或者最佳適應度值的增量小于某個給定的閾值時算法停止。
5. 小結
PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應值(fitnessvalue)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索。
免責聲明：本文系網(wǎng)絡轉載。版權歸原作者所有。如涉及版權，請聯(lián)系刪除！