干貨 | 【算法】粒子群算法Particle Swarm Optimization超詳細(xì)解析+代碼實(shí)例講解
定義
- 粒子群算法，也稱粒子群優(yōu)化算法或鳥群覓食算法（PSO）屬于進(jìn)化算法的一種艾蓝，是一種并行算法骨望，它從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解爸黄，通過適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)滞伟，通過追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。具有實(shí)現(xiàn)容易炕贵、精度高梆奈、收斂快等優(yōu)點(diǎn)
- 在初始化階段，PSO生成一群隨機(jī)粒子(即隨機(jī)解)称开，然后通過迭代找到最優(yōu)解亩钟。在每一次迭代中，粒子通過跟蹤兩個(gè)"極值"來(lái)更新自己鳖轰。第一個(gè)極值就是粒子本身所找到的歷史最優(yōu)解清酥，這個(gè)解叫做個(gè)體極值pBest。另一個(gè)極值是整個(gè)種群找到的歷史最優(yōu)解蕴侣，這個(gè)極值是全局極值gBest焰轻。
粒子抽象
- 粒子群算法通過設(shè)計(jì)一種無(wú)質(zhì)量的粒子來(lái)模擬鳥群中的鳥，粒子僅具有兩個(gè)屬性：速度和位置昆雀，速度代表移動(dòng)的快慢和方向辱志。
-
PSO初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過迭代找到最優(yōu)解狞膘。在每一次的迭代中荸频，粒子通過跟蹤兩個(gè)“極值”(pbest，gbest)來(lái)更新自己客冈。在找到這兩個(gè)最優(yōu)值后旭从，粒子通過下面的公式來(lái)更新自己的速度和位置。速度和位置的更新
- 公式(1)的第①部分稱為【記憶項(xiàng)】场仲，表示上次速度大小和方向的影響和悦；
- 公式(1)的第②部分稱為【自身認(rèn)知項(xiàng)】，是從當(dāng)前點(diǎn)指向粒子自身最好點(diǎn)的一個(gè)矢量渠缕，表示粒子的動(dòng)作來(lái)源于自己經(jīng)驗(yàn)的部分鸽素；
- 公式(1)的第③部分稱為【群體認(rèn)知項(xiàng)】，是一個(gè)從當(dāng)前點(diǎn)指向種群最好點(diǎn)的矢量亦鳞，反映了粒子間的協(xié)同合作和知識(shí)共享馍忽。粒子就是通過自己的經(jīng)驗(yàn)和同伴中最好的經(jīng)驗(yàn)來(lái)決定下一步的運(yùn)動(dòng)棒坏。
速度變化
算法流程
- 初始化一群微粒(群體規(guī)模為N)，包括隨機(jī)位置和速度遭笋；
- 評(píng)價(jià)每個(gè)微粒的適應(yīng)度坝冕；
- 對(duì)每個(gè)微粒，將其適應(yīng)值與其經(jīng)過的最好位置pbest作比較瓦呼，如果較好喂窟，則將其作為當(dāng)前的最好位置pbest；
- 對(duì)每個(gè)微粒央串，將其適應(yīng)值與其經(jīng)過的最好位置gbest作比較磨澡，如果較好，則將其作為當(dāng)前的最好位置gbest质和；
- 根據(jù)公式(2)稳摄、(3)調(diào)整微粒速度和位置；
- 未達(dá)到結(jié)束條件則轉(zhuǎn)第2步饲宿。
迭代終止條件根據(jù)具體問題一般選為最大迭代次數(shù)Gk或(和)微粒群迄今為止搜索到的最優(yōu)位置滿足預(yù)定最小適應(yīng)閾值厦酬。
流程圖
PSO流程圖
