1 引言

粒子群优化算法(Particle Swarm Optimization, PSO)是一种经典元启发式算法, 是基于群体的智能随机优化算法. 在1995年^[1]被Kennedy J和Eberhart RC等提出, 现今该算法已被许多学者关注并且在现实优化问题上也受到广泛运用^[2,3], 如神经网络、车辆控制等领域. 粒子群算法设置的参数少、执行速度较快、实现比较便捷^[4], 但是该算法也存在一些不足, 比如较容易陷入局部最优、后期收敛速度变慢或出现早熟收敛等问题. 因此, 许多研究学者对此想出了一些对策来优化算法. Clerc^[5]在把收缩因子的概念引入到粒子群算法中来更新算法的速度从而能更好的控制算法的收敛性. Taherkhani等^[6]通过粒子历史最佳位置以及距离得到不同惯性权重, 提高粒子群算法在静态、动态环境中最优解的质量和收敛速度. 王永贵等^[7]在算法中引入动态分裂算子以增加种群的多样性避免陷入局部最优, 而后采用指数衰减的惯性权重以平衡粒子的全局和局部的搜索. 还有一些学者加入混沌搜索、混沌运动^[8,9]的思想来优化算法. 通过对文献[5–9]中粒子群算法改进思想研究的理解和对比, 对粒子群基本原理理解的基础上, 本文提出了一种动态调整惯性权重的粒子群算法.

2 算法基础理论

粒子群算法是从生物界鸟群捕食中获得的灵感. 模仿鸟类觅食的过程把每个粒子的运动过程比作小鸟, 为了搜寻未知位置的食物即适应值而逐步找寻最近的路线, 即比作算法中寻找最优解的过程. 从一个随机解出发, 通过迭代找到最优解, 以适应度值来作为评判标准, 属于进化算法的一种, 它的运作原理可以假设在一个N维搜索空间中, 由m个粒子组成一个种群, 每个粒子拥有位置和速度两个属性, 设第i个粒子的位置表示为向量X_i=(x_i1, x_i2, …, x_id), i=1, 2, …, m; 第i个粒子的速度可表示为向V_i=(v_i1, v_i2, …, v_id), i = 1, 2, …, m. 随着粒子位置和速度的不断更新, 全局最优解和局部最优解也不断地更新, 利用每个粒子属性计算目标函数当前的适应度, 通过迭代更新从而找到最优适应值. 算法中每个粒子的速度和位置更新公式:

$\begin{aligned}[b] v_i^{j + 1} =& w*v_i^j + {c_1}*{r_1}*\left( {pbes{t_i} - x_i^j} \right) \\ &+ {c_2}*{r_2}*\left( {gbest - x_i^j} \right) \end{aligned} $

(1)

$x_i^{j + 1} = x_i^j + v_i^{j + 1}$

(2)

式中, w表示的是惯性权重; j为当前迭代次数; c₁, c₂表示学习因子; r₁, r₂是随机数在[0,1]范围内取值; pbest_i表示局部最优解; gbest表示全局最优解^[10]. 粒子群算法的终止条件一般为当前可达到的最大迭代次数或者在迭代结束之前达到了算法要求的精度.

算法的基本流程图如图1所示^[11], 算法的基本步骤如下:

Step 1. 初始化算法中的各个固定有效参数值, 包括种群大小MaxIt、最大迭代次数nPop等;

Step 2. 初始化设置一个模型, 用来存放粒子的速度、位置、适应度值、最佳适应度值和最佳位置, 再从种群中挑选出某个粒子的最佳适应度值以及其对应的最佳位置;

Step 3. 根据算法中每个粒子的速度和位置更新公式来更新粒子的位置和速度;

Step 4. 计算出粒子的适应度值, 通过位置的不断更新, 找到每个粒子所能寻到的个体最优pbest, 每得到一个新的pbest来比较最优值, 哪个最优就更新为全局最优gbest, 随着一个个粒子的更新迭代来一步步更新全局最优解gbest;

Step 5. 判断是否达到算法的终止条件, 如果还未达到, 就返回Step 3继续; 否则输出结果.

