粒子群优化

Fighting365 机器学习算法与Python学习

在机器学习问题中以及实际实践中，大多数的建模与控制问题最终都可以转化为一个约束或者无约束的优化问题，这些问题一般比较复杂，主要表现为规模大、维数高、非线性、非凸以及不可微等性质，而且由于非凸的原因往往存在较多的井点，传统的基于梯度的优化算法收敛速度快，但是对于初始值比较敏感，容易陷入局部最优(这也一直以来是bp神经网络的问题)，对于高维复杂的函数难以实现高效优化。
粒子群优化(Particle Swarm Optimization)，又称微粒群算法，是由J. Kennedy和R. C. Eberhart等于1995年开发的一种演化计算技术，来源于对一个简化社会模型的模拟。其中“群(swarm)”来源于微粒群符合M. M. Millonas在开发应用于人工生命(artificial life)的模型时所提出的群体智能的5个基本原则。“粒子(particle)”是一个折衷的选择，因为既需要将群体中的成员描述为没有质量、没有体积的，同时也需要描述它的速度和加速状态。
基本思想如下所示：
通过群体中个体间的协作和信息共享来寻找最优解，本质上是一种并行的去哪聚性随机搜索算法。算法最初是为了图形化的模拟鸟群优美而不可预测的运动。而通过对动物社会行为的观察，发现在群体中对信息的社会共享提供一个演化的优势，并以此作为开发算法的基础。通过加入近邻的速度匹配、并考虑了多维搜索和根据距离的加速，形成了PSO的最初版本。之后引入了惯性权重w来更好的控制开发(exploitation)和探索(exploration)，形成了标准版本。

从社会人之学角度而言，粒子群优化算法应用如下简单道理：即群体中的每个个体都可以从临近个体的认知经验中收益，其理论基础主要包括以下几个基本步骤：

刺激的评价
与临近的比较
对邻先近邻的模仿

PSO算法是基于群体的，根据对环境的适应度将群体中的个体移动到好的区域。然而它不对个体使用演化算子，而是将每个个体看作是D维搜索空间中的一个没有体积的微粒（点），在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第i个微粒表示为Xi = (xi1, xi2, …, xiD)，它经历过的最好位置（有最好的适应值）记为Pi = (pi1, pi2, …, piD)，也称为pbest。在群体所有微粒经历过的最好位置的索引号用符号g表示，即Pg，也称为gbest。微粒i的速度用Vi = (vi1, vi2, …, viD)表示。对每一代，它的第d维(1 ≤ d ≤ D)根据如下方程进行变化：

其中w为惯性权重(inertia weight)，c1和c2为加速常数(acceleration constants)，rand()和Rand()为两个在[0,1]范围里变化的随机值。
此外，微粒的速度Vi被一个最大速度Vmax所限制。如果当前对微粒的加速导致它的在某维的速度vid超过该维的最大速度vmax,d，则该维的速度被限制为该维最大速度vmax,d。
对公式(1a)，第一部分为微粒先前行为的惯性，第二部分为“认知(cognition)”部分，表示微粒本身的思考；第三部分为“社会(social)”部分，表示微粒间的信息共享与相互合作。

a). 初始化一群微粒（群体规模为m），包括随机的位置和速度；
b). 评价每个微粒的适应度；
c). 对每个微粒，将它的适应值和它经历过的最好位置pbest的作比较，如果较好，则将其作为当前的最好位置pbest；
d). 对每个微粒，将它的适应值和全局所经历最好位置gbest的作比较，如果较好，则重新设置gbest的索引号；
e). 根据方程(1)变化微粒的速度和位置；
f). 如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数Gmax），回到b)。

