粒子群算法惯性算子凹凸性分析
The Analysis of the Convexity of Inertia Weight Operator
朱雅敏 ZHU Ya-min
（西安工业大学理学院，西安 710021）
（School of Science，Xi′an Technological University，Xi′an 710021，China）
摘要：粒子群算法的惯性因子是算法中的一个重要的参数，目前的研究结果表明，惯性因子为减函数时算法的运行效果更为良好。文中提供了四种减函数作为惯性因子可以使用的算子，它们的凹凸性各有不同。对四个算例的数值仿真结果表明，表现最好的是惯性因子先上凸后下凸的PSO，惯性因子为下凸函数的PSO综合表现优于惯性因子为上凸函数的情况。
Abstract: Aimed to the efficiency changes of PSO caused by different inertia weight operators, some research and analysis had been done in this paper. The study showed that the inertia weight should decrease progressively if you want to expand the search region and assure the convergence of PSO. Four operators of inertia weight were proposed in this paper， their convexity were different with each other.The research about four examples showed that if the inertia weight operator was concave at first and then went to convex, the performance of corresponding PSO was best in all four circumstances, and the convex strategy performed better than concave strategy.
教育期刊网 http://www.jyqkw.com
关键词 ：粒子群算法；惯性因子；凹凸性；收敛
Key words: Particle Swarm Optimization；inertia weight；convexity；convergence
中图分类号：TP18文献标识码：A文章编号：1006-4311（2015）20-0198-03
0引言
粒子群算法也称为粒子群优化算法（Particle Swarm Optimization），缩写为PSO.1995年，由Eberhart博士和Kennedy博士提出。粒子群算法是一种基于仿生学的群体智能优化算法，该算法通过群体中个体之间协作和信息共享达到共同寻求最优解的目的，与其他智能算法相比，粒子群算法原理简单，实现容易。从算法问世至今，得到了各个领域学者的广泛关注。Van对PSO算法的稳定性和收敛性做了初步分析，指出基本PSO算法无法保证收敛到全局最优。针对粒子群算法难以跳出局部极值，收敛效率低等特点，学者们对其做了各种改进。
惯性因子是粒子群算法中的一个重要参数，它表示粒子对其原始速度的继承状况。目前对粒子群算法的改进工作很大一部分集中在对惯性因子的改进上，主流的改进方式是惯性因子随着迭代次数逐步递减，也有学者根据粒子实时的进化速度动态调整惯性权值[5]。文献[6]定义了粒子群优化的参数空间，把探索性能最优的粒子群算法转化为一个参数优化问题，这些参数中包含惯性因子。文献[7]提出了模糊规则惯性权值（Fuzzy inertia Weight，FIW）粒子群算法，但这些调整策略都使的算法计算复杂，虽对算法有一定改进，却总体上使得算法“性价比”降低。
Shi 和 Eberhart提出，较大的惯性权值有助于粒子跳出局部极小点，便于全局搜索；而较小的惯性权值有助于粒子对于当前的搜索区域进行精细搜索，便于算法收敛.因此在算法进行过程中，有必要通过一些方法和手段来调整惯性权值，使算法在全局搜索和精细搜索（以便于收敛）之间达到平衡[8]。基于这种考量，文献[8]给出了一种惯性因子线性递减的调整方案，较之惯性因子一直取固定值，这种调整方案被证明是更有效率的。文献[8]中的算法简单，但在处理一些复杂问题时，存在局限性。文献[9]提出了几种基于非线性递减策略惯性因子的粒子群优化算法，与文献[8]中的算法相比，基于正弦曲线和对数曲线的调整策略会优于后者，而基于正切曲线的调整策略甚至比后者的表现还要略差。文献[10]构造了开口向下的抛物线和开口向上的抛物线和指数曲线三种非线性的惯性权值调整策略，得出的结论是凹函数（下凸）递减策略优于线性递减策略，而凸函数（上凸）递减策略效果最差。
1标准粒子群算法原理
鸟搜索食物的空间设为D维，鸟可抽象为D维空间的一个点。设鸟群一共有N只鸟，则其对应D维空间的N个粒子。第i只鸟（第i个粒子）经过t次飞行后的位置可表示为
2惯性因子
之前的关于惯性因子的研究基本都是不断提出不同的递减算子，通过实验验证它们各自的效率差异，而并没有通过惯性因子的凹凸性来分析其对PSO算法性能的影响，另外只是构造区间上的线性递减或者凹函数或者凸函数，模型构造过于简化。惯性因子体现的对粒子之前速度的继承，而惯性因子的取值直接影响到粒子速度的变化，而速度的变化又影响到搜索的广度（全局搜索的程度）和深度（精细搜索的程度）。全局搜索有利于跳出局部极值，而精细搜索有利于尽可能的靠近真正的最优解。而一个好的算法应该尽可能的照顾到这两者。对于粒子群算法来说，如果单纯考虑惯性因子，那么惯性因子越大，就越有利于全局搜索，而惯性因子越小，就越有利于精细搜索。体现在惯性因子的变化上，也就是惯性因子应该是一个减函数。而为了最大的同时保证全局搜索和精细搜索，惯性因子在最开始应该尽可能多的取较大的值，而在算法结束时，要尽可能的保持取较小的值得时间。由此可以分析出，惯性因子如果是先上凸后下凸函数时，算法能够最大的同时保证全局搜索和精细搜索，即算法的性能会更好。为了验证这个结论，本文提出了一个先上凸后下凸的函数和一个先下凸后上凸的函数，通过数值仿真与文献[10]和[11]中的函数进行了对比，并从函数凹凸性上进一步说明了惯性因子的选取原则。
文献[10]中提出了抛物线型的惯性因子调整算子：
以上几种调整策略的函数曲线如图1所示（这里对ω2（t）做了处理，本来它的区间在0.95-0.4，高于0.9的部分都做了线性处理，使得它的最大值和其它惯性算子一样都是0.9）。
由上图可以看出上述四个惯性因子算子有一个是下凸函数（ω1），一个是上凸函数（ω2），一个是先上凸后下凸函数（ω3），一个先下凸后上凸函数（ω4）。几种惯性因子的极大极小值都为0.9，0.4。
3几种惯性因子算子对应的PSO
针对上述的几种策略，可分别将ω1（i=1，2，3，4）分别带入标准粒子群算法中，标准粒子群算法可以依此改写为
得到的粒子群算法记为iPSO（i=1，2，3，4），c1，c2都取值为2。N为粒子总数，Tmax为程序设定的最大迭代次数。
算法步骤：①初始化.确定种群数量，随机生成粒子群种群和初始速度，初始化位置，确定最大迭代次数；②把对应的ωi（i=1，2，3，4）带入（3）式，根据式（3）和式（4）进行速度更新和位置更新；③每一步计算最新位置的适应度值，确定gbest=（gi1，gi2，…，giD）和Pbest=（Pi1，Pi2，…，PiD）；④如果迭代次数达到算法结束的条件，则结束；否则回到第二步；⑤输出gbest，并计算gbest的适应度值，算法运行结束。
4数值仿真及分析
基于上文所述之算法，采用Python语言及其科学计算扩展包numpy、scipy编写了仿真测试程序，针对下面两个典型的函数进行了实际测试。
4.1 Rosenbrock函数Rosenbrock函数，非凸，病态函数，在xi=1时达到极小值0。
参数设置：粒子总数 50， 搜索空间 [-30，30]，迭代次数500次，经过500次运行后，测试数据如表1所示。（为了体现算法性能的差异，数据都保留到小数点之后六位）
通过表1可以发现几种惯性因子对应的粒子群算法针对Rosenbrock函数在50次运行中的平均性能从优到劣排序依次为：3PSO，1PSO，2PSO，4PSO。
由表1可看出：①3PSO不管是从平均值还是从稳定性（方差）来看，都是四种调整方案中表现最好的，而在500次迭代中取得的极小值来看，表现也很不错；②在这几种惯性因子对应的PSO算法中，2PSO和4PSO的平均值相差不大，但方差较4PSO的小，即它比4PSO在500次运行中表现稳定，2PSO在500次运行中能够找到的最小值比4PSO找到的要大，也就是说4PSO表现不稳定，但在时好时坏的表现中，那些好的表现比2PSO的最好的表现要好；③从稳定性来看，3PSO在500次运行中的平均表现（均值和方差）都要好于1PSO。
综上，在求解Rosenbrock函数时，表现最好的是3PSO（对应的惯性因子图像先上凸后下凸），而1PSO（下凸）表现优于2PSO（上凸）。
4.2 Rastrigin函数Rastrigin函数，多峰函数，在xi=0（i=1…n）时达到全局极小点，在S={xi∈（-5.12，5.12），i=1，2…n}范围内大概存在约10n个局部极小点。
参数设置：粒子总数 50， 搜索空间 [-5.12， 5.12]，自变量维度30，常数A取10，迭代次数500次，经过500次运行后，测试数据如表2所示。
通过多峰函数Rastrigin函数的测试可以发现：
①四种PSO在500次的运行中都寻找到了全局最优0，而3PSO的表现无论是从平均值还是从方差（稳定性）来看都是最好的，1PSO表现次之。②表现最差的是4PSO。
综上，在求解Rastrigin函数时，表现最好的是3PSO（对应的惯性因子图像先上凸后下凸），而1PSO（下凸）表现优于2PSO（上凸）。
4.3 Schewelfel函数
Schewelfel函数，单峰，在xi=0时达到极小值0。
参数设置：粒子总数 50， 搜索空间 [-30， 30]，自变量维度30，迭代次数500次，经过50次运行后，测试数据如表3所示。
通过Schewelfel函数测试可以发现：①四种PSO在500次的运行中都未能寻找到到全局最优0，而3PSO的表现无论是从平均值还是从方差（稳定性）来看都是最好的，虽然在迭代500次未能达到全局最优，但适当增加迭代次数能够解决这个问题，1PSO表现次之。②表现最差的是4PSO。
综上，在求解Schewelfel函数时，表现最好的是3PSO（对应的惯性因子图像先上凸后下凸），而1PSO（下凸）表现优于2PSO（上凸）。
4.4 Schaffer函数Schaffer 函数，多峰，由 J.D.Schaffer 提出，全局极大点是（0，0），在距离全局极大点大约3.14 的范围内存在无限多的次全局极大点，函数强烈震荡的性态使其很难于全局最优化。
参数设置：粒子总数 50， 搜索空间 [-100， 100]，自变量维度30，迭代次数500次，经过50次运行后，测试数据如表4所示。
（因为四舍五入，四种方案能够找到的最大值都是0.002456）通过Schaffer 函数测试可以发现：①四种PSO在500次的运行中都未能寻找到到全局最优0，但都比较接近全局最优，接近的程度都差不多。四种调整方案500次迭代取得的均值和最小值在同样精度的情况下完全相同，而方差可以看出，1PSO和3PSO的稳定性要优于其他两个。②表现最差的是2PSO。
在求解Schaffer函数时，1PSO和3PSO表现都很不错，而1PSO（下凸）表现优于2PSO（上凸）。
综合以上四个算例的仿真结果可知，3PSO在四个案例中有三个表现都明显优于其他三种调整方案。
5结论
本文通过四个函数的数值实验结果表明：惯性因子为先上凸后下凸函数时对应的PSO性能在四种调整方案中表现最佳.甚至四种情况中有三种比文献[10]中认为的表现最好的惯性因子为凹函数（下凸）时的表现更好，实验4中两者效果基本持平。
教育期刊网 http://www.jyqkw.com
参考文献：
[1]Kennedy J,Eberhart R,Shi Y.Swarm Intelligence[M].San Francisco,USA:Morgan Kaufmann Publishers,2001.
[2]J.Kennedy and R.Eberhart.Particle swarm optimization.In Proceedings ofIEEE International Conference on Neural Networks,volume IV,Perth,Australia,1995：1942-1948.
[3]Van DenBerghF.An analysis of particle swarmoptimizers[D].Pretoria:Department of Computer Science,University of Pretoria,2001.
[4]I.C.Trelea.The Particle swarm optimization algorithm:convergence analysis and parameter selection[J].Information ProcessingLetters,2003，85（6）：317-325.
[5]GENG H T,HUANGY H,GAO J,et al.A self-guided Particle swarm optimization with independent dynamic inertia weights setting on each particle[J].Applied Mathematics and Information Sciences.2013，7（3）：545-552.
[6]Wang Shaowei，Lo David，Jiang Lingxiao.Active code search:Incorporating user feedback to improve code search relevance[C]//Proceedings of the 29thIEEE/ACM International Conference onAutomated Software Engineering(ASE14).2014.
[7]Shi Y,Eberhart R.Particle Swarm Optimization with Fuzzy Adaptive Inertia Weight[C]//Proc.of Workshop on Particle Swarm Optimization.Indianapolis,Indiana,USA:Purdue School of Engineering and Technology,2001.
[8]Shi Y, EberhartR C.A modified Partical Swarm Optimizer[C].In:IEEE World Congress On computational Intelligence,1998:69-73.
[9]周敏，李太勇.粒子群优化算法中惯性权值非线性调整策略[J].计算机工程，2011，37（5）：203-206.
[10]陈贵敏，贾建援，韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报，2006，40（1）：53-56.
[11]田东平，赵天绪.基于sigmoid惯性权值的自适应粒子群优化算法[J].计算机应用，2008，28（12）：3058-3061.