袁 罗，葛洪伟+，姜道银

1.轻工过程先进控制教育部重点实验室（江南大学），江苏 无锡 214122

2.江南大学 物联网工程学院，江苏 无锡 214122

1 引言

粒子群优化（particle swarm optimization，PSO）算法是一种基于迭代的优化方法[1]，它源于对鸟群和鱼群群体觅食运动行为的模拟，是一类新兴的基于群智能的随机优化算法，较其他的进化算法相比，易于实现且参数较少，已在科学和工程领域得到了广泛的应用。然而，基本PSO算法在实现中存在一些不足，如难以跳出局部最优和收敛速度慢等。近些年来，许多学者在优化算法性能上做出的贡献有：（1）在PSO算法中引入惯性权重[2-3]，增加收敛因子[4]，修正学习因子[5]等，以平衡粒子群的全局探索和局部搜索能力。（2）在PSO混合策略上，如将GA（genetic algoritim）中选择、变异和交叉的思想融入PSO算法[6-7]，PSO和DE（differential evolution）融合[8]，PSO与其他的一些局部和全局收缩技术都有一定程度的融合，如蚁群算法、单纯形算法和模糊逻辑算法等。（3）避免种群陷入局部最优，如引入自适应变异机制[9-13]、交叉机制[14]等方法。但总体而言，这些算法仍然存在易陷入局部最优和收敛速度慢等缺陷。

为弥补PSO算法难以跳出局部最优和收敛速度慢等不足，本文提出了基于健康度[15]的自适应过滤粒子群算法（PSO algorithm with adaptive filter based on health degree，HAFPSO）。该算法通过计算粒子健康度区分粒子状态，处理并标记异常粒子，当该粒子被处理次数超过一定阈值而仍没有逼近最优解趋势时，自适应过滤该粒子位置，重新生成新的位置；同时，利用引导因子更新全局最差粒子值，过滤异常粒子数，避免无效搜索，提高算法的收敛速度。实验表明，本文算法能够显著提高收敛速度和性能。

2 基于健康度的自适应过滤粒子群算法

2.1 标准粒子群算法

标准PSO算法通过模拟鸟群飞行中的觅食行为，把鸟类个体看作随机的粒子，通过局部和全局最优来引导粒子飞向最优解。粒子根据自己在解空间中的飞行经验以及粒子群体的飞行状况动态更新自己的速度和位置。其所经历的最优位置即个体历史最优位置记为pi=(pi1,pi2,…,piD)，其中所有粒子经历过的最优位置即全局最优位置记为pg=[pg1,pg2,…,pgD]。粒子的位置和速度更新公式分别为：

其中，w为惯性权值；c1和c2是加速系数；r1和r2均为[0,1]之间的随机数。

2.2 HAFPSO算法

2.2.1 健康度

文献[15]提出健康度概念：在每一次迭代进程中，都会记录当前的粒子振荡数NOSC和停滞数NS，如果粒子在每一次迭代中越来越接近最优解，则粒子健康度上升，否则下降。当粒子的健康度低于设定的门限值时，粒子则被判定为异常粒子。粒子健康度计算公式如下：

其中，WS和WOSC分别是粒子的停滞次数和振荡次数的权值系数。

2.2.2 自适应过滤机制

定义1Limit为一个调节变量，用于衡量异常粒子是否需要自适应过滤处理：

其中，β取值[0,2]；M为最大迭代次数，本文设为2 000；t为当前迭代次数；D为粒子的维度。显然，随着迭代次数的增加，Limit值也在增加，能够更加准确地识别懒惰粒子，从而对懒惰粒子进行救治，避免无效搜索，加快算法收敛速度。

定义2懒惰粒子L定义为：

准确地确定懒惰粒子是关键。根据定义1，调节变量Limit用于确定是否对异常粒子进行自适应过滤处理。当异常粒子被处理次数超过Limit值而仍没有逼近最优解的趋势时，即被视为懒惰粒子。在锁定懒惰粒子后，立刻重新生成一个新的位置，更新公式如下：

