粒子群優化算法

2011-12-05 19:49:55

标簽：群智能 休閑 蟻群優化 粒群優化 粒子群優化

原創作品，允許轉載，轉載時請務必以超連結形式标明文章 原始出處 、作者資訊和本聲明。否則将追究法律責任。http://nxlhero.blog.51cto.com/962631/734212

粒子群優化算法屬于群智能(swarm intelligence)優化算法。群智能分兩種，一種是粒群優化，另一種是蟻群優化。

群智能概念

       假設你和你的朋友正在尋寶，每個人有個探測器，這個探測器可以知道寶藏到探測器的距離。你們一群人在找，每個人都可以把資訊共享出去，就跟打dota時你 可以有你隊友的視野，你可以知道其他所有人距離寶藏的距離，這樣，你看誰離寶藏最近，就向誰靠近，這樣會使你發現寶藏的機會變大，而且，這種方法比你單人 找要快的多。

       這是一個群行為(swarm behavior)的簡單執行個體，群中各個體互動作用，使用一個比單一個體更有效的方法求解全局目标。可以把群(swarm)定義為某種互動作用的組織或Agent之結構集合，在群智能計算研究中，群的個體組織包括螞蟻，白蟻，蜜蜂，黃蜂，魚群，鳥群等。在這些群體中，個體在結構上是很簡單的，而它們的集體行為卻可能變得相當複雜。研究人員發現，螞蟻在鳥巢和食物之間的運輸路線，不管一開始多随機，最後螞蟻總能找到一條最短路徑。

粒群優化概念

粒群優化(particle swarm optimization,PSO)算法是一種基于群體搜尋的算法，它建立在模拟鳥群社會的基礎上。粒群概念的最初含義是通過圖形來模拟鳥群優美和不可預 測的舞蹈動作，發現鳥群支配同步飛行和以最佳隊形突然改變飛行方向并重新編隊的能力。這個概念已經被包含在一個簡單有效的優化算法中。

在粒群優化中，被稱為“粒子”(particle)的個體通過超維搜尋空間“流動”。粒子在搜尋空間中的位置變化是以個體成功地超過其他個體的社會心理意向為基礎的，是以，群中粒子的變化是受其鄰近粒子（個體）的經驗或知識影響的。一個粒子的搜尋行為受到群中其他粒子的搜尋行為的影響。由此可見，粒群優化是一種共生合作算法。

算法描述

先通過一個形象的場景來描述一下：5隻鳥覓食，每個鳥都知道自己與食物的距離，并将此資訊與其他鳥共享。

一開始，5隻鳥分散在不同的地方，假設沒隻鳥每秒鐘更新自己的速度和方向，問題是怎麼更新呢？

每隻鳥記下自己離食物最近的位置，稱為pbest，pbest0,pbest1,..分别表示5隻鳥的pbest，從這裡面選一個gbest，組裡最好的。

每過一秒鐘，鳥更新自己的速度v(此處為矢量)，

v_new  = v_old + c1*rand()*(pbest-pcurrent) +c2*rand()*(gbest-pcurrent)

c1,c2一般為2，rand()産生0~1的随機數。

然後以這個速度飛行1秒，再次更新，最終離食物越來越近。

 以下僞碼摘自百度百科

　程式的僞代碼如下

　　For each particle

　　____Initialize particle

　　END

　　Do

　　____For each particle

　　________Calculate fitness value

　　________If the fitness value is better than the best fitness value (pBest) in history

　　____________set current value as the new pBest

　　____End

　　____Choose the particle with the best fitness value of all the particles as the gBest

　　________Calculate particle velocity according equation (a)

　　________Update particle position according equation (b)

　　While maximum iterations or minimum error criteria is not attained

　　在每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新後的速度超過使用者設定的Vmax，那麼這一維的速度就被限定為Vmax。

程式執行個體

計算f(x) = x*x - 20x + 100 的最小值及取最小值時的x

