一种多样性驱动的自适应粒子群优化算法

宗 敏，杨玉群，徐 刚*

(南昌大学a.数学系，江西 南昌 330031；b.附属中学，江西 南昌 330047)

粒子群优化(Particle Swarm Optimization,PSO)算法是对鸟群觅食行为过程的模拟而提出的全局随机搜索算法[1]。相对遗传算法、模拟退火等算法而言，PSO具有算法简单，参数少和易实现等优点，一直是群智能优化方法研究领域的热点。仿真实验表明，PSO作为一种并行优化算法，可以用于解决非线性、不可微和多峰值的复杂优化问题，并已广泛用于函数优化、预测和运输问题等科学和工程领域[2-5]，但它存在陷入局部最优和早熟问题，为此国内外的研究者做了大量的工作，提出了各种改进算法[6-11]。种群多样性是影响PSO算法性能的一个重要因素，为避免PSO算法的缺陷，一些研究者提出了通过控制种群多样性提高算法性能的方法[11-12]。

PSO算法搜索过程中，种群多样性大，能提高算法的全局搜索能力，但局部搜索能力降低；种群多样性小，局部搜索能力提高，但全局搜索能力降低。为了防止粒子陷入局部最优和早熟，本文提出了一种多样性驱动的自适应粒子群优化(Diversity driven adaptive particle swarm optimization,DDA-PSO)算法。本算法采用线性递减惯性权重机制加速种群收敛；当种群多样性降低到一定的程度，利用多样性驱动速度(DDV)策略进行勘探，帮助粒子跳出局部最优和防止早熟。采用的机制和策略自适应地相互转换，使得算法的勘探与开拓达到平衡。实验结果表明，DDA-PSO算法能有效地避免陷入局部最优和防止早熟，PSO算法的性能得到显著提高。

1 PSO算法与相关算法

1.1 PSO算法设搜索空间为D维，种群大小为N，第i个粒子位置表示为向量xi=(xi1,xi2,…,xiD)，迄今为止个体最优位置为pi=(pi1,pi2,…,piD),整个粒子群迄今为止最优位置为g=(g1,g2,…,gi)，第i个粒子的速度表示为向量vi=(vi1,vi2,…,viD)。粒子在进化过程中速度和位置更新公式分别如下[1]：

(1)

(2)

其中i=1,2,…,N，d=1,2,…,D；c1和c2为加速常数，通常设为相同值；rand为[0,1]内的随机数；ω为惯性权重。

1.2 PSO-LDIW算法

从式(1)可以看出，ω表示保留原粒子速度的程度；ω较大，粒子速度较大，种群多样性也较大，算法全局搜索能力较强，但局部搜索能力较弱；ω较小，粒子速度较小，种群多样性也较小，这样算法局部搜索能力较强，但全局搜索能力较弱。为了加快PSO算法的收敛速度，Shi[6]针对ω提出了基于惯性权重线性递减机制的粒子群优化(PSO-LDIW)算法，惯性权重线性递减的表达式如下：

(3)

其中ωmax为最大惯性权重；ωmin为最小惯性权重；t为迭代次数；Tmax为最大迭代次数。

2 多样性驱动的自适应粒子群优化算法

2.1 种群多样性度量

在PSO算法中，种群多样性用于描述单个粒子在搜索区域的分布，是影响PSO算法全局性能的一个重要因素。PSO算法在搜索时，通常伴随着种群多样性的缺失，致使算法陷入局部最优和早熟。一般来说，种群多样性越好，算法的全局收敛概率越高。本文利用种群多样性作为每个粒子感知到的一种群体信息，并用它来指导粒子的行为。种群多样性的度量公式[14]如下：

(4)

(5)

2.2 种群速度度量

由于式(1)包含了随机项，速度vi(t)会产生波动，所有粒子的平均速度的绝对值(va)可以作为种群速度度量来了解所有粒子的敏捷度。va表达式[15]如下：

va较大值意味着粒子当前位置关于个体最优位置和全局最优位置发生了较大的改变，从而能提高算法的勘探能力，保持了种群的多样性。va较小值意味着粒子在个体最优位置和全局最优位置附近进行搜索，种群多样性较小。

2.3 多样性驱动速度策略

根据基本PSO算法的收敛性分析[13]，随着迭代运行，粒子之间变得越来越靠近，种群多样性减小，影响算法的全局搜索能力，导致算法陷入局部最优和早熟。粒子速度是改变种群多样性的根本原因，如果种群多样性变小，可以增大粒子速度来提高种群多样性。根据PSO算法的全局搜索特性，随着算法的迭代运行，希望粒子的速度由大到小逐渐减小，这能保证前期种群多样性大，有利于全局搜索，后期种群多样性小，有利于局部搜索，达到了勘探和开拓的平衡。鉴于上面的分析，为了防止局部收敛或早熟，需要多样性驱动速度(DDV)策略，帮助粒子跳出局部最优或防止早熟。在DDV策略中，本文使用的多样性驱动速度(vD)函数如下：

