带有非线性惯性权重和柯西变异的粒子群优化算法∗

李会荣 彭 娇

（商洛学院数学与计算机应用学院 商洛726000）

1 引言

粒子群优化算法（Particle swarm optimization，PSO）是由1995年美国的社会心理学家James Ken⁃nedy和电气工程师Russell Eberhart提出的一种模拟自然界中鸟类和鱼群觅食行为的智能优化算法［1］。由于PSO算法参数较少、求解速度较快、精准度高且收敛性强，而且不需要优化函数的任何可导、可微等信息，目前已经在函数优化［2~3］、滤波器的设计［4］、多模态优化［5］、目标跟踪［6］等领域得到了广泛的应用。

由于标准PSO算法容易陷入局部最优，后期震荡等缺点，针对此问题，很多学者对其进行了大量的研究［7~12］。文献［7］对基本粒子群优化算法的速度方程进行了改进，减少了控制参数，引入随机调节因子，使得粒子的自我认知能力和社会认知能力在一定范围内随机产生，同时对个体最优粒子进行自适应随机变异，提高了PSO算法的全局搜索能力。文献［8］提出了一种最为经典的线性减小惯性权重算法。文献［9］等探讨了高斯分布、正态分布等知识，并以此为原理设置随机变异算子来提高算法寻优能力。文献［10］提出了一种混沌初始化和自动更新机制的粒子群优化算法。受到教学优化算法的启发，文献［11］提出了一种带有个体扰动和相互学习的粒子群优化算法。

本文在对PSO算法参数惯性权值分析的基础上，提出了一种非线性惯性权值和柯西变异的粒子群优化（NCMPSO）算法。该算法首先提出了一种非线性的惯性权重，然后利用柯西变异算子增加了种群的多样性，从而提高了算法的性能。数值实验表明，提出的NCMPSO算法能够有效克服早熟收敛现象并且较有较高精度。

2 标准粒子群优化算法

PSO算法将社会中的个体比作一个无空间大小的粒子，再由大量的粒子组成一个粒子群，每个粒子在问题搜索空间中通过“飞行”找到途经的最佳方位，从而通过迭代计算的方式找到全局最优值或局部最优解。设由N个粒子组成的一个群体，在M维搜索空间中，向量xi=( )xi1，xi2，…xiM表示第i个粒子的位置，第i个粒子的速度表示为第i个粒子迄今为止搜索的最优位置为pi=(bi1，bi2，… ，biM)，整个群体的最优位置记为pg=(pg1，pg2，…，pgM)。对于每一个粒子，其第d维(1≤d≤M)空间中速度和位置更新如下：其中d=1，2，…，M；社会学习因子c1，c2为非负常数，用于调节粒子朝pi和pg方向飞行时的最大单次移动距离；r1和r2是两个独立分布在区间[0，1]上随机数；t表示粒子目前的迭代次数；vid为粒子的速度，且为设定的最大速度；w为惯性权重，它决定了粒子先前速度对当前速度的影响程度，从而起到平衡算法全局搜索和局部搜索能力的作用，w一般采用线性递减策略［12］。

3 带有非线性惯性权重和柯西变异的粒子群算法（NCMPSO）

3.1 非线性动态递减权值策略

惯性权重是影响PSO算法性能的重要参数之一，惯性权重越大，粒子群的运行速度加快，搜索局部空间的能力降低，探测全局空间的能力就随之增强；惯性权重越小，粒子的运行速度降低，搜索局部空间的能力就会增强，探测全局空间的能力也就随之减弱。因此对惯性权重进行适当的改进可以提高PSO算法的性能。为此Shi Y等学者在1998年的IEEE会议上提出了一种线性递减惯性权重粒子群算法（Linear Decreasing Particle Swarm Optimiza⁃tion，LDPSO），其线性递减惯性权重策略如下［8］：

其中：tmax表示最大的迭代次数；t表示当前的迭代次数；wmax和wmin分别表示设定的最大惯性权值和最小惯性权值。通过多次实验分析，作者发现随着迭代次数的增加，当wmax=0.9，wmin=0.4时，算法的搜寻性能大大提高。

本文在对LDPSO算法的基础上，受文献［13~14］思想的启发，提出了一种非线性动态递减权值策略粒子群优化算法（Nonlinear Dynamic Iner⁃tia Weight Particle Swarm Optimization，NDIWPSO），即将惯性权重设置成非线性的指数函数：

其中k为控制因子。与LDPSO相比，当w接近于wmax时，w的取值增大，NDIWPSO在大部分迭代期间内以式（1）的首项为主，则粒子扩大搜索空间的能力增强，在搜寻全局空间时更具优势，同时粒子向最优值所处位置的收缩能力下降，搜索局部空间能力随之减弱；当w接近于wmin时，w的取值减小，NDIWPSO在大部分迭代期间内以式（1）的后两项为主，则粒子在搜寻局部区间的最优值时更具优势，而搜寻全局空间能力随之减弱。所以非线性指数函数式（4）可以使算法在局部搜寻和全局搜寻的能力之间达到更佳。

此外，对于复杂的非线性多峰函数，粒子就极容易陷入局部极值，这时就需要引领该粒子跳出这个局部极值点。如此一来，式（4）提出的惯性权重策略就无法解决多峰函数的问题，于是对式（4）再进行改进得到如下公式。

为了增加种群的多样性，在式（5）的基础上对其采用变异策略，从而引领粒子跳出局部最优值点，在更全局的空间中进行搜索。

