粒子群优化算法.pdf

粒子群优化算法 1 粒子群优化算法的起源 粒子群算法(Particle Swarm Optimization, PSO)最早是由 Eberhart 和 Kennedy 于 1995 年提出，它的基本概念源于对鸟群觅食行为的研究设想这样一个场景: 一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在 哪里， 但是它们知道当前的位置离食物还有多远那么最简单有效的就是搜寻目 前离食物最近的鸟的周围区域 PSO 算法就从这种生物种群行为特性中得到启发并用于求解优化问题在 PSO 中， 每个优化问题的潜在解都可以想象成 d 维搜索空间上的一个点， 我们称 之为“粒子”（Particle） ，所有的粒子都有一个被目标函数决定的适应值(Fitness Value )，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随 当前的最优粒子在解空间中搜索 Reynolds 对鸟群飞行的研究发现 鸟仅仅是追 踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下. 即复杂的全局行为是由简单规则的相互作用引起的 2 标准粒子群算法 速度更新公式及位置更新公式如下所示： 1 12 2(1)( )(( )( ))(( )( ))(1)( )(1)iiiigiiiitwtc rttc rttttt vvpxpxxxv其中，( )itv表示在迭代时刻t，粒子i的速度；( )itx表示粒子的位置；( )itp表示粒子i所经历的最优位置(pbest)；( )gtp表示种群中运行最优粒子的位置(gbest)；1r和2r是两个在[0,1]均匀分布的随机数；w表示惯性权重， 当[0.9,1.2]w时， 算法具有较理想的搜索性能，1c和2c表示粒子的加速度常数， 通常在[0,2]取 值。

引入研究 PSO 常用的两个概念： 1、 探索(exploration)是指粒子在一定程度上 离开原先的搜索轨迹， 向新的方向进行搜索， 体现了一种向未知区域开拓的能力， 类似于全局搜索；2、开发(exploitation)指粒子在一定程度上继续在原先的搜索轨 迹上进行更细一步的搜索， 主要指对探索过程中所搜索到的区域进行更进一步的 搜索，类似于局部搜索 惯性权重w较大时探索能力强，w较小时开发能力强下面给出w对算法的 影响分析： (1) 如果=0w时，当前的粒子速度取决于 pbest 和 gbest在当前迭代时刻， 位于全局最优位置的那些粒子将保持静止，而其他粒子将向 pbest 和 gbest 的加 权中心1 12 21 12 2()/()igc rc rc rc rpp 飞行此时，种群收敛到 gbest 所在的位置，算法变成了一个局部算法 (2) 如果0w ，当前粒子的速度将受到前一时刻速度的影响，粒子有扩大 空间、探索新区域的趋势，对w进行调整，可以权衡全局和局部的搜索能力 3 粒子群优化算法特点 和其他算法相比，粒子群优化算法主要有以下特点: (1) PSO 算法简单，需要调节的参数不多，尤其是算法在引入惯性权重后，许多 情况下可以按经验值设置参数即可获得较好的收敛性。

(2) PSO 算法采用实数编码，可直接取目标函数本身作为适应度函数，根据目标 函数值进行迭代搜索 (3) PSO 算法的各粒子间信息交流采用单向的信息流动方式，整个搜索更新过程 是跟随当前最优解的过程 (4) PSO 算法的各粒子具有记忆性，使得邻域算子不能破坏己搜索到的较优解 (5) PSO 算法根据粒子速度来决定搜索路径， 且沿着梯度方向搜索， 搜索速度快， 在大多数的情况下，所有的粒子能收敛于最优解但是，粒子群优化算法并 不保证一定能找到最优解 这是由于PSO算法在优化过程中存在着一些问题， 这些问题使得粒子在搜索过程中易陷入局部最优，导致算法“早熟” ，从而降 低了算法的稳定性 4 验证粒子群算法 (1) 测试函数12ysin()cos()xx其中12,( 5,5)x x  ，图像如下： 由上图可知，该函数在取值范围内的最小值为-2 粒子群算法优化参数设置 惯性权重 W 加速因子 C1 加速因子 C2 种群规模 迭代次数 0.9 1.496172 1.496172 20 100 优化结果如下： 由以上对比可知，对于函数12ysin()cos()xx，粒子群算法满足要求。

视角 1 视角 2 角度 1 角度 2 (2) 测试函数 Rosenbrock 函数22 2 121(1)100()yxxx其中12,( 5,5)x x  ， 图像如下： 由上图可知，该函数在取值范围内的最小值为 0 粒子群算法优化参数设置 惯性权重 W 加速因子 C1 加速因子 C2 种群规模 迭代次数 0.9 1.496172 1.496172 20 100 优化结果如下： 由以上对比可知，对于函数22 2 121(1)100()yxxx，粒子群算法满足要求 4 粒子群算法改进 我们希望粒子在开始时探索能力较强，以便扩大搜索范围，避免过早收敛； 后期开发能力较强，寻求已知区域的最优解 在算法开始时，可给w赋予较大正值，随着搜索的进行，可以线性地使w逐 渐减小，这样可以保证在算法开始时，各粒子能够以较大的速度步长在全局范围 内探测到较好的区域；而在搜索后期，较小的w值则能保证粒子能够在极值点周 围做精细地搜索，从而使算法有较大的概率向全局最优解位置收敛 目前， 采用较多的动态权重值是Shi提出的线性递减权值策略， 表达式如下： maxmin max max()wwtwwT其中，maxT表示最大进化代数；minw表示最小惯性权重；maxw表示最大惯性权重；t表示当前迭代次数。

在大多数应用中，max0.9w，min0.4w。