粒子群算法的惯性权重调整策略

1、粒子群算法的惯性权重调整策略李丽 1 薛冰 2 牛奔 31 深圳大学管理学院信管系，广东深圳（ 518060 ）2 深圳大学管理学院信管系，广东深圳（ 518060 ）3 深圳大学管理学院信管系，广东深圳（ 518060 ）E-mail （小五，Times New Roman ）摘 要： 惯性权重是粒子群算法改进的一个重要出发点，通过调整惯性权重可以大大提高算法的性能。本文在介绍粒子群算法原理、流程的基础上，分析了惯性权重在算法寻优过程中的重要作用，然后归纳了运用不同方法对惯性权重的改进，进行了简单的讨论，并对下一步工作进行了展望。关键词：粒子群算法惯性权重改进策略1 引言粒子群优化算法（ P

2、articleSwarmO ptimization， PSO） 是 1995 年由 Eberhant 和 Kennedy在文献 1 中提出的一种基于群体智能、自适应的搜索优化方法。其基本思想源于对鱼类、鸟类等群体社会行为的观察研究。粒子群算法提出以后，由于其算法概念简单、需要调整的参数较少、容易实现和快速收敛能力，已被广泛地用在科学和工程领域，如电力系统优化（文献 31 33） 、 TSP问题（ 文献 34 ）、神经网络训练（文献 35） 、函数优化（文献 37 、 38 ）等。粒子群算法在应用过程中体现出了很强的寻优能力，但与其他全局优化算法相同，粒子群算法也存在早熟局部收敛和后期震荡现象。

3、针对这些问题，国内外学者经过大量研究工作，提出了多种改进方法，包括参数改进，拓扑结构改进和混合算法等。其中惯性权重是最重要的可调整参数，惯性权重由于其概念简单、容易理解、改进的方法较多、改进的空间较大且容易实现等特点，成为很多学者研究的焦点。通过调整惯性权重的值可以实现全局搜索和局部搜索之间的平衡：较大的权值有利于提高全局搜索能力，而较小的权会提高局部搜索能力。诸多研究者运用线性递减、非线性递减等方法对惯性权重进行调整，实现了算法在不同方面和不同程度上的改进。本文通过对国内外研究人员所提出的调整惯性权重策略进行归纳总结，讨论了各种策略的优缺点，并在此基础上提出了下一步工作方向及需要解决的问题。

4、2 基本粒子群算法在粒子群算法中，每个寻优的问题解都被想像成一只“鸟”，也称为一个没有重量和体积的粒子，每个的粒子在n 维搜索空间里飞行，并有一个速度决定其飞行的距离与方向，且在飞行过程中，每一个粒子都是所有粒子都有一个适应值函数来判断其目前位置的好坏，具有记忆性的，能记得所搜寻到的最佳位置。因此，在飞行过程中，每一代都能找出两个“极值”：每一个粒子到目前为止的搜寻过程中最优解，代表粒子自身认知水平，称之为个体极值Pbest ；所有群体中的最优解，代表社会认知水平，称之为全局极值Gbest。粒子群算法首先初始化一群随机粒子，然后根据两个“极值”通过更新迭代找到最优解，其基本迭代方程如下：Vid

