泛统计理论初探——初探粒子群算法

神经网络学习-初探粒子群算法

理解粒子群算法思路
   在上一篇介绍搜索的文章中&＃xff0c;我们谈到了关于模拟退火算法的思路和算法实现步骤&＃xff0c;模拟退火算法是一种启发式的搜索方法&＃xff0c;可以使用在各个领域。本次文章中需要介绍的是粒子群算法&＃xff0c;该算法是一种基于鸟类群体寻找食物的算法&＃xff0c;因而也称之为“鸟群算法”&＃xff0c;通过整个鸟群的集体搜索&＃xff0c;找出全局的最优点&＃xff0c;因此该算法其实也是一种启发式搜索算法&＃xff0c;并且是类似“群智感知”的一种处理思路。该算法的核心思路其实是通过信息的共享&＃xff0c;根据群体的最优和个体的最优进行选择&＃xff0c;反复进行位置的移动&＃xff0c;最终寻找到全局的最优点。在粒子群算法的解决过程中&＃xff0c;每一个可能的可行解都是搜索空间的一个粒子&＃xff0c;或者说是一只鸟&＃xff0c;而整个问题的最优解就是整个鸟群寻找的食物所在地。
   粒子群算法中每一个粒子都有两个特征&＃xff0c;第一个是速度特征、第二个是位置特征&＃xff1b;其中速度特征是决定粒子在下一次的移动方向和速度&＃xff0c;而位置特征是决定粒子在整个空间的位置&＃xff0c;可以用三维空间去理解这个思路&＃xff0c;但实际的问题特征维度较高&＃xff0c;可能是几十个维度或者几百个维度&＃xff0c;所以初学者只需要理解三维空间粒子的移动即可。每一次粒子的移动都是根据目标移动公式去计算当前的目标值&＃xff0c;最终的目标是群体的目标值最小或者是最大&＃xff0c;整个粒子群在移动的时候&＃xff0c;每个粒子可以根据自己历史的位置信息进行学习&＃xff0c;也可以根据群体的最优粒子经验去学习&＃xff0c;以此去综合考虑下一次移动的方向和速度&＃xff0c;经过反复的迭代或者说移动&＃xff0c;最终整个群体的粒子就会收敛稳定在一个最优解的位置。

   对于粒子群算法的大致步骤&＃xff0c;我们可以进行一个总结&＃xff0c;主要是分为以下5个步骤&＃xff1a;
   1、相关参数设置初始化与群体粒子信息初始化&＃xff0c;通过随机初始化的方法&＃xff0c;并且根据初始化的信息进行计算当前群体的全局最优位置和每个个体的最优位置。
   2、设置好迭代次数和迭代终止条件&＃xff0c;并且确定初始化后当前的迭代次数是1次。
   3、速度信息和位置信息更新&＃xff0c;即对于每一个粒子来说&＃xff0c;去更新它们的速度向量和位置向量。
   4、计算局部位置和全局位置的向量&＃xff0c;更新每个粒子的局部最优解和整体粒子群的全局最优解。
   5、判断是否满足终止条件&＃xff0c;即如果满足最大迭代次数或者满足终止条件就跳出循环&＃xff1b;否则继续进行迭代&＃xff0c;继续跳转到步骤3。
根据基本步骤的理解后&＃xff0c;我们对于具体的速度向量和位置向量的计算公式来进行分析和介绍&＃xff0c;计算公式如下所示。

   在上面的公式&＃xff0c;下标i表示第i个粒子&＃xff0c;上标d表示第d个维度的值&＃xff1b;w是惯性因子&＃xff0c;是一个非负数&＃xff1b;r1和r2是[0,1]范围内变化的随机数&＃xff0c;α是约束因子。从上述公式我们可以发现&＃xff0c;首先是对速度的计算&＃xff0c;每个粒子的速度都可以被pi所影响&＃xff0c;也就是该粒子的历史最优信息&＃xff1b;同时也可以被pg所影响&＃xff0c;也就是群体的最优信息。在计算了速度后&＃xff0c;通过第二个公式可以计算出下一步的移动位置&＃xff0c;从而按照公式进行迭代和计算。
   对于上述的参数&＃xff0c;我们在设定初始化参数的时候需要进行确定&＃xff0c;一般来说&＃xff0c;粒子数量设为20到50个&＃xff0c;对于一些计算资源宽裕的情况或者问题复杂的情况&＃xff0c;需要设定100到300个粒子。显然粒子的数量越大&＃xff0c;搜索的范围就越大&＃xff0c;也容易找到全局的最优解&＃xff0c;但是非常消耗资源并且计算的时间较长。对于惯性因子w&＃xff0c;可以取0.6至0.8范围的值&＃xff0c;该参数值对于整个算法的收敛效果有较大的影响&＃xff0c;如果设置的较大会使得粒子有很大的惯性&＃xff0c;也就是很难改变方向&＃xff0c;并且收敛较为困难&＃xff0c;所以w设置的较大可以帮助全局搜索、设置的较小可以促进局部搜索。对于常数c1和c2的设定是要看问题而定&＃xff0c;一般来说将c1和c2设定的大小一样都是等于2&＃xff0c;也就是默认了在粒子迭代的过程中&＃xff0c;自身经验和群体经验在迭代步骤的重要性是基本等同的。
   总的来说&＃xff0c;粒子群算法是一种适用于不同搜索问题的智能启发式搜索方法&＃xff0c;通过对于参数的设置&＃xff0c;可以决定是看重于全局的搜索或者是局部的搜索。而该方法还有延伸的方法&＃xff0c;也就是所谓的局部粒子群算法&＃xff0c;通俗来说就是设定公式中的群体是部分群体&＃xff0c;选中的可以被称之为“骨干”&＃xff0c;这种方法也被称之为骨干粒子群算法。初学者在学习粒子群算法的过程中&＃xff0c;需要理解迭代的公式和里面的参数含义&＃xff0c;该算法受到参数的控制影响较大&＃xff0c;所以通常需要使用不同的参数进行多次搜索才可以。