其中，pg为第i个粒子的全局最优位置；xi为第i个粒子的位置。

定义3引导因子q为每轮迭代中最接近最优解的粒子，q满足条件：

其中，xi代表粒子的位置；cosθ计算方式为：

粒子运动轨迹如图1所示，粒子在运动过程中，如果连续两代都朝着同一方向，则可以判断为粒子的运动轨迹存在朝着最优解方向运动的趋势。随着迭代次数的增加，如果粒子运动轨迹重复这种状态，即可以判断该粒子在朝着最优解方向运动。如果迭代后期出现粒子当前迭代与上一次迭代运行方向相异时，则在当前迭代中该粒子不满足引导因子的条件，直接利用传统方法更新该粒子速度和位置。

Fig.1 Particle trajectory图1 粒子轨迹图

在收敛的情况下，因为所有的粒子都向最优解的方向运动，所以粒子趋向同一化，失去了多样性，使得后期收敛速度明显变慢，以致算法收敛到一定精度时无法继续优化。粒子群在寻优过程中，无论是找到最优解还是陷于局部最优，整个过程中pg的变化率会越来越小，最终趋于静止。随着迭代次数的增加，所有粒子的位置会逐步靠近并停止在pg处。一旦粒子赶上种群最优，粒子会聚集到相应位置并停止移动，种群的多样性会慢慢丧失，从而导致算法过早收敛而出现早熟现象。

而引导因子q为每轮迭代中最接近最优解的粒子，随着迭代次数的增加，通过记录每个粒子当前迭代与上一次迭代运行的方向是否相异来判断粒子的飞行状态，在当前迭代中选择最接近最优解的粒子作为引导因子。引导因子是由粒子的飞行状态决定的，可以指引最差粒子径直地朝最优解方向飞行，提高种群多样性的同时加快收敛速度。因此利用引导因子来更新最差全局粒子值，可以有效地平衡搜索过程的多样性和方向性，避免算法陷入局部最优。

因此，利用引导因子q引导更新全局最差粒子值，从而在每一次迭代中降低异常粒子数，提高整体粒子的健康度。其计算公式如下：

其中，xw是种群中适应度最差的粒子位置。

在粒子实际运行过程中，大部分的粒子运行状态并不尽如人意，存在一些粒子始终无法逼近最优位置。文献[15]提出的HPSO（particle swarm optimization based on health degree）算法通过计算粒子健康度区分正常粒子和异常粒子，将异常粒子的历史最优位置进行更新，但是随着迭代次数的增加，粒子速度下降导致很难跳出局部最优；另外，每一次迭代要对每一个粒子进行判断处理，而存在一些粒子始终无法逼近最优位置，这就延长了寻优时间。

自适应过滤机制通过对异常粒子进行标记，利用调节变量Limit识别懒惰粒子，重新生成一个新的位置；同时，用引导因子q引导全局最差粒子，过滤异常粒子数，提高整体粒子的健康度。利用这种自适应的过滤机制，一方面可以增加粒子的多样性，有助于算法在迭代后期跳出局部最优，加大算法跳出局部最优的几率，提升粒子的全局寻优能力；另一方面避免无效搜索，加快算法收敛速度。

2.2.3 算法步骤

输入：粒子个数N，粒子维数D，迭代次数Iterations，运行次数number。

步骤2计算粒子的适应度值。

步骤3更新每个粒子的速度和位置。

步骤4计算每一个粒子的健康度，若判断是异常粒子，更新异常粒子历史最优值位置pi=rand(0,1)×(pg-xi)，识别懒惰粒子，重新生成新的位置xi=xi+rand(0,1)×(pg-xi)。

步骤5更新全局最差粒子值，提高整体粒子的健康度xw=xw+rand(0,1)×(qi-xw)。

