一种易跳出局部最优的粒子群优化算法

赵维浩，苏宾，夏筱筠

,（1.中国航空沈阳黎明航空发动机有限责任公司，辽宁沈阳，110043；2.中国科学院沈阳计算技术研究所有限公司，辽宁沈阳，110004）

一种易跳出局部最优的粒子群优化算法

赵维浩1，苏宾1，夏筱筠2

,（1.中国航空沈阳黎明航空发动机有限责任公司，辽宁沈阳，110043；2.中国科学院沈阳计算技术研究所有限公司，辽宁沈阳，110004）

针对粒子群优化算法（PSO）中出现的极易陷入局部最优的问题，本文提出了一种易跳出局部最优的粒子群优化算法。该算法是在算法陷入局部最优时，通过加大惯性权重来改变群体多样性，从而使得该算法能够跳出局部最优。最后，通过大量仿真试验表明，对于求解高维、多峰等复杂的非线性优化问题，该算法能表现出很好的搜索性能。

粒子群优化算法；局部最优；多样性；惯性权重

0 引言

粒子群优化算法（PSO）是Kennedy和Eberhart于1995年提出的一种新的智能优化算法，其基本概念源于对鸟类捕食的行为模拟该算法[1]。该算法是一种基于群体的随机优化方法，系统初始化为一组随机解和运行速度，采用群体解的相互合作机制，通过迭代搜寻最优值[2]。粒子群优化算法与其他智能算法相比，其概念简单、容易实现，并且需要调节的参数较少，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，非常适用于对复杂环境中的优化问题的求解。虽然粒子群优化算法有许多优点，但也存在着易陷入局部最优，进化后期收敛速度慢，精度较差等缺点[3]。为了克服粒子群优化算法的这些缺点,研究人员提出了许多改进的粒子群优化算法。其改进方法的主要目的是通过混合其它智能优化算法或改进控制参数取值来改变群体的多样性，使该算法能够跳出局部最优。

对于通过改变惯性权重而改进该算法的方法主要是线性递减和非线性递减两种，这两种方法在陷入局部最优时，惯性权重较小，并不能更好的改变群体多样性，从而使该类算法容易陷入局部最优。本文通过研究惯性权重对全局探测能力和局部搜索能力的影响，提出一种易跳出局部最优的粒子群优化算法，通过非递减函数改变惯性权重，提高粒子群优化算法的速度和效率。

1 易跳出局部最优的粒子群优化算法

1.1 粒子群优化算法

粒子群优化算法的基本过程为[4]：设算法中粒子群个数为N，搜索空间的维度为D维，其中第i个粒子用向量Xi=(xi1,xi2…,xiD)表示，速度用向量Vi=(vi1,vi2…,viD)表示，到目前为止，该粒子搜索到的最优位置用向量Pi(k)=(pi1(k),pi2(k)…,piD(k ))表示，整个粒子群搜索到的最优位置用向量Pg(k)=(pg1(k),pg2(k)…,pgD(k ))表示。在搜索过程中，每个粒子的位置和速度按如公式(1)和(2)进行变化：

其中，c1和c2为加速因子，分别用于调节粒子飞向自身最好位置方向的步长和调节粒子向全局最好位置飞行的步长；r1和r2是[0,1]中的随机数，为了控制在迭代过程中，粒子的搜索空间； 1dD≤≤；ω为惯性因子。

粒子群优化算法在搜索过程中存在易陷入局部最优的 缺点。由公式(1)可知，当xid(k)=pid(k)=pgd(k )（1≤d≤D，D为搜索空间维度）时，粒子的飞行速度仅由ω(k )和vid(k)决定；若ω(k )≠0且vid(k)≠0， 则粒子将按原有轨迹飞行； 若ω(k)=0且vid(k)=0，一旦所有粒子满足xid(k)=pid(k)=pgd(k )时，则它们将停止飞行，并收敛于局部最优解[5]。因此，需要提高算法的全局搜索能力。

1.2 跳出局部最优方法

为了克服上述基本粒子群优化算法的不足，本文采用动态改变惯性权重的方法使其跳出局部最优。常用的动态改变惯性权重的方法主要分为线性递减[6]和非线性递减，由于使用递减函数改变惯性权重，当粒子群算法陷入局部最优时，惯性权重也变得比较小，有时甚至接近于最小值。因此需要一个函数来满足当粒子群算法陷入局部最优时，惯性权重变得比较大，这样算法就不会停止，继续搜索，从而跳出局部最优。因此这样的函数应满足先递增后递减，基本在陷入局部最优时达到最大值。

根据以上分析本文提出一个二次函数用于动态改变惯性权重，其函数应满足如下公式：

其中，k为当前迭代次数。对于常数a、b和c的取值，通过找到函数应满足的三个坐标点，从而计算出该二次函数。如：ω−ωmin的函数过点(0,0)、(M/2, ωmax−ωmin)和(M,0)，则动态改变惯性权重的函数为：其中，maxω为最大惯性因子；minω为最小惯性因子；M为最大迭代次数；k为当前迭代次数。

1.3 算法流程

易跳出局部最优的粒子群优化算法流程为：

