刘生建　罗林　杨艳

摘 要：为了解决标准粒子群优化算法（SPSO）不能适应复杂非线性优化过程的问题，提出了一种动态改变惯性权重的快速自适应粒子群优化算法（QAPSO），直接利用群粒子的位置分布情况控制粒子飞行的惯性权重，借助于个体最优位置和全局最优位置的平均作用避免粒子陷入局部最优。通过多个基准函数仿真结果表明，在不引入额外设计及增加实现复杂度的前提下，相对于SPOS等经典算法，QAPSO在收敛速度、最优解精度等方面获得了大幅提升，尤其对于多峰函数效果更明显。

关键词：粒子群算法；均值粒子群算法；快速自适应

DOI：10.11907/rjdk.171514

中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2017）009-0042-04

Abstract：A quickly adaptive particle swarm optimization algorithm （QAPSO） with dynamically changing inertia weight was presented to solve the problem that the Standard Particle Swarm Optimization algorithm （SPSO） cannot adapt to the complex and nonlinear optimization process.The QAPSO evaluates the population distribution， and automatic control inertia weight. By using the mean of the optimal individual position and the global optimal position， the best global particle can jump out of the local optima. The QAPSO has comprehensively been evaluated based on benchmark functions. Results show that QAPSO substantially enhances the performance of paradigm such as the SPSO in terms of convergence speed， solution accuracy without introducing an additional design or implementation complexity， especially for multimodal functions.

Key Words：swarm intelligence optimizationalgorithm； mean swarm optimization algorithm； inertia weight adaptability

0 引言

自蚁群算法（Ant Colony Optimization ， ACO）成功应用于旅行商问题（TSP）之后[1]，仿生群智能研究开始迅速发展，先后出现了粒子群、蜂群、人工鱼群、蝙蝠群、狼群、萤火虫等主要解决连续问题的优化算法。

Kennedy和Eberhart在1995年提出了来源于鸟群等生物种群觅食行为的粒子群优化算法（Particle Swarm Optimizer， PSO）[2-3]，由于概念简单，实现容易，且只有少数参数需要调整，所以PSO算法发展迅速，并广泛应用于函数寻优、神经网络训练、模式分类、模糊系统控制等领域。虽然PSO相比鱼群算法等有较强的全局搜索能力，但还是容易陷入局部极值，不易收敛到全局最优。所以出现了一些改进的PSO算法。例如Shi Y等[4]提出了线性递减权值（LDIW）策略；Kusum Deep等[5]提出均值粒子群优化方法（MPSO）；Zhan Z H等[6]提出了自适应粒子群优化算法等。

本文主要对经典粒子群算法的性能及问题进行分析，并针对收敛精度低和收敛速度慢的问题，在均值粒子群算法基础上，根据粒子间的距离函数动态调整算法中的惯性权重，合理调整粒子飞行速度。当最优粒子和其它粒子位置相距较远时，设置较大的惯性系数，由此解决函数寻优过程中探索和开发之间的矛盾。实验仿真结果表明，本文提出的改进算法性能有了明显提高，具有相对收敛速度快、精度高等优点。

1 标准粒子群优化算法

设N个粒子组成一个群，其中第i个粒子的位置表示为一个D维的矢量xi=（xi1，xi2，…，xid），第i個粒子的历史最优位置为pi=（pi1，pi2，…，pid），整个粒子群迄今为止搜索到的最好位置记为pg=（pg1，pg2，…，pgd）。第i个粒子的速度vi=（vi1，vi2，…，vid）。粒子群算法基于迭代思想，粒子按如下公式（1）、（2）调整自己的相应位置[7]：vk+1id=ω*vkid+c1*r1*（pkid-xkid）+

c2*r2*（pkgd-xkid）

（1）

xk+1id=xkid+vk+1idxid∈[xd-min，xd-max]

（2） 其中，1≤i≤N（N为种群个体总数），1≤d≤D，k为迭代次数，c1和c2是非负数，c1表示粒子个体最优位置的自我影响，而c2则表示群体最优位置的群体影响。r1和r2是[0 ，1]区间的随机数。ω表示惯性权重因子，在公式（1）中一般是固定值，范围一般为[0.4，0.9]，可决定粒子先前速度对目前运动的影响程度，从而起到平衡算法全局搜索和局部搜索能力的作用。当粒子速度较大时，飞行较快，有利于全局勘探，但有可能超过最优解；反之则有利于局部开发。endprint

粒子在解空间内不断跟踪个体极值与全局极值， 直到达到规定的迭代次数或满足规定的误差标准为止。在寻优初期，ω应取0.9～1.4，然后根据迭代次数线性减少到0.4，公式如下：ω=ωmax-（ωmax-ωmin）ttmax

（3） 其中，t表示目前的迭代次数，tmax表示设定的最大迭代次数，ωmax表示最大惯性权重因子，ωmin表示最小惯性权重因子。