步骤6判断是否满足结束条件，若不满足，跳转至步骤2，否则，算法结束。

3 HAFPSO算法分析

3.1 粒子移动进程模拟

改进前后的两种算法的粒子移动进程模拟如图2、图3所示，在引导因子的作用下，每次迭代后，异常粒子数降低，整体粒子健康度上升，收敛速度明显加快。

Fig.2 Particle trajectory by HPSO图2 改进前粒子移动进程图

Fig.3 Particle trajectory by HAFPSO图3 改进后粒子移动进程图

3.2 时间复杂度分析

衡量算法优劣的另一标准就是算法的复杂程度。假设粒子个数N，粒子维数D，考虑到最坏的情况，HAFPSO算法进行一次迭代的时间复杂度分析如下：

（1）初始化粒子参数，时间复杂度为O(ND)。

（80）瓦氏皱指苔Telaranea wallichiana（Gottsche）R.M.Schust.

（2）判断停止迭代，时间复杂度为O(1)。

（3）计算粒子健康度，如果判断为异常粒子，进行处理的同时标记该粒子，被搜索次数加1；再判断无效搜索次数是否大于设定阈值，若是，则重新更新位置，时间复杂度为O(ND)。

（4）引导因子更新最差粒子值，时间复杂度为O(ND)。

（5）更新历史最优位置表和全局最优位置表，时间复杂度为O(N)。

因此，HAFPSO算法的时间复杂度为O(ND)。

3.3 算法收敛性分析

一个算法是否收敛必须满足两个条件：（1）在搜索空间中，产生的解都是独立的。（2）能够保存最优解。HAFPSO算法收敛性分析如下。

定义4设X∗为算法的最优解，则X∗须满足：

其中，X为搜索变量，f为目标函数。θ(R)=|R⋂X∗|解空间R中最优解的个数。

定义5若，则HAFPSO算法收敛。其中，R0代表初始化的解，t表示迭代次数。

定理1 HAFPSO算法收敛。

证明令P0(t)=P{θ(R(t))=0}，则：

在HAFPSO算法中，如果存储的最优解中不为空的话，那下一次迭代中最优解的个数肯定不为0，即P{θ(R(t+1))=0|θ(R(t))≠0}=0 。因此，P0(t+1)=P{θ(R(t+1))=0|θ(R(t))=0}×P{θ(R(t))=0}。由算法描述可知，P{θ(R(t+1))=1|θ(R(t))=0}＞0，令,… 然后：

因此，当t→∞时，P{θ(R(t))≥1}→1，即HAFPSO算法是收敛的。 □

4 仿真实验及结果分析

4.1 测试函数

为了测试HAFPSO算法的效果，对11个标准测试函数进行仿真实验。表1给出了11个测试函数的名称、搜索空间范围、属性和最优值。

Table 1 Test functions表1 测试函数

4.2 调节变量Limit中β值选择实验

为了确定HAFPSO算法Limit变量中β的最佳值，设定粒子维数D=50，粒子数目N=30，最大迭代次数为2 000，对β分别取值为0.2、0.4、0.6、0.9、1.1、1.3、1.6、1.8进行了测试，实验结果如表2所示。其中Mean代表20次实验中解的平均值，反应了解的质量；Std表示解的方差，反映了算法的稳定性。

从表2中可以看出，当β的取值为1.1时，算法的寻优精度最高，性能最好。这一点充分体现了算法在对异常粒子处理过程中的自适应过滤机制对提高算法收敛精度有一定的贡献。从表2中数据分析可知，当β值较大的话，会出现对懒惰粒子的更新速度不够而寻优精度不高的现象；β取值较小的话，算法的自适应过滤能力过度，这在F2、F3、F5中体现得较为明显；当β小于1.1时，算法在给定迭代次数内的寻优精度随着β的增加而有所提高。

Table 2 Influence of different βon HAFPSO表2 不同β对HAFPSO算法的影响

