基于进化能力的多策略粒子群优化算法

王晓艳，曹德欣

中国矿业大学 数学学院，江苏 徐州 221116

粒子群优化（particle swarm optimization，PSO）[1]算法是受鸟群捕食行为启发提出的一种群体智能算法。该算法简单、收敛快、鲁棒性高、易于实现，已经在特征选择[2]、移动机器人定位[3]、工程设计[4]等多个问题上被广泛应用。然而，在算法后期，粒子常常被困于局部最优，从而过早收敛，因此研究人员从改进参数、增加种群多样性、与其他智能算法结合等方向对粒子群算法进行改进。Shi和Eberhart提出线性递减惯性权重[5]，算法性能得到提升，之后又针对动态系统提出一种随机调整惯性权重[6]的方法。文献[7]设计了一种自适应惯性权重，并对群体最优引入混沌策略，从而避免粒子陷入局部极值。文献[8]利用其他粒子的个体历史最优来更新粒子的速度，以提高种群的多样性。文献[9]结合RMSProp算法中对学习率每个维度自适应调整的策略，设计自适应的惯性权重。文献[10]对粒子的进化趋势进行干预，减少随机性，同时用个体最优指导群体最优在单个维度的学习，提高收敛精度。文献[11]将遗传算法、蚁群算法和粒子群算法相结合，提升算法的探索和开发能力。同时，有学者利用混合多种不同进化策略或学习机制的方式，取长补短，克服算法缺陷。文献[12]中让粒子根据历史经验和环境感知自适应选择不同的进化策略。文献[13]引入三洞系统捕获策略提升种群多样性，多维随机干扰策略和早熟扰动策略提升算法精度。文献[14]在简化粒子群算法的基础上融入基于相似度及聚集度分析的莱维飞行，帮助粒子逃离局部最优。这些措施对算法性能有一定程度的提升。

在粒子群算法中，整个种群都采用同一个进化策略，迭代后期就易出现多样性不足，从而降低算法全局寻优能力。将种群分为多个子群，分别采取不同的学习机制，是一种较好的增加种群多样性方式。文献[15]将种群分为三个协同优化的子群，各个子群分别侧重搜索不同的区域，实现算法性能提升。文献[16]将粒子群分为多个子种群，并分别采取不同的DPPSO变体进化，子种群间以一定的迁移规则实现信息交流，提升算法稳定性。文献[17]根据粒子适应值以及适应值均值和标准差将粒子所在区域分为拒绝域、亲近域、合理域，并分别选取不同的惯性权重和学习因子。文献[18]根据粒子适应值，在迭代过程中将粒子动态分为三个阶层，并分别采取局部、标准、全局学习模型，增加种群多样性。但是目前大多的分群策略都是依据粒子适应值的优劣进行的，对粒子的进化能力关注较少，导致算法较易陷入局部最优。

基于此，本文基于粒子的进化能力将粒子群分为不同子群，并融合多策略的思想，提出基于进化能力的多策略粒子群优化算法（EAMSPSO）。首先，在线性递减惯性权重中引入随机性，设计一种带有随机波动的惯性权重，使粒子在算法后期仍然具有跳出当前区域的能力，利于全局搜索。其次，将粒子按照进化能力分为进步粒子、暂时停退粒子、长久停退粒子，并依据不同子群的特性分别执行不同的进化策略，增加种群多样性。

半无限规划问题（semi-infinite programming，SIP）是数学规划中的一类典型非光滑优化问题，是数学规划中的一个重要研究分支，在最优控制、信息技术、交通问题等领域中有着广泛的应用。但半无限规划自身的特点和复杂性，给数值求解带来困难。有学者利用精确罚

函数法[19]、滤波器信赖域方法[20]、区间算法[21]进行求解，取得了较好的结果。本文将EAMSPSO算法应用于半无限规划问题的求解。

1 粒子群优化算法（PSO）

PSO算法由一个随机种群开始，群体中的粒子均有自身的速度参数和位置参数，粒子通过追踪自己在飞行过程中搜索到的最佳位置即个体最优，以及全部粒子经过的最优位置即群体最优，更新速度和位置，不断迭代以达到最优。

