博客

Particle Swarm Optimization

  • Post author:
  • Post category:其他



1、粒子群优化算法介绍：

粒子群优化算法(PSO：Particle swarm optimization) 是一种进化计算技术（evolutionary computation）。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想：

同种动物之间的社会信息共享提供了一种进化优势，通过群体中个体之间的协作和信息共享来寻找最优解。

论文：Kennedy J, Eberhart R. Particle swarm optimization[C]//Proceedings of ICNN’95-international conference on neural networks. IEEE, 1995, 4: 1942-1948.


2、粒子群算法的演变历程

2.1


Nearest




Neighbor




Velocity




Matching(最近领域速度匹配)




and




Craziness



最近领域速度匹配

：假设有n只鸟，每只鸟是环面像素网格的一个点，有X速度和Y速度两个方向。在每次迭代的过程中，设置一个循环：对于每个鸟，如果有另一只鸟距离这只鸟最近，就将这只鸟的X和Y分配给另一只鸟。这个简单的规则就创造了同步的运动。


Craziness



：


随着迭代的继续，鸟群的的飞行方向就会保持不变了。我们要引入一个”Craziness”的随机变量，在每次迭代的过程中，使得随机选择的X和Y速度都会增加一些变化。

2.2


The




Cornfield Vector(康菲尔德矢量)


当我们放置一个喂鸟器，一会就会有很多鸟过来，虽然事先这些鸟并不知道这里有食物。这说明了他们之间存在协作和信息共享的情况。

cornfield vector：(X,Y)向量组表示鸟的位置。每个鸟根据下面的公式来获得当前位置的评估值：

\text { Eval }=\sqrt{(\text { presentx }-100)^{2}}+\sqrt{(\text { presenty }-100)^{2}}

所以(100,100)位置的评估值就是0。

现在假设每只鸟飞过很多地方，而(100,100)就是食物的位置。

而每只鸟记录下走过的路途中距离食物最近的位置pbest[n]

，n只鸟就可以形成2个一个n*1的向量，记为

pbestx[n]、pbesty[n]

。而下一步n只鸟的位置为vx[n]、vy[n]。假设n只鸟之间不存在信息共享，那么n只鸟寻食物的流程如下：

  1. for iter < iter_num
  2. for i < n
  3. if vx[i] > pbestx[i] ：vx[i] = vx[i] – rand() * p_increment
  4. else: vx[i] = vx[i] + rand() * p_increment
  5. if vy[i] > pbesty[i] ：vy[i] = vy[i] – rand() * p_increment
  6. else：vy[i] = vy[i] + rand() * p_increment
  7. if pbest[i] < Eval(vx[i],vy[i])： 不做改变
  8. else pbest[i] = Eval(vx[i],vy[i]), pbestx[i] = vx[i], pbesty[i] = vy[i]
  9. end
  10. end

现在让n只鸟之间存在信息共享：我们取pbest[n]中最小的数对应的索引为gbest，对应的值为pbest，n只鸟当前位置为presentx[n]、presenty[n]，下一步n只鸟的位置为vx[n]、vy[n]。那么n只鸟寻食物流程为：


  1. if presentx[] > pbestx[gbest] then


    vx[]


    =


    vx[]


    –


    rand()


    *g_increment

  2. if presentx[] < pbestx[gbest] then


    vx[]


    =


    vx[] +




    rand()


    *g_increment

  3. if presenty[] > pbesty[gbest] then


    vy[]


    =


    vy[]


    –


    rand()


    *g_increment

  4. if presenty[] < pbesty[gbest] then


    vy[]


    =


    vy[] +




    rand()


    *g_increment

  5. presentx = vx[], presenty = vy[]
  6. Eval(vx[],vy[]), 如果Eval[n]中有小于pbest[n]的值，将该值覆盖到pbest[n]向量的对应位置(更新pbest[n])。

