粒子群算法

简述

粒子群算法就像他的名字，就是一群粒子，每个粒子都在经行搜索，而且搜索行为在不同程度上受其他粒子的影响，同时这些粒子还具备对所经历最佳位置的记忆能力，即其搜索行为在受其他个体影响的同时还受到自身经验的引导。基于独特的搜索机制，粒子群算法首先生成初始种群，即在可行解空间和速度空间随机初始化粒子的速度与位置，其中粒子的位置用于表征问题的可行解，然后通过种群间粒子个体的合作与竞争来求解优化问题。

基础知识

粒子群算法没有比较复杂的公式，它主要是速度大小的计算，在优化问题中，速度的方向都是会受到当前最优解的影响的，经可能像最优解的方向移动。面对不同的优化问题，粒子群算法也会有不同的模型来求解。首先有如下定义，X为随机生成的粒子群，V为随机生成的速度，P_best为至今每个位置生成的最优个体，g_best为全局最优解

基本定义

基本粒子群算法

基本粒子群算法的速度变化和粒子变化如下式所示

基本粒子群算法
其中c₁c₂是学习因子，也成为加速常数，r₁r₂是[0, 1]的随机数，增加了粒子飞行的随机性。速度变化公式右边由三部分组成：第一部分为“惯性”或“动量”部分，反映了粒子的运动“习惯”， 代表粒子有维持自己先前速度的趋势；第二部分为“认知”部分，反映了粒子对自身历史经验的记忆或回忆，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为“社会”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势。

标准粒子群算法

标准粒子群算法的速度变化和粒子变化如下式所示

标准粒子群
式中惯性权重表示在多大程度上保留原来的速度: w较大，则全局收敛能力较强，局部收敛能力较弱;较小，则局部收敛能力较强，全局收敛能力较弱。当w=1时， 与基本粒子群算法完全一样，表明带惯性权重的粒子群算法是基本粒子群算法的扩展。实验结果表明：w在0.8~1.2之间时，粒子群算法有更快的收敛速度;而当w>1.2时，算法则容易陷入局部极值。当然权重是个随之搜索的进行而变化的，在搜索初期可以较大方便扩散粒子，后前较小，方便粒子收敛。书中也有一个通用的公式
权重变化
式中: T_max表示 最大进化代数; W_min表示最小惯性权重; W_max表示最大惯性权重; t表示当前迭代次数。在大多数的应用中，W_min = 0.4, W_max = 0.9

压缩因子粒子群算法

压缩因子粒子群

其中λ为压缩因子的计算如下

压缩因子

离散粒子群算法

离散粒子

其中r为[0, 1]中的随机数

粒子群算法流程

粒子群算法基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索[13]，其流程如下:
(1)初始化粒子群，包括群体规模N，每个粒子的位置x_i和速度v_i。
(2)计算每个粒子的适应度值fit[i]。
(3)对每个粒子，用它的适应度值fit[i]和个体极值P_best(i)比较。如果fit[i] < P_best (i)，则用fit[i]替换掉phest
(4)对每个粒子，用它的适应度值fit[i]和全局极值S_best比较。如果fit[i]<gbest，则用fit[i]替换gbest。
(5)迭代更新粒子的速度v_i和位置x_i
(6)进行边界条件处理。
(7)判断算法终止条件是否满足:若是，则结束算法并输出优化结果;否则返回步骤(2)。