粒子群算法

前言

粒子群算法是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法，通常认为它是群集智能 (Swarm intelligence, SI) 的一种。它可以被纳入多主体优化系统(Multiagent Optimization System, MAOS)。粒子群优化算法是由Eberhart博士和kennedy博士发明。（百度百科）

一、算法描述

以鸟群寻找食物为例，鸟群的鸟是可以共享信息的，类似于每只鸟都会向大家公布自己的找到的最好的进食地点。每只鸟都有自己的速度矢量，每一次遍历，每只鸟都向鸟群公布自己找到的最合适的进食地点。每只鸟通过整个鸟群找到的最优地点和自己找到的最优地点，决定下次自己飞行的方向。也就是说，如果某只鸟找到了一个最优地点，下次寻找的方向可能就会偏向这个最优地点的附近。

二、算法公式

速度更新公式：

            V(t+1)=w * V(t) + r1 * c1 * (pbest-X(t)) + r2 * c2 * (gbest - X(t) )

位置更新公式：

                 X(t+1)=X(t)+V(t+1)

V(t+1)和 X(t+1)表示t+1时刻的速度和位置，V(t)和X(t)表示t时刻的速度和位置，pbest是个体的最优位置，属于局部最优解，gbest是群体的最优位置，也称全局最优解。
V,X,w,pbest,gbest均是多维向量。V是速度矢量，X是位置坐标，w是惯性权重，也就是上一时刻对下一时刻速度的影响。
r1,r2是在(0,1)之间的随机数；
c1,c2是学习因子，一般取2。

根据公式理解粒子群算法的基本思想，下一个时刻速度受个体最优解和群体最优解影响，这个很容易理解，就是在较优解附近寻找更优解，慢慢找出全局最优解。这里有一个风险，如果鸟群太少，或者初始化速度和位置不够广泛，很容易陷入局部最优解而出不来。

三、算法流程

1、初始化
初始化惯性权重w；
设定常数：遍历次数cycle，学习因子c1,c2，群体个数n；
随机生成速度矢量V，位置坐标X；
2、运行
a.计算第i只个体下一时刻的解f_i(X_i)
b.如果f_i(X_i)<pbest_i，pbest_i=f(X_i)
c.如果f_i(X_i)<gbest，gbest=f_i(X_i)
d.重复运行2，直至计算出所有个体的个体最优解，和群体最优解。
3、更新
根据更新公式更新每个个体的速度和位置；
若cycle==0或者群体最优解保持不变，结束，输出群体最优解；
否则，返回2；

举个例子

求函数 f=sin(x)+cos(y)+z^2在范围x,y,z属于[-3,4]的最小值：
函数参数有3个，所以粒子群算法的速度和位置向量都是三维的，对应x,y,z的坐标，速度矢量表示x,y,z坐标系方向的改变大小，位置向量就是坐标系的坐标。确定好这些变量，就可以初始化速度和位置，在设定粒子群算法的常数，就可以了。
实际操作中，随机函数取值范围不合理，还是很容易陷入局部最优解的，慢慢调参就是了。

总结

不知道是因为前面写蚁群算法有了些经验还是什么，实现这个粒子群算法比蚁群算法简单多了，感觉粒子群算法比较好理解，毕竟更新公式就是以前学的向量的加减法。