vD(t)=vmax·e-kDiv(t)

(7)

其中vmax是最大速度限制值。k>0是一个系统参数，用于确定算法搜索性能对种群多样性的依赖程度。

根据式(7)可以看出，种群多样性较小时，vD较大；当种群多样性较大时，vD较小。当算法陷入局部最优或早熟时，粒子速度较小，同时种群多样性也较小，这时需要通过vD来驱动粒子速度使其增大，从而提高种群多样性。为了能够根据多样性的变化驱动粒子速度(即步长)自适应改变，使粒子跳出局部最优和防止早熟，本文根据vD与va比较，通过改变权重ω，使得粒子的步长发生改变，从而达到种群多样性驱动速度的目标。惯性权重值变化如下，

(8)

其中ωini是惯性权重的最大值；ωfin是惯性权重的最小值；Δω是惯性重量的步长。根据文献[11]建议，ωini=0.9，ωfin=0.3。

当多样性迅速减小时，应及时增大惯性权值，提高粒子速度，增强算法全局探索能力；反之，当多样性不断增大时，应减小惯性权值，降低粒子速度，加强算法局部开拓能力。同时应该注意，进化后期的惯性权值不应取值过大，否则种群无法精确寻优且算法很难收敛。

2.4 种群多样性设置

DDA-PSO算法启动多样性驱动速度策略，种群多样性会不断地提高，但种群多样性不宜一直增大，否则粒子很难进行精细搜索，因此需要设定种群多样性最大值(di)，一旦种群多样性达到最大值，多样性驱动速度策略停止执行。根据PSO算法的搜索特性，DDA-PSO算法的种群多样性在早期应较大，有利于进行勘探；种群多样性在后期应较小，以便进行开拓。鉴于上述分析，di使用随时间线性递减的方式，其表达式如下：

(9)

其中d1和d2分别是种群多样性的最大值和最小值。

2.5 提出的算法

DDA-PSO算法分为吸引阶段和多样性驱动阶段。在吸引阶段，DDA-PSO算法采用惯性权重线性递减机制，既加速算法收敛，又能进行局部精细搜索，这正好是PSO-LDIW算法[6],但种群多样性逐渐降低，从而粒子容易陷入局部最优。为了能预估PSO算法陷入局部最优，利用计数器(记作NC)跟踪最佳适应值一直未改变的次数。当计数超过设定次数时，DDA-PSO算法切换到多样性驱动阶段。在多样性驱动阶段，DF-APSO采用DDV策略提高粒子速度，从而增加种群多样性，帮助粒子跳出局部最优或防止早熟。一旦种群多样性达到设定值，多样性驱动阶段停止，DDA-PSO算法再次切换到吸引阶段，重复此过程，直到达到最大迭代次数或满足停止标准。为清晰起见，DDA-PSO算法的主要步骤描述如下：

步骤1：对粒子的位置，速度和系统参数进行初始化；

步骤2：计算粒子的适应度值，根据适应度值确定个体最优位置和全局最优位置；

步骤3：执行PSO-LDIW算法进行搜索；

步骤4：如果全局最优值保持不变，NC加1，否则NC设置为0；

步骤5：如果NC大于等于设定值，停止PSO-LDIW算法搜索，采用DDV策略；

步骤6：更新粒子速度、位置、个体极值和全局最优值，根据式(9)计算di；

步骤7：根据式(4)计算Div，如果Div>=di，停止DDV策略；如果Div

步骤8：判断算法终止准则是否满足，如果满足，算法停止，否则转向步骤3。

3 数值实验及分析

3.1 基准函数和比较算法

为了提供一个全面的比较，6个具有不同特性的基准函数[11]用于实验测试。表1列出了这些基准函数的简要说明。根据它们的特性，6个基准函数包括单峰函数(f1)、多峰函数(f2,f3,f4)、旋转多峰函数(f5)和复合函数(f6)。为了验证算法的性能，DDA-PSO分别与PSO-LDIW[6]，MPSO[10]，APSO[7]和APSO-MAM[9]在6个基准函数上进行仿真比较。根据原文献，所有PSO算法的参数设置见表2。通过实验分析，本文k=1和NC=50。根据文献建议[16]，d1=0.25，d2=0.05。

表1 用于测试的基准函数及其参数Tab.1 Benchmark functions and their parameters for testing

所有粒子群优化算法的粒子位置初始化都均匀地分布在表1中描述的初始范围内以体现算法的搜索能力。为了防止种群初值影响测试结果，对每个基准函数进行30次独立实验后取其最优适应值的平均值。根据文献建议[17]，所有PSO算法的种群大小均设定为40，最大迭代次数为10 000。

表2 各种PSO算法的参数设置Tab.2 Parameter setting of various PSO algorithms

3.2 实验结果分析