5、 (t1)Vid (t) c1 rand () (pid xid (t) c2 rand () (pgdxid (t)( 1)xi(t 1) xi(t) Vi(t 1)( 2)其中， vid 表示粒子i 在第 d 维的速度，n 维向量xi (t)(xi1 , xi 2, xin )表示迭代到第t 代时粒子 i 的位置， n 维向量vi (t)(vi1 ,vi2, vin ) 表示粒子 i的速度。c1 、c2 是学习因子，rand () 是均匀分布于0,1 之间的随机数，pid 表示个体极值 Pbest， pgd表示全局极值Gbest。为了防止xi (t) 溢出，设置vmax 来控制vi (t)

6、 的范围：Vi (t)Vi(t)VmaxVi(t)( 3)VmaxVi(t)Vmax具体算法流程如下：(1) 初始化所有微粒( 群体规模为N , 在允许范围内随机设置微粒的初始位置和速度,并将各微粒的pid 设为初始位置, 取 p gd 为pid 中的最优值。(2) 评价每个微粒的适应值, 即分别计算每个微粒的目标函数值。(3) 对于每个微粒, 将其适应值与所经历过的最好位置pid 的适应值进行比较, 若较好 ,则将其作为当前的最优位置。(4) 对于每个微粒, 将其适应值与群体所经历过的最好位置p gd 的适应值进行比较, 若 较好 , 则将其作为当前的全局最优位置。(5) 根据速度和位置更新

7、方程对微粒的速度和位置进行更新。,则(6) 如未达到结束条件, 通常为足够好的适应值或是达到一个预设的最大迭代代数返回第(2)步。具体算法流程图如下：3 惯性权重的提出经过大量的研究试验，为了提高基本粒子群算法的收敛性能和避免算法陷入局部最优，Y.Shi 和 R.C.Eberhant 于 1998 年在 A modified particle swarm optimizer (文献 2)一文中提出了惯性权重这一概念，在进化方程(1)中引入惯性权重因子w ，即：Vid (t1)wVid (t)c1 rand () (pidxid (t) c2 rand () (pgd xid (t)( 4)等式

8、右边的结构和(1 )式一样，第一部分是粒子先前的自身速度，用来保证算法的全局收敛性；第二和第三部分是引起微粒速度变化的社会因素，使算法具有局部搜索能力。所以 w 起到了一个平衡全局搜索能力和局部搜索能力的作用，w 值较大时全局搜索能力强，局部搜索能力弱；w 值较小时，反之。恰当的w 值可以提高算法性能，提高寻优能力，减少迭代次数。惯性权重的引入，对粒子群算法的发展起到了很大推动作用，大大拓展了算法改进的空间。但是要达到算法性能最优还存在很多缺陷，因为当w 值较大时，有利于全局搜索，虽收敛速度快，但不易得到精确解；w 值较小时有利于局部搜索和得到更为精确的解，但收敛速度慢且有时会陷入局部极值。如

9、何寻找合适的w 值使之在搜索精度和搜索速度方面起恰当的协调作用，成为很多学者研究的一个新方向，通过几年的发展，已有了不少研究成果。4 惯性权重调整策略基于研究各种问题的复杂性和惯性权重在算法迭代过程中所起到的平衡作用，除了固定惯性权重以外，学者们还提出了很多种惯性权重调整策略，主要有线性递减策略、非线性递减策略和自适应调整策略等以下几种：4.1 线性递减策略由于在一般的全局优化算法中，总希望前期有较高的全局搜索能力以找到合适的种子，而在后期有较高的开发能力，以加快收敛速度，所以惯性权重的值应该是递减的。其中的线性递减策略主要有以下几种：4.1.1 典型线性递减策略Y.Shi 和 R.C.Ebe

10、rhant 在文献 2还中提到了w 应是随着进化线性递减的。这是首次提出的惯性权重递减策略，我们称之为典型线性递减策略，w 的计算公式如下：w(t)wmaxwmaxwmintmax5)其中wmax、 wmin 分别是w 的最大值和最小值；t 、 t max 分别是当前迭代次数和最大迭代次数(全文中符号表示意义相同)。文献9试验了将w 设置为从0.9 到 0.4 的线性下降，使得PSO 在开始时探索较大的区域，较快地定位最优解的大致位置，随着w 逐渐减小，粒子速度减慢，开始精细的局部搜索。该方法使PSO 更好地控制全局搜索能力和局部搜索能力，加快了收敛速度，提高了算法的性能。这种典型的惯性权重线

11、性递减策略在目前是应用最为广泛，但是由于这种策略下，迭代初期全局搜索能力较强，如果在初期搜索不到最好点，那么随着w 的减小，局部搜索能力加强，就易陷入局部极值。4.1.2 线性微分递减策略为了克服典型线性递减策略的局限性，文献14中提出了一种线性微分递减策略，惯性权重的计算公式如下：dw 2(wmax w min )2t(6)dtt max(wmaxwmin )27)w(t)wmax2ttmax通过对 w 变化方程及实验结果进行分析，由于在算法进化初期w 的减小趋势缓慢，全局搜索能力很强，有利于找到很好的优化种子，在算法进化后期，w 的减小趋势加快，因此一旦在前期找到合适的种子，可以使得算法收

12、敛速度加快，在一定程度上减弱了典型线性递减策略的局限性，相应地在算法性能提高上有了很大改善。4.2 非线性递减策略4.2.1 带阀值的非线性递减策略惯性权重线性递减策略经过不断改进，已经比原始的惯性策略有了很大改善。但是由于其线性递减的特征，对于很多问题，在迭代过程中，算法一旦进入局部极值点邻域内就很难跳出来，为了克服这种不足，文献18 在典型线性递减策略的基础上引入了递减指数和迭代阀值T0 ，提出了一种惯性权重的非线性递减策略，即：t1w(t) wmax () (wmax wmin )( 8)T01此时参数集变为 ， wmax 、 wmin 、 T0 ， 当迭代次数到达T0 时， 令 w(t

13、)wmax，并保持到搜索结束，整个迭代过程由于的引入，w(t ) 随着 t 的增大而非线性递减，有利于跳出局部极值点。迭代初期w 较大，粒子以较大的飞行速度遍布整个搜索空间从而确定最优值的大概范围，随着迭代的进行w 非线性减小，大部分粒子的搜索空间逐渐减小，并且集中在最优值的邻域范围内；在迭代末期当达到迭代阀值时，将惯性权重限定为w ，max粒子以近乎不变的飞行速度在最优值邻域范围内找到全局最优解，有利于提高算法的收敛速度， 尤其对于低维测试函数，无论在搜索最优值精度、收敛速度还是在稳定性方面都有明显的优势。4.2.2 先增后减策略针对递减策略中仍然存在的不足，文献 16提出了一种具有先增后减

14、惯性权重的微粒群算法， w 的惯性权重计算方程如下：1 t 0.40 t 0.5tmaxt max9）10)W(t)tt11.40.51tmaxt max文献 16经过试验研究，这种先增后减的惯性权重，在前期有较快的收敛速度，而后期的 局部搜索能力也不错，在一定程度上保持了递减和递增策略的优点，同时克服了一些缺点，相对提高了算法性能。此外， 国内还有人提出了其他的非线性动态递减惯性权重，如文献 19 中提出依据下式来计算惯性权重的方法：1w(t) (wmax wmin d1)e1 d2t/tmax其中 d 1 ， d 2 为控制因子，目的是为了控制w 在 wmax 和 w min 之间。经过大

15、量实验证明当d10.2 ， d 20.7 时算法的性能会大大提高。4.3 自适应动态改变惯性权重4.3.1 依据早熟收敛程度和适应值进行调整以上的惯性权重调整策略都是依据迭代次数的递增而递减的，文献 20 提出了一中自适应调整策略，根据群体早熟收敛程度和个体适应值的来确定惯性权重的变化。设粒子pi 的适1n应值为 fi ，最优粒子的适应值是f m粒子群的平均适应值是favgfi ；将优于favg 的ni1''适应值求平均得到favg ； 且定义fm f avg 。依据fi 、favg 和favg将群体分为3 个 子群，分别进行不同的自适应操作。则其惯性权重的调整如下：'

16、（ 1） fi 优于favg 则11)w(t) w (w wmin )fi f avg'fmf avg2) fi 优于 f avg但次于 favg ，则惯性权重不变；3) fi 次于 favg则w(t) 1.5( 12)1 k1 exp( k2)其中第一类子群是群体中较优秀的粒子，已经接近全局最优解，赋予其较小的惯性权重，从而强化了局部搜索能力；第二类粒子为一般粒子，具有较好的全局搜索能力和局部搜索能力， 不需要改变其惯性权重；第三类粒子为群体中较差粒子，借鉴自适应调整遗传算法控制参数的方法对其进行调整。k1 、 k2 为控制参数，k1 用来控制w 的上限(一般为大于1的常数) ， k

17、 2 主要用来控制上式的调节能力。当算法停止时，若粒子分布较为分散，则较大，由上式来降低粒子的w ，加强局部搜索能力，以使群体趋于收敛，若粒子分布较为聚集，则较小，由上式增加粒子的w ，使粒子具有较强的探查能力，从而有效地跳出局部最优。4.3.2 根据距全局最优点的距离进行调整国内一些学者认为惯性权重的大小还应该和其距全局最优点的距离有关。文献 21 中提出各不同粒子的惯性权重w 的值不仅随迭代次数的增加而递减，并且应该随其距全局最优点距离增加而递增，即权重w 根据粒子的位置不同而动态变化：(l ig l min )( wmaxwmin )tw(t) wmax (l l )t( 13)(l m

18、ax l min )tmax其中 lig 为第 i 个粒子到最优粒子的距离，l max和 lmin 分别是预先设的最大距离和最小距离参数。根据上式，当 l ig l max 时， wwmax ； 当 l ig l mni 时， wwmin ； 当 l mni l ig l mxa时， w随着 lig 单调递增。仿真实验结果表明在这种策略下算法在收敛速度和迭代次数方面都有了改进，特别是对于多峰函数效果提高的更明显。4.4其他的惯性权重调整策略4.4.1 模糊调整w 的策略Shi 等认为粒子群算法搜索过程是一个非线性的复杂过程，让w 线性下降的方法不能正确的反映真实的搜索过程。因而，提出用模糊推理

19、机来动态地调整惯性权重的技术6。模糊 w 法的优缺点如下：模糊推理机能预测合适的w ，动态地平衡全局和局部搜索能力，大为提高了平均适应值；但是其参数比较多，增加了算法的复杂度，使得其实现较为困难。4.4.2 随机调整w 的策略目前的研究中，很多学者认为w 应为一组随机值，如：Eberhart7等提出一种动态惯性权重法以试图解决优化目标变化显著的问题，该方法令w(t)0.5 rand ()2.014)能产生一个在0.5， 1之间的w 值。 通过使用函数测试性能，显示这种策略下的粒子群算法能跟随非静态目标函数，比进化规划和进化策略得到的结果精度更高，收敛速度更快8提出了 w 服从均匀分布、正态分布