设一个种群含有N个粒子，每个粒子是D维空间中的个体。对粒子i，用Xi=[Xi1,Xi2,…,XiD]表示粒子位置，用Vi=[Vi1,Vi2,…,ViD]表示飞行速度，个体最优位置用pbest表示，群体最优位置用gbest表示。速度和位置更新方程是：

其中，t为当前迭代次数，w为惯性权重，c1、c2为学习因子，r1、r2为(0,1)间均匀分布的随机数。

2 基于进化能力的多策略粒子群优化算法（EAMSPSO）

2.1 惯性权重

文献[5]中说明，在算法中惯性权值能够协调局部、全局搜寻能力。惯性权重较大，对于初始种群的依赖较小，粒子发现新领域的能力较强，利于全局搜索；反之，若惯性权重较小，算法则更趋向局部搜寻。对于线性递减的惯性权重，每代所有粒子的惯性权重都一样，粒子的惯性权重在算法后期都较小，如果初步搜寻到的领域中包含全局最优解，粒子可以较迅速地聚拢至全局最优，相反如果前期搜索到的区域不存在全局最优解，那么在迭代后期粒子失去了跳出当前区域的能力，就会陷入局部极值。针对这一问题，在线性递减策略中引入随机性，同时考虑不同粒子的位置的优劣，给予位置较优的粒子较小的惯性权重，位置较差的粒子较大的惯性权重，设计一种带随机波动的惯性权重，如下：

其中，t为当前迭代次数，T为总迭代次数，wmax、wmin为线性递减惯性权重的最大、最小值。r[1,E]是[1,E]上的随机整数，其中E是一个整数，E的大小决定波动的程度。ranki是粒子i的历史最优在整个种群中的位次，个体最优位置越好，排序越靠前，位次越小。

改进后的惯性权重总体呈减小趋势，但是存在一定的随机波动。前期较大的惯性权重能够使得粒子在初期进行广泛的搜寻，同时后期也有一定的概率获得比较大的惯性权重，从而使粒子具有跳出局部极值的能力。

2.2 改进粒子进化方式

定义1粒子i在第t(t≥2)代的适应值变化定义为：

当ΔF(Xit)<0时，说明粒子按照当前方向移动，适应值下降，即粒子处于进步状态，当前的速度仍然具有可参考性。反之，说明粒子按照当前方向移动，适应值没有变好反而变差了，当前速度方向的可参考性降低。

定义2粒子i在第t(t>d,d>1)代的粒子活性定义为：

当dF(Xit)<0时，说明粒子位置对比d代前更好，反映出粒子仍然存在活性，否则说明粒子位置有可能连续d代无优化，粒子已经失去活性。

PSO算法中所有粒子都按照式（1）、（2）更新速度、位置，没有考虑到不同表现的粒子的差异性，导致进化后期，容易出现多样性丢失，从而早熟收敛。考虑到这一问题，本文在每次迭代中，根据适应值的变化将粒子分为进步粒子和停止或者退步的粒子简称停退粒子。针对停退粒子进一步根据粒子活性分为暂时停退粒子和长久停退粒子，并根据不同类型粒子的特点采取不同的进化策略。

2.2.1 进步粒子

进步粒子即适应值下降的粒子，说明粒子当前在沿着正确的方向移动。因此，粒子应该参考过去的经验继续前进。进步粒子采用原算法中粒子的进化方式，通过参考上一代中的速度，并追随个体历史最优和全局最优进行更新，保留原算法的优点。

2.2.2 暂时停退粒子

暂时停退粒子即d代内粒子的位置没有变好，说明粒子当前的速度方向可能需要调整。针对暂时停退的粒子，减小对历史速度的参考，或者对其进行反向参考。更新方式按照式（6）、（2）。

其中，ε是为了减小或者反向对历史速度的参考而引入的调节因子。

2.2.3 长久停退粒子

长久停退粒子即超过d代（含d代）粒子的适应值没有变好。对于这些粒子分为两种情况进行讨论，一类是个体最优对应的适应值较优的粒子，这类粒子可能已经陷入局部最优，如果仍然按照原始进化策略更新会导致粒子停滞在局部最优。同时，这类粒子的适应值较优说明它们占据的位置较好，靠近最优解的概率相对较大，因此这类粒子以一定的概率在个体最优位置周围进一步搜索，或者沿着全局最优的方向搜索。具体更新方式按照式（7）、（8）：

