粒子群算法

• 基本思想
• 更新公式
• 算法流程
• 抽象出的鳥類數據結構
• C語言實現

基本思想

粒子群算法是由鳥類覓食啟發而來，鳥類會朝著食物豐盛的地方移動，鳥類移動的指導思想有兩點。1是每只鳥自身的移動過程中記下了自己曾遇到過的最好的食物所在的位置。2是整個鳥群中的鳥類在覓食過程中會交流自己所遇到的最好食物所在位置，會通知其他鳥過來。這兩點就是鳥類的移動規則。

更新公式

有了基本思想，那鳥類覓食過程中的移動方式也就是優化算法的迭代公式被總結如下：

v(i+1) = w * v(i) + c1 * rand(0, 1) * (pbest - x(i)) + c2 * rand(0, 1) * (gbest - x(i))

x(i + 1) = x(i) + v(i + 1)

w = (wini - wend) * (Gk - g) / Gk + wend

v 代表了鳥個體的移動方向和移動距離，x 代表了鳥個體所處的位置。
【1】 式1中，是鳥速度和方向的更新公式。w 是慣性因子,用式3計算。c1, c2是學習因子，通常都等于2。rand(0, 1) 是 (0, 1) 之間的隨機數。pbest 是鳥個體歷史移動過程中的最優位置，和x同類型。gbest 是整個鳥群的位置最優值，和 x 同類型。
【2】 式2中，是鳥位置的更新公式。
【3】 式3中，是2慣性因子的更新公式。wini 是初始慣性權值，一般取0.9。wend 是迭代之最大代數時的慣性權值，一般取0.4。Gk 是最大迭代代數。g 是當前迭代代數。

算法流程

算法流程：

抽象出的鳥類數據結構

根據基本思想和移動公式，抽象出鳥類個體數據結構和算法參數結構：

struct particle{vtype v;xtype x;pbest p; /* 個體極值 */fitness f;/* 個體歷史最優適應度 */ };struct psopara{wtype w; /* 慣性因子 */ctype c; /* 學習因子 */gbest g; /* 全局極值 */int Gk; /* 最大迭代次數 */int N; /* 種群大小 */fitness f;/* 最優適應度 */ };

C語言實現

以計算函數 f(x) = x1 ^ 2 + x2 ^ 2 的最小值為例，設計代碼如下：

初始化種群

/* func: 初始化種群* argu: 種群大小* retu: 種群數組* date: 2019-11-29*/ struct particle *particle_init(int n) {struct particle *p = (struct particle*)malloc(n * sizeof(struct particle));for(int i = 0; i < n; ++i){p[i].v.x1 = (float)(rand()%10000) / 100.0f;p[i].v.x2 = (float)(rand()%10000) / 100.0f;p[i].x.x1 = (float)(rand()%10000) / 100.0f;p[i].x.x2 = (float)(rand()%10000) / 100.0f;p[i].p = p[i].x;p[i].f = mypso_cal_fitness(p[i].p);// mypso_display_fitness(p[i].p);}return p; }

粒子更新

/* func: 粒子更新* argu: 參數，粒子，迭代代數* retu: 無，以傳地址的方式對粒子進行更新* date: 2019-11-29*/ void mypso_x_v_type(struct psopara *pp, struct particle *pt, int g) {wtype w = (W_INI - W_END) * (pp->Gk - g) / pp->Gk + W_END;/* 更新速度 */pt->v.x1 = w * pt->v.x1 + pp->c.c1 * rand_0to1() * (pt->p.x1 - pt->x.x1) + pp->c.c2 * rand_0to1() * (pp->g.x1 - pt->x.x1);pt->v.x2 = w * pt->v.x2 + pp->c.c1 * rand_0to1() * (pt->p.x2 - pt->x.x2) + pp->c.c2 * rand_0to1() * (pp->g.x2 - pt->x.x2);/* 更新位置 */pt->x.x1 = pt->x.x1 + pt->v.x1;pt->x.x2 = pt->x.x2 + pt->v.x2;/* 更新個體歷史極值 */fitness f = mypso_cal_fitness(pt->x);if(f < pt->f){pt->f = f;pt->p = pt->x;} }

全局極值計算

/* func: 更新全局極值* argu: 種群數組* retu: 無，以傳地址的方式改變全局極值* date: 2019-11-29*/ void mypso_gbest(struct psopara *pp, struct particle *pt) {for (int i = 0; i < pp->N; ++i){if(pp->f > pt[i].f){pp->f = pt[i].f;pp->g = pt[i].p;}}// mypso_display_fitness(pp->g, pp->f); }

適應度計算

/* func: 計算適應度函數* argu: 位置* retu: 適應度* date: 2019-11-29*/ fitness mypso_cal_fitness(xtype x) {return x.x1 * x.x1 + x.x2 * x.x2; }

主循環

int main(int argc, char const *argv[]) {struct psopara pp;struct particle *pt;platform_init(0);mypso_init(&pp);pt = particle_init(pp.N);mypso_gbest(&pp, pt);for (int i = 1; i <= pp.Gk; ++i){for (int j = 0; j < pp.N; ++j){mypso_x_v_type(&pp, &pt[j], i);}mypso_gbest(&pp, pt);mypso_display_fitness(pp.g, pp.f, i);}mypso_end(pt);return 0; }

實驗結果
共迭代一百次，90代左右找到全局最優值。

代碼地址

本打算設計一套通用的粒子群算法代碼，奈何水平有限，只能拋磚引玉。已將代碼上傳至GitHub，希望能完善代碼倉庫。之后還會有其他演化算法的C語言實現加入，力求改造封裝，提高程序設計水平。
GitHub地址：https://github.com/worangnidongdong/evolutionary-computation-C
link.

參考

參考：https://blog.csdn.net/daaikuaichuan/article/details/81382794
link.

總結

以上是生活随笔為你收集整理的粒子群算法及C语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。