（1） 设置最大迭代次数M，设置加速因子c1和c2；惯性权重最大值和最小值，和三个坐标，确定动态改变惯性权重函数。

（2）在D维空间中，初始化粒子群的位置X1=(x11,x12…,x1D)和速度V1=(v11,v12…,v1D)，同时初始化粒子当前的最优适应度值和最优位置，全局最优适应度值和最优位置。

（3）根据动态改变惯性权重函数，即公式(4) 动态改变惯性权重。

（4） 根据公式(1)和(2)更新粒子的位置和速度。

（5） 根据适应度函数，更新粒子当前的最优适应度值和最优位置，全局最优适应度值和最优位置。

（6） 判断当前迭代次数j,若j

2 实验及结果分析

2.1 测试函数

为了验证改进的粒子群优化算法的性能，本文采用3个标准测试函数（见表1）进行实验验证，其中3个标准测试函数的维数都设为20。测试函数的特点为：函数1是单峰函数，各个变量之间没有相互作用；函数2是一个复杂的单峰病态函数，其部分变量之间的关联性特别强，全局极值点分布区域特别小，所以运用传统的方法很难找到较好值；函数3是多峰函数，变量之间相互独立，有大量的局部极小值，因此很容易陷入局部最优。

表1 3个标准测试函数

2 Rosenbrock ()()()2fxxxx =∑niii i=1■1001■−+−■2+1■−≤≤3030xin 3 Rastrigin ()() fxxxπ =−+∑(2i10cos210i)−≤≤55xii=1

2.2 参数设置

由于3个标准函数相对比较简单，因此实验仿真时，算法迭代次数设为20；种群大小设为100；加速因子c1和c2都设为2.0；惯性权重的最大值设为1.5，最小值设为0.5；则ω−ωmin的函数过点(0,0)、(10, 1)和(20,0)，则动态改变惯性权重的函数为：

其中，k为当前迭代次数。

2.3 实验结果及分析

为了验证本文算法的性能，本文将算法与基本的粒子群优化算法PSO和文献[6]提出的线性递减惯性权重的粒子群优化算法MPSO进行比较。其中图1为函数1的3种函数的比较结果，由于函数1为单峰函数，因此3种算法都不会陷入局部最优，所以3种算法比较结果中，线性递减惯性权重的粒子群优化算法与本文算法性能相当。

图1 算法性能比较（函数1）

尽管函数2是一个复杂的单峰病态函数，其部分变量之间的关联性特别强，全局极值点分布区域特别小，但是函数2仍是单峰函数，因此图2中作为函数2的3种算法的比较结果，同样看不出本文算法性能的优越性。

图2 算法性能比较（函数2）

图3为函数3的3种算法的比较结果，由于函数3是多峰函数，有大量的局部极小值，因此很容易陷入局部最优。从图3的比较中可以看到当线性递减惯性权重的粒子群优化算法陷入局部最优时，不能跳出局部最优找到最优解，而本文算法却能跳出局部最优，找到最优解。因此对于求解高维、多峰等复杂的非线性优化问题，该算法能够跳出局部最优，进而找到全局最优。

图3 算法性能比较（函数3）

3 结论

改变惯性权重，能够使算法在陷入局部最优时，通过增大惯性权重，跳出局部最优，进而找到全局最优解。测试函数的实验结果表明，对于高维、多峰等复杂的非线性优化问题，采用改进的粒子群优化算法能够使函数摆脱局部极值点，通过迭代最终找到全局最优解。

[ 1 ] Kennedy J, Eberhart R C. Particle Swarm Optimization[C]. Proceedings of the IEEE International Conference on Neural Networks, IV. Piscataway, NJ: IEEE Service Center, 1995: 1942-1948.

[ 2 ] 徐从东,陈春.一种自适应动态控制参数的粒子群优化算法[J].计算机工程,2013,10(39):203-207.

[3]吴昌友,王福林,马力.一种新的改进粒子群优化算法[J].控制工程, 2010,3(17):359-362.

[ 4 ]张安玲,王中.一种混合粒子群优化算法的研究[J].计算机工程与应用, 2011,47(31):27-37.

[ 5 ]刘爱军,杨育,李斐等.混沌模拟退火粒子群优化算法研究[J].浙江大学学报,2013,10(47):1722-1730.

[ 6 ] Ai-Qin Mu, De-Xin Cao, Xiao-Hua Wang. A Modified Particle Swarm Optimization Algorithm[J]. Natural Science, 2009,2(1):151-155.

A Particle Swarm Optimization Algorithm of Easily Skipping Local Optimum

Zhao Weihao1，Su Bin1，Xiao Xiaojun2
（1.AVIC Shenyang Liming Aero-engine(Group) Corporation Ltd，Shenyang Liaoning,110043; 2.Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang Liaoning,110004）

Aiming at the problem that the particle swarm optimization (PSO) algorithm falls into local optimum. This paper proposes a particle swarm optimization algorithm of easily skipping local optimum. This algorithm can get out of local optimum by ramping up inertia weight that can change the variety of group, when it traps into local optimum. At last, a great of simulation results show that this algorithm can have excellent search performance for solving the multi-dimension and multi-peak nonlinear optimization questions.

particle swarm optimization; local optimum; diversity; inertia weight