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

任贺宇，郭 磊，赵开新

（1.河南交通职业技术学院，郑州 450000；2.河南省民政学校，郑州 450002；3.河南工学院，河南 新乡 453002）

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

任贺宇1，郭 磊2，赵开新3

（1.河南交通职业技术学院，郑州 450000；2.河南省民政学校，郑州 450002；3.河南工学院，河南 新乡 453002）

针对基本粒子群算法存在着收敛速度慢、效率低、易陷入局部最优等缺陷，为了更好地平衡全局和局部搜索能力，在粒子群算法中引入收缩因子，使算法中粒子不仅向种群最优的粒子进行学习，而且向种群中比自己优秀的所有粒子学习，增加了粒子的多样性。实验结果证明，与基本蚁群算法相比，改进的粒子群算法提高了收敛速度和效率，能一定程度地避免局部最优解的产生。

粒子群，全局最优，局部最优，学习规则

0 引言

粒子群算法［1-2］（Particle swarm optimization algorithm）是由Eberhart和Kennedy在1995年基于鸟群的捕食活动而提出的一种启发式的全局优化算法。其基本思想是通过群体中个体的合作机制来迭代寻找最优解的。算法中鸟群在捕食时个体的行为与自身的最佳位置信息和整个群体的最佳位置相关，在捕食初始阶段，每只鸟向各个方向的运动是随机的，随着时间的推移，所有鸟都趋向于一个中心移动，最终鸟群的运动轨迹都趋于一致。基本粒子群算法存在着收敛速度慢、局部最优等缺陷，为了提高粒子群算法的性能，近些年来国内外学者提出了许多优化方案。其中包括动态修改惯性权重值、设置粒子的跳出和牵引机制、使粒子群算法与其他智能算法相融合等［3-4］。

1 粒子群算法的数学模型

图1 粒子群速度更新图

式（1）中ω为惯性权重值，c1和c2为学习因子，用于调节粒子对自己历史经验最优位置和整个群体最优解位置的依赖程度，pkid表示粒子i在d维的个体位置最优值，pkgd表示粒子群在d维的最优值，r1，r2为（0，1）随机数。为了防止粒子速度太快，还应满足式（3），其中 Vmax表示速度向量的最大值［5-6］。

在粒子群算法中，个体位置最优解按式（4）进行更新，群体位置最优解按式（5）进行更新［7-8］。

2 粒子群算法的改进

2.1 在粒子群算法中引入收缩因子

为平衡种群局部和全局搜索能力，在基本粒子群算法引入收缩因子后，粒子速度的更新为式（6）。

2.2 改进粒子的社会学习规则

式（1）中第3部分社会认知选项只考虑了当前粒子向群体内全局最优粒子学习，而忽略了向其他次优粒子的学习，这样可能会导致局部最优解，改进的算法中粒子向当前群体中比自己优秀的所有粒子学习，这增加了粒子的多样性，能一定程度上避免局部最优解的产生。改进后粒子的速度更新为式（8）。

式（9）中m为粒子群中粒子数，f（）为粒子适应度值的计算函数，pj表示第j个粒子的最优位置，表示粒子群全局最优位置，从式中可以看出，f（pj）越大，被学习的粒子越优秀，ekid的值越大，gp表示当前粒子i向粒子j学习程度越强。f（pj）的值越大，ekid的值越小，表示当前粒子越优秀，当前粒子i向粒子j学习程度越弱。

2.3 改进后粒子群算法的实现

用上述两种方法优化后粒子群算法的速度更新为式（10），位置更新仍采用式（1）。

优化后粒子群算法的实现步骤。

Step1:初始化粒子群相关参数。

Step2:根据适应度函数f（）求出各粒子的初始适应度值。

Step3:根据优化后粒子群算法更新式（10）更新各粒子的速度，根据位置更新式（2）更新各粒子的位置向量。

Step4:根据式（4）和式（5）更新最优个体位置与最优种群全局位置。

Step5:如果达到优化后粒子群算法结束的条件或设定的迭代次数则搜索终止，否则转到Step2继续执行。

3 仿真测试与分析

3.1 测试函数

