本文關鍵詞：粒子群算法，由筆耕文化傳播整理發(fā)布。

粒子群優(yōu)化算法簡介

　　好好學數(shù)學。

　　經(jīng)朋友介紹，接了一份工作，就是做PSO及其優(yōu)化，恰好我導師也研究這個，剛開學也有接觸，那我就接了.......賺點生活費。

　　歡迎大家和我聯(lián)系做算法類項目，QQ：791909235，Tel：13137910179。

　　5、適應性原則：群體的模式應在計算代價值得的時候改變。

　　對鳥群行為的模擬： Reynolds、Heppner和Grenader提出鳥群行為的 模擬。他們發(fā)現(xiàn)，鳥群在行進中會突然同步的改 變方向，散開或者聚集等。那么一定有某種潛在 的能力或規(guī)則保證了這些同步的行為。這些科學 家都認為上述行為是基于不可預知的鳥類社會行 為中的群體動態(tài)學。 在這些早期的模型中僅僅依賴個體間距的操作， 也就是說，這中同步是鳥群中個體之間努力保持 最優(yōu)的距離的結果。

　　對魚群行為的研究：生物社會學家E.O.Wilson對魚群進行了研究。提出：“至少在理論上，魚群的個體成員能夠受益于群體中其他個體在尋找食物的過程中的發(fā)現(xiàn)和以前的經(jīng)驗，這種受益超過了個體之間的競爭所帶來的利益消耗，不管任何時候食物資源不可預知的分散。”這說明，同種生物之間信息的社會共享能夠帶來好處。這是PSO的基礎。　

　　粒子群優(yōu)化算法的基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解．
　　PSO的優(yōu)勢在于簡單容易實現(xiàn)并且沒有許多參數(shù)的調節(jié)。目前已被廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模糊系統(tǒng)控制以及其他遺傳算法的應用領域。

　　設想這樣一個場景：一群鳥在隨機的搜索食物。 在這個區(qū)域里只有一塊食物，所有的鳥都不知 道食物在那。但是它們知道自己當前的位置距 離食物還有多遠。 那么找到食物的最優(yōu)策略是什么？ 最簡單有效的就是搜尋目前離食物最近的鳥的 周圍區(qū)域。

　　鳥被抽象為沒有質量和體積的微粒(點)，并延伸到N維空間，粒子I 在N維空間的位置表示為矢量Xi＝(x1，x2，…，xN)，飛行速度表示為矢量Vi＝(v1，v2，…，vN)．每個粒子都有一個由目標函數(shù)決定的適應值(fitness value)，并且知道自己到目前為止發(fā)現(xiàn)的最好位置(pbest)和現(xiàn)在的位置Xi．這個可以看作是粒子自己的飛行經(jīng)驗．除此之外，每個粒子還知道到目前為止整個群體中所有粒子發(fā)現(xiàn)的最好位置(gbest)(gbest是pbest中的最好值)．這個可以看作是粒子同伴的經(jīng)驗．粒子就是通過自己的經(jīng)驗和同伴中最好的經(jīng)驗來決定下一步的運動。  

　　PSO初始化為一群隨機粒子(隨機解)。然后通過迭代找到最優(yōu)解。在每一次的迭代中，粒子通過跟蹤兩個“極值”(pbest,gbest)來更新自己。

　　在找到這兩個最優(yōu)值后，粒子通過下面的公式來更新自己的速度和位置。

　�。ㄎ矣浀肰i需要乘以慣性權重）。

　　i＝1，2，…，M，M是該群體中粒子的總數(shù)；Vi 是粒子的速度； pbest和gbest如前定義； rand()是介于（0、1）之間的隨機數(shù)； Xi 是粒子的當前位置。 c1和c2是學習因子，通常取c1＝ c2＝2 在每一維，粒子都有一個最大限制速度Vmax，如果 某一維的速度超過設定的Vmax ，那么這一維的速度 就被限定為Vmax 。（ Vmax >0） 以上面兩個公式為基礎，形成了后來PSO 的標準形式。

　　1998年shi等人在進化計算的國際會議上 發(fā)表了一篇論文《A modified particle swarm optimizer》對前面的公式進行了修正。引入 慣性權重因子。值較大，全局尋優(yōu)能力強，局部尋優(yōu)能力弱； 值較小反之。

　　初始時，shi將 取為常數(shù)，后來實驗發(fā)現(xiàn)，，動 態(tài) 能夠獲得比固定值更好的尋優(yōu)結果。動態(tài) 可以在PSO搜索過程中線性變化，也可根據(jù)PSO 性能的某個測度函數(shù)動態(tài)改變。 目前，采用較多的是shi建議的線性遞減權值 (linearly decreasing weight, LDW)策略。

　　標準PSO算法的流程：

　　Step1:初始化一群微粒(群體規(guī)模為m)，包括隨機位置和 速度；

　　Step2:評價每個微粒的適應度；

　　Step3:對每個微粒，將其適應值與其經(jīng)過的最好位置 pbest作比較，如果較好，則將其作為當前的 最好位置pbest;

　　Step4:對每個微粒，將其適應值與其經(jīng)過的最好位置 gbest作比較，如果較好，則將其作為當前的 最好位置gbest;

　　Step5:根據(jù)(2)、(3)式調整微粒速度和位置；

　　Step6：未達到結束條件則轉Step2。

　　迭代終止條件根據(jù)具體問題一般選為最大迭代次數(shù)Gk或(和)微粒群迄今為止搜索到的最優(yōu)位置滿足預定最小適應閾值。

　　方程中pbest和gbest分別表示微粒群的局部和 全局最優(yōu)位置，當C1＝0時，則粒子沒有了認知能力， 變?yōu)橹挥猩鐣哪Ｐ?social-only):