由于传统的粒子群算法在后期比较容易陷入局部最优, 多样性减少且后期收敛速度过慢的问题, 本文在下一章对粒子群算法进行了改进并进行对比实验.

3 改进的粒子群算法 3.1 动态调整惯性权重的粒子群算法

惯性权重表示粒子的历史速度对当前速度的影响, 决定了新粒子对于历史速度记忆的保持, 具有平衡粒子侦察和开采的能力. 惯性权重偏大时, 表示对算法的全局搜索能力较强, 而对于局部搜索则较弱, 这对一些偏差较少的区域难以准确的找到极值; 而当惯性权重偏小时, 局部搜索能力则会有提高, 而对全局搜索就会变弱, 这时粒子多样性就会减少而导致对新的区域难以搜索^[12]. 本文针对这一特点对惯性权重进行了优化使算法能够自适应.

将差分进化算法(DE)^[13]的思想引用到粒子群算法中, 该算法通过反复迭代进而将适应度好的个体保留, 不同于粒子群算法的是DE算法有自己的记忆能力, 即可以动态地追踪当前能够搜索的情况来调整搜索策略, 具有较好的全局收敛能力和鲁棒性, 利用此特性用来弥补粒子群算法后期容易陷入局部最优的状况. 文献[13]为了提升对短期电力负荷预测, 对差分进化算法进行优化, 优化其种群的变异算子, 在防止种群多样性减少的同时又能在后期加快收敛速度, 最初的惯性只是一个固定取值, 例如取值为1等, 本文利用上述改进的差分进化算法引入到惯性权重参数中来实现对惯性权重的动态调整.

本文之所以将差分进化算法中改进后的变异算子加入到惯性权重中, 是因为其引入了三角函数中的余弦函数, 余弦函数具有周期振荡性, 以总迭代次数为基础, 使每个粒子在搜索时获得振荡扩大搜索空间增大种群多样性, 有助于粒子跳出局部最优, 实验证明用这种方法提高算法搜索效率能有效改善早熟现象.

优化后的动态惯性权重如式(3)所示, 其中nPop表示迭代的次数, i则表示迭代次数.

$w = a*\left(\cos \left(\frac{{\pi (i - 1)}}{{nPop}}\right) + 1\right) + b$

(3)

式中, a取值0.1, b取值0.2.

除了上述对惯性权重的改进, 本文还加入了对边界值^[14]的处理, 包括对速度的限制和位置边界的限制, 为了限制粒子的速度, 设定有最大速度和最小速度, 以搜索空间为基准设定速度, 不同测试对应不同速度, 算法速度的最大值与最小值公式如式(4)和式(5)所示.

$MaxVelocity = k*(VarMax - VarMin)$

(4)

$MinVelocity = - MaxVelocity$

(5)

其中, VarMin表示最小搜索空间值, VarMax表示最大搜索空间值, k的取值为0.2.

为了防止粒子的搜索范围会超出算法所规定的空间则对位置边界也进行了设定, 根据给定的搜索空间范围, 设定当前粒子的最大位置等同或者小于最大搜索空间值, 同理当前粒子的最小值可以等同或者大于最小搜索空间值, 但是两者不能超过范围之外.

4 算法结果分析 4.1 测试函数选择

为了验证优化后的算法的有效性, 将动态调整惯性权重的粒子群算法(PSO-I)与加入惯性系数阻尼比^[15]的粒子群优化算法(PSO-W)、文献[5]中Clerc提出的带收缩因子的粒子群算法(PSO-X)进行对比, 在Windows 7旗舰版, MATLAB R2016a仿真软件的条件下进行实验. 本文使用5个测试函数来验证改进之后基于动态调整惯性权重的粒子群算法的有效性. 基本参数设定为: c₁取值为2, c₂取值为2, 种群数量MaxIt为50, 种群维数为10, 最大迭代次数nPop为200次. 根据文献[16]的测试研究选出以下几个测试函数:

F₁: Sphere函数

$f(x) = \sum\limits_{i = 1}^n {x_i^2} $