也可以从物理含义上来解释公式（1），一个单位质量的粒子在单位时间上受到来自Pi和Pg两处吸引力的共同作用，从而引起加速度变化。加速度变化导致速度改变，最终改变粒子所处位置。本文将ω固定的PSO简称为SPSO，而依据公式（3）计算的PSO简称为LPSO，以对算法性能进行对比分析。

2 均值粒子群优化算法

与基本粒子群形成对比的是，均值粒子群优化算法（MPSO）速度更新公式中用线性组合pkid+pkgd2和pkid-pkgd2取代了pkid和pkgd。因此，速度更新公式（1）轉换为公式（4）：vk+1id=ω*vkid+c1*r1*（pkid+pkgd2-xkid）+

c2*r2*（pkid-pkgd2-xkid）

（4） 其中等式中的第一项与公式（1）含义相同；第二项与矢量（pkid+pkgd2-xkid）成比例变化，它吸引粒子由当前位置方向指向全局最优位置和粒子个体最优位置的平均位置方向；第三项与矢量（pkid-pkgd2-xkid）成比例变化，它吸引粒子由当前位置方向指向粒子个体最优位置方向和全局最优位置负方向的平均位置方向。其它更新和参数设置与基本粒子群算法相同。

3 快速自适应粒子群算法（QAPSO）

3.1 基本思想

计算现有粒子群中每个粒子距离其它粒子的距离因子di，现有粒子群中适应度最高的粒子，设其距离因子为dg，距离因子的最小值为dmin，最大值为dmax，计算粒子群的分布信息因子f。f值为1表示最优粒子远离其它粒子，直接将下一次迭代的惯性权重设置为f值，即可合理控制其它粒子飞向最优位置的速度。

粒子的距离因子如公式（5）所示：di=1N-1∑Nj=1，j≠i∑Dk=1xik-xjk

（5） 公式（5）也可使用欧氏距离，但采用曼哈顿距离计算量较少。

粒子群的分布信息因子如公式（6）所示：f=dg-dmindmax-dminf∈[0，1]

（6）

ωk+1i=f

（7） 最优粒子和其它粒子之间的位置关系主要有3种情况，如图1所示。

图1（a）表示算法初期，所有粒子随机分布，最优粒子与其它粒子差别不大，dg≈di，粒子群处于勘探阶段；图1（b）表示其它粒子向当前最优粒子靠拢，dgdi，处于收敛阶段；图1（c）表示出现新的更优位置后，dgdi，其它粒子纷纷跳出原有局部最优位置。

3.2 QAPSO算法描述

Step1：初始化粒子群数目N，在函数定义域内对每个粒子的初始位置和初始速度进行随机初始化。

Step2：将粒子的pi设置为当前位置，pg设置为初始群体中最佳粒子的位置。

Step3：判断算是否满足终止条件，如果满足，转Step6；否则执行（4）。

Step4：对粒子群中的所有粒子i执行如下操作：①根据式（2）、（4）更新粒子的速度及位置；②计算粒子i的适应度值fi；③如果fi优于pi的适应度值，则更新pi为粒子i的当前位置；④如果fi优于pg的适应度值，则更新pg为粒子i的当前位置；④根据式（5）计算距离因子di，更新dg、dmin、dmax。

Step5：根据式（6）、（7）计算粒子群的分布信息因子，从而确定下一次迭代惯性权重ω的值。然后回到Step3继续执行。

Step6：输出pg，结束算法运行。

4 仿真实验与数值分析

本文使用Matlab2014b对上述QAPSO算法编写了仿真程序，同时也针对标准粒子群算法（SPSO）、均值粒子群算法（MPSO）、惯性权重线性递减粒子群算法（LPSO）在同样的环境下进行仿真。仿真程序中，粒子群规模N取40，对比算法中加速常数c1和c2为2，固定惯性权重ω取0.729 8。LPSO算法中，ω从0.9线性递减到0.4。对每个测试函数均进行20次独立实验，函数评估精度设为10-15。参考文献[8]选取了6个测试函数。

单峰函数有：

（1）Rosenbrock 函数。f1（X）=∑D-1i=1[100（xi+1-x2i）2+（xi-1）2]

（8）

-10≤xi≤10 当D=30，X*=（1，…，1）时，其全局最优值f（X*）=0， 寻优成功标准为f（X）≤10。该函数在全局最优位置附近变换十分平缓，当D=2时，该函数分布如图2所示。很多优化算法很难找到全局最优位置或找到最优值需要的迭代次数较多。

（2）Schwefel′s 函数。f2（X）=∑Di=1xi+∏Di=1xi

（9）

-10≤xi≤10 当D=30，X*=（0，…，0）时，其全局最优值f（X*）=0， 寻优成功标准为f（X）≤0.01。

多单峰函数有：

（3）Dropwave函数。f3（X）=-1+cos（12x1+x2）0.5（x1+x2）+2

（10）

-2≤x1，x2≤2 当X*=（0，0）时，其全局最优值f（X*）= -1，寻优成功标准为f（X）≤-0.99。

