一种变异的改进粒子群优化算法

陈永刚 邱 涌 肖春宝

(河南科技大学电子信息工程学院，河南 洛阳 471003)

1.引言

粒子群优化算法（PSO）是由Kennedy和Eberhart等于1995年发明的一种基于群智能的进化计算技术[1，2]，来源于对鸟群捕食的行为研究。后来shi等人[3]引入惯性权重，形成了当前的标准版本。PSO的优势在于概念简单，容易实现并且没有许多参数需要调整，目前已经成功应用于结构设计、神经网络[4]、多目标优化[5]等工程优化中。

PSO算法收敛速度较快，但会出现早熟收敛，甚至不收敛的情况，尤其对于多峰函数而言不能令人满意，对高维函数优化在求解质量上和速度上有些缺点。对PSO算法进行改进提高优化性能为该领域的一个研究热点。相继出现了一些改进的算法，然而这些算法在一定程度上改善了算法的优化性能，但很难在搜索精度和早熟收敛之间达到平衡。针对上述缺点，本文提出了一种改进的粒子群算法，该算法引入了合作算子[6]，在迭代优化过程中对粒子进行两种合作策略的变异，使粒子群体保持多样性。本文分析了粒子速度更新公式的基础上，提出了动态改变粒子的粒子分享个体最优和群体最优的信息比例的方法，使算法初期具有全局搜索能力，后期具有较好的搜索精度。实验结果表明，该算法具有较好的优化效率。

2.粒子群算法介绍

2.1 PSO算法基本原理

PSO初始化为一群随机粒子（随机解），然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个叫做个体极值，记为Pi。另一个极值是整个种群目前找到的最优解，这个极值是全局极值，记为Pg。

设搜索空间为D维，总粒子数为n，第i个粒子表示为xi=(xi1，xi2，…xiD)；第 i个粒子的历史最优位置记为 Pi=(pi1，pi2，…piD)；整个群体经历过的最好位置记为 Pg=(pg1，pg2，…pgD)，粒子速度记为 Vi=(vi1，vi2，…viD)。则对于每一代，每个粒子的位置根据如下方程变化。

其中c1和c2是非负常数并且通常取值为2，称为学习因子。r1和r2是介于[0，1]之间的随机数。每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被设定为Vmax，即 vid∈[-Vmax，Vmax]。

2.2 算法流程

标准PSO的算法流程如下：

Step1：初始化所有粒子，包括随机位置和速度；

Step2：评价每个粒子的适应值；

Step3：对每个粒子，将其适应值与其经历过的最好位置Pi作比较，如果较好，则将其作为当前的最好位置Pi；

Step4：对每个粒子，将其Pi与全局所经历的最好位置pg作比较，如果较好，则重新设置pg；

Step5：根据公式(1)和(2)进行速度和位置(解)的迭代；

Step6：重复Step2～Step5，直到满足算法停止迭代的条件。

3.改进的粒子群优化算法(IPSO)

标准的PSO算法中，若粒子找到一个最优位置，则其他粒子会迅速向其靠拢，此时若最优位置为局部最优，则粒子就可能陷入早熟收敛。这样就导致了粒子群体不能在优化空间重新搜索和运动。为了使粒子能进一步进化和继续优化，本文采用了合作算子对历史最优粒子进行变异的方法。这样不仅使变异后历史最优粒子更好地引导粒子的运动，使粒子摆脱局部收敛。还可以进化整个种群的最优粒子，更好地搜索最优解，提高搜索精度。同时对最优粒子采取保序策略，确保群体最优解向好的方向进化。

3.1 合作算子

设两个个体粒子为 p1=(x1，x2，…xD)和 p2=(y1，y2，…yD)。如果∈(0，1)

合作策略1中，q和r由式（3）产生：

其中，βk为0和1之间的随机数。

合作策略2中，由式（4）产生：

其中，1

3.2 对运动公式进行动态调整

由于算法的优化效果取决于粒子运动的两个公式，所以改动公式，就相当于是粒子的运动发生了变化，进而产生不同的优化效果。

从公式(1)可见，粒子速度更新由三部分完成。第一部分反应粒子当前速度的影响，联系粒子当前的状态，起到了平衡全局和局部搜索的能力；第二部分反应认知模式的影响，即粒子本身记忆的影响，使粒子具有全局搜索能力，避免陷入局部极小；第三部分反应社会模式的影响，即群体信息的影响，体现粒子间的信息共享。令φ1=c1r1，φ2=c2r2，显然φ1和φ2是介于0和2之间的随机数。显然在算法初期应该增加粒子的群体搜索能力，这样必须加强粒子本身记忆的影响，削弱群体最优粒子的影响。这时，令φ1=1+φ1/2，φ2=φ2/2，这样就有，φ1∈(1，2)，φ2∈(0，1)，较好地增加了个体经验对粒子速度的影响，提高群体多样性，从而增加算法的全局搜索能力，有效增强避免早熟收敛能力。算法后期，由于大部分粒子都聚集在最优粒子周围，为了找到更好的结果，需要增加最优解附近的搜索，需要最优粒子分享更多的信息给整个种群。这时，令 φ1=φ1/2，φ2=1+φ2/2。这样粒子局部搜索能力得到了加强，提高了优化精度。

4.仿真实验和结果分析

本文采用了标准PSO算法和改进算法进行实验，并将结果进行对比。两种算法采用相同的参数设置。线性下降的惯性权重的变化范围是[0.3，0.9]。实验中的种群规模设置为30，粒子的维数为30，最大的迭代次数为1000次。CS设置为0.5，保证粒子的两种变异方式都能平均地采用。两个测试函数如下：

Rastrigin函数

Griewank函数

算法迭代次数为1000次。算法对每个函数独立运行30次，取最优值和平均最优值作对比。结果如表1。

表1 仿真结果

从表中的测试结果中，可以看出本文IPSO算法的最优收敛值和平均收敛值要优于标准PSO，这充分说明了IPSO算法具有更好的搜索精度，较强的抗早熟能力和较快的收敛速度，并且算法也具有较好的稳定性。

5.结论

本文提出的改进PSO算法，对于每次迭代，粒子群体之间采用合作算子进行变异进化，合作算子通过粒子之间相互作用来增加彼此的适应度，提高了算法的收敛速度和精度。对于算法不同阶段粒子运动公式的改变，可以较好地平衡粒子的全局搜索和局部搜索的能力，避免算法陷入早熟收敛。通过对2个基准测试函数的仿真，证明了本文的IPSO算法对于高维、多极值点的函数有较好的效果。

[1]Kennedy J，Eberhart R .Particle swarm optimization[A].Proc IEEE Int Conf on Neural Networks[C].Perth，1995.1942-1948.

[2]Eberhart R，Kennedy J.A new optimizer using particle swarm theory[A].Proc 6th Int Symposium on Micro Machine and Human Science[C].Nagoya，1995.39-43.

[3]Shi Y，Eberhart R.A modified particle swarm optimizer[C].In：IEEE World Congress on Computational Intelligence，1998：69-73.

[4]王建芳，李伟华.基于扩展的T-S模型的PSO神经网络在故障诊断中的应用[J].计算机科学，2009，36(9)：224-245.

[5]刘衍民，牛奔，赵庆祯.基于交叉和变异的多目标粒子群算法[J].计算机应用，2011，31(1)：82-84.

[6]焦李成，刘静，钟伟才.协同进化计算与多智能体系统[M].北京：科学出版社，2006.