如果p_increment，g_increment过大，鸟群会比较快地接近目标，但是最终可能无法寻得最优位置，可能会在最优位置处徘徊；如果p_increment，g_increment过小，鸟群会比较慢地接近目标，但是可以更好地寻得最优位置，但是也有可能存在局部最优的问题。

2.3 消除辅助变量

上述过程我们消除了“

最近领域速度匹配”和

“Craziness”的随机变量，但是我们引入了pbest[n]和gbest。

pbest[n]和gbest是十分重要的，gbest在概念上类似于公开的知识，或个人寻求达到的群体规范或标准。也是群体之间信息交互的重要方式。

2.4 多维搜索

这似乎是一个简单的步骤来改变presentx[n]和presenty[n](以及vx[n]和vy[n])，从一维数组转变到Dxn矩阵，其中D是任意维数，n是代理的数量。


2.5

Acceleration


by


Distance(距离加速度)


为了消除判断这个流程以及将变量扩充到D维，我们将上述：

if presentx[] > pbestx[gbest] then vx[]


=


vx[]


–


rand()


*g_increment

改为：

vx[ ][ ]=v x[ ][ ]+\text { rand }()^{*} p_{-} \text {increment } *(p \text {bestx }[ ][ ]-\text { presentx }[ ][ ])


2.6当前简化的版本

人们很快意识到，没有什么好的方法来猜测p_increment还是g_increment应该更大。因此这些属性也在算法中剔除了，通过常数2来代替。替代后的表达式为：

xv[][] = vx[ ][ ] + 2*rand()*(pbestx[ ][ ] – presentx[ ][ ]) + 2*rand()*(pbestx[ ][gbest] – presentx[ ][ ])

2*rand()*(pbestx[ ][ ] – presentx[ ][ ]) 这一部分主要是往小鸟自己熟悉的最佳位置靠拢，2*rand()*(pbestx[ ][gbest] – presentx[ ][ ])这一部分主要是小鸟往所有小鸟中熟悉的最佳位置靠拢。

2.7其他的版本

xv[][] = 2*rand()*(pbestx[ ][ ] – presentx[ ][ ]) + 2*rand()*(pbestx[][gbest] – presentx[ ][ ])，但是在论文中，作者表示这种位置更新方式的效果是不如上述的位置更新方式。

3. 算法的实现和测试

clc;clear;clearvars;
% 随机生成5个数据
num_initial = 5;
num_vari = 5;
% 搜索区间
upper_bound = 5;
lower_bound = -5;
iter = 100;
% 随机生成5个数据,并获得其评估值
sample_x = lhsdesign(num_initial, num_vari).*(upper_bound - lower_bound) + lower_bound.*ones(num_initial, num_vari);
sample_y = f(sample_x);

% 初始化一些参数
pbestx = sample_x;
pbesty = sample_y;
% 当前位置信息presentx
presentx = lhsdesign(num_initial, num_vari).*(upper_bound - lower_bound) + lower_bound.*ones(num_initial, num_vari);
vx = sample_x;
[fmin, gbest] = min(pbesty);

for i = 1 : iter
    r = rand(num_initial, num_vari);
    % pso更新下一步的位置,这里可以设置一下超过搜索范围的就设置为边界
    vx = vx + 2 * r .* (pbestx - presentx) + 2 * r .* (pbestx(gbest, :) - presentx);
    % vx = 2 * r .* (pbestx - presentx) + 2 * r .* (pbestx(gbest, :) - presentx);
    vx(vx > upper_bound) = 5;
    vx(vx < lower_bound) = -5;
    vy = f(vx);
    presentx = vx;
    % 更新每个单独个体最佳位置
    pbestx(vy < pbesty, :) = vx(vy < pbesty, :);
    pbesty = f(pbestx);
    % 更新所有个体最佳位置
    [fmin, gbest] = min(pbesty);
    fprintf("iter %d fmin: %.4f\n", i, fmin);
end
function f = f(x)
% 极小值为0,(0,0....)
f = sum(x.*x, 2);
end