其中，β、α、γ是服从（0，1）正态分布的随机数，pa表示在个体最优周围搜索的概率，1-pa为沿全局最优方向搜寻的概率。

另一类是个体最优对应的适应值相对较差的粒子，这类粒子本身占据的位置相对较差，而且适应值没有下降，说明这类粒子的位置和速度均需要重新调整，让这类粒子直接由个体历史最优出发，向群体最优方向进行搜索。具体的更新方式如式（9）、（8）。

其中，r是（0，1）之间均匀分布的随机数。

2.3 EAMSPSO算法

根据2.1和2.2节的介绍，提出基于进化能力的多策略粒子群优化算法（EAMSPSO），算法的具体执行流程在图1中展示。

图1 算法执行流程Fig.1 Algorithm execution flow

算法EAMSPSO

输入：种群规模N、总迭代次数T

输出：gbest

1.随机初始化N个粒子；

2.计算粒子适应值；

3.初始化gbest；

4.Whilet

5.Fori=1 toNdo

6.按照式（3）更新惯性权重；

7.若t>2按式（4）计算ΔF(Xit-1)否则为-∞；

8.若t>d+1按式（5）计算dF(Xit-1)否则为-∞；

9.IfΔF(Xit-1)≥0

10.IfdF(Xit-1)≥0

11.根据个体最优对应适应值的优劣按照式（7）、（8）或式（9）、（8）更新；

12.Else

13.按照式（6）、（2）更新速度、位置；

14.End if

15.Else

16.按照式（1）、（2）更新速度、位置；

17.End if

18.更新pbest、gbest；

19.End for

20.End while

21.Returngbest

2.4 算法的时间复杂度分析

在PSO算法里，设共N个粒子，粒子维数为D，共迭代T次。算法时间复杂度主要体现在种群初始化以及粒子速度、位置、适应值更新上。假设计算粒子适应度值的时间为f(D)，则种群初始化的复杂度是O(ND+Nf(D))，进行粒子更新的复杂度为O(TND+TNf(D))，算法总时间复杂度为O(TN(D+f(D)) )[14]。

在EAMSPSO算法中，种群初始化的复杂度仍然为O(ND+Nf(D))。每次迭代，首先要计算粒子的适应值变化方向和粒子活性，该过程的时间复杂度为O(N)。其次，粒子被分为进步粒子、暂时停退粒子、长久停退粒子三类分别更新，设每次迭代进步粒子的个数为n1，暂时停退粒子的个数为n2，长久停退粒子的个数为n3，那么n1+n2+n3=N。在每次迭代中，进步粒子、暂时停退粒子、长久停退粒子更新的时间复杂度分别为O(n1D+n1f(D))、O(n2D+n2f(D))、O(n3D+n3f(D))，所以种群更新一次的时间复杂度是O(n1D+n1f(D))+O(n2D+n2f(D))+O(n3D+n3f(D))=O(ND+Nf(D))。此外，对于长久停退粒子需要根据个体最优的适应值优劣分别采取不同的更新策略，因此在每次迭代时，需要将粒子根据个体最优位置的适应值进行排序，排序过程的时间复杂度为O(N2)。综上可知，每次迭代中包含粒子适应值变化方向和粒子活性计算、粒子更新、排序三个步骤，时间复杂度分别是O(N)、O(ND+Nf(D))、O(N2)，当粒子的维度比较小的时候，粒子维度与种群规模接近，当粒子的维度适中或较大时，种群规模接近或者小于粒子维度，所以算法总体复杂度近似为O(TN(D+f(D)))。

3 性能测试

3.1 测试函数

本文通过10个基准函数测试EAMSPSO算法性能。

（1）Sphere函数

（2）Schwefel 2.22函数

（3）Rotated Hyper-Ellipsoid函数

（4）Sum of Different Powers函数

（5）Zakharov函数

（6）Griewank函数

（7）Rastrigin函数

（8）Ackley函数

（9）Quartic函数

（10）Shubert函数

