粒子群算法的那些事

用户7506105

发布于 2021-08-09 14:57:59

3910

发布于 2021-08-09 14:57:59

文章被收录于专栏：碎片学习录碎片学习录

粒子群算法，顾名思义是仿生一大堆粒子的整体行为的一种启发式算法，谈到粒子群算法就不得不提到模拟鸟类群集行为的Boid模型

Boid模型

Boids 是涌现行为的一个例子，其描述了鸟群中的个体如何根据周边同伴的位置和速度移动，主要有几个特点

冲突避免: 鸟群在一个有限的空间内飞动，每只鸟有自己独立的移动意志但是却不会影响别的鸟，会自发避免碰撞与争执
速度匹配：个体必须配合鸟群中心的移动速度，包括方向和速率上都必须相互配合
群体中心化：即个体倾向于鸟群中心移动(物以类聚不掉队)，并配合中心向目标方向前进(比如大雁南飞)

粒子群算法的一些假设和前提条件是基于Boid模型的，它的本质是初期粒子可能呈现杂乱无章随机的排布，但是到了最后通过各种因素一定会朝向一个目标收敛，每个粒子可以看成是自变量向量，粒子会不断更新，从而不断更新自变量向量达到搜索解空间的效果，粒子根据自己曾经寻找目标的经验和其他粒子信息共享，绝大部分鸟粒子不断向目标迈进，经过有限次位移迭代，绝大多数粒子就会聚集在一起并达到离目标近在咫尺的地方

核心思想

首先需初始化化各个粒子(鸟)的在空间中的位置和速度，一般采用对称初始化随机分布策略，这样粒子在最开始可以落到搜索空间的任意位置，这样有助于避免陷入某一个局部区域
正如人类在对待解决的问题或待选择的做决策一样，往往会综合自己经验和周围人的行为获取知识两种途径一样，前者主要是根据以往的尝试自身的储备，后者主要是见贤思齐，如此一来就需要群体信息共享和不断更新自身经验，当群体中所有个体都经过这样迭代之后，那么必将会逐渐朝向全局最优的目标迈进(这也是人生哲理之一)
量化自身经验的手段是利用当前的信息估计现在的自己对于达到目标有多大的贡献值(即对于达到目标有多大适应值)，然后不断记住自己最好的位置(自己的局部最优)，所以所有粒子的局部最优就可以找到全局最优，即同步效应，朝着最优的方向移动(每个个体看成是一个解)

量化

将每个个体看成一个粒子，假设D维的搜索空间中有m只鸟，第i只鸟的位置为

x_i = (x_i^1,x_i^2,...,x_i^D)

,每只鸟是一个潜在解，将鸟的位置

X_i

代入待优化的目标函数算出适应值，根据适应值大小衡量优劣，第i只鸟的最好位置记为

p_i = (p_i^1,p_i^2,...,p_i^D)

,整个群体所有粒子经历的最好位置为

p_s = (p_s^1,p_s^2,...,p_s^D)

,粒子速度为

V_i = (v_i^1,v_i^2,...,v_i^D)

更新速度和位置(算法核心),更新公式为

v_i^d = \omega v_i^d + c_1 r_1 (p_i^d - x_i^d) + c_2 r_2(p_g^d - x_i^d)

x_i^d = x_i^d + \alpha v_i^d

p_g

的出现是为了共享信息(

p_g

是当前迭代情况下所有粒子最优适应度的位置,向强者看齐），

p_i

的出现是为了记住自己的经验

式中

\omega

是惯性因子，非负数，

c_1,c_2

是加速常数，也是非负数，

r_1,r_2

是满足[0,1]上均匀分布的随机数，

\alpha

是约束因子，目的是控制速度，约束速度

速度是有限制的(可以作为有约束优化的切入点)

v_i^d \in [-v_{max}^d, v_{max}^d]

当某个粒子更新后的速度超过了最大（小）飞翔速度，则这个时候就规定此时的速度取最大（小）飞翔速度,一般是约束边界

迭代终止条件一般达到预定最大迭代次数或粒子群目前为止搜索到的最优位置满足目标函数的最小容许误差即可

方法步骤

1、初始化粒子群速度和位置，惯性因子，加速常数，最大迭代次数，算法终止的最小误差
2、评价每个粒子的初始适应值，即代入目标函数
3、将初始适应值作为当前粒子的局部最优值(因变量)，且将位置作为当前的局部最优所在的位置(自变量)
4、将所有粒子中的最佳局部最优(初始适应值)作为当前全局最优值，并将其作为当前的全局最优值(最强的那个)，最佳位置最为全局最优的位置
5、代入速度更新关系式，更新粒子的飞行速度，并限幅处理，使其不能超过该粒子最大的粒子飞行速度
6、然后代入位移更新表达式，更新每个粒子的位置
7、对每个粒子比较每个粒子的适应值是否比历史的局部最优值好，如果好的话则当前适应值作为粒子的局部最优值，对应位置作为粒子的局部最优的位置
8、在当前粒子群中找出全局最优值，并将对应的位置作为全局最优的位置
9、重复5~9，直到满足设定的最小误差或达到最大迭代次数
10、输出最优值和位置以及其他粒子的局部最优值和位置

一些参数的选取

1、粒子数m，一般选20~40,粒子数越多搜索范围越大，但是一般30个左右就够了
2、惯性因子

\omega

越大，粒子飞翔幅度越大，全局最优搜索能力越强，但局部寻优能力较弱，用来控制历史速度对当前速度的影响程度，决定了粒子对当前速度继承的多少，越大表明速度更新的幅度越大，因此更加偏离原先的寻优轨道，较好的策略是惯性因子随着迭代的次数不断减小，这样在后期就利于寻找局部最优解

3、加速常数c1,c2,一般都取2，衡量自身经验与群体经验在运动中的比重
4、最大飞翔速度，可以防止搜索范围毫无意义地扩大发散，防止速度过大直接俯冲过最优目标解，一般根据实际问题讨论

思想进阶

粒子群算法可能会容易有一些问题

粒子容易飞跃局部最优位置，造成局部搜索能力差，精度不高
如果适应度目标函数较为慢收敛，也容易出现粒子抱团，飞行速度为0的情况
较为相信别人的话导致一大堆粒子陷入别人自以为的最优位置里面，而这个所谓的别人一直一览众山小速度近乎不更新，从而得到局部极值的情况

遇到这些问题，第一也是最重要的应该是明白粒子在哪可以有概率跳出局部最优(该信别人多一些还是信自己多一些？是否可以动态调整加速常数？)，第二个是如果问题是有约束优化问题的话采用万能方法罚函数法，将问题转化为对正则系数的优化选取上(拉格朗日乘数法)，变成无约束规划，第三个就是挖掘更多的约束，用最大（小）飞翔速度来限制粒子

笔者较为喜欢该算法所折射出的一些道理，前路漫漫，集众家之长地向强者学习的大背景下也不要忽视自身的经验和所得！还有就是只有自身知识积累到一定高度后才能更有机会地融入更高的圈子！

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-06-21，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自碎片学习录微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度