（4）Eggcrate函数。该函数的局部峰值很多，当D=2时，该函数分布如图3所示。f4（X）=x21+x22+25（sin2x1+sin2x2）endprint

（11）

-π≤x1，x2≤π 當X*=（0，0）时，其全局最优值 f（X*）= 0，寻优成功标准为f（X）≤0.01。

（5）Rastrigin函数。f5（X）=∑Di=1[x2i-10cos（2πxi）+10]

（12）

-5.12≤xi≤5.12 当D=30，X*=（0，…，0）时，其全局最优值f（X*）= 0，寻优成功标准为f（X）≤0.01。

（6）Ackley 函数。f6（X）=-20exp（-0.21D∑Di=1x2i）-

exp（1D∑Di=1cos（2πxi））+20+exp（1）

（13）

-32≤xi≤32 当D=30，X*=（0，…，0）时，其全局最优值f（X*）= 0，寻优成功标准为f（X）≤0.01。

表1～表6分别给出了6个函数在Intel Xeon E3-1230V2和8G DDR3内存、128G固态硬盘计算机上运行计算的结果比较，所有算法的最大迭代次数均为200。

从表1～表6中可以看出，QAPSO除单峰函数f1和其它优化算法一样均未成功找到最优值外，其它函数寻优精度和时间都明显优于LPSO、MPSO、SPSO，尤其是在处理变化剧烈的多峰函数（f4、f5等）时。LPSO和MPSO算法性能相差不大，SPSO表现最差。在收敛速度上，QAPSO与LPSO、MPSO、SPSO相比有明显优势，收敛时间大大缩短。由于收敛速度差别较大，所以图中的横坐标迭代次数从20开始计数，以避免纵坐标函数值差距过大。从图2、图3可以明显看出，算法总体性能表现为：QAPSO>MPSO>LPSO>SPSO。

5 原因分析

由表1可知，单峰函数f1的寻优能力不太理想，其原因是函数值在最优位置区域内变化十分缓慢，各粒子的函数值非常接近，直接导致f取值接近0。QAPSO直接使用f作为惯性系数，所以使得粒子失去惯性作用。

由于SPSO采用固定惯性权重策略，在前期探索解空间时能力不强，而在后期由于惯性较大，又缺乏局部开发能力，很难搜索到最优解；LPSO则在前期加强了勘探能力，在后期采用较小的惯性权重，增强了局部寻优能力；MPSO则考虑到当前个体最优和群体最优位置对粒子群可能产生的“误导”，增强了粒子跳出局部最优的能力；而QAPSO进一步使用群体分布因子来动态调整下一次迭代的惯性权重，从而在多峰函数的寻优过程中表现出较强的适应能力。图4、图5表示QAPSO、SPSO对f4寻优过程中群分布因子的变化过程，可看出在迭代后期，SPSO算法过早收敛到了局部最优值，群个体趋向相同位置，减少了群体多样性。反之，QAPSO则在整个过程中一直充分保持了群体多样性。

6 结语

本文提出了一种基于粒子群分布因子的均值粒子群改进优化算法，实验结果表明，与标准粒子群算法、线性改变权重粒子群优化算法、均值粒子群算法相比，本文算法的收敛速度快、精度较高。本文以种群位置分布因子作为惯性权重，平衡了算法的全局探索和局部开发能力，使粒子跳出局部最优束缚。6个函数优化的仿真结果表明， 本文算法在成功率、平均最优值、收敛时间上都有很大改善，特别对于多峰函数，算法性能的改善更为明显。对于单峰函数，可继续进行研究改进，一种简单策略是在发现最优值变化缓慢时切换为标准粒子群方法，从而扩大算法的使用范围。

参考文献：

[1] DORTGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony cooperating agents[J]. IEEE Trans. on Systems， Man， and Cybernetics Part B： Cybernetics，1996，26（1）：29-41.

[2] KENNEDY J， EBERHART R. Particle swarm optimization[C]. International Conference on Neural Networks，Perth， Australia： IEEE，1995：1942-1948.

[3] EBERHART R C， KENNEDY J. A new optimizer using particle swarm theory[J]. Institute of Electrical and Electronics Engineers，1995（10）：39-43.

[4] SHI Y， EBERHART R. A modified swarm optimizer[C].IEEE International Conference of Evolutionary Computation Anchorage， Alaska： IEEE Press，1998：69-73.

[5] KUSUM DEEP， JAGDISH CHAND BANSAL. Mean particle swarm optimisation for function optimisation[J]. Computational Intelligence Studies，2009（1）：72-92.

[6] ZHANZH， ZHANGJ， LIY， et al. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems Man， and Cybernetics — Part B： Cybernetics，2009，39（6）：1362-1381.

[7] X YAO， YLIU， G M LIN. Evolutionary programming made faster[J] . IEEE Trans. Evol. Comput.，1999（2）：82-102.

[8] SHI Y， EBERHART R. Empirical study of particle swarm optimization[C]. International Conference on Evolutionary Computation，Washington， USA： IEEE，1999：1945-1950.

（责任编辑：黄 健）endprint