仿真结果与统计数据见表3。表3列出了6个基准函数在30维的最优适应值的平均值和标准差(标准差显示在括号中)。图1～图6是6个基准函数分别采用5个PSO算法迭代10 000次后得到的平均最佳适应度进化曲线，FEs表示迭代次数，Function1-6按顺序分别为表1中的f1，f2，f3，f4，f5，f6。

表3 优化基准函数搜索结果的比较Fig.3 Comparison of benchmark functhion search results

FEs图1 Sphere函数的平均最优适应度进化曲线Fig.1 Evolution curve of average optimal fitness of Sphere

FEs图2 Rastrigin函数的平均最优适应度进化曲线Fig.2 Evolution curve of average optimal fitness of Rastrigin

FEs图3 Weierstrass函数的平均最优适应度进化曲线Fig.3 Evolution curve of average optimal fitness of Weierstrass

FEs图4 Griewank函数的平均最优适应度进化曲线Fig.4 Evolution curve of average optimal fitness of Griewank

FEs图5 旋转Griewank函数的平均最优适应度进化曲线Fig.5 Evolution curve of average optimal fitness of Rotation Griewank

FEs图6 Hybrid composite CF5函数的平均最优适应度进化曲线Fig.6 Evolution curve of average optimal fitness of Hybrid composite CF5

函数f1是简单的单峰函数，由表3可知几乎所有的算法在求解精度上都能提供最好的性能。DDA-PSO算法的收敛精度排第一，远优于排第二的APSO算法。从图1可以看出，前期APSO-MAM算法的收敛速度优于其他四种算法，且其他四种算法的收敛速度非常接近。随着迭代进化，DDA-PSO算法的收敛速度和精度远优于其他四种算法。

函数f2、f3和f4都是复杂的多峰函数，算法很容易陷入局部最优。由表2可知，除了在函数f2上DDA-PSO算法与APSO-MAM算法的收敛精度一样，DDA-PSO算法的收敛精度远优于其他四个算法。在函数f2和函数f4上，DDA-PSO算法的收敛精度达到理论最优值0。从图2到图4可以看出，前期五种算法的收敛速度非常接近。随着迭代进化，DDA-PSO算法的收敛速度远优于其他四种算法。在函数f2上，虽然APSO-MAM算法的收敛精度也达到理论最优值0，但由图2可以看出，APSO-MAM算法的收敛速度低于DDA-PSO算法。

函数f5由Griewank函数旋转而得，是非常复杂的多峰函数，算法非常容易陷入局部最优。由表3可见，PSO-LDIW，MPSO，APSO和APSO-MAM四个算法的收敛精度都受到较大的影响，然而，DF-APSO算法的性能不受旋转的影响，收敛精度仍然达到理论最优值0。从图5可以看出，前期DF-APSO算法的收敛速度与其他四种算法相比不具优势，但随着迭代进化，DDA-PSO算法的收敛速度远优于PSO-LDIW算法，MPSO算法和APSO算法。虽然APSO-MAM算法的收敛速度也较快，但DF-APSO算法的收敛速度一直优于APSO-MAM算法。

函数f6是带旋转和非对称多峰的复合函数，在不同的区域具有不同的性质，这种函数更难找到全局最优解，会削弱所有粒子群算法的搜索能力。由表3可见，虽然所有粒子群算法的收敛精度都有所降低，但DF-APSO算法的收敛精度仍然最高，远远优于PSO-LDIW算法，MPSO算法和APSO算法。虽然APSO-MAM算法的收敛精度接近于DF-APSO算法，但其标准差远远大于DF-APSO算法。从图6可以看出，PSO-LDIW算法，MPSO算法和APSO算法很快陷入局部最优。虽然APSO-MAM算法也能跳出局部最优，但DF-APSO算法的收敛速度一直优于APSO-MAM算法。

综上可以看出，DDA-PSO算法在6个基准函数上的收敛精度和收敛速度都优于其他四种算法，这归因于DDA-PSO算法在吸引阶段利用惯性权重线性递减机制加速算法收敛，粒子能进行局部开拓；驱动阶段利用多样性驱动速度策略提高粒子群的多样性，粒子能进行全局勘探。两阶段能自适应地相互转换，勘探和开拓达到平衡，保持了种群多样性，使得粒子能跳出局部最优，且防止了早熟收敛，大大提高了全局搜索能力，同时提高了收敛速度。

4 结论

本文针对粒子群优化算法容易陷入局部最优和早熟问题，在基本PSO算法的基础上引入惯性权重线性递减机制和多样性驱动速度策略对PSO算法进行了改进，提出了一种多样性驱动的自适应粒子群优化算法。在6个基准函数上，DDA-PSO算法与4个已有的粒子群优化算法进行了比较。实验结果表明，DDA-PSO算法不仅具有很强的全局搜索能力，而且收敛速度明显提高，收敛精度得到改善，很大程度上防止了早熟和避免了陷入局部最优。