4.3 性能测试实验与分析

将本文算法HAFPSO与标准粒子群PSO、APSO（adaptive particle swarm optimization）[10]、HPSO[15]进行对比，从而验证算法的性能。本文中实验种群个数为30，测试函数的维数为50维，迭代次数为2 000；APSO和HPSO算法的参数设置分别见文献[10,15]，实验结果如表3所示。

从表3数据对比可以看出，在标准测试函数中，HAFPSO算法相较于HPSO算法在解的质量、算法的稳定性上都有了很大的提高。特别地，在F8、F11的寻优精度和稳定性上表现得尤为突出：F8是非凸的病态函数，常用于考察算法的执行效率；F11为多峰函数，用于测试算法跳出局部最优的能力。显然，HPSO算法在单峰函数F2、F3、F9以及多峰函数F8、F11中寻优精度较弱。而HAFPSO算法在上述所有的测试函数中都有着很好的表现。

为了更直观地反映算法的寻优效果，4种算法对相关测试函数的收敛曲线如图4所示。图中的横坐标表示迭代次数，因篇幅有限，图中只列出其中6幅，其他效果类似。从图4中可以看出，HAFPSO算法具有较快的收敛速度，无论是单峰函数还是多峰函数都只需较少的迭代次数就能找到全局最优。

为了进一步展示各种算法种群的位置多样性[16]随迭代次数的变化情况，图5给出了4种算法的位置多样性在迭代过程中的变化曲线，由于篇幅有限，本文仅列举3幅，其他效果类似。图中横纵坐标分别表示种群的迭代次数和当前的位置多样性I(X(t))，表达式如下：

从图5中可以看出，HAFPSO算法在迭代初期粒子多样性相对偏低，种群搜索范围相对较小，从而使算法具有相对较强的局部搜索能力，加快算法收敛速度；在迭代后期，粒子多样性相对较高，粒子能够在较大范围内进行搜索，增强了粒子群的全局搜索能力，提高算法收敛速度。纵观整个迭代过程，HAFPSO算法中粒子群的位置多样性I(X(t))较为稳定，有利于平衡种群的局部探索和全局探索能力。因此，通过对表3、图4、图5的分析可知，HAFPSO算法在寻优精度和收敛速度方面明显优于其他算法。

4.4 算法寻优时间对比

为了进一步表现HAFPSO算法在寻优速度上的优势，将各算法独立运行20次，比较相同仿真环境，粒子维数皆为50的情况下，达到指定收敛精度（1.00E-04）所需要的运行时间，如果200 000次迭代后仍然没有达到该精度，则用“—”表示，结果如表4所示。

Table 3 Comparison for 50-dimension problems表3 各算法在50维下的计算结果比较

Fig.4 Convergence curves图4 收敛曲线

Fig.5 Position variety图5 位置多样性

由表4中数据分析可知，在仿真环境和参数设置相同的情况下，本文提出的HAFPSO算法达到给定的寻优精度所需的运行时间优于HPSO算法，这也从另一方面再次验证了HAFPSO算法的有效性。

5 结束语

针对标准粒子群算法在寻优时存在收敛速度慢以及难以跳出局部最优等问题，本文提出了基于健康度的自适应过滤粒子群算法（HAFPSO）。通过计算粒子健康度区分粒子状态，标记异常粒子，当该粒子被处理次数超过一定阈值而仍没有逼近最优解的趋势时，重新生成新的位置；同时，利用引导因子引导更新最差粒子值，避免无效搜索，加快算法收敛速度。仿真实验结果表明，HAFPSO算法寻优精度高，收敛速度快，在性能上比文中给出的其他改进算法更优。

Table 4 Comparison of time for achieveing optimization表4 算法寻优时间比较

[1]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//Proceedings of the 6th International Symposium on Micro Machine and Human Science,Nagoya,Oct 4-6,1995.Piscataway:IEEE,1995:39-43.

