文/墨茶

编辑/墨茶

引言

【研究意义】PSO是Kennedy和Eberhart在1995年首次提出，这是一种基于微粒群的全局寻优方法。该方法将每一个最优问题的求解，都看作是一个无体无质的小颗粒，并将该小颗粒扩展到N维，将颗粒的运动轨迹用一个向量表达。

粒子群算法相对于其他优化算法，对优化目标的建模无特殊要求，可调参数较少，收敛速度较快，同时还兼具随机可扩展的特点，在多目标优化、模糊控制、神经网络学习等方面得到了广泛的应用。

【前人研究进展】为了改善PSO的搜索效果，许多研究者从各个角度对PSO进行了改进。例如，胡旺等人提出了一种新的方法，即在微分方程中加入了一种新的微分方程的方法，使其实可以求解出微分方程的解；刘伟等人给出了一种惯性权函数，这种方法可以很好地兼顾全局和局部寻优的性能；王等人用Cauchy突变将其他颗粒导向更好的地方。

【本研究切入点】针对传统PSO方法存在收敛慢、搜索精度低、易陷入局部极值等问题，通过引入干扰系数，使得自适应的惯性加权和Cauchy突变，这样就解决了传统PSO方法收敛慢、搜索精度低、易陷入局部极值等问题。

【拟解决的关键问题】通过与已有PSO算法进行对比，总结各种PSO算法的优势与不足，为PSO算法的完善与应用奠定理论基础。

标准粒子群优化算法（SPSO）

PSO中的每颗颗粒都有一个运动速率vi，它能控制颗粒的运动路径，并通过一种新的适应性函数来决定颗粒的运动路径。其中，微粒的运动路径由微粒自己的经验pbest和种群的最佳gbest决定。一个颗粒了解自己的当前位置以及到现在为止找到的最佳位置，一组中最佳体验的gbest表示，迄今为止，在一组中找到的最佳地点。

Kennedy和Eberhart首先给出了粒子群优化方法对定位修正的速率的计算方法，其结果是：

其中：t代表的是当前的迭代次数，c1和c2代表的是学习因子，r1、r2代表的是分布在[0,1]内的随机数，pbest代表的是个体极值，gbest代表的是全局极值。

为了改善PSO算法的收敛性能，并考虑到对不同的问题，局部和全局的优能力权衡是不相同的，Shi和Eber-Hart在1998年引进了惯性加权ω，并将其加入到基本粒子群算法的速度更新公式中，

其中，t为最大值迭代值，Tmax为粒子的最大迭代值。

粒子群优化算法的改进

微粒群中的微粒，随着微粒群的个数和整体的极大值点而不断地在微粒群中运动。当微粒群的个数占支配地位时，则很可能会导致微粒群的局部极小。

由于该方法容易使得问题的求解过程进入到局部最小，从而导致求解过程中的“提前”问题。为了防止微粒群的“提前”，本文从三个角度对常规微粒群算法作了进一步的完善。

1.极值扰动的引入

由于微粒群具有趋同性，因此，在微粒群算法演化过程中，微粒群的运动速率Vi很难得到实时的调整。而微粒群又存在“聚集性”，此时微粒群仅能在很小的区域中进行搜寻，极易导致微粒群的局部极值问题。

为了获得问题的整体最优，需要解决PSO容易落入局部极值的缺点，而增大PSO的搜索区域是解决PSO问题的一个重要途径。

为此，本项目拟将干扰因素r3、r4加入到速率修正方程中，通过对单个极限点和整体极限点的任意调节，使颗粒能够在较短时间内获得较大的运动轨迹，使颗粒能够快速脱离局部最小化。从Hughwan等人的实验中得到的启示，本文对速率修正公式进行了以下修改：

在[0,1]之间，r3,r4是一个平均分布在[0,1]之间的随机数。随着r3,r4的干扰，每个人的极限pbest和整体极限gbest都发生了变化，使得这些颗粒可以在更广阔的区域进行搜寻。这就增加了颗粒发现最优解的几率，使得颗粒有了跳出局部最优解的可能性。

2.自适应惯性权重

在PSO中，惯量加权gamma是一种可调节的参量，通过对惯量加权的适当设定，可以有效地兼顾PSO的整体和局部搜索性能。当omega值增大时，该方法具有更好的整体优化性能，而当omega值减小时，则具有更好的局部优化性能。

针对欧米伽，采用线性下降的惯性权仅适用于少数几个问题，而在求解过程非常复杂的情况下，这一方法将导致粒子群优化方法在演化结束时，极易进入局部极值而不能获得所需的最优解。基于刘伟等人的报告，本文给出了如下的惯性加权修正公式：

从上面的公式可以看出，这个惯性加权函数是一个非线性的，呈指数形式下降的函数，这会使得欧姆在迭代开始的时候能长时间维持一个很大的值，这样就可以提高迭代开始阶段的全局搜索时间和整体搜索强度。

同时，由于该算法能够在迭代期晚期长期维持在一个很低的数值，因此可以提高算法的全局寻优时间，提高算法的全局寻优能力，提高算法的收敛性。

3.自适应柯西变异