其中，函数f1~f9的理论最优均为0，f10理论最优为−186.730 9。f1~f5、f9是单峰函数，f6~f8、f10是多峰函数。

3.2 参数设置

实验在MATLAB软件环境下进行，算法的粒子规模设为40，算法最大迭代次数设为2 000。EAMSPSO算法中c1=c2=2，粒子活性的评估间隔d取为3。ε取为（0，0.5）之间的随机数，使得暂时停退粒子可以减小对历史速度的参考，在进化后期还存在一定的可能对历史速度进行反向参考。个体最优适应值较优粒子的比例取为1/3。为了平衡算法的探索和开发能力，使长久停退的个体最优适应值较优的粒子以相同的概率在个体最优周围搜索和沿全局最优方向搜寻，因此pa取为50%。

本文采用带随机波动的惯性权重，以使粒子可以跳出局部最优，从而提高算法性能。针对惯性权重中的参数wmax、wmin、E，本文设置以下几组参数，并在函数f2和f9上进行实验对比。不同的参数组合均独立运行30次，实验结果在表1中展示。从表1中的数据可以看出，wmax为0.8，wmin为0.3，E的值取为5时，其实验效果最好。所以本文wmax取0.8，wmin取0.3，E取为5。

表1 惯性权重的参数对比Table 1 Parameter comparison of inertia weights

3.3 数值实验

为了测试算法的性能，通过3.1节中的10个基准测试函数测试EAMSPSO算法性能，并与线性递减惯性权重粒子群优化算法（LPSO）[5]、综合学习粒子群优化算法（CLPSO）[8]、具备自纠正和逐维学习能力的粒子群算法（SCDLPSO）[10]、粒子群优化与灰狼优化的混合算法（HPSOGWO）[22]进行对比实验。LPSO、SCDLPSO算法中c1=c2=2，w:0.9∼0.4，CLPSO算法中c=1.494 45，w:0.9∼0.4，HPSOGWO算法中c1=c2=c3=0.5，w=0.5+rand()/2。5种算法分别在10个测试函数上独立运行30次。

3.3.1 算法在低维函数上的实验

将基准测试函数f1~f9的维度设置为30维，5种不同算法对10个函数的优化结果，包括各个算法独立运行30次得到的平均值、最大值和标准差，在表2中展示。其中，加粗的结果为对比实验中最好的结果。5种算法在10个测试函数下的适应度值变化趋势对比在图2中展示。

3.3.2 算法在高维函数上的实验

利用单峰函数f1、f2和多峰函数f6、f8测试EAMSPSO算法对于高维问题的优化性能，将这4个函数维度设置为100维。各个算法对函数优化30次的平均值在表3中展示。

表3 五种算法对高维测试函数的实验结果对比Table 3 Comparison of experimental results of five algorithms on high-dimensional test functions

3.4 结果分析

当测试函数维度较低时，由表2中的结果可以看出，在单峰函数上，对于函数f1、f3、f4、f5，本文算法EAMSPSO均可收敛到理论最优，其他算法在迭代次数内均未达到理论最优。对于函数f2和f9，本文算法及对比算法均未能收敛到理论最优，但是从表2和图2中可看出，相比其他对比算法，EAMSPSO算法找到的解相对更优。多峰函数具有多个局部极值，求解困难度较高，对于函数f6、f7，本文算法EAMSPSO与算法HPSOGWO可以找到最优值，其他算法在迭代次数内未达到理论最优，而且从图2中可以看出算法EAMSPSO的收敛速度快于算法HPSOGWO。对于函数f8，所有算法均未收敛到理论最优，但从表2中的求解结果和图2中的收敛曲线可以看出，算法EAMSPSO的求解精度和收敛速度均优于其他算法。多峰函数f10理论最优非零，本文算法EAMSPSO和算法LPSO、CLPSO、SCDLPSO均可以找到最优解，从求解的标准差来看本文算法的稳定性更好。

图2 低维函数不同算法的适应值变化趋势对比图Fig.2 Comparison chart of fitness value change trend of different algorithms for low-dimensional functions

表2 五种算法对低维测试函数的实验结果对比Table 2 Comparison of experimental results of five algorithms on low-dimensional test functions