测试结果：

iter 1 fmin: 30.3861

iter 2 fmin: 29.7636

iter 3 fmin: 29.7636

iter 4 fmin: 20.1373

iter 5 fmin: 20.1373

iter 6 fmin: 11.8266

iter 7 fmin: 11.8266

iter 8 fmin: 11.8266

iter 9 fmin: 10.3098

iter 10 fmin: 10.3098

iter 11 fmin: 4.6355

iter 12 fmin: 4.6355

iter 13 fmin: 4.6355

iter 14 fmin: 4.6355

iter 15 fmin: 4.6355

iter 16 fmin: 3.6638

iter 17 fmin: 3.4861

iter 18 fmin: 3.2420

iter 19 fmin: 3.2420

iter 20 fmin: 1.6142

iter 21 fmin: 1.6142

iter 22 fmin: 1.6142

iter 23 fmin: 1.6142

iter 24 fmin: 1.4709

iter 25 fmin: 1.3968

iter 26 fmin: 0.7710

iter 27 fmin: 0.4064

iter 28 fmin: 0.4064

iter 29 fmin: 0.3684

iter 30 fmin: 0.3477

iter 31 fmin: 0.3434

iter 32 fmin: 0.3390

iter 33 fmin: 0.2561

iter 34 fmin: 0.1161

iter 35 fmin: 0.1161

iter 36 fmin: 0.1161

iter 37 fmin: 0.1161

iter 38 fmin: 0.1161

iter 39 fmin: 0.1161

iter 40 fmin: 0.1057

iter 41 fmin: 0.0967

iter 42 fmin: 0.0967

iter 43 fmin: 0.0885

iter 44 fmin: 0.0880

iter 45 fmin: 0.0864

iter 46 fmin: 0.0858

iter 47 fmin: 0.0850

iter 48 fmin: 0.0840

iter 49 fmin: 0.0839

iter 50 fmin: 0.0838

iter 51 fmin: 0.0775

iter 52 fmin: 0.0775

iter 53 fmin: 0.0766

iter 54 fmin: 0.0766

iter 55 fmin: 0.0737

iter 56 fmin: 0.0665

iter 57 fmin: 0.0609

iter 58 fmin: 0.0604

iter 59 fmin: 0.0501

iter 60 fmin: 0.0432

iter 61 fmin: 0.0364

iter 62 fmin: 0.0296

iter 63 fmin: 0.0276

iter 64 fmin: 0.0224

iter 65 fmin: 0.0142

iter 66 fmin: 0.0091

iter 67 fmin: 0.0071

iter 68 fmin: 0.0071

iter 69 fmin: 0.0066

iter 70 fmin: 0.0057

iter 71 fmin: 0.0049

iter 72 fmin: 0.0044

iter 73 fmin: 0.0042

iter 74 fmin: 0.0041

iter 75 fmin: 0.0040

iter 76 fmin: 0.0040

iter 77 fmin: 0.0040

iter 78 fmin: 0.0040

iter 79 fmin: 0.0039

iter 80 fmin: 0.0039

iter 81 fmin: 0.0039

iter 82 fmin: 0.0038

iter 83 fmin: 0.0038

iter 84 fmin: 0.0038

iter 85 fmin: 0.0038

iter 86 fmin: 0.0038

iter 87 fmin: 0.0038

iter 88 fmin: 0.0038

iter 89 fmin: 0.0038

iter 90 fmin: 0.0038

iter 91 fmin: 0.0038

iter 92 fmin: 0.0037

iter 93 fmin: 0.0037

iter 94 fmin: 0.0037

iter 95 fmin: 0.0037

iter 96 fmin: 0.0037

iter 97 fmin: 0.0037

iter 98 fmin: 0.0037

iter 99 fmin: 0.0037

iter 100 fmin: 0.0037

后续改进的粒子群优化算法后续也有介绍。


版权声明：本文为qq_42148307原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。