#include <iostream>  

#include <cmath>  

#include <cstdlib>  

using namespace std;  

#define C1 2  

#define C2 2  

#define VMAX 5.0  

#define MAX_ITERATIONS 100  

float rand01()  

{  

        return (float) (rand()/(double)RAND_MAX);  

}  

struct particle{  

        float current;  

        float pbest;  

};  

float fitness(float x)  

        return x*x - 20*x + 100;  

float gbest = 10000;  

struct particle p[5];  

float v[5] = {0};  

void init_particles()  

        int i;  

        for(i = 0; i < 5; i++)  

        {  

                p[i].current = -2+i;  

                p[i].pbest = p[i].current;  

        }  

void find_gbest()  

                        if(fitness(gbest) > fitness(p[i].current))  

                                gbest = p[i].current;  

void adjust_v()  

        int i ;  

                v[i] = v[i] + C1*rand01()*(p[i].pbest - p[i].current) + C2*rand01()*(gbest - p[i].current);  

                if(v[i] > VMAX)  

                        v[i] = VMAX;  

void pso()  

        int i,iter_num;  

        iter_num = 1;  

        while(iter_num < MAX_ITERATIONS)  

                /*for(i = 0; i < 5; i++)  

                {  

                        cout <<"p"<<i<<":current "<<p[i].current<<" pbest "<<p[i].pbest<<endl;  

                }  

                cout <<"gbest:"<<gbest<<endl;  

                cout <<endl;  

                getchar();*/ 

                for(i = 0; i < 5; i++)  

                        if(fitness(p[i].current) < fitness(p[i].pbest))  

                                p[i].pbest = p[i].current;  

                find_gbest();  

                adjust_v();  

                        p[i].current += v[i];  

                iter_num ++;  

int main()  

        init_particles();  

        pso();  

        printf("After %d iterations,gbest is %f\n",MAX_ITERATIONS,gbest);  

        return 0;  

運作結果

下面是每次疊代後的結果，可以看到，經過5次疊代，結果就很好了。

After 1 iterations  

p0:current -2 pbest -2  

p1:current -1 pbest -1  

p2:current 0 pbest 0  

p3:current 1 pbest 1  

p4:current 2 pbest 2  

gbest:10000  

After 2 iterations  

p0:current 1.15506 pbest -2  

p1:current 3.79064 pbest -1  

p2:current 0.790205 pbest 0  

p3:current 2.53646 pbest 1  

gbest:2  

After 3 iterations  

p0:current 6.15506 pbest 1.15506  

p1:current 8.58128 pbest 3.79064  

p2:current 5.79021 pbest 0.790205  

p3:current 5.87216 pbest 2.53646  

p4:current 4.17373 pbest 2  

gbest:3.79064  

After 4 iterations  

p0:current 11.1551 pbest 6.15506  

p1:current 13.3719 pbest 8.58128  

p2:current 10.7902 pbest 5.79021  

p3:current 9.79741 pbest 5.87216  

p4:current 8.27141 pbest 4.17373  

gbest:8.58128  

After 5 iterations  

p0:current 13.8766 pbest 11.1551  

p1:current 10.1764 pbest 8.58128  

p2:current 14.7492 pbest 10.7902  

p3:current 13.7227 pbest 9.79741  

p4:current 13.2714 pbest 8.27141  

gbest:9.79741  

After 6 iterations  

p0:current 8.03327 pbest 11.1551  

p1:current 6.98078 pbest 10.1764  

p2:current 13.2414 pbest 10.7902  

p3:current 4.78856 pbest 9.79741  

p4:current 11.6974 pbest 8.27141  

gbest:10.1764  

After 7 iterations  

p0:current 5.84287 pbest 11.1551  

p1:current 9.25245 pbest 10.1764  

p2:current 5.23059 pbest 10.7902  

p3:current -3.28694 pbest 9.79741  

p4:current 9.93147 pbest 11.6974