当测试函数设置为100维时，对于函数f1、f6算法EAMSPSO仍然可以找到最优解，对于函数f2、f8五种算法均未到达理论最优，但是相比对比算法，EAMSPSO算法求解的精度更高。可见本文提出的EAMSPSO算法不仅对低维问题的优化效果较好，对于高维问题的求解同样具有优势。

数值结果表明，本文提出的EAMSPSO算法可以有效地跳出局部极值，且算法的稳定性较高。对无论是低维还是高维函数，单峰还是多峰函数，EAMSPSO算法求解精度和收敛速度上都具备优势。

4 EAMSPSO算法求解半无限规划问题

4.1 问题描述及算法

本文所研究的半无限规划问题具体表达形式如下：

其中，X(0)={x=(x1,x2,…,xn)T∈Rn}，f:Rn→R，ϕi:Rn×Rpi→R。

利用罚函数问题（11）可以转化为无约束优化问题（12）：

F(x,β)=f(x)+βq(x)，q(x)=max{0,h(x)}，β为罚因子，当罚因子足够大时问题（12）的解就是问题（10）的解。

本文采用EAMSPSO算法求解半无限规划问题（10），即求解问题（12）。当给定罚因子后，F(x)是关于x的函数，算法中粒子位置即x，粒子适应值即F(x)函数值。该问题的难点在于适应值的计算，F(x)计算中包含一个求解最大值的子问题即对h(x)的计算：

计算过程中需要对m个求最大值的问题进行求解。当x给定时，ϕi(x,t)即为关于t的函数。每个求最大值问题都可以转化无约束优化问题（13）的形式。

针对无约束优化问题（13），同样可以采用EAMSPSO算法进行求解。

4.2 数值实验

将EAMSPSO算法应用于半无限规划问题1~5的求解，并与3.3节中的对比算法进行对比，各个算法参数与3.3节保持一致。求解半无限规划问题时，算法粒子规模设为40，最大迭代次数设为500，每个算法独立运行5次求平均值。同时每个适应值的计算包含的求最值问题，采用同样的算法进行计算，种群规模设为40，最大迭代次数设为100。数值结果在表4~8中展示。

表4 问题1的计算结果Table 4 Calculation result of question 1

表5 问题2的计算结果Table 5 Calculation result of question 2

表6 问题3的计算结果Table 6 Calculation result of question 3

表7 问题4的计算结果Table 7 Calculation result of question 4

表8 问题5的计算结果Table 8 Calculation result of question 5

问题1[23]：

Subject toϕ(x,t)=x12+2x2t2+ex1+x2-et≤0,t∈[0,1]

最优解为（0.719 961，−1.450 487）。

问题2[23]：

最优解为(-ln 1.1,ln 1.1)。

问题3[24]：

最优解为（0，0，0）。

问题4[25]：

最优解为（−1，0，0）。

问题5[25]：

最优解为（3，0，0，0，0，0）。

4.3 结果分析

问题1、2、3中，t是一维变量，问题4、5中t是二维变量。从实验结果可以看出，对于问题1、问题2和问题4，算法EAMSPSO可以找到最优解，其他对比算法均未找到最优解，而且从函数值来看，对比算法求得的函数值小于算法EAMSPSO，说明对比算法在求适应值中包含的最大值问题时存在未达到最优的情况。问题3的目标函数不可微，本文算法EAMSPSO及对比算法在迭代次数内均未达到理论最优，但从求解结果可以看出，本文算法的求解精度更高。对于问题5，五种算法均未找到理论最优，CLPSO算法的求解结果最优，其次是本文算法EAMSPSO。可见，EAMSPSO算法适用于半无限规划问题的求解，且具有一定的优势。

5 结束语

本文提出了基于进化能力的多策略粒子群优化算法（EAMSPSO）。该算法设计了带随机波动的惯性权重，可以使粒子在进化后期也具有跳出当前区域的能力。将粒子群按照适应值变化方向和粒子活性分为进步粒子、暂时停退粒子、长久停退粒子，并分别采取不同的进化策略，提高全局寻优能力。实验结果表明，EAMSPSO算法在求解精度和收敛速度上都具备优势。同时，将EAMSPSO算法应用于半无限规划问题的求解，进一步验证了改进算法的有效性。