在该方法的收敛性以前，选择最好的gbest时，会在以前的一些候选者中来回摆动。通过对最优解的gbest进行突变，使其在最优解上获得更大的寻踪范围，从而使其更容易从局部极值中跳出。

基于Wang等人的前期工作，我们拟采用Cauchy突变策略，通过对gbest突变函数的突变来防止算法的早期收敛性。

柯西分布（Cauchydistribution）是一类既无预期也无方差的连续分布。标准的柯西的分配函数是这样的：

根据本文所述的柯西突变方法，先对N个在每个维度上的pbest的均值avg_pbest（i）进行计算：

方程（8）中，i=1,2，…，pbest[j][i]表示第j个颗粒在i维中的位置，使用下面的公式（9）来计算avg_pbest（i）到gbest上每个维度的距离。

公式（10）中的re为一个常量，因此在本文中将re=20；最大值为每一维之间的最大间距。将（10）等式替换为（7）等式。

自适应柯西变异操作如式（１１）所示：

其中，z（i）为每个维度的变化加权平均，而v(j)[i]为在i维度中的第j个颗粒的速度成分。

4.基于扰动的自适应粒子群优化算法

在对2.1-2.3进行集成的基础上，提出了一种新的微粒群（ADPSO）算法。

第一步：使微粒的位置xi和其速度vi以任意方式进行初值。

第二步：将第i个微粒的目前位置设为pbest，将最佳微粒的位置设为gbest。

第三步：根据（2）、（5）、（6）等式来调节颗粒的状态，并根据（2）、（5）、（6）等式来修正颗粒的运动轨迹。

第四步：从适应性功能f（x）中，计算出颗粒i的适应性功能f(xi)。

第五步：将f（xi）和f（pbest）进行对比，如果f（xi）好于f(pbest)，则将此颗粒的pbest更新为xi。

第六步：将f（xi）和f（gbest）进行对比，如果f（xi）好于f(gbest)，则将gbest更新为xi。

第七步：利用适应性柯西突变策略，也就是公式（11）对目前得到的gbest进行突变运算。

第8步：判定该算法的最大迭代数是否已经到达，如果该算法的最大迭代数已经到达，则进入第9步，反之，进入第3步。

第9步：输出gbest及对应的目标函数f(gbest)，完成该算法。

仿真实验

在此基础上，将该方法与：①SPSO；②AMPSO；③带有压缩和发散运算的seAPSO。使用5个基准测试函数f1:Sphere,f2:Rosenbrock,f3:Ackley,f4:Grie-wank,f5:Rastrigin（理论最小值都为0)，对它们进行了最优性能的测试。

在这个实验中，设定了以下几个参数：粒子群的种群大小N=40，粒子维数D=30，最大迭代次数Tmax=500,c1=c2=1.4962,omegamax=0.95,omegamin=0.4,AMP-SO和seAPSO算法的参数与原来的文献相同。

我们对每个功能进行20次的运算，并求出平均值，分别将SPSO、AMP-SO、seAPSO、ADPSO记为A1、A2、A3、A4，模拟结果与统计数据见表1，每个功能的适应度演化曲线如图1~5所示。

函数f1主要被用来进行算法寻优精度的测试，它是一个非线性的对称单峰函数。与其他3个算法相比，ADPSO算法拥有更快的收敛速度，并且优化性能更好（图1）。F2是一类具有代表性的二次病理学问题，且该问题难以求解，ADPSO比其他方法具有更高的收敛性和更高的均值（图2）。

函数f3,f4,f5都是多峰值函数，存在较多的局部极小点，一般的方法很可能会导致收敛到局部极小，不能得到最优或接近最优。

如图3所示，SPSO,AMPSO和seAPSO均处于局部最优状态，ADPSO是在迭代期开始时，因为ADPSO是从局部最优状态中挣脱出来的。因此，ADPSO是在演化结束时，在接近整体最优状态下获得的。

从图4可以看出，AMPSO和ADPSO都可以最终在近似于最优化的情况下，达到较好的适应性，但是ADPSO的适应性更好。

由图5可知，只有ADPSO在演化初期才能打破这一瓶颈，而且该方法的适应均优于其他三种方法。

由此可以看出，与其他三种方法相比，本文所设计的ADPSO算法，在适应性等方面都要优于其他三种方法，是一种更为高效、快捷的PSO方法。

结论

本项目拟对经典微粒群算法进行改进，设计一种新的微粒群算法。我们通过引入干扰系数，使用了一种新的惯性权函数，实现了对最佳微粒的Cauchy突变。

采用试验模拟和比较研究相结合的方法，本项目所设计的新方法，不仅能够有效地提升PSO的整体寻优能力，而且能够显著地提升PSO的适应性。

参考文献：

1.徐鹤鸣．多目标粒子群优化算法的研究．上海：上海交通大学

2.孟庆宽，仇瑞承，张漫，等．基于改进粒子群优化模糊控制的农业车辆导航系统．农业机械学报

3.高海兵，高亮，周驰，等．基于粒子群优化的神经网络训练算法研究．电子学报

4.胡旺，李志蜀．一种更简化而高效的粒子群优化算法．软件学报