　　被稱為全局PSO算法.粒子有擴展搜索空間的能力，具有 較快的收斂速度，但由于缺少局部搜索，對于復雜問題 比標準PSO 更易陷入局部最優(yōu)。

　　當C2＝0時，則粒子之間沒有社會信息，模型變?yōu)?只有認知(cognition-only)模型：

　　被稱為局部PSO算法。由于個體之間沒有信息的 交流，整個群體相當于多個粒子進行盲目的隨機 搜索，收斂速度慢，因而得到最優(yōu)解的可能性小。

　　群體規(guī)模m 一般取20～40，對較難或特定類別的問題 可以取到100～200。

　　最大速度Vmax決定當前位置與最好位置之間的區(qū)域的 分辨率(或精度)。如果太快，則粒子有可能越過極小 點;如果太慢，則粒子不能在局部極小點之外進行足 夠的探索，會陷入到局部極值區(qū)域內。這種限制可以 達到防止計算溢出、決定問題空間搜索的粒度的目的。

　　權重因子 包括慣性因子 和學習因子c1和c2。 使粒子 保持著運動慣性，使其具有擴展搜索空間的趨勢，有 能力探索新的區(qū)域。C1和c2代表將每個粒子推向Pbest 和gbest位置的統(tǒng)計加速項的權值。較低的值允許粒子 在被拉回之前可以在目標區(qū)域外徘徊，較高的值導致粒 子突然地沖向或越過目標區(qū)域。

　　通常設c1＝c2＝2。Suganthan的實驗表明：c1和c2 為常數(shù)時可以得到較好的解，但不一定必須等于2。 Clerc引入收斂因子(constriction factor) K來保證 收斂性。

　　通常取 為4.1,則K＝0.729.實驗表明，與使 用慣性權重的PSO算法相比，使用收斂因子的 PSO有更快的收斂速度。其實只要恰當?shù)倪x取 和c1、c2，兩種算法是一樣的。因此使用收 斂因子的PSO可以看作使用慣性權重PSO的特 例。 恰當?shù)倪x取算法的參數(shù)值可以改善算法的性能。

　　基本PSO是用于實值連續(xù)空間，然而許多實際問題是組合 優(yōu)化問題，因而提出離散形式的PSO。 速度和位置更新式為：

　　共性: （1）都屬于仿生算法。 (2) 都屬于全局優(yōu)化方法。 (3) 都屬于隨機搜索算法。 (4) 都隱含并行性。 (5) 根據(jù)個體的適配信息進行搜索，因此不受函數(shù) 約束條件的限制，如連續(xù)性、可導性等。 (6) 對高維復雜問題，往往會遇到早熟收斂和收斂 性能差的缺點，都無法保證收斂到最優(yōu)點。

　　差異： (1) PSO有記憶，好的解的知識所有粒子都保 存，而GA，以前的知識隨著種群的改變被改變。 (2) PSO中的粒子僅僅通過當前搜索到最優(yōu)點進行共享信息，所以很大程度上這是一種單共享項信息機制。而GA中，染色體之間相互共享信息，使得整個種群都向最優(yōu)區(qū)域移動。 (3) GA的編碼技術和遺傳操作比較簡單，而PSO 相對于GA，沒有交叉和變異操作，粒子只是通過內部速度進行更新，因此原理更簡單、參數(shù)更少、實現(xiàn)更容易。

　　GA可以用來研究NN的三個方面：網(wǎng)絡連接權重、網(wǎng)絡 結構、學習算法。優(yōu)勢在于可處理傳統(tǒng)方法不能處理的 問題，例如不可導的節(jié)點傳遞函數(shù)或沒有梯度信息。 缺點:在某些問題上性能不是特別好；網(wǎng)絡權重的編碼和 遺傳算子的選擇有時較麻煩。 已有利用PSO來進行神經(jīng)網(wǎng)絡訓練。研究表明PSO是一 種很有潛力的神經(jīng)網(wǎng)絡算法。速度較快且有較好的結果。 且沒有遺傳算法碰到的問題。

　　各算法對應的問題如下：

　　PSO 用基本粒子群算法求解無約束優(yōu)化問題
　　YSPSO 用帶壓縮因子的粒子群算法求解無約束優(yōu)化問題
　　LinWPSO 用線性遞減權重粒子群優(yōu)化算法求解無約束優(yōu)化問題
　　SAPSO 用自適應權重粒子群優(yōu)化算法求解無約束優(yōu)化問題
　　RandWPSO 用隨機權重粒子群優(yōu)化算法求解無約束優(yōu)化問題
　　LnCPSO 用學習因子同步變化的粒子群優(yōu)化算法求解無約束優(yōu)化問題
　　AsyLnCPSO 用學習因子異步變化的粒子群優(yōu)化算法求解無約束優(yōu)化問題
　　SecPSO 用二階粒子群優(yōu)化算法求解無約束優(yōu)化問題
　　SecVibratPSO 用二階振蕩粒子群優(yōu)化算法求解無約束優(yōu)化問題
　　CLSPSO 用混沌粒子群優(yōu)化算法求解無約束優(yōu)化問題
　　SelPSO 用基于選擇的粒子群優(yōu)化算法求解無約束優(yōu)化問
　　BreedPSO 用基于交叉遺傳的粒子群優(yōu)化算法求解無約束優(yōu)化問
　　SimuAPSO 用基于模擬退火的粒子群優(yōu)化算法求解無約束優(yōu)化問題

csdn鏈接（包含了基本PSO和12種優(yōu)化PSO算法，絕對能用）。

參考文獻：西電姚新正老師課件

csdn鏈接。

posted @

  本文關鍵詞：粒子群算法，由筆耕文化傳播整理發(fā)布。