2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

粒子群优化算法的性能分析和参数选择

王东风 孟丽

王东风, 孟丽. 粒子群优化算法的性能分析和参数选择. 自动化学报, 2016, 42(10): 1552-1561. doi: 10.16383/j.aas.2016.c150774
引用本文: 王东风, 孟丽. 粒子群优化算法的性能分析和参数选择. 自动化学报, 2016, 42(10): 1552-1561. doi: 10.16383/j.aas.2016.c150774
WANG Dong-Feng, MENG Li. Performance Analysis and Parameter Selection of PSO Algorithms. ACTA AUTOMATICA SINICA, 2016, 42(10): 1552-1561. doi: 10.16383/j.aas.2016.c150774
Citation: WANG Dong-Feng, MENG Li. Performance Analysis and Parameter Selection of PSO Algorithms. ACTA AUTOMATICA SINICA, 2016, 42(10): 1552-1561. doi: 10.16383/j.aas.2016.c150774

粒子群优化算法的性能分析和参数选择


DOI: 10.16383/j.aas.2016.c150774
详细信息
    作者简介:

    王东风   博士, 华北电力大学控制与计算机工程学院教授.主要研究方向为群智能优化算法和智能控制.E-mail:wangdongfeng@ncepu.edu.cn

    通讯作者: 孟丽  华北电力大学控制与计算机工程学院博士研究生.主要研究方向为智能优化算法及其应用.本文通信作者.E-mail:mengli2014@163.com
  • 基金项目:

    中央高校基本科研基金 20140139

    国家自然科学基金 61203041

    教育部高等学校博士学科点专项科研基金 20120036120013

Performance Analysis and Parameter Selection of PSO Algorithms

