标准粒子群算法的优化方式综述

吕柏行 郭志光 赵韦皓 张 凡

（中国建筑土木建设有限公司，北京 100071）

1 标准粒子群算法

Kennedy 和Eberhart 在1995 年提出经典PSO 算法，后被Shi 等修改，形成了目前的标准PSO 算法。式（1）为标准PSO 算法的速度迭代公式，其核心思想是在有限空间中创建N 个粒子，每个粒子单独搜寻最优解并将最优解由整个粒子群共享，从而达到优化的目的。

2 国内外研究应用现状及评述

由于标准粒子群算法容易陷入局部最优、收敛精度低，学者们常对粒子群算法进行优化，以完成各种实际问题的求解。本文将常用的优化方法分为五大类，包括对最大速度、惯性因子、学习因子进行改进、优化变异策略及优化编码方式。

2.1 最大速度限制值的改进

算法中常常需要用粒子的最大速度限制值vmax来限制其运动轨迹，防止粒子群快速飞过最优区域。一般算法采用单一极值限制方式，超出则取最大或最小值。

但这种方式的局限性也很明显，即每代粒子的搜索范围在整个迭代过程中不变。因此有学者采用动态限制方式：随着迭代次数的增加，降低粒子的最大速度，以保证后期精细的局部搜索[1]。其中：T 为最大迭代次数，δ 是0-1 的随机数。

2.2 惯性因子的改进

针对多目标粒子群空间优化效率较低的问题，杨震伦[5]引入了一种惯性权重周期变化的调节方法，能够在(T/m)个周期内完成反复搜索。其中m 是单个周期的迭代次数，mod(t,m)表示t 对m 取余数。

以上对于ω 的调整均为全局性的。董文永[6]提出了一种惯性权重自适应调节法，使每个粒子能够独立思考，并根据群体适应值进行动态调整：在粒子群趋同时提高ω，扩大算法的全局搜索空间，而在粒子群分散时减小ω，保证粒子的局部搜索能力。其中：f1表示粒子i 的适应值，fmin、favg分别表示粒子总体的最小适应值和平均适应值。

2.3 学习因子的改进

惯性因子决定了粒子对于上一代速度的继承量大小，而学习因子则确定了粒子对于最优位置的学习量大小，包括对个体最优和全局最优的学习。标准PSO 算法设置的固定学习比例，即c1、c2为常数，在多维且局部极值较多的函数中常表现乏力。2004 年，Ratnaweera[7]首次提出了一种随迭代次数增加而变化的学习因子优化方法，并与Shi 提出的惯性权重线性递减调节法混合共用，经Benchmark 函数集测试：c1的最佳取值区间为2.5至0.5、c2的最佳取值区间为0.5 至2.5，其表现优于同条件的固定学习因子（c1=c2=2）优化方法，其中 c1i,c1f,c2i,c2f均为常数。

但上述方法在收敛速度方面表现不佳。Chen[8]采用三角函数学习因子平衡前期全局搜索与后期全局趋同的权重，使公式转为非线性，并在多数函数中表现出了更快的收敛速度和更高的收敛精度。其中，c1、c2的取值区间仍为2.5 至0.5 与0.5 至2.5，∂=2,δ =0.5。

除了对学习因子取值的改进外，增加速度系数c3可以使学习因子受到额外的随机因素影响，从而提高算法的搜索能力。李艳丽[9]将该项速度分量设定地相对随机，从而提高粒子的全局搜索能力。其中c3为常数，Ri为随机数。

Benedetti[10]提出一种增强粒子速度记忆的改进方法，期望对环境变化做出快速响应：其第四项速度分量是基于动态变化的历史精英解集，即每次迭代时将前M 个个体最优解储存为历史精英解集，并将当前适应度最差的粒子替换为外部最优解，这在一定程度上可以克服某些干扰因素。其中H 为常数（这里取10），M 为记忆储存长度，m=1, 2,…,M，r1～ r3为随机数。

2.4 优化变异策略