20、等随机策略，使算法性能较线性递减策略都有明显提高。5 结论综上所述可以看出，惯性权重作为粒子群算法中的一个重要参数，是算法改进的一个重要途径，可改进的方向和方法有很多种，已经有很多学者经过长期研究提出了不同的改进策略， 本文通过对各种改进策略的归纳总结，分类说明了各种策略的优缺点，为使用者提供了方便。作者的进一步工作有两个方面：1. 通过仿真试验对各种算法进行更深层次的分析对比， 找出适合不同问题的最优改进算法；2 结合各种问题和各种测试函数，提出效果更优的惯性权重调整策略。参考文献1J.Kennedy,R.C. Eberhart. Particle swarm optimization A.

21、Proceedings of the IEEE International Conference on Neural Networks C. 1995:194219482ShiYuhui,Eberhart,R.A modified particle swarm optimizerA.Proc IEEE Int Confon Evolutional ComputationC.Anchorage,1998.69-733Kennedy J.The particle swarm Sociala adaptation knowledge A.Proc IEEE Int Confon Evolutiona

22、l ComputationC.Indiamapolis,1997.303-3084J.Kennedy,R.C.Eberhart.A Discrete Binary Version of the Particle Swarm Algorithm. Proceedings of the World Multi conference on Systemic, Cybernetics and Informatics C. Piscataway, NJ: IEEE Service Center, 1997:41044105Kennedy J,EberhartRC.Particle Swarm Optim

23、ization C.Proc IEEE Int Conf Neural Networks .Piscataway,NJ:IEEEServiceCenter,1995:1942-19486Y . H. Shi, R. C. Fuzzy Adaptive Particle Swarm Optimization A. Proceedings of the Congress on Evolutionary Computation C. Seoul, Korea, 2001:1011067R. C. Eberhart,. H. Shi. Tracking and Optimizing Dynamic S

24、ystems with Particle Swarms A.Proceedings of the 2001 Congress on Evolutionary Computation C. Piscataway, NJ: IEEEPress, 2001:941008Van den Bergh F. An Analysis of Particle Swarm Optimizer D. South Africa: Department of Computer Science, University of Pretoria,20029Y . H. Shi,R. C. Eberhart. Empiric

25、al Study of Particle Swarm Optimization A. Proceeding of Congress on Evolutionary Computation C. Piscataway,NJ:IEEE Service Center, 1999:1945194910Elegbede C.Structural reliability assessment based on particles swarm optimization J Structural Safety2005.27(10)1 171-18611 Robinson J,Rahmat-Samii Y Pa

26、rticle swarm optimization in electromagneticJ IEEE Transactions on Antennas and Propagation,2004,52(2):397 40612 Salman A。 Ahmad I,A1 一 Madani S Particle swarm optimization for task assignment problem FJ Microprocessors and Microsystems, 2002,26 (8):363 37113 谢晓锋，张文俊，杨之廉. 微粒群算法综述J. 控制与决策. 2003， 18(2

27、):129)13314 胡建秀 曾建潮 . 微粒群算法中惯性权重的调整策略 J. 计算机工程, 2007.615 肖人彬，陶振武. 群体智能研究进展 J. 管理科学学报, 200716 崔红梅，朱庆保. 微粒群算法的参数选择及收敛性分析 J. 计算机工程与应用, 200717 曾建潮， 崔志华 . 一种保证全局收敛的PSO算法 J. 计算机研究与发展, 2004， ( 8) :1333 133818 王丽，王晓凯. 一种非线性改变惯性权重的粒子群算法 J. 计算机工程与应用, 2007.4319 李会荣，高岳林，李济民. 一种非线性递减惯性权重策略的粒子群优化算法 J. 商洛学院学报 2007

28、.1220 韩江洪，李正荣，魏振春. 一种自适应粒子群优化算法及其仿真研究 J. 系统仿真学报 , 2006.1021 刘建华，樊晓平. 一种惯性权重动态调整的新型粒子群算法J. 计算机工程与应用，2007.43( 7)22 胡建秀，曾建潮. 具有随机惯性权重的PSO算法 J. 计算机仿真, 2006.823 郭文忠 . 粒子群优化算法中惯性调整的一种新策略J. 计算机工程与科学, 2007.1024 王伯成，施锦丹，王凯. 粒子群优化算法的研究现状与发展概述 J. 电视技术, 2008.525 唐岑琦， 周有人 . 具有综合学习机制的粒子群算法J. 计算机工程与应用, 2007， 43( 3

29、1)26 陈贵敏 . 粒子群优化算法的惯性权值递减策略研究J. 西安交通大学学报, 2006.27 王启付，王战江. 一种改变惯性权重的粒子群优化算法J. 中国机械工程, 2005.16(11)28 王俊伟，汪定伟. 粒子群算法中惯性权重的实验与分析 J. 系统工程学报, 2005.20( 2) :194-19829 张选平，杜玉平. 秦国强，覃征. 一种动态改变惯性权重的自适应粒子群算法 J. 西安交通大学学报, 2005.1030 张丽平 , 俞欢军 . 粒子群优化算法的分析与改进J. 信息与控制, 2004.33( 5) :513-51731 张振宇 . 粒子群优化算法及其在电力系统优化运行中的应用D . 天津 : 天津大学, 200732 李丹,高立群. 电力系统机组组合问题的动态双种群粒子群算法 J. 计算机应用, 200833 侯颖君 . 粒子群优化算法在