[2]Chatterjee A,Siarry P.Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization[J].Computers&Operations Research,2006,33(3):859-871.

[3]Pi Qianying,Ye Hongtao.A dynamic adjusting inertia weight particle swarm optimization[J].Journal of Guangxi University of Science and Technology,2016,27(3):26-32.

[4]Clerc M.The swarm and the queen:towards a deterministic and adaptive particle swarm optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation,Washington,Jul 6-9,1999.Piscataway:IEEE,1999:1951-1957.

[5]Zhang Shuiping,Zhong Weibiao.Hybrid particle swarm optimization algorithm of new learning factors and constraint factor[J].Application Research of Computers,2015,32(12):3626-3628.

[6]Khamsawang S,Wannakarn P,Jiriwibhakorn S.Hybrid PSODE for solving the economic dispatch problem with generator constraints[C]//Proceedings of the 2nd International Conference on Computer and Automation Engineering,Singapore,Feb 26-28,2010.Piscataway:IEEE,2010,5:135-139.

[7]Premalatha K,Natarajan A M.Discrete PSO with GA operators for document custering[J].International Journal of Recent Trends in Engineering,2009,1:20-24.

[8]Qin Quande,Cheng Shi,Zhang Qingyu,et al.Particle swarm optimization with interswarm interactive learning strategy[J].IEEE Transactions on Cybernetics,2015,46(10):2238-2251.

[9]Ao Yongcai,Shi Yibing,Zhang Wei,et al.Improved particle swarm optimization with Adaptive inertia weight[J].Journal of the University of Electronic Science and Technology of China,2014,43(6):874-880.

[10]Zhan Zhihui,Zhang Jun,Li Yun,et al.Adaptive particle swarm optimization[J].IEEE Transactions on Systems,Man&Cybernetics:Part B,2009,39(6):1362-1381.

[11]Das S,Goswami D,Chatterjee S,et al.Stability and chaos analysis of a novel swarm dynamics with applications to multi-agent systems[J].Engineering Applications of Artificial Intelligence,2014,30(3):189-198.

[12]Gong Yuejiao,Li Jingjing,Zhou Yicong,et al.Genetic learning particle swarm optimization[J].Journal of Power&Energy Engineering,2016,46(10):2277-2290.

[13]Angeline P J.Evolutionary optimization versus particle swarm optimization:philosophy and performance differences[C]//LNCS 1447:Proceedings of the 7th International Conference on Evolutionary Programming VII,San Diego,Mar 25-27,1998.Berlin,Heidelberg:Springer,1998:601-610.

[14]Zhang Chengxing.Comprehensive informed particle swarm optimizer based on constrict factor[J].Journal of Frontiers of Computer Science and Technology,2014,8(4):506-512.

[15]Jin Qibing,Wang Kewen,Zhao Zhenxing,et al.HPSO algorithm with high speed convergent based on particle health degree[J].Applied Mathematics&Information Sciences,2014,8(4):1809-1821.

[16]Shen Yuanxia,Wang Guoyin,Zeng Chuanhua.Study on the relationship between population diversity and learning parameters in particle swarm optimization[J].Acta Electronica Sinica,2011,39(6):1238-1244.

附中文参考文献：

[3]皮倩瑛,叶洪涛.一种动态调节惯性权重的粒子群算法[J].广西科技大学学报,2016,27(3):26-32.

[5]张水平,仲伟彪.改进学习因子和约束因子的混合粒子群算法[J].计算机应用研究,2015,32(12):3626-3628.

[9]敖永才,师奕兵,张伟,等.自适应惯性权重的改进粒子群算法[J].电子科技大学学报,2014,43(6):874-880.

[14]张成兴.压缩因子综合信息粒子群算法[J].计算机科学与探索,2014,8(4):506-512.

[16]申元霞,王国胤,曾传华.PSO模型种群多样性与学习参数的关系研究[J].电子学报,2011,39(6):1238-1244.