为测试优化后粒子群算法的效率，分别用函数Rosenbrock和Rastrigin来测试优化前后的粒子群算法进行分析，测试使用的算法有标准粒子群算法（PSO），引入收缩因子和改进社会学习规则的粒子群算法（Particle swarm optimization algorithm with shrinkage factor and improved social learning rule，PSO-SFISLR），具体测试参数见表1。

表1 测试函数

3.2 测试结果分析

仿真实验中设置种群规模为20个，每个粒子为30维，最大迭代次数为200，算法中ω取值为0.5，σ 值取 1，c1=c2=2.05，=0.792。图2和图3为用两个测试函数对基本粒子群算法和优化粒子群算法的测试结果，其中横坐标为迭代次数，纵坐标为适应度值。

图2 函数F1进化曲线

图3 函数F2进化曲线

从图2和图3可以看出，通过两个函数的测试结果，PSO-SFISLR比PSO有更快的收敛速度和求解速度，并且PSO-SFISLR能够边求解、边优化，而PSO会找到局部最优的解而停止优化，虽然迭代次数增加，仍不能跳出局部最优解。PSO-SFISLR由于引入收缩因子和向比自己优秀的所有粒子学习的特性，保持了种群的多样性，提高了算法的求解性能和效率。

4 结论

本文提出了改进社会学习规则和引入收缩因子的粒子群算法（PSO-SFISLR），该算法较好地平衡了全局和局部搜索能力，在粒子信息更新时不仅向种群最优的粒子进行学习，而且向比自己优秀的所有粒子学习，通过仿真证明PSO-SFISLR有较高的全局搜索能力、较快的收敛速度和精度较高的寻优搜索效率。

［1］袁正午，李君琪.基于改进粒子群算法的云资源调度［J］.计算机工程与设计，2016，37（2）:401-404.

［2］赵莉.基于改进量子粒子群算法的云计算资源调度［J］.南京理工大学学报，2016，40（2）:223-228.

［3］蔡琪，单冬红.改进粒子群算法的云计算环境资源优化调度［J］.辽宁工程技术大学学报，2016，35（1）:93-96.

［4］赵志刚，林玉娇.基于自适应惯性权重的均值粒子群优化算法［J］.计算工程与科学，2016，38（2）:501-505.

［5］彭建新，詹志辉.全局信息引导的改进粒子群优化算法［J］.小型微型计算机系统，2016，37（7）:1518-1521.

［6］李桂琴，李刘东.一种结合自适应惯性权重的混合粒子群算法［J］.哈尔滨理工大学学报，2016，21（3）:49-53.

［7］徐从东.一种平衡全局与局部搜索能力的粒子群优化算法［J］.微电子学与计算机，2016，33（6）:134-138.

［8］王辉，朱龙彪.基于粒子群遗传算法的泊车系统路径规划研究［J］.工程设计学报，2016，23（2）:195-200.

An Improved Particle Swarm Optimization Algorithm

REN He-yu1，GUO Lei2，ZHAO Kai-xin3
（1.Henan Communication Vocational Technology College，Zhengzhou 450000，China；2.Henan Provincial Civil Affairs School,Zhengzhou 450002，China；3.Henan Institute of Technology,Xinxiang 453002，China）

In view of the basic particle swarm optimization algorithm exits the slow speed convergence,low efficiency,and is easy to fall into the local optimum.In order to better balance the global and local search capability,the shrinkage factor is introduced into the particle swarm optimization algorithm.The particle of the population not only learn from the best particle,but also learn from all the particles in the algorithm,the diversity of particles is increased,The experimental results show that the improved particle swarm optimization algorithm can improve convergence speed and efficiency,and avoid the generation of local optimal solution comparing with the basic ant colony algorithm.

particle swarm，global optimum，local optimum，learning rule

TP242

A

10.3969/j.issn.1002-0640.2017.08.027

1002-0640（2017）08-0120-03

2016-06-19修回日期：2016-08-14

国家自然科学基金（61174085）；河南省高等学校重点科研基金资助项目（16A520084）

任贺宇（1981- ），男，河南滑县人，硕士。研究方向：人工智能、计算机网络技术。