标准粒子群算法的变形
在这个分支中，主要是对标准粒子群算法的惯性因子、收敛因子（约束因子）、“认知”部分的c1，“社会”部分的c2进行变化与调节，希望获得好的效果。
惯性因子的原始版本是保持不变的，后来有人提出随着算法迭代的进行，惯性因子需要逐渐减小的思想。算法开始阶段，大的惯性因子可以是算法不容易陷入局部最优，到算法的后期，小的惯性因子可以使收敛速度加快，使收敛更加平稳，不至于出现振荡现象。经过本人测试，动态的减小惯性因子w，的确可以使算法更加稳定，效果比较好。但是递减惯性因子采用什么样的方法呢？人们首先想到的是线型递减，这种策略的确很好，但是是不是最优的呢？于是有人对递减的策略作了研究，研究结果指出：线型函数的递减优于凸函数的递减策略，但是凹函数的递减策略又优于线型的递减，经过本人测试，实验结果基本符合这个结论，但是效果不是很明显。
对于收敛因子，经过证明如果收敛因子取0.729,可以确保算法的收敛，但是不能保证算法收敛到全局最优，经过本人测试，取收敛因子为0.729效果较好。对于社会与认知的系数c2,c1也有人提出：c1先大后小，而c2先小后大的思想，因为在算法运行初期，每个鸟要有大的自己的认知部分而又比较小的社会部分，这个与我们自己一群人找东西的情形比较接近，因为在我们找东西的初期，我们基本依靠自己的知识取寻找，而后来，我们积累的经验越来越丰富，于是大家开始逐渐达成共识（社会知识），这样我们就开始依靠社会知识来寻找东西了。
2007年希腊的两位学者提出将收敛速度比较快的全局版本的粒子群算法与不容易陷入局部最优的局部版本的粒子群算法相结合的办法，利用的公式是
v＝nv(全局版本)＋（1－n）v(局部版本)
速度更新公式，v代表速度
w（k＋1）＝w(k)＋v
位置更新公式
该算法在文献中讨论了系数n取各种不同情况的情况，并且运行来了20000次来分析各种系数的结果。

这个分支主要是将粒子群算法与各种算法相混合，有人将它与模拟退火算法相混合，有些人将它与单纯形方法相混合。但是最多的是将它与遗传算法的混合。根据遗传算法的三种不同算子可以生成3中不同的混合算法。
粒子群算法与选择算子的结合，这里相混合的思想是：在原来的粒子群算法中，我们选择粒子群群体的最优值作为pg，但是相结合的版本是根据所有粒子的适应度的大小给每个粒子赋予一个被选中的概率，然后依据概率对这些粒子进行选择，被选中的粒子作为pg，其它的情况都不变。这样的算法可以在算法运行过程中保持粒子群的多样性，但是致命的缺点是收敛速度缓慢。
粒子群算法与杂交算子的结合，结合的思想与遗传算法的基本一样，在算法运行过程中根据适应度的大小，粒子之间可以两两杂交，比如用一个很简单的公式
w（新）＝n×w1＋（1－n）×w2；
w1与w2就是这个新粒子的父辈粒子。这种算法可以在算法的运行过程中引入新的粒子，但是算法一旦陷入局部最优，那么粒子群算法将很难摆脱局部最优。
粒子群算法与变异算子的结合，结合的思想：测试所有粒子与当前最优的距离，当距离小于一定的数值的时候，可以拿出所有粒子的一个百分比（如10％）的粒子进行随机初始化，让这些粒子重新寻找最优值。

最初的PSO是从解决连续优化问题发展起来的.Eberhart等又提出了PSO的离散二进制版.用来解决工程实际中的组合优化问题。他们在提出的模型中将粒子的每一维及粒子本身的历史最优、全局最优限制为1或0，而速度不作这种限制。用速度更新位置时，设定一个阈值，当速度高于该阈值时，粒子的位置取1，否则取0。二进制PSO与遗传算法在形式上很相似，但实验结果显示，在大多数测试函数中，二进制PSO比遗传算法速度快，尤其在问题的维数增加时

协同PSO，该方法将粒子的D维分到D个粒子群中，每个粒子群优化一维向量，评价适应度时将这些分量合并为一个完整的向量。例如第i个粒子群，除第i个分量外，其他D-1个分量都设为最优值，不断用第i个粒子群中的粒子替换第i个分量，直到得到第i维的最优值，其他维相同。为将有联系的分量划分在一��ƭ,����个群，可将D维向量分配到m个粒子群优化，则前D mod m个粒子群的维数是D/m的向上取整。后m－(Dmod m)个粒子群的维数是D/m的向下取整。协同PSO在某些问题上有更快的收敛速度。