3.2 柯西变异策略

若粒子的种群规模为N，f(xi)代表第i个粒子的适应度值，favg表示粒子群中粒子适应度值的平均值，δ代表粒子群的聚集度。则将聚集度δ定义如下［15］：

其中h为控制因子，可以自适应限制聚集度δ的大小。h定义为如下

由式（6）可知，粒子群的聚集度δ代表的是粒子群中所有粒子的汇集程度。若单个粒子的适应度值和群体平均适应度值的差距越大，则粒子能具备更好的多样性，反之粒子的多样性就越少。所以若δ越大，则偏差越小，即粒子的多样性就越优；若δ越小，则所有粒子的汇集程度越小，而偏差就越大，即粒子的多样性越差。

故当δ

然后对粒子群进行混合变异，得

带有非线性惯性权重和柯西变异的混合粒子群算法（NCMPSO）的基本流程如下。

步骤1（初始化）设置当前迭代次数t=1，最大迭代次数tmax，种群规模N，搜索空间的维数M，以及随机产生每个粒子的初始位置和速度。

步骤2根据式（1）、（2）以及式（5）更新每个粒子的速度与当前位置，计算每个粒子的适应度函数值f(xi)。

步骤3（个体最优更新）对每一个粒子xi，如果当前适应度函数值f(xi)优于个体历史最优位置f(pi)，则更新个体最优pi。

步骤4（全局最优更新）对每一个粒子xi，如果当前适应度函数值f(xi)优于全局最优位置f(pg)，则更新全局最优pg。

步骤5根据式（6）计算粒子群的聚集度δ，若δ

步骤6令t=t+1，返回到步骤2，直到获得一个预期的适应值或t达到设定的最大迭代次数停止。

4 实验结果及分析

4.1 基本测试函数

为了验证本文提出的NCMPSO算法的性能，选取6个常用的测试函数（如表1所示）进行实验，函数的最优值均为0。

表1 中的测试函数都是高维复杂的最小化问题，其中f1，f3为非线性对称单峰函数，用于检测算法的收敛精度；f2也是单峰函数，用于测试算法的执行能力，其全局最优值点在一个平滑且极长的抛物线性山谷里，曲面山谷中点的降落方位和到函数最小值的最好方位垂直；f4，f5，f6都是非线性多峰函数，峰形高低起伏不定，具有大量的局部最优值点。

表1 标准的测试函数

4.2 参数设置

为了选取式（5）和式（8）中参数k的取值，对于六个不同的测试函数，我们分别选取k∈{0.1，0.5，1.0，1.5，2.0，2.5，3.0，3.5，4}，搜索空间维数M=30，每个实验独立运行10次对参数k进行选取。

实验中参数设置如下：粒子的种群规模N=50，最大迭代次数为tmax=1000，社会因子c1=c2=1.8，最大最小惯性权重分别为wmax=0.9和wmin=0.4，允许的最大误差为10-6。对于Sphere函数，k=4；对于Rosenbrock函数，k=2；对于Schwefel函数，k=0.1；对于Ackley函数，k=4；对于Griewank函数，k=2；对于Rastrigin函数，k=3。

4.3 实验结果分析

为了验证本文提出NDIWPSO算法、NCMPSO算法的性能，并分别与固定权重w=1的标准PSO算法、线性减小惯性权重LDPSO算法进行比较。每个实验独立运行20次，表2~3分别列举了搜索空间的维数M=10、30不同情况下PSO、LDPSO、NDI⁃WPSO以及NCMPSO算法20次运行的最优值、最优值的平均值、最优值的标准差的测试结果。

表2 实验结果统计表（M=10）

表3 实验结果统计表（M=30）

从表2~3中可以看出，无论搜索空间M=10还是M=30，提出的NDIWPSO、NCMPSO算法的寻优性能都优于PSO、LDPSO算法。这表明，引入非线性递减的惯性权重和柯西混合变异策略能够有效地提高算法的性能。但是对于单峰函数Sphere、Rosenbrock和Schwefel函数，NDIWPSO算法的性能优于NCMWPSO算法；对于多峰函数Ackley、Grie⁃wank和Rastrigin函数，NCMWPSO算法的性能优于NDIWPSO算法。由此可见，对于复杂多峰测试函数，柯西变异算子能够有效地跳出局部极值点，保持了种群的多样性，进一步提高了NCMWPSO算法的性能。

图1 给出了PSO、LDPSO、NDIPSO以及NCMP⁃SO算法的收敛曲线图，从图1中可以看出，NDIP⁃SO、NCMPSO无论在收敛速度还是收敛精度上都明显地优于PSO算法和LDPSO算法，且在较小的迭代次数内收敛到最优点，使得粒子能够保持较好的活性，能够有效从局部极值中跳出，搜索精度优于PSO、LDPSO算法。

图1 PSO、LDPSO、NDIPSO和NCMPSO算法的收敛曲线

5 结语

为了克服粒子群优化算法早熟收敛、容易陷于局部极值的不足，对标准PSO算法中的惯性权值进行改进，提出新的惯性权重函数公式，同时利用柯西变异算子让算法能够跳出局部最优，从而提出一种新的带有非线性惯性权重和柯西变异的粒子群优化算法。数值实验表明，本文提出的NDIPSO、NCMPSO算法相比于PSO、LDPSO算法具有更高的有效性和稳定性，有着更广阔的应用前景。