基于改进粒子群算法的函数优化

陈永刚 邱涌 牛丹梅

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

1.引言

粒子群优化算法（PSO）是由Kennedy和Eberhart等于1995年发明的一种基于群智能的进化计算技术[1，2]，来源于对鸟群捕食的行为研究。后来shi等人[3]引入惯性权重，形成了当前的标准版本。PSO的优势在于概念简单，容易实现并且没有许多参数需要调整。因此，该算法很快应用于神经网络[4]、多目标优化[5]、函数优化[6]等问题。作为一种高效的全局优化算法，PSO可用于求解大量非线性、不可微和多峰值的复杂函数优化问题。为了提高算法的优化效率，近几年出现了很多改进的PSO算法,并且已经应用于许多科学和工程领域。然而，当遇到某些具有较多局部极值点的搜索空间时，PSO算法的搜索效率可能会突然大大降低并且在最优点附近的搜索效率也不高。

对于这些问题，许多人做了大量的工作来改进算法的性质，比如从参数的控制角度出发，可以结合其它算法来增强算法的效率。本文提出了一种改进的粒子群算法，通过不断随机初始化部分适应值较差的粒子的位置，个体历史最优粒子做相互交叉变异和群体最优粒子在最优值空间附近的变异搜索，有效地克服了算法的早熟收敛，搜索效率和速度都有较大的提高。

2.粒子群优化算法介绍（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是非负常数，称为学习因子。r1和r2是介于[0，1]之间的随机数。w称为惯性因子，w较大适用于对解空间进行大范围探查，w较小适用于进行小范围搜索。每一维粒子的速度都会被限制在一个最大速度Vmax,如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被设定为Vmax，即 Vid∈[-Vmax,Vmax]。

PSO算法基本步骤如下：

Step1：随机初始化粒子种群，即初始化种群中所有粒子的速度和位置(可行解)；

Step2：根据适应度函数对粒子种群进行评价；

Step3：更新粒子的个体极值；

Step4：更新粒子的群体极值；

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

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

3.改进的粒子群算法（MPSO）

本文提出的改进算法中，位置和速度更新公式仍然与PSO相同。

3.1 部分粒子的位置随机变化

由于粒子群算法对于多峰值函数空间的优化容易早熟收敛，每次迭代搜索时，使适应值最差的部分粒子的位置在搜索空间中重新随机分布，这样就改善了部分粒子的位置值，保持了粒子的多样性，使部分粒子进行算法发散的搜索。这里取全部粒子的30%进行随机初始化。

3.2 历史个体最优粒子之间进行交叉变异

对历史个体最优粒子之间进行两两杂交，这个杂交概率由一个随机数确定，与粒子的适应度没有关系。在每次迭代中，所有的个体最优粒子进行随机的两两杂交，产生同样数目的孩子粒子，并用孩子粒子代替父母粒子作为个体最优粒子来引导粒子的运动。孩子粒子的位置由父母粒子的位置的算术加权计算。公式如下：

3.3 对群体最优粒子进行小范围位置变异

PSO算法的一个不足之处在于在算法运行的后期，受到速度等因素影响，粒子会在全局最优点附近摆动，却不能到达到全局最优点。考虑到此时粒子距离最优点已经很近了，因此应该进行小步长的变异。使最优粒子位置做出变异，除了能做进一步搜索之外，还可以引导其它粒子作搜索。位置变异公式如下：

其中Pi的适应值比较接近Pg，可在个体历史最优群体中前10%的个体中随机选取一个。r3为随机整数，r4是介于[0，1]之间的随机数。算法中Pg对采取保序策略，用一个变量保存最优的Pg，保证算法得到的最优解。

4.仿真结果及其分析

（1）为了验证本文改进算法的有效性，本文以求解两个基准测试函数的最小值为例，通过计算机仿真比较本文算法和标准PSO算法的性能。选择以下2个典型函数进行测试：

sphere函数

实验中两种算法的群体规模为30，惯性权重w的值从1.1线性递减到0.3，c1=c2=2，第一个函数为10维，第二个函数为2维。

算法迭代次数为1000次，取平均适应值和平均迭代次数。结果如表1：

表1 仿真结果

从表中的指标上看，改进的算法MPSO都优于标准的PSO，且求解精度优势明显优于标准PSO，说明了改进算法的有效性。

5.结论

对标准的PSO算法主要进行了3个方面的改进，大大改善了粒子种群的多样性，增强了优化性能的稳定性，较好地解决了算法的早熟收敛和后期搜索精度较低的缺点。实验证明，改进后的算法达到了预期的目的。

[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 Congresson Computational Intelligence,1998：69-73.

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

[5]基于小生境的极性PSO多目标优化及应用 [J].自动化与仪表,2011,08：45-48.

[6]一种基于量子行为的改进粒子群算法 [J].计算机工程与应用,2007,43(36)：89-91.