(6)

对Sphere设定的搜索空间为[–10, 10]ⁿ.

F₂: Rosenbrock函数

$f(x) = \sum\limits_{i = 1}^{n - 1} {[100{{({x_{i + 1}} - x_i^2)}^2} + {{(1 - {x_i})}^2}]} $

(7)

对Rosenbrock设定的搜索空间为[–10, 10]ⁿ.

F₃: Ackley函数

$\begin{aligned}[b] f(x) =& - 20\exp\left( - 0.02\sqrt {\displaystyle\sum\limits_{i = 1}^n {x_i^2/n} }\right. \\ & \left. - \exp \left (1/n\displaystyle\sum\limits_{i = 1}^n {\cos (2\pi {x_i})} \right ) + 20\right) \end{aligned}$

(8)

对Ackley函数设定的搜索空间为[–30, 30]ⁿ.

F₄: Rastrigin函数

$f(x) = \sum\limits_{i = 1}^n {[x_i^2 - 10\cos (2\pi {x_i} + 10)]} $

(9)

Rastrigin函数设定的搜索空间为[–5, 5]ⁿ.

F₅: Griewank函数

$f(x) = \frac{1}{{4000}}\sum\limits_{i = 1}^n {x_i^2} - \mathop \prod \limits_{i = 1}^n \cos \left(\frac{{{x_i}}}{{\sqrt i }}\right) + 1$

(10)

对Griewank搜索空间设为[–600, 600]ⁿ.

针对以上5个不同的函数进行对比性测验来比较3个算法, 以上5个函数的理论最优值均为0.

4.2 测试结果分析

对以上5个测试函数进行200迭代寻优^[16]后, 计算出200次的平均值和均方差如表1所示.

从表1可以看出, 在对函数F₁、F₂、F₄和F₅的测试中相对于PSO-W和PSO-X而言, PSO-I的平均值有明显的优化, 且PSO-I的均方差也有进一步提升, 说明优化算法PSO-I稳定性相对的进步了. 函数F₃在均值方面虽然没有明显的提升, 但是在均方差数据上却有较好的提高, 说明动态调整惯性权重的粒子群算法(PSO-I)针对此类函数在稳定性上有所提升, 而函数F₃的测试值则显示PSO-W、PSO-X和PSO-I 3个算法的均值和均方差的结果相似, 并无过大的浮动, 说明动态调整惯性权重的粒子群算法在对F₃这类的函数上没有过人之处. 综上所述, PSO-I算法对于F₁、F₂、F₄和F₅这类函数的改进是有意义的.

表1中, Mean表示平均值, Std表示均方差.

为了让读者能更清楚地观察到改进后的动态调整惯性权重的粒子群算法和其他两种优化算法相比的收敛效果, 通过5个测试函数的实验仿真结果来真实地反馈出PSO-W、PSO-X和PSO-I 3个粒子群优化算法的收敛情况. 其仿真结果如图2~图6所示.

从5个图中可以看出, 相较于PSO-X和PSO-W算法, PSO-I算法对5个函数的收敛性都有所提升, 对于函数F₄和函数F₅的后期收敛效果有明显的提高, 对于函数F₁和函数F₃而言只是有略微的提高, 而对于函数F₂来看与带有收缩因子的粒子群优化算法(PSO-X)相比并没有明显的提升.

5 结束语

经过上述实验的分析与对比, 考虑到了原本粒子群算法后期出现收敛过慢且易陷入局部收敛的问题, 提出了能动态调整惯性权重的粒子群算法(PSO-I), 将差分进化算法思想融入到粒子群算法中, 改进惯性权重一贯的固定值, 使其能够进行动态的调节来适应当前的适应度. 将动态调整惯性权重的算法(PSO-I)与另外2种粒子群算法PSO-X和PSO-W进行仿真对比测试, 从最后得出的数据和图形结果来看, 优化惯性权重后的粒子群算法在稳定性和后期收敛速度上都有所提升, 但是对于部分测试函数的提高不是很明显, 因此而言, 该算法在后期的有效性上还是有待提高.