变异优化分为主动变异和被动变异，即按一定规则主动触发变异或预设条件满足时被动触发变异。

2.4.1 被动变异

在精英解集连续几代无改进时，以一定的规则随机生成N个粒子取代精英解集中最差的N 个粒子，起到帮助群体跳出局部最优的作用[11]。

张建科[12]利用外推技巧对标准PSO 算法的位置公式进行优化，即在粒子尚未到达最优位置时，必定存在一个系数k，使得粒子当前的适应值更小。

他提出的2 个新的位置公式，在高维搜索时，收敛性优于标准PSO 算法。

2.4.2 主动变异

也可以采用概率变异方法，在每个粒子的每次迭代过程中，以加权变异概率替代群体最优[14]。

或者采用自适应策略，对gbest 做自适应变异操作（变异值前期大而后期小），由其产生的新个体对环境做进一步试探，优，则取代之[15]。变异种子xm 在各维上的值：

2.5 优化编码方式

在解决实际问题的过程中，合理选择编码方式可以显著优化函数性能。

2.5.1 二进制编码：简单易行，符合最小字符集编码原则。以车辆运输路径问题（VRP）为例，车辆1 前往工点2，车辆2 前往工点3，车辆3 前往工点1 用二进制矩阵来表示为：

2.5.2 十进制编码：随着规模的扩大，二进制占用计算空间急剧增长。而十进制增长速度远小于二进制，可用整数部分表示车辆前往的目的地，上述问题用(2, 3, 1)即可清晰表达。

2.5.3 实数编码：随着问题复杂性提升，采用实数编码可以扩充粒子群携带的信息。仍以上述问题为例，以小数部分表示所载的商品数量，则将(2, 3,1)扩展为(2.4, 3.5, 1.2)后，可以表示车辆1 商品数量400，前往目的地2；车辆2 商品数量500，前往目的地3；车辆3 商品数量200，前往目的地1。

基于实数编码的思想，宋强[16]提出了一种随机键编码。文章以VRP 问题为例，利用一串0 到1 之间的随机数来表示一种车辆路径，先确定编码长度维度，再进行随机键转化操作，最后进行整数解码操作，用前N 个数字表示工点编号，中间(N+1)～(2N-1)表示单个配送车辆行程分割符，用M 表示配送车辆总数，(2N-1)～[2N+(M-2)]为配送车辆总行程分割符。

2.5.4 概率幅编码：按照最小编码单元的不同，以一个量子位为最小编码单元的被称为单比特概率幅编码[17]，以一串量子位的集合为最小编码单元的被称为多比特概率幅编码[18]。

一个量子位可处于“1”状态、“0”状态或两者的线性叠加状态，而n 个量子位组成的集合可包含2n个不同的状态，即包含2n个不同的信息。任一量子位的状态发生变化，整个量子系统的概率幅均发生变化。这种编码方式用于粒子群算法，不仅可以减少更新全部种群的运算时间，也可以减少计算机内存占用[19]。

3 结论

本文通过对粒子群算法优化方法的梳理和归纳，得到如下结论：

3.1 对粒子群运动速度的改进由线性向非线性发展，由连续向间断变化。无论变量因子是线性、非线性或三角函数变化、引入随机因子或是优质解替代，其目的都是调节收敛速度，从而使函数能够在全局寻优和局部寻优之间灵活切换。具体调节方法分为全局调控和个体调控：全局调控如线性递减、非线性递减、余弦函数递减及周期性调节，个体调控如自适应策略。

3.2 对粒子群的变异策略分为被动变异和主动变异。被动变异如函数连续几代无改进时触发变异，利用外推技巧稳定提高适应值，主动变异如加权变异、概率变异、自适应策略变异。

3.3 粒子群的编码方式由简至繁发展。从二进制、十进制编码到实数编码及量子位编码，复杂的编码方式更适应复杂的多解问题。

3.4 总体来说，对于标准粒子群算法的改进方法无好坏之分，需视目标函数而灵活选择。