8.3粒子群算法劉金琨8.3粒子群算法粒子群算法，也稱粒子群優(yōu)化算法(ParticleSwarmOptimization)，縮寫為PSO。粒子群優(yōu)化算法是一種進化計算技術，1995年由Eberhart博士和Kennedy博士提出，該算法源于對鳥群捕食的行為研究，是近年來迅速發(fā)展的一種新的進化算法。8.3粒子群算法最早的PSO是模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機搜索算法，讓一群鳥在空間里自由飛翔覓食，每個鳥都能記住它曾經飛過最高的位置，然后就隨機的靠近那個位置，不同的鳥之間可以互相交流，它們都盡量靠近整個鳥群中曾經飛過的最高點，這樣，經過一段時間就可以找到近似的最高點。8.3粒子群算法PSO算法屬于進化算法的一種，和遺傳算法相似，它也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解，它也是通過適應度來評價解的品質，但它比遺傳算法規(guī)則更為簡單，沒有遺傳算法的“交叉”和“變異”操作，通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學術界的重視，并且在解決實際問題中展示了其優(yōu)越性。目前已廣泛應用于函數優(yōu)化、系統(tǒng)辨識、模糊控制等應用領域。8.3粒子群算法8.3.1粒子群算法基本原理PSO算法模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪里，但是它們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略就是搜尋目前離食物最近的鳥的周圍區(qū)域。8.3粒子群算法8.3.1粒子群算法基本原理PSO算法從這種模型中得到啟示并用于解決優(yōu)化問題。PSO算法中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數決定的適應度值，適應度值越大越好。每個粒子還有一個速度決定他們飛行的方向和距離，粒子們追隨當前的最優(yōu)粒子在解空間中搜索。8.3粒子群算法8.3.1粒子群算法基本原理PSO算法首先初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個"極值"來更新自己的位置。第一個極值是粒子本身所找到的最優(yōu)解，這個解叫做個體極值。另一個極值是整個種群目前找到的最優(yōu)解，這個極值稱為全局極值。8.3粒子群算法8.3.1粒子群算法基本原理粒子群基本算法速度更新位置更新8.3粒子群算法8.3.2參數設置

8.3粒子群算法8.3.2參數設置a)粒子數：一般取20-40，對于比較難的問題,粒子數可以取到100或200；b)最大速度Vmax：決定粒子在一個循環(huán)中最大的移動距離，通常小于粒子的范圍寬度。較大的Vmax可以保證粒子種群的全局搜索能力，較小的Vmax則粒子種群的局部搜索能力加強；c)學習因子：c1和c2通常可設定為2.0。c1為局部學習因子，c2為全局學習因子，c2一般取大些。8.3粒子群算法8.3.2參數設置d)慣性權重：一個大的慣性權值有利于展開全局尋優(yōu)，而一個小的慣性權值有利于局部尋優(yōu)。當粒子的最大速度Vmax很小時，使用接近于1的慣性權重。當Vmax不是很小時，使用權重ω=0.8較好。8.3粒子群算法8.3.2參數設置還可使用時變權重。如果在迭代過程中采用線性遞減慣性權值，則粒子群算法在開始時具有良好的全局搜索性能，能夠迅速定位到接近全局最優(yōu)點的區(qū)域，而在后期具有良好的局部搜索性能，能夠精確的得到全局最優(yōu)解。經驗表明，慣性權重采用從0.90線性遞減到0.10的策略，會獲得比較好的算法性能；中止條件：最大循環(huán)數或最小誤差要求。8.3粒子群算法8.3.3算法流程（1）初始化：設定參數運動范圍，設定學習因子

c1、c2

，最大進化代數G，kg表示當前的進化代數。在一個D維參數的搜索解空間中，粒子組成的種群規(guī)模大小為Size，每個粒子代表解空間的一個候選解，其中第i個粒子在整個解空間的位置表示為Xi，速度表示為Vi。第i個粒子從初始到當前迭代次數搜索產生的最優(yōu)解，個體極值Pi，整個種群目前的最優(yōu)解為BestS。隨機產生Size個粒子，隨機產生初始種群的位置矩陣和速度矩陣。8.3粒子群算法8.3.3算法流程

8.3粒子群算法8.3.3算法流程（3）更新粒子的速度和位置，產生新種群，并對粒子的速度和位置進行越界檢查，為避免算法陷入局部最優(yōu)解，加入一個局部自適應變異算子進行調整。(8.25)(8.26)其中kg=1,2…G

，i=1,2…Size

，r1

和

r2為0到1的隨機數，c1為局部學習因子，c2

為全局學習因子，一般取

c2大些。8.3粒子群算法8.3.3算法流程（4）比較粒子的當前適應值f(Xi)和自身歷史最優(yōu)值Pi，如果f(Xi)

優(yōu)于Pi，則置f(Xi)為當前值，并更新粒子位置。（5）比較粒子當前適應值f(Xi)與種群最優(yōu)值BestS，如果f(Xi)優(yōu)于BestS，則置f(Xi)為當前值，更新種群全局最優(yōu)值。（6）檢查結束條件，若滿足，則結束尋優(yōu)；否則kg=kg+1，轉至（3）。結束條件為尋優(yōu)達到最大進化代數，或評價值小于給定精度。8.3粒子群算法圖PSO的算法流