More Information
    Author Bio:

      Ph. D., professor at the School of Control and Computer Engineering, North China Electric Power University. His research interest covers swarm intelligence-based optimization and intelligent control.E-mail:

    Corresponding author: MENG Li   Ph. D. candidate at the School of Control and Computer Engineering, North China Electric Power University. Her research interest covers swarm intelligence-based optimization and its application. Corresponding author of this paper.E-mail:mengli2014@163.com
  • Fund Project:

    the Fundamental Research Funds for the Central Universities 20140139

    National Natural Science Foundation of China 61203041

    Specialized Research Fund for the Doctoral Program of Higher Education 20120036120013

  • 摘要: 惯性权重和加速因子是影响粒子群算法优化性能的重要参数.基于常用的12个测试函数,本文通过实验研究了不同参数组合下粒子的探索能力和算法的优化性能,在此基础上推荐了一组固定的参数组合.通过惯性权重和加速因子的不同变化策略组合对算法性能影响的实验分析,推荐了一种变化的参数设置方法.基于CEC2015发布的15个基准函数进一步验证了本文推荐的参数选取方法的有效性.最后讨论了粒子群优化(Particle swarm optimization,PSO)算法在连续优化和离散优化方面的应用问题.
  • 图  1  具有不同参数的种群优化函数Sphere时粒子的Pnum

    Fig.  1  The Pnum value of function Sphere optimized by PSO with different population scale

    图  2  粒子探索能力与参数的关系

    Fig.  2  Relationship between particle exploration ability and its parameters

    图  3  算法成功率与参数的关系

    Fig.  3  Relationship between the algorithm success rate and particle parameters

    图  4  算法在12个测试函数上的性能总和

    Fig.  4  Total optimization performance on the 12 test functions

    图  5  c1所占比率对算法成功率的影响

    Fig.  5  The influence of ratio c1 on algorithm0s success rate

    图  6  变化的c1c2取值策略对算法成功率的影响

    Fig.  6  The influence of varying c1 and c2 on algorithm0s success rate

    表  1  5组参数的运行结果对比

    Table  1  Comparison of running results on 5 parameters

    函数PARAminmaxmean±stdSR
    Fun 111.47E-258.64E-226.32E-23±1.34E-221.00
    29.05E-365.64E-311.73E-32±7.16E-321.00
    31.98E-402.94E-341.31E-35±4.50E-351.00
    41.81E-572.84E-332.86E-35±2.84E-341.00
    51.63E-271.45E-232.71E-25±1.46E-241.00
    Fun 212.72E-027.29E+002.40E+00±1.43E+000.84
    23.18E-031.20E+023.75E+00±1.19E+010.76
    31.20E-038.27E+003.45E+00±1.96E+000.30
    46.03E-028.96E+004.30E+00±1.57E+000.07
    52.21E-028.45E+003.45E+00±1.40E+000.31
    Fun 316.55E-108.21E-081.38E-08±1.58E-081.00
    25.68E-141.07E-109.80E-12±1.70E-111.00
    32.98E-117.36E-098.82E-10±1.32E-091.00
    47.06E-124.01E-046.10E-06±4.09E-050.94
    51.23E-101.02E-081.63E-09±1.77E-091.00
    Fun 411.06E-141.00E+015.00E-01±2.19E+000.95
    27.73E-201.00E+011.00E-01±1.00E+000.99
    37.38E-237.89E-209.10E-21±1.60E-201.00
    48.37E-201.00E+011.00E-01±1.00E+000.98
    51.64E-151.12E-131.82E-14±1.87E-141.00
    Fun 511.14E-251.00E+042.00E+02±1.40E+030.00
    26.54E-351.82E-292.24E-31±1.82E-301.00
    31.74E-392.36E-331.04E-34±3.60E-341.00
    42.45E-546.74E-346.74E-36±6.74E-351.00
    51.44E-267.31E-245.72E-25±9.94E-250.32
    Fun 619.91E-131.39E+015.73E+00±3.06E+000.55
    29.94E-011.59E+016.61E+00±3.23E+000.43
    30.00E+001.39E+014.87E+00±2.94E+000.68
    49.94E-014.47E+019.87E+00±7.05E+000.23
    51.66E-137.95E+003.29E+00±1.84E+000.85
    Fun 711.47E-021.64E-017.49E-02±3.35E-020.83
    27.39E-031.84E-017.77E-02±3.52E-020.77
    31.47E-022.21E-017.94E-02±4.10E-020.74
    41.72E-023.05E-011.12E-01±5.99E-020.53
    51.11E-151.69E-016.15E-02±3.39E-020.86
    Fun 812.38E-131.99E+011.99E-01±1.99E+000.99
    23.55E-157.10E-153.94E-15±1.11E-151.00
    33.55E-157.10E-153.97E-15±1.16E-151.00
    43.55E-151.15E+001.15E-02±1.15E-010.97
    51.42E-146.18E-131.51E-13±1.19E-131.00
    Fun 910.00E+001.30E+036.41E+02±2.28E+020.35
    20.00E+001.42E+036.83E+02±2.86E+020.30
    31.18E+021.54E+036.41E+02±3.04E+020.44
    41.18E+001.19E+036.40E+02±2.51E+020.36
    50.00E+009.49E+024.48E+02±1.86E+020.67
    Fun 1013.55E-101.57E+001.46E-01±4.41E-010.86
    20.00E+003.07E+001.69E-01±5.28E-010.86
    30.00E+001.50E+006.00E-02±2.96E-010.96
    41.81E-133.00E+001.40E-01±4.50E-010.46
    50.00E+003.46E-023.46E-04±3.46E-030.99
    Fun 1115.76E-275.30E-215.90E-23±5.30E-221.00
    24.71E-321.90E-314.94E-32±1.53E-321.00
    34.71E-323.11E-011.55E-02±6.81E-020.95
    44.71E-323.11E-011.24E-02±6.12E-020.95
    55.16E-293.55E-245.37E-26±2.57E-251.00
    Fun 1216.86E-276.65E-222.13E-23±7.32E-231.00
    21.34E-324.65E-312.13E-32±4.68E-321.00
    31.34E-322.72E-265.45E-28±3.85E-271.00
    41.34E-324.23E-134.23E-15±4.26E-140.99
    52.78E-281.93E-232.82E-25±1.93E-241.00
    下载: 导出CSV

    表  2  本文与文献[17]参数设置的优化结果比较

    Table  2  Comparison of optimization results between the parameters set in this paper and [17]

    函数MMethodminmaxmean±stdSR
    Fun 1Ours
    [17]
    3.91E-331.42E-291.20E-30±2.51E-301.00
    5.01E-336.95E-293.09E-30±9.83E-301.00
    Fun 2Ours
    [17]
    9.79E-022.26E+001.30E+00±5.31E-011.00
    1.00E+005.72E+002.40E+00±7.33E-010.84
    Fun 3Ours
    [17]
    5.90E-132.27E-102.13E-11±3.88E-111.00
    6.03E-132.48E-102.99E-11±4.90E-111.00
    Fun 4Ours
    [17]
    5.58E-187.20E-161.60E-16±1.52E-161.00
    8.12E-182.87E-136.86E-15±4.09E-141.00
    Fun 5Ours
    [17]
    7.24E-323.86E-281.60E-29±5.49E-291.00
    2.12E-323.44E-281.65E-29±5.70E-291.00
    Fun 6Ours
    [17]
    9.94E-017.95E+003.34E+00±1.55E+000.92
    1.98E+001.09E+015.49E+00±2.36E+000.54
    Fun 7Ours
    [17]
    0.00E+001.42E-015.20E-02±2.94E-020.96
    0.00E+001.84E-017.81E-02±3.58E-020.76
    Fun 8Ours
    [17]
    3.55E-157.10E-154.68E-15±1.67E-151.00
    3.55E-152.13E-147.81E-15±3.58E-151.00
    Fun 9Ours
    [17]
    1.18E+021.04E+034.71E+02±1.99E+020.64
    1.18E+021.19E+035.48E+02±2.16E+020.42
    Fun 10Ours
    [17]
    0.00E+001.44E-026.04E-04±2.51E-030.94
    0.00E+001.15E-013.03E-03±1.64E-020.84
    Fun 11Ours
    [17]
    4.71E-322.90E-279.03E-29±4.35E-281.00
    4.71E-321.34E-283.09E-30±1.90E-291.00
    Fun 12Ours
    [17]
    1.34E-326.16E-293.88E-30±9.45E-301.00
    1.34E-321.09E-022.19E-04±1.55E-030.98
    下载: 导出CSV

    表  3  本文给出的固定参数推荐值在CEC2015基准函数F1~F15上的运行结果

    Table  3  Running results on CEC2015 Benchmark functions F1~F15 with fixed parameters

    PARA F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
    [6] 0.02 0.02 0.30 0.24 0.45 0.24 0.95 0.08 0.90 0.56 0.90 0.92 0.04 0.12 0.40
    [7] 0.08 0.12 0.40 0.14 0.40 0.10 1.00 0.30 0.85 0.68 0.80 0.91 0.02 0.16 0.48
    Ours 0.02 0.10 0.10 0.18 0.50 0.14 1.00 0.15 0.90 0.60 0.95 0.95 0.04 0.30 0.50
    下载: 导出CSV

    表  4  本文给出的时变参数设置方式在CEC2015基准函数F1~F15上的运行结果

    Table  4  Running results on CEC2015 Benchmark functions F1~F15 with time-varying parameters

    Method F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
    Ours 0.70 0.26 0.30 0.94 1.00 0.64 1.00 0.50 1.00 0.95 1.00 1.00 0.25 0.40 0.96
    [17] 0.16 0.14 0.01 0.82 0.85 0.25 1.00 0.22 1.00 0.85 1.00 1.00 0.20 0.40 0.90
    下载: 导出CSV
  • [1] Kennedy J, Eberhart R. Particle swarm optimization. In:Proceedings of the 1995 IEEE International Conference on Neural Networks. Perth, Australia:IEEE, 1995. 1942-1948 http://www.oalib.com/references/17617167
    [2] Shi Y, Eberhart R. A modified particle swarm optimizer. In:Proceedings of the 1998 IEEE International Conference on Evolutionary Computation. Anchorage, AK, USA:IEEE, 1998. 69-73
    [3] 张勇, 巩敦卫, 张婉秋.一种基于单纯形法的改进微粒群优化算法及其收敛性分析.自动化学报, 2009, 35(3):289-298 doi:  10.3724/SP.J.1004.2009.00289

    Zhang Yong, Gong Dun-Wei, Zhang Wan-Qiu. A simplex method based improved particle swarm optimization and analysis on its global convergence. Acta Automatica Sinica, 2009, 35(3):289-298 doi:  10.3724/SP.J.1004.2009.00289
    [4] 潘峰, 周倩, 李位星, 高琪.标准粒子群优化算法的马尔科夫链分析.自动化学报, 2013, 39(4):381-389 doi:  10.1016/S1874-1029(13)60037-3

    Pan Feng, Zhou Qian, Li Wei-Xing, Gao Qi. Analysis of standard particle swarm optimization algorithm based on Markov chain. Acta Automatica Sinica, 2013, 39(4):381-389 doi:  10.1016/S1874-1029(13)60037-3
    [5] 刘朝华, 周少武, 刘侃, 章兢.基于双模态自适应小波粒子群的永磁同步电机多参数识别与温度监测方法.自动化学报, 2013, 39(12):2121-2130 http://www.aas.net.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=18241

    Liu Zhao-Hua, Zhou Shao-Wu, Liu Kan, Zhang Jing. Permanent magnet synchronous motor multiple parameter identification and temperature monitoring based on binary-modal adaptive wavelet particle swarm optimization. Acta Automatica Sinica, 2013, 39(12):2121-2130 http://www.aas.net.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=18241
    [6] Eberhart R C, Shi Y. Comparing inertia weights and constriction factors in particle swarm optimization. In:Proceedings of the 2000 Congress on Evolutionary Computation. La Jolla, CA:IEEE, 2000. 84-88
    [7] Trelea I C. The particle swarm optimization algorithm:convergence analysis and parameter selection. Information Processing Letters, 2003, 85(6):317-325 doi:  10.1016/S0020-0190(02)00447-7
    [8] Samal N R, Konar A, Das S, Abraham A. A closed loop stability analysis and parameter selection of the particle swarm optimization dynamics for faster convergence. In:Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Singapore:IEEE, 2007. 1769-1776 http://www.academia.edu/2724938/A_closed_loop_stability_analysis_and_parameter_selection_of_the_particle_swarm_optimization_dynamics_for_faster_convergence
    [9] Carlisle A, Dozier G. An off-the-shelf PSO. In:Proceedings of the 2001 Workshop on Particle Swarm Optimization. Indianapolis, USA, 2001. 1-6
    [10] 胡建秀, 曾建潮.微粒群算法中惯性权重的调整策略.计算机工程, 2007, 33(11):193-195 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJC200711069.htm

    Hu Jian-Xiu, Zeng Jian-Chao. Selection on inertia weight of particle swarm optimization. Computer Engineering, 2007, 33(11):193-195 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJC200711069.htm
    [11] 延丽平, 曾建潮.具有自适应随机惯性权重的PSO算法.计算机工程与设计, 2006, 27(24):4677-4679, 4706 http://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ200624020.htm

    Yan Li-Ping, Zeng Jian-Chao. Particle swarm optimization with self-adaptive stochastic inertia weight. Computer Engineering and Design, 2006, 27(24):4677-4679, 4706 http://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ200624020.htm
    [12] Chalermchaiarbha S, Ongsakul W. Stochastic weight trade-off particle swarm optimization for nonconvex economic dispatch. Energy Conversion and Management, 2013, 70:66-75 doi:  10.1016/j.enconman.2013.02.009
    [13] 敖永才, 师奕兵, 张伟, 李焱骏.自适应惯性权重的改进粒子群算法.电子科技大学学报, 2014, 43(6):874-880 http://www.cnki.com.cn/Article/CJFDTOTAL-DKDX201406014.htm

    Ao Yong-Cai, Shi Yi-Bing, Zhang Wei, Li Yan-Jun. Improved particle swarm optimization with adaptive inertia weight. Journal of University of Electronic Science and Technology of China, 2014, 43(6):874-880 http://www.cnki.com.cn/Article/CJFDTOTAL-DKDX201406014.htm
    [14] Zhan Z H, Zhang J, Li Y, Chung H S H. Adaptive particle swarm optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009, 39(6):1362-1381 doi:  10.1109/TSMCB.2009.2015956
    [15] Alfi A. PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems. Acta Automatica Sinica, 2011, 37(5):541-549 doi:  10.1016/S1874-1029(11)60205-X
    [16] Suganthan P N. Particle swarm optimiser with neighbourhood operator. In:Proceedings of the 1999 Congress on Evolutionary Computation. Washington DC, USA:IEEE, 1999. 1958-1962
    [17] Ratnaweera A, Halgamuge S K, Watson H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 2004, 8(3):240-255 doi:  10.1109/TEVC.2004.826071
    [18] Yamaguchi T, Yasuda K. Adaptive particle swarm optimization:self-coordinating mechanism with updating information. In:Proceedings of the 2006 IEEE International Conference on Systems, Man, and Cybernetics. Taipei, China:IEEE, 2006. 2303-2308
    [19] Liang J J, Qu B Y, Suganthan P N, Chen Q. Problem Definitions and Evaluation Criteria for the CEC 2015 Competition on Learning-based Real-parameter Single Objective Optimization. Technical Report 201411A, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China, and Technical Report, Nanyang Technological University, Singapore, 2014. http://web.mysites.ntu.edu.sg/epnsugan/PublicSite/Shared%20Documents/CEC-2015/Learning-Based%20Single%20Objective%20Optimization/CEC%202015%20Learning_based.pdf
    [20] 崔志华, 曾建潮.微粒群优化算法.北京:科学出版社, 2011.

    Cui Zhi-Hua, Zeng Jian-Chao. Particle Swarm Optimization. Beijing:Science Press, 2011.
    [21] 王凌, 刘波.微粒群优化与调度算法.北京:清华大学出版社, 2008.

    Wang Ling, Liu Bo. Particle Swarm Optimization and Scheduling Algorithms. Beijing:Tsinghua University Press, 2008.
    [22] 郭文忠, 陈国龙.离散粒子群优化算法及其应用.北京:清华大学出版社, 2012.

    Guo Wen-Zhong, Chen Guo-Long. Discrete Particle Swarm Optimization Algorithm and Its Application. Beijing:Tsinghua University Press, 2012.
  • [1] 刘耿耿, 庄震, 郭文忠, 陈国龙. VLSI中高性能X结构多层总体布线器[J]. 自动化学报, 2020, 46(1): 79-93. doi: 10.16383/j.aas.c170714
    [2] 余伟伟, 谢承旺, 闭应洲, 夏学文, 李雄, 任柯燕, 赵怀瑞, 王少锋. 一种基于自适应模糊支配的高维多目标粒子群算法[J]. 自动化学报, 2018, 44(12): 2278-2289. doi: 10.16383/j.aas.2018.c170573
    [3] 吕柏权, 张静静, 李占培, 刘廷章. 基于变换函数与填充函数的模糊粒子群优化算法[J]. 自动化学报, 2018, 44(1): 74-86. doi: 10.16383/j.aas.2018.c160547
    [4] 任子武, 朱秋国, 熊蓉. 快速连续反应-避障作业环境下的七自由度灵巧臂轨迹规划[J]. 自动化学报, 2015, 41(6): 1131-1144. doi: 10.16383/j.aas.2015.c140676
    [5] 杨强大, 张卫军, 牛大鹏. 基于改进PSO的发酵过程同步串联混合建模[J]. 自动化学报, 2015, 41(3): 620-630. doi: 10.16383/j.aas.2015.c131195
    [6] 周晓君, 阳春华, 桂卫华, 董天雪. 带可变随机函数和变异算子的粒子群优化算法[J]. 自动化学报, 2014, 40(7): 1339-1347. doi: 10.3724/SP.J.1004.2014.01339
    [7] 潘峰, 周倩, 李位星, 高琪. 标准粒子群优化算法的马尔科夫链分析[J]. 自动化学报, 2013, 39(4): 381-389. doi: 10.3724/SP.J.1004.2013.00381
    [8] 蔡国榕, 李绍滋, 吴云东, 苏松志, 陈水利. 一种透视不变的图像匹配算法[J]. 自动化学报, 2013, 39(7): 1053-1061. doi: 10.3724/SP.J.1004.2013.01053
    [9] 刘建华, 刘国买, 杨荣华, 胡文瑜. 粒子群算法的交互性与随机性分析[J]. 自动化学报, 2012, 38(9): 1471-1484. doi: 10.3724/SP.J.1004.2012.01471
    [10] 刘钢, 老松杨, 袁灿, 侯绿林, 谭东风. 反舰导弹航路规划的OACRR-PSO算法[J]. 自动化学报, 2012, 38(9): 1528-1537. doi: 10.3724/SP.J.1004.2012.01528
    [11] 李毅, 孙正兴, 陈松乐, 李骞. 基于退火粒子群优化的单目视频人体姿态分析方法[J]. 自动化学报, 2012, 38(5): 732-741. doi: 10.3724/SP.J.1004.2012.00732
    [12] 刘朝华, 章兢, 李小花, 张英杰. 免疫协同微粒群进化算法的永磁同步电机多参数辨识模型方法[J]. 自动化学报, 2012, 38(10): 1698-1708. doi: 10.3724/SP.J.1004.2012.01698
    [13] ALFI Alireza. 具有适应性突变和惯性权重的粒子群优化(PSO)算法及其在动态系统参数估计中的应用[J]. 自动化学报, 2011, 37(5): 541-549. doi: 10.3724/SP.J.1004.2011.00541
    [14] 黄发良, 肖南峰. 基于线图与PSO的网络重叠社区发现[J]. 自动化学报, 2011, 37(9): 1140-1144. doi: 10.3724/SP.J.1004.2011.01140
    [15] 潘峰, 陈杰, 辛斌, 张娟. 粒子群优化方法若干特性分析[J]. 自动化学报, 2009, 35(7): 1010-1016. doi: 10.3724/SP.J.1004.2009.01010
    [16] 黄肖玲, 柴天佑. 粒子群优化算法在大型选矿企业原料采购计划中的应用[J]. 自动化学报, 2009, 35(5): 632-636. doi: 10.3724/SP.J.1004.2009.00632
    [17] 吕强, 刘士荣, 邱雪娜. 基于信息素机制的粒子群优化算法的设计与实现[J]. 自动化学报, 2009, 35(11): 1410-1419. doi: 10.3724/SP.J.1004.2009.01410
    [18] 钟一文, 蔡荣英. 求解二次分配问题的离散粒子群优化算法[J]. 自动化学报, 2007, 33(8): 871-874. doi: 10.1360/aas-007-0871
    [19] 金欣磊, 马龙华, 吴铁军, 钱积新. 基于随机过程的PSO收敛性分析[J]. 自动化学报, 2007, 33(12): 1263-1268. doi: 10.1360/aas-007-1263
    [20] 潘峰, 陈杰, 甘明刚, 蔡涛, 涂序彦. 粒子群优化算法模型分析[J]. 自动化学报, 2006, 32(3): 368-377.
  • 加载中
图(6) / 表(4)
计量
  • 文章访问数:  1210
  • HTML全文浏览量:  214
  • PDF下载量:  2284
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-11-18
  • 录用日期:  2016-03-26
  • 刊出日期:  2016-10-20

粒子群优化算法的性能分析和参数选择

doi: 10.16383/j.aas.2016.c150774
    基金项目:

    中央高校基本科研基金 20140139

    国家自然科学基金 61203041

    教育部高等学校博士学科点专项科研基金 20120036120013

    作者简介:

    王东风   博士, 华北电力大学控制与计算机工程学院教授.主要研究方向为群智能优化算法和智能控制.E-mail:wangdongfeng@ncepu.edu.cn

    通讯作者: 孟丽  华北电力大学控制与计算机工程学院博士研究生.主要研究方向为智能优化算法及其应用.本文通信作者.E-mail:mengli2014@163.com

摘要: 惯性权重和加速因子是影响粒子群算法优化性能的重要参数.基于常用的12个测试函数,本文通过实验研究了不同参数组合下粒子的探索能力和算法的优化性能,在此基础上推荐了一组固定的参数组合.通过惯性权重和加速因子的不同变化策略组合对算法性能影响的实验分析,推荐了一种变化的参数设置方法.基于CEC2015发布的15个基准函数进一步验证了本文推荐的参数选取方法的有效性.最后讨论了粒子群优化(Particle swarm optimization,PSO)算法在连续优化和离散优化方面的应用问题.

English Abstract

王东风, 孟丽. 粒子群优化算法的性能分析和参数选择. 自动化学报, 2016, 42(10): 1552-1561. doi: 10.16383/j.aas.2016.c150774
引用本文: 王东风, 孟丽. 粒子群优化算法的性能分析和参数选择. 自动化学报, 2016, 42(10): 1552-1561. doi: 10.16383/j.aas.2016.c150774
WANG Dong-Feng, MENG Li. Performance Analysis and Parameter Selection of PSO Algorithms. ACTA AUTOMATICA SINICA, 2016, 42(10): 1552-1561. doi: 10.16383/j.aas.2016.c150774
Citation: WANG Dong-Feng, MENG Li. Performance Analysis and Parameter Selection of PSO Algorithms. ACTA AUTOMATICA SINICA, 2016, 42(10): 1552-1561. doi: 10.16383/j.aas.2016.c150774
  • 粒子群优化(Particle swarm optimization, PSO)算法是Kennedy和Eberhart在1995年提出的一种群智能优化算法[1], 源于对鸟群捕食行为的研究. 1998年, Shi等[2]在原始PSO中引入了惯性权重, 后来被称为标准PSO.由于PSO结构简单、易于实现, 且不需要借助问题的特征信息, 已受到众多学者的关注, 在算法的性能改进和分析方面不断取得新的成果[3-4], 在多个领域得到广泛应用[5].

    在PSO算法中, 有一些需要调节的参数:种群规模(种群的个体数目) $N$ , 速度限值 ${{\pmb {V}}_{\rm {max}}}$ , 位置限值 ${{\pmb {X}}_{\rm max}}$ , 惯性权重 $w$ , 加速因子 ${c_1}$ 和 ${c_2}$ .其中, $w$ , ${c_1}$ 和 ${c_2}$ 对算法性能的影响较大, 目前有很多学者对其设定和调节方式进行了研究.在参数选取方面, 文献[6 $-$ 9]通过实验或理论分析, 推荐了一组固定参数值.在时变参数的调节方面, 对于惯性权重的调整, 文献[2, 10]提出了随迭代次数减小惯性权重, 文献[11 $-$ 12]给出了随机惯性权重策略, 文献[13 $-$ 15]根据种群的信息自适应地调节惯性权重; 对于加速因子的调整, 文献[16]提出在迭代的过程中, ${c_1}$ 和 ${c_2}$ 线性递减, 文献[17]则提出 ${c_1}$ 线性递减、 ${c_2}$ 线性递增, 文献[18]基于个体的更新信息给出了一种 ${c_1}$ 和 ${c_2}$ 的自适应调整策略.以上这些参数的调整方法, 都在一定程度上提高了算法的性能, 但是, 当涉及到时变参数时, 并没有考虑到惯性权重和加速因子之间的配合作用.单独依靠调整惯性权重或加速因子, 并不能在种群的局部开发能力(Exploitation ability)和全局探索能力(Exploration ability)之间进行平衡.事实上, 各个参数之间需要相互配合, 才能够达到预定的效果.本文考虑了各个参数之间的配合, 基于在感兴趣的参数范围内进行的优化测试实验数据, 通过定义最优解超越次数, 推荐了一组固定和时变的参数值.

    本文其余部分安排如下:第1节先给出标准粒子群算法的形式; 第2节通过仿真实验研究不同参数对粒子探索能力、算法成功率和算法性能的影响, 推荐一组固定参数值; 第3节研究算法中的认知参数 ${c_1}$ 和社会参数 ${c_2}$ 的变化策略对算法性能的影响, 并推荐一组变参数的组合设定方式; 第4节基于CEC2015发布的15个基准函数进一步验证本文推荐的参数选取方法的有效性; 第5节讨论PSO算法在连续优化和离散优化方面的应用问题; 第6节对全文进行了总结.

    • 在粒子群算法中, 每个粒子代表寻优空间中一个潜在的解, 有一个由被优化的函数决定的适应值.在每一次迭代进化中, 粒子通过自身和群体的历史最优位置更新当前的速度和位置.在任意 ${t+1}$ 时刻, 粒子群算法中第 $i$ 个粒子第 $d$ 维的速度和位置更新公式为

      $$ \begin{align} &{v_{id}}(t + 1) = w{v_{id}}(t) + {c_1}{r_{1d}}(t)({p_i}_d(t)~ - \nonumber\\[1mm] &\qquad {x_{id}}(t)) + {c_2}{r_{2d}}(t)({p_g}_d(t) - {x_{id}}(t)) \end{align} $$ (1)
      $$ \begin{align} {x_{id}}(t + 1) = {x_{id}}(t) + {v_{id}}(t + 1) \end{align} $$ (2)

      其中, ${v_{id}}$ 和 ${x_{id}}$ 分别为粒子的速度和位置, $w$ 为惯性权值, ${c_1}$ 和 ${c_2}$ 称为加速因子, 分别为认知参数和社会参数, ${p_{id}}$ 和 ${p_{gd}}$ 分别为个体和群体的历史最优位置, ${r_{1d}}$ 和 ${r_{2d}}$ 为两个相互独立的服从[0, 1]之间均匀分布的随机数, 正是这两个随机数的引入, 使得算法的进化过程具有一定的不确定性, 也因此赋予了算法一定的空间探索能力, 从而有利于找到问题的最优解.

    • 下面通过实验说明粒子的探索能力和算法的性能与参数之间的关系.我们感兴趣的参数区域是 $w$ $\in$ $\left[{-1, 1} \right]$ , ${c_1} + {c_2} \in \left[{0, 8} \right]$ , 这也是绝大多数文献研究的区域.所有的实验都基于以下12个常用的基准函数, 由于这些基准函数被普遍应用, 在此只给出函数的名称, 即: Fun 1: Sphere; Fun 2: Rosenbrock; Fun 3: Schwefel $'$ s P2.21; Fun 4: Schwefel $'$ s P2.22; Fun 5: Schwefel $'$ s P1.2; Fun 6: Rastrigin; Fun 7: Griewank; Fun 8: Ackley; Fun 9: Schwefel; Fun 10: Weierstrass; Fun 11: Penalized1; Fun 12: Penalized2.

    • 粒子群算法参数 $w$ , ${c_1}$ , ${c_2}$ 的选取对算法的优化性能有很大影响.不同的参数组合下, 粒子的轨迹形式是不同的, 决定了粒子探索能力的大小.在种群进化过程中的第 $t$ 代, 若粒子能够找到比 $t-1$ 代的全局最优解更好的解, 那么则认为粒子具有一定的探索能力.我们通过以下实验观察不同的参数对粒子探索能力的影响.设种群规模为 $N$ , 为每个粒子设置不同的参数, 设置变量 $Pnu{m_i}$ 记录具有不同参数的粒子 $i$ 在进化的过程中超越上一代的全局最优解的次数:

      $$ \begin{align*} &Pnu{m_i}(t) =\\ &\ \, \begin{cases} {Pnu{m_i}(t - 1) + 1, }& \mbox {若}~f({p_i}(t)) < f({p_g}(t - 1))\\ {Pnu{m_i}(t - 1), }& \mbox {若}~f({p_i}(t)) \ge f({p_g}(t - 1)) \end{cases} \end{align*} $$

      其中, $t = 2, 3, \cdots, {t_{\max }}$ .

      将上面定义的 $Pnu{m_i}$ 称为粒子 $i$ 的第 $t$ 代最优解超越次数, 它表征了粒子探索能力的大小.显然, 探索能力大的粒子更有可能找到全局最优解.

      对于所有的粒子设置相同参数的粒子群算法, 则所有的粒子在统计意义上具有相同的探索能力; 随着算法进化进程的推进, 具有不同的状态的粒子在当前迭代步则具有不同的探索能力; 被设置不同参数的粒子, 一般则具有不同的探索能力.这已得到作者们进行的大量仿真优化计算实例的证实. 图 1为4组不同的PSO种群在优化函数Sphere时每个粒子的 $Pnum$ 值:种群大小均为50, 函数设置为10维, 最大迭代次数为500, 每组种群运行50次, 记录每个粒子 $Pnum$ 值的平均值. 图 1(a)为种群中粒子设置为相同的参数时( $w = 0.6$ , ${c_1} = {c_2} = 1.7$ )每个粒子的 $Pnum$ 值; 图 1(b)图 1(c)图 1(d) 为种群中粒子设置不同参数时每个粒子的 $Pnum$ 值, 其中图 1(b)中, 第 $1$ $\sim$ $50$ 个粒子的 $w$ 值均为0.6, ${c_1}$ $=$ ${c_2}$ 为 $0.04:0.04:2$ ; 图 1(c)中, 第 $1$ $\sim$ $50$ 个粒子的 $w$ 值均为1.7, ${c_1} = {c_2}$ 分别为 $0.02:0.02:1$ , 图 1(d)中, 第 $1$ $\sim$ $10$ 个粒子的 $w$ 值均为0.2, ${c_1} = {c_2}$ 分别为 $0.2:0.2:2$ , 第 $11$ $\sim$ $20$ 个粒子的 $w$ 均为0.4, ${c_1}$ $=$ ${c_2}$ 分别为 $0.2:0.2:2$ , 依此类推, 第 $41$ $\sim$ $50$ 个粒子的 $w$ 均为1.0, ${c_1} = {c_2}$ 分别为 $0.2:0.2:2$ .

      图  1  具有不同参数的种群优化函数Sphere时粒子的Pnum

      Figure 1.  The Pnum value of function Sphere optimized by PSO with different population scale

      在 $w \in \left[{-1, 1} \right]$ , ${c_1} + {c_2} \in \left[{0, 8} \right]$ 的参数区域上对所用的12个基准函数进行蒙特卡罗实验.每个函数进行两组实验: 1)种群中的个体取相同的 $w$ , ${c_1}=$ ${c_2}$ 则取不同的数值.本组实验中, 根据种群参数 $w$ 的值分为51组子实验, $w$ 的取值按0.04的间隔从 $-1$ $\sim$ $1$ , 每个子实验中, 种群大小均为81, ${c_1}$ $=$ ${c_2}$ 按0.05的间隔从 $0$ $\sim$ $4$ 取81个值分配给不同的粒子, 函数运行50次, 记录不同粒子在50次运行中的 $Pnum$ 的平均值. 2)种群中的个体取不同的 $w$ , 而 ${c_1}$ $=$ ${c_2}$ 取相同的固定值.本组实验中, 根据种群参数 ${c_1}$ $({c_2})$ 的值分为81组子实验, ${c_1} = {c_2}$ 的取值按0.05的间隔从 $0$ $\sim$ $4$ , 每个子实验中, 种群大小均为51, $w$ 按0.04的间隔从 $-1$ $\sim$ $1$ 共取51个值分配给不同的粒子, 函数运行50次, 记录不同粒子在50次运行中的 $Pnum$ 的平均值.将两组实验中得到的相同参数组合下粒子 $i$ 的 $Pnu{m_i}$ 进行求和, 得到此参数组合在不同种群环境中的综合探索性能, 进而得到整个参数区域内不同参数组合的综合超越次数.相比于超越次数的绝对值, 我们更关心不同参数组合下粒子探索能力的相对关系, 因此对每个函数得到的结果分别进行归一化处理, 结果如图 2所示.值得注意的是, 在 $6 < {c_1} + {c_2}\leq 8$ 的区域中, 对于任意的 $w$ 运行结果 $Pnu{m_i}$ 均为0, 因此, $6 < {c_1} + {c_2}$ $\leq$ $8$ 的区域并未在图中进行展示.从图 2可以明显地看到粒子群算法的参数取值对不同基准函数的优化性能的共性和特性, 即对每个基准函数来说, 算法的探索能力对参数的取值表现出明显的区域性, 总体来说大同小异, 这为PSO的参数选择提供了很好的指导作用.

      图  2  粒子探索能力与参数的关系

      Figure 2.  Relationship between particle exploration ability and its parameters

    • 在 $w \in \left[{-1, 1} \right]$ , ${c_1} + {c_2} \in \left[{0, 8} \right]$ 矩形域上按照等间隔的网格取点, $\left( {{c_1} + {c_2}} \right)$ 轴取点间隔为0.02, 共101点, $w$ 轴取点间隔为0.04, 共201点, 共可得到20 301组不同的参数组合.对每一组参数组合进行蒙特卡罗仿真实验, 优化12个基准函数.种群规模 $N$ 为50, 最大迭代次数 ${t_{\rm {max}}}$ 为500, 每个函数独立运行50次.为每个函数设置寻优精度goal, 记录不同参数组合下达到所设置寻优精度的成功率, 绘制成灰度图像.每个函数的寻优精度为图中的goal所示, 是通过实验测试得到的, 原则是不会使测试结果得到的最佳参数组合区域过大而失去指导意义, 也不会使其过小而失去一般性参考价值.设置一定的寻优精度, 实验结果如图 3所示.

      图  3  算法成功率与参数的关系

      Figure 3.  Relationship between the algorithm success rate and particle parameters

      图 3可以看到, 除了Fun 2、Fun 6、Fun 7和Fun 9, 其他8个函数的最优参数区域在形状上非常相似, 并且都出现在靠近过渡区域的边界部分.这一部分的参数使得粒子轨迹能够以一定的幅值振荡, 使得探索能力和开发能力获得很好的平衡.对于Fun 2、Fun 6、Fun 7和Fun 9这4个函数, Fun 2为很难极小化的典型病态二次函数; Fun 6、Fun 7为典型的具有大量局部最优点的复杂多峰函数; Fun 9的全局最优点与第2最优点相距很远, 算法往往朝着错误的方向(第2最优点)收敛.这4个函数只靠调节算法参数很难得到满意的解, 运行结果的规律性没有其他函数那么明显.

      图 2图 3对比可以看到, 图 2图 3并不是完全对应的. 图 2中展示的粒子的探索能力为粒子的局部探索能力和全局探索能力的总和, 而不同的函数具有不同的特性, 对群体的局部探索能力和全局探索能力的要求是不同的.虽然总的探索能力与寻优性能并不是完全对应的, 但是, 没有探索能力的参数区域, 基本上是不可取的.

      几种典型参数选取策略的性能对比及一组固定参数推荐值}由图 3可以看到, 使得算法获得优良性能的参数区域因函数的不同而有一些差异, 基本上没有一组参数能够使得所有的函数同时获得最优, 尤其可以看到, Fun 2和Fun 9的较优参数区域的交集部分是非常小的.尽管如此, 仍然可以选择出一些参数, 使算法在所有函数上获得比较令人满意的综合性能.为了能够更加容易地选择出在12个函数上综合性能较优的参数, 我们将不同函数下得到的运行结果进行整合, 得到算法在不同参数下的综合性能的示意图, 见图 4.

      图  4  算法在12个测试函数上的性能总和

      Figure 4.  Total optimization performance on the 12 test functions

      图 4中标示的PARA1和PARA2分别为文献[6]和文献[7]推荐的参数取值.其中, 参数组合PARA1 ( $w=0.7298$ , ${c_1}={c_2}=1.49618$ )是Eberhart等[6]将带有惯性权重和带有收缩因子的两种形式的粒子群算法进行比较后推荐的一组参数; 参数组合PARA2 ( $w = 0.6$ , ${c_1} = {c_2} = 1.7$ )是[7]在分析粒子轨迹收敛域的基础上推荐的参数.参数组合PARA3是我们根据性能综合图, 即图 4推荐的一组参数: $w = 0.4$ , ${c_1} = {c_2} = 2$ .在另外的工作中, Samal等[8]在理论分析的基础上给出了一组具有较快收敛速度的参数: $w = 0.6$ , ${c_1}{r_1}=0.103$ , ${c_2}{r_2} = 2.897$ (参数组合PARA4); Carlisle等[9]在文献[6]的基础上进行了进一步的实验, 考虑了 $c_1' \ne c_2'$ 的情况, 通过仿真实验得到, 当 $c_1' = 2.8$ , $c_2' = 1.3$ 时, 算法的性能较优, 即 $w=0.7298$ , ${c_1} = 2.0434$ , ${c_2} = 0.9487$ (参数组合PARA5).我们将这5组参数在12个函数上进行测试, 种群规模、最大迭代次数和每个函数独立运行的次数都与第2.2节一致.记录运行数次结果中的最小值(min)、最大值(max)、平均值 $\pm$ 标准差(mean $\pm$ std), 以及优化成功率(Success rate, SR), 并且记录了不同参数在每个函数指定寻优精度下的成功率, 结果列于表 1中.为了清晰地显示参数对算法性能的影响, 此处为12个函数指定的寻优精度依次为: ${10^{ - 20}}$ , 3, ${10^{ - 5}}$ , ${10^{ - 10}}$ , ${10^{ - 20}}$ , 5, ${10^{ - 1}}$ , ${10^{ - 10}}$ , 500, ${10^{ - 3}}$ , ${10^{ - 20}}$ , ${10^{ - 20}}$ .以下各测试试验中所用的寻优精度均与此相同.首先来看参数PARA1 $\sim$ PARA3的运行结果, 这三个参数组合基本上都在图 4中的较优区域里.三组参数在Fun 1, Fun 3, Fun 4, Fun 8, Fun 11和Fun 12上的运行结果差别不大.在Fun 2, Fun 5, Fun 6, Fun 7, Fun 9和Fun 10上的差别相对较大, 参数PARA1在Fun 2, Fun 7上表现较优, 在Fun 5上表现较差; 参数PARA2在Fun 6, Fun 9上表现较差; 参数PARA3在Fun 6, Fun 9和Fun 10上表现较优, 在Fun 2, Fun 7上表现较差.正如从图 3中看到的, 每组参数都有其适应的函数.再来看参数PARA4和参数PARA5, 同样的, 每组参数在不同函数上表现出的性能也是有差别的.参数PARA4的综合性能在所有的参数中是比较差的.参数PARA5是在参数PARA1的基础上发展而来的, 保持 ${c_1}$ 与 ${c_2}$ 之和不变, 改变 ${c_1}$ 和 ${c_2}$ 的比例, 除了在Fun 2上, 参数PARA5的性能要优于参数PARA1.

      表 1  5组参数的运行结果对比

      Table 1.  Comparison of running results on 5 parameters

      函数PARAminmaxmean±stdSR
      Fun 111.47E-258.64E-226.32E-23±1.34E-221.00
      29.05E-365.64E-311.73E-32±7.16E-321.00
      31.98E-402.94E-341.31E-35±4.50E-351.00
      41.81E-572.84E-332.86E-35±2.84E-341.00
      51.63E-271.45E-232.71E-25±1.46E-241.00
      Fun 212.72E-027.29E+002.40E+00±1.43E+000.84
      23.18E-031.20E+023.75E+00±1.19E+010.76
      31.20E-038.27E+003.45E+00±1.96E+000.30
      46.03E-028.96E+004.30E+00±1.57E+000.07
      52.21E-028.45E+003.45E+00±1.40E+000.31
      Fun 316.55E-108.21E-081.38E-08±1.58E-081.00
      25.68E-141.07E-109.80E-12±1.70E-111.00
      32.98E-117.36E-098.82E-10±1.32E-091.00
      47.06E-124.01E-046.10E-06±4.09E-050.94
      51.23E-101.02E-081.63E-09±1.77E-091.00
      Fun 411.06E-141.00E+015.00E-01±2.19E+000.95
      27.73E-201.00E+011.00E-01±1.00E+000.99
      37.38E-237.89E-209.10E-21±1.60E-201.00
      48.37E-201.00E+011.00E-01±1.00E+000.98
      51.64E-151.12E-131.82E-14±1.87E-141.00
      Fun 511.14E-251.00E+042.00E+02±1.40E+030.00
      26.54E-351.82E-292.24E-31±1.82E-301.00
      31.74E-392.36E-331.04E-34±3.60E-341.00
      42.45E-546.74E-346.74E-36±6.74E-351.00
      51.44E-267.31E-245.72E-25±9.94E-250.32
      Fun 619.91E-131.39E+015.73E+00±3.06E+000.55
      29.94E-011.59E+016.61E+00±3.23E+000.43
      30.00E+001.39E+014.87E+00±2.94E+000.68
      49.94E-014.47E+019.87E+00±7.05E+000.23
      51.66E-137.95E+003.29E+00±1.84E+000.85
      Fun 711.47E-021.64E-017.49E-02±3.35E-020.83
      27.39E-031.84E-017.77E-02±3.52E-020.77
      31.47E-022.21E-017.94E-02±4.10E-020.74
      41.72E-023.05E-011.12E-01±5.99E-020.53
      51.11E-151.69E-016.15E-02±3.39E-020.86
      Fun 812.38E-131.99E+011.99E-01±1.99E+000.99
      23.55E-157.10E-153.94E-15±1.11E-151.00
      33.55E-157.10E-153.97E-15±1.16E-151.00
      43.55E-151.15E+001.15E-02±1.15E-010.97
      51.42E-146.18E-131.51E-13±1.19E-131.00
      Fun 910.00E+001.30E+036.41E+02±2.28E+020.35
      20.00E+001.42E+036.83E+02±2.86E+020.30
      31.18E+021.54E+036.41E+02±3.04E+020.44
      41.18E+001.19E+036.40E+02±2.51E+020.36
      50.00E+009.49E+024.48E+02±1.86E+020.67
      Fun 1013.55E-101.57E+001.46E-01±4.41E-010.86
      20.00E+003.07E+001.69E-01±5.28E-010.86
      30.00E+001.50E+006.00E-02±2.96E-010.96
      41.81E-133.00E+001.40E-01±4.50E-010.46
      50.00E+003.46E-023.46E-04±3.46E-030.99
      Fun 1115.76E-275.30E-215.90E-23±5.30E-221.00
      24.71E-321.90E-314.94E-32±1.53E-321.00
      34.71E-323.11E-011.55E-02±6.81E-020.95
      44.71E-323.11E-011.24E-02±6.12E-020.95
      55.16E-293.55E-245.37E-26±2.57E-251.00
      Fun 1216.86E-276.65E-222.13E-23±7.32E-231.00
      21.34E-324.65E-312.13E-32±4.68E-321.00
      31.34E-322.72E-265.45E-28±3.85E-271.00
      41.34E-324.23E-134.23E-15±4.26E-140.99
      52.78E-281.93E-232.82E-25±1.93E-241.00

      为了能够比较全面地了解 ${c_1}$ 和 ${c_2}$ 的比例对算法的影响, 我们保持参数PARA1中的 $w = 0.7298$ , ${c_1}+{c_2}=2.992$ , 将 ${c_1}$ 在 ${c_1} + {c_2}$ 的总和中所占的比率由0逐渐增加到1, 在12个函数上的运行结果如图 5所示. Fun 2, Fun 6, Fun 7和Fun 9在整个比率范围内的变化情况较为复杂, 图 5(a)为这4个函数的变化情况, 另外8个函数的优化情况展示在图 5(b)中.当 ${c_1}$ 在 ${c_1}$ 与 ${c_2}$ 之和中所占比例 ${c_1}/( {c_1} + {c_2} )$ 在0.6 $\sim$ 0.8之间时, 图 5(b)中的8个函数都获得了很好的性能, 而图 5(a)中, 算法在Fun 6, Fun 7和Fun 9上的成功率随 ${c_1}/( {c_1} + {c_2})$ 的增加而增大, 在0.8附近到达最好值; Fun 2则相反, 成功率随着 ${c_1}/({c_1}+{c_2})$ 的增加而减小, 在0.8时的成功率非常低.当 ${c_1}/({c_1}+{c_2})$ 取为0.683时, 便可得到参数组合PARA5, 对于图 5(b)的8个函数来说, 是最好的选择.而对于图 5(a)的4个函数来说, 是综合考虑的折中选择.

      图  5  c1所占比率对算法成功率的影响

      Figure 5.  The influence of ratio c1 on algorithm0s success rate

    • 以上的实验和讨论都是基于在种群进化过程中 ${c_1}$ 和 ${c_2}$ 为定值的情形下进行的, 从表 1图 5的运行结果可以看到, 无论 ${c_1}$ 和 ${c_2}$ 是否相等, 采用 ${c_1}$ 和 ${c_2}$ 定值的调节算法在算法性能上是有局限性的.为了进一步提高算法的性能, 下面观察在迭代的过程中 ${c_1}$ 和 ${c_2}$ 按照不同的方式变化时对算法性能的影响.实验仍然基于12个测试函数, 对于固定的 $w$ , ${c_1}$ 和 ${c_2}$ 有9种不同的调整策略, 为简洁表示, 引入3个符号: `` $\rightarrow$ ''表示参数 ${c_1}$ 或 ${c_2}$ 保持不变, 为1.5; `` $\uparrow$ ''表示参数 ${c_1}$ 或 ${c_2}$ 在迭代的过程中线性地由0.5上升到2.5; `` $\downarrow$ ''表示参数 ${c_1}$ 或 ${c_2}$ 在迭代的过程中线性地由2.5下降到0.5.则 ${c_1}$ 和 ${c_2}$ 的9种调节策略表示为:

      1) ${c_1}\rightarrow$ , ${c_2}\rightarrow$ ; ~~~2) ${c_1}\rightarrow$ , ${c_2}\uparrow$ ; ~~~3) ${c_1}\rightarrow$ , ${c_2}\downarrow$ ;

      4) ${c_1}\uparrow$ , ${c_2}\rightarrow$ ; ~~~~5) ${c_1}\uparrow$ , ${c_2}\uparrow$ ; ~~~6) ${c_1}\uparrow$ , ${c_2}\downarrow$ ;

      7) ${c_1}\downarrow$ , ${c_2}\rightarrow$ ; ~~~~8) ${c_1}\downarrow$ , ${c_2}\uparrow$ ; ~~~9) ${c_1}\downarrow$ , ${c_2}\downarrow$ .

      对于每个函数, 进行如下实验: $w$ 从0逐渐增加到1, 对于每个 $w$ 的值, 分别用以上9种策略进行实验.每个优化实验运行50次.记录最终结果到达指定精度的成功率.运行结果如图 6所示, 纵轴为算法寻优的成功率, 横轴为 $w$ 值, 每个子图中的9条曲线, 分别对应上述 ${c_1}$ 和 ${c_2}$ 的9种取值策略.

      图  6  变化的c1c2取值策略对算法成功率的影响

      Figure 6.  The influence of varying c1 and c2 on algorithm0s success rate

      图 6可以看到, 每一种 ${c_1}$ 和 ${c_2}$ 的取值策略都有与其对应的 $w$ 的最佳取值范围.除了Fun 2, Fun 6, Fun 7和Fun 9, 各种策略的性能随着 $w$ 的变化情况是类似的, 即:沿着 $w$ 轴的正方向, $w$ 的整个区间可以分为5个区域: 1)初始阶段, 成功率几乎为0; 2)紧随其后的很小的区域内, 成功率由0迅速上升达到曲线的最大值; 3)在一段区域内, 成功率保持为最大值; 4)紧随其后的很小的区域内, 成功率迅速下降; 5)最后区域, 成功率几乎为零.区域1和区域3的大小与参数的取值策略紧密相关.而所有的策略在 $w>0.68$ 时, 成功率几乎均为0.区域3正是我们需要的部分.在这8个函数上, 策略3、策略7和策略9使得区域3较为宽广.再来看Fun 6, Fun 7和Fun 9, 策略2取得了最好的成功率, 其次为策略8.在Fun 6和Fun 7上, 对于某些 ${c_1}$ 和 ${c_2}$ 的取值策略, $w$ 的取值可以比较小, 也能够使算法获得不错的性能.在Fun 2上, 各个策略相适应的 $w$ 值范围都很小.相比较而言, 不论是从 $w$ 的适用范围的大小还是从成功率的高低来看, 策略4、策略5和策略6都是不可取的, 即增大的调节方式总是不可取的.综合12个测试函数来看, 策略8在Fun 6, Fun 7和Fun 9上, 在 $w=0.68$ 时具有很突出的效果, 并且, 在其他8个函数上, 虽然策略8的 $w$ 的适用范围并不宽广, 但在 $w=0.68$ 时, 恰恰都具有很好的性能, 因此, $w=0.68$ , ${c_1}$ 在迭代过程中由2.5线性减小到0.5, ${c_2}$ 由0.5线性增加到2.5, 是一种很好的参数设置方式.这与Ratnaweera等[17]提出的 ${c_1}$ 递减和 ${c_2}$ 递增的调整策略是相符的, 在文献[17]中, ${c_1}$ 和 ${c_2}$ 的变化范围与本文相同, 而 $w$ 的取值由0.9随迭代线性减小到0.4.本文提出的和文献[17]中的参数设置方法在12个函数上的运行结果如表 2所示.在表 2中, Method-ours指本文推荐的 $w=0.68$ , ${c_1}$ 在迭代过程中由2.5线性减小到0.5, ${c_2}$ 由0.5线性增加到2.5. Method-[17]是指文献[17]给出的 $w$ 的取值由0.9随迭代线性减小到0.4, ${c_1}$ 和 ${c_2}$ 的变化范围与Method-ours相同.由表 2的运行结果可以看到, 本文的参数设置方法要优于文献[17]中的方法.值得注意的是, ${c_1}$ 和 ${c_2}$ 的变化范围, 与使其获得较优性能的 $w$ 也是相互配合的, 在我们的实验中发现, 当变化范围为[0.5, 2.05]时, $w$ 取0.75的性能要优于0.68.因此, 3个参数之间的相互配合是非常重要的.

      表 2  本文与文献[17]参数设置的优化结果比较

      Table 2.  Comparison of optimization results between the parameters set in this paper and [17]

      函数MMethodminmaxmean±stdSR
      Fun 1Ours
      [17]
      3.91E-331.42E-291.20E-30±2.51E-301.00
      5.01E-336.95E-293.09E-30±9.83E-301.00
      Fun 2Ours
      [17]
      9.79E-022.26E+001.30E+00±5.31E-011.00
      1.00E+005.72E+002.40E+00±7.33E-010.84
      Fun 3Ours
      [17]
      5.90E-132.27E-102.13E-11±3.88E-111.00
      6.03E-132.48E-102.99E-11±4.90E-111.00
      Fun 4Ours
      [17]
      5.58E-187.20E-161.60E-16±1.52E-161.00
      8.12E-182.87E-136.86E-15±4.09E-141.00
      Fun 5Ours
      [17]
      7.24E-323.86E-281.60E-29±5.49E-291.00
      2.12E-323.44E-281.65E-29±5.70E-291.00
      Fun 6Ours
      [17]
      9.94E-017.95E+003.34E+00±1.55E+000.92
      1.98E+001.09E+015.49E+00±2.36E+000.54
      Fun 7Ours
      [17]
      0.00E+001.42E-015.20E-02±2.94E-020.96
      0.00E+001.84E-017.81E-02±3.58E-020.76
      Fun 8Ours
      [17]
      3.55E-157.10E-154.68E-15±1.67E-151.00
      3.55E-152.13E-147.81E-15±3.58E-151.00
      Fun 9Ours
      [17]
      1.18E+021.04E+034.71E+02±1.99E+020.64
      1.18E+021.19E+035.48E+02±2.16E+020.42
      Fun 10Ours
      [17]
      0.00E+001.44E-026.04E-04±2.51E-030.94
      0.00E+001.15E-013.03E-03±1.64E-020.84
      Fun 11Ours
      [17]
      4.71E-322.90E-279.03E-29±4.35E-281.00
      4.71E-321.34E-283.09E-30±1.90E-291.00
      Fun 12Ours
      [17]
      1.34E-326.16E-293.88E-30±9.45E-301.00
      1.34E-321.09E-022.19E-04±1.55E-030.98
    • 为进一步验证本文参数设置方法的有效性, 将第2节的一组固定参数推荐值和第3节的时变参数设置方式, 应用于2015年的进化计算世界大会, 即CEC2015发布的15个基准函数[19].

      对于参数优化能力的验证, 种群大小与前面所有试验设置相同(设置为50), 函数维数为10, 最大迭代次数为5 000, 每个函数运行次数为100.试验仅记录达到指定精度的成功率(Success rate, SR), 其中, F1 $\sim$ F15的指定精度分别为: 3 000, 1 500, 20, 10, 500, 1 000, 10, 200, 110, 1 000, 500, 110, 30, 3 000, 110.

      图 4给出的3种典型固定参数, 即文献[6]和文献[7]推荐的参数取值PARA1和PARA2, 以及本文的参数推荐取值PARA3, 表 3给出了应用于CEC2015的15个基准函数上运行结果的对比.可以看出, 本文的参数推荐值PARA3在15个函数上的表现略优于PARA1和PARA2.

      表 3  本文给出的固定参数推荐值在CEC2015基准函数F1~F15上的运行结果

      Table 3.  Running results on CEC2015 Benchmark functions F1~F15 with fixed parameters

      PARA F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
      [6] 0.02 0.02 0.30 0.24 0.45 0.24 0.95 0.08 0.90 0.56 0.90 0.92 0.04 0.12 0.40
      [7] 0.08 0.12 0.40 0.14 0.40 0.10 1.00 0.30 0.85 0.68 0.80 0.91 0.02 0.16 0.48
      Ours 0.02 0.10 0.10 0.18 0.50 0.14 1.00 0.15 0.90 0.60 0.95 0.95 0.04 0.30 0.50

      对第3节推荐的时变参数设置方式和文献[17]的参数设置方式, 表 4给出了应用于CEC2015的15个基准函数上运行结果的对比.可以看出, 本文推荐的时变参数设置方式在15个函数上的表现优于文献[17]的参数设置方式.

      表 4  本文给出的时变参数设置方式在CEC2015基准函数F1~F15上的运行结果

      Table 4.  Running results on CEC2015 Benchmark functions F1~F15 with time-varying parameters

      Method F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
      Ours 0.70 0.26 0.30 0.94 1.00 0.64 1.00 0.50 1.00 0.95 1.00 1.00 0.25 0.40 0.96
      [17] 0.16 0.14 0.01 0.82 0.85 0.25 1.00 0.22 1.00 0.85 1.00 1.00 0.20 0.40 0.90
    • PSO算法最初是针对连续优化问题提出的, 相关研究也主要集中在连续函数优化方面[20-22], 即第1节描述的标准算法被广泛研究和应用.本文研究的出发点也主要是针对连续优化问题, 文中给出的12个标准测试函数和CEC2015发布的15个基准函数[19]的优化测试, 验证了本文方法在连续优化问题上的有效性.

      对于离散优化(或组合优化)问题而言, 解空间是离散点的集合, 而非连续区域, 因此利用PSO算法解决离散优化问题, 一般需要修正位置和速度更新公式, 或者对问题进行变形, 这方面的工作大致可分为如下三类[21-22]: 1)直接将连续PSO用于离散优化问题的求解; 2)将速度作为位置变化的概率; 3)重新定义PSO算法的操作算子.对于前两种情形, 本文推荐的参数取值方法仍然适用, 因为算法在本质上依然遵从标准的PSO连续问题求解规则.但对于第三种情形, 一般都是针对要求解的具体问题, 定义不同的PSO操作算子, 使得PSO算法在形式上与标准PSO算法差别较大, 从而本文推荐的参数取值方法难以保证其优化效果, 这方面的问题有待进一步研究.

    • 粒子群算法的可调参数共同影响着算法的优化性能, 本文将研究重点放在了惯性权重 $w$ 和加速因子 ${c_1}$ , ${c_2}$ 的设定和调节上.基于12个常用的、不同类型的基准函数, 在 $w \in \left[{-1, 1} \right]$ , ${c_1} + {c_2} \in \left[{0, 8} \right]$ 的参数区域内进行了全面的仿真研究.通过实验结果可以看到, 常常被提到的``惯性权重起着调节种群全局搜索能力和局部搜索能力''的说法是欠全面的, 种群的搜索能力和算法的性能, 是依靠 $w$ , ${c_1}$ 和 ${c_2}$ 的相互配合来调节的, 并不是仅靠一个参数可以决定的.在对固定参数的情形进行仿真并给出参数推荐值后, 还研究了时变参数对算法的影响, 给出了一种推荐的时变参数设置方法.最后通过CEC2015发布的15个基准函数进一步验证了本文推荐的参数选取方法的有效性, 并讨论了PSO算法在连续优化问题和离散优化问题方面的应用.

参考文献 (22)

目录

    /

    返回文章
    返回