基于马尔科夫链的灰狼优化算法收敛性研究

doi:10.3969/j.issn.0372-2112.2020.08.018

电子学报 ›› 2020, Vol. 48 ›› Issue (8): 1587-1595.DOI: 10.3969/j.issn.0372-2112.2020.08.018

基于马尔科夫链的灰狼优化算法收敛性研究

张孟健¹, 龙道银², 王霄¹, 杨靖¹

1. 贵州大学电气工程学院, 贵州贵阳 550025;
2. 中国电建集团贵州工程有限公司, 贵州贵阳 550001

收稿日期:2019-11-13 修回日期:2020-02-18 出版日期:2020-08-25
- 通讯作者:
- 杨靖
- 作者简介:
- 张孟健 男,1996年出生于安徽芜湖,贵州大学电气工程学院硕士研究生,研究方向为群体智能优化算法、无线传感器网络. E-mail:2311082906@qq.com
- 基金资助:
- 国家自然科学基金 (No.61861007，No.61640014）; 贵州省科技支撑计划 (No.[2019]2152，No.[2017]2520-1）; 贵州省研究生创新基金 (No.YJSCXJH[2019]005）; 贵州省物联网理论与应用案例库 (No.KCALK201708）; 贵州省学科建设 (No.ZDXK[2015]8）

Research on Convergence of Grey Wolf Optimization Algorithm Based on Markov Chain

ZHANG Meng-jian¹, LONG Dao-yin², WANG Xiao¹, YANG Jing¹

1. Electrical Engineering College, Guizhou University, Guiyang, Guizhou 550025, China;
2. Power China Guizhou Engineering Company Limited, Guiyang, Guizhou 550001, China

Received:2019-11-13 Revised:2020-02-18 Online:2020-08-25 Published:2020-08-25
- Corresponding author:
- YANG Jing
- Supported by:
- National Natural Science Foundation of China (No.61861007, No.61640014); Science and Technology Support Project of Guizhou Province (No.[2019]2152, No.[2017]2520-1); Postgraduate Innovation Fund of Guizhou Province (No.YJSCXJH[2019]005); Case Base of Internet of Things Theory and Application in Guizhou Province (No.KCALK201708); Discipline Construction in Guizhou Province (No.ZDXK[2015]8)

摘要/Abstract

摘要： 针对灰狼优化算法（Grey Wolf Optimization，GWO）在收敛性研究上的不足，首先，通过定义灰狼群状态转移序列，建立了GWO算法的马尔科夫（Markov）链模型，通过分析Markov链的性质，证明它是有限齐次 Markov链；其次，通过分析灰狼群状态序列最终转移状态，结合随机搜索算法的收敛准则，验证了GWO算法的全局收敛性；最后，对典型测试函数、偏移函数及旋转函数进行仿真实验，并与多种群体智能算法进行对比分析.实验结果表明，GWO算法具有全局收敛性强、计算耗时短和寻优精度高等优势.

关键词: 灰狼优化, 灰狼群状态空间, 马尔科夫链, 状态转移概率, 收敛准则

Abstract: The global convergence is one of the important features of an intelligent algorithm. In this paper, we take the initiative to handle the convergence of Grey Wolf Optimization (GWO) with Markov chain. Firstly, a Markov chain model of the GWO algorithm is established through defining the state transition sequence of a gray wolf population. Analyzing the properties of the Markov chain proves that it is homogeneous finite. Secondly, based on the convergence criteria of random search algorithms, the global convergence of the GWO algorithm is verified via analyzing the final state transition sequence of the grey wolf population. Finally, simulation studies on typical testing functions, shifting functions and rotating functions are carried out comparing with a few typical swarm intelligent algorithms. The experimental results show that the GWO algorithm has excellent performance on the global convergence, the computational time and precision of optimization.

Key words: Grey Wolf Optimization, grey wolf population state space, Markov chain, state transition probability, convergence criteria

中图分类号:

TP301.6

张孟健, 龙道银, 王霄, 等. 基于马尔科夫链的灰狼优化算法收敛性研究[J]. 电子学报, 2020, 48(8): 1587-1595.

ZHANG Meng-jian, LONG Dao-yin, WANG Xiao, et al. Research on Convergence of Grey Wolf Optimization Algorithm Based on Markov Chain[J]. Acta Electronica Sinica, 2020, 48(8): 1587-1595.

参考文献

[1] MIRIJALILI S,MIRJALILI S M,LEWIS A.Grey Wolf optimizer [J].Advances in Engineering Software,2014,69(1):46-61.
[2] DORIGO M,BIRATTARI M,STUTZLE T.Ant colony optimization [J].Computational Intelligence Magazine IEEE,2007,1(4):28-39.
[3] WHITLEY D.A genetic algorithm tutorial [J].Statistics and Computing,1994,4(2):65-85.
[4] TRELEA I C.The particle swarm optimization algorithm:convergence analysis and parameter selection [J].Information Processing Letters,2003,85(6):317-325.
[5] BOOPATHI M,SUJATHA R,KUMAR C S,et al.Quantification of software code coverage using artificial bee colony optimization based on Markov approach [J].Arabian Journal for Science and Engineering,2017,42:3503-3519.
[6] 朱庆保.蚁群优化算法的收敛性分析[J].控制与决策,2006,21(7):763-768. ZHU Qing-bao.Analysis of convergence of ant colony optimization algorithms [J].Control and Decision,2006,21(7):763-768.(in Chinese)
[7] 骆剑平,李霞,陈泯融.混合蛙跳算法的Markov模型及其收敛性分析[J].电子学报,2010,38(12):2875-2880. LUO Jian-ping,LI Xia,CHEN Min-rong.The markov model of shuffled frog leaping algorithm and its convergence analysis [J].Acta Electronica Sinica,2010,38(12):2875-2880.(in Chinese)
[8] GANG X,YU G S.Reprint of:On convergence analysis of particle swarm optimization algorithm [J].Journal of Computational and Applied Mathematics,2018,340(1):709-717.
[9] 任子晖,王坚,高岳林.马尔科夫链的粒子群优化算法全局收敛性分析[J].控制理论与应用,2011,28(4):462-466. REN Zi-hui,WANG Jian,GAO Yue-lin.The global convergence analysis of particle swarm optimization algorithm based on Markov chain[J].Control Theory & Applications,2011,28(4):462-466.(in Chinese)
[10] 李军华,黎明.元胞遗传算法的收敛性分析和收敛速度估计[J].模式识别与人工智能,2012,25(5):874-879. LI Jun-hua,LI Ming.Convergence analysis and convergence rate estimate of cellular genetic algorithms[J].Pattern Recognition and Artificial Interlligence,2012,25(5):874-879.(in Chinese)
[11] 宁爱平,张雪英.人工蜂群算法的收敛性分析[J].控制与决策,2013,28(10):1554-1558. NING Ai-ping,ZHANG Xue-ying.Convergence analysis of artificial bee colony algorithm [J].Control and Decision,2013,28(10):1554-1558.(in Chinese)
[12] 王继超,李擎,崔家瑞,等.一种改进的人工蜂群算法——粒子蜂群算法[J].工程科学学报,2018,40(7):871-881. WANG Ji-chao,LI Qing,CUI Jia-rui,et al.An improved artificial bee colony algorithm:particle bee colony [J].Chinese Journal of Engineering,2018,40(7):871-881.(in Chinese)
[13] 吴定会,孔飞,纪志成.鸡群算法的收敛性分析[J].中南大学学报(自然科学版),2017,48(8):2106-2112. WU Ding-hui,KONG Fei,JI Zhi-cheng.Convergence analysis of chicken swarm optimization algorithm [J].Journal of Central South University(Science and Technology),2017,48(8):2106-2112.(in Chinese)
[14] SUZUKI J.A Markov chain analysis on simple genetic algorithms [J].IEEE Transactions on Systems,Man & Cybern.1995,25(4):655–659.
[15] DOREA CH C Y,JUDINOR A G Jr,MORGADO R,et al.Multistage Markov chain modeling of the genetic algorithm and convergence results [J].Numerical Functional Analysis and Optimization,2010,31(2):164–171.
[16] He X S,Yang X S,Karamanoglu M,Zhao Y X.Global convergence analysis of the flower pollination algorithm:a discrete-time Markov chain approach [J].Procedia Computer Science.2017,108(1):1354–1363.
[17] 胡小平,曹敬.改进灰狼优化算法在WSN节点部署中的应用[J].传感技术学报,2018,31(5):753-757. HU Xiao-ping,CAO Jing.Improved grey wolf optimization algorithm for WSN node deployment [J].Journal of sensors and actuators,2018,31(5):753-757.(in Chinese)
[18] 魏政磊,赵辉,李牧懂,等.控制参数值非线性调整策略的灰狼优化算法[J].空军工程大学学报(自然科学版),2016,17(3):68-72. WEI Zheng-lei,ZHAO Hui,LI Mu-dong,et al.A grey wolf optimization algorithm based on nonlinear adjustment strategy of control parameter[J].Journal of Air Force Engineering University:Natural Science Edition,2016,17(3):68-72.(in Chinese)
[19] 段亚青,王华倩,乔学工.基于测距和灰狼优化的无线传感器网络定位算法[J].传感技术学报,2018,31(12):1894-1899. DUAN Ya-qing,WANG Hua-qian,QIAO Xue-gong.Sensor node localization based on RSSI ranging and Grey Wolf optimizer algorism in wireless sensor network[J].Journal of sensors and actuators,2018,31(12):1894-1899.(in Chinese)
[20] 滕志军,吕金玲,郭力文,等.一种基于Tent 映射的混合灰狼优化的改进算法[J].哈尔滨工业大学学报,2018,50(11):40-49. TENG Zhi-jun,LÜ Jin-ling,et al.An improved hybrid grey wolf optimization algorithm based on Tent mapping [J].Journal of Harbin Institute of Technology,2018,50(11):40-49.(in Chinese)
[21] 薛俊杰,王瑛,李浩,肖吉阳.一种狼群智能算法及收敛性分析[J].控制与决策,2016,31(12):2131-2139. XUE Jun-jie,WANG Ying,LI Hao,XIAO Ji-yang.A smart wolf pack algorithm and its convergence analysis [J].Control and Decision,2016,31(12):2131-2139.(in Chinese)
[22] LONG W,WU T B,CAI S H,et al.A novel grey wolf optimizer algorithm with refraction learning [J].IEEE Access,2019,7:78012-78028.
[23] SOLIS F J,WETS J B.Minimization by random search techniques [J].Mathematics of Operations Research,1981,6(1):19-30.
[24] LIANG J J,QIN A K,SUGANTHAN P N,et al.Comprehensive learning particle swarm optimizer for global optimization multimodal functions [J].IEEE Transactions on Evolutionary Computation,2006,10(3):281-295.
[25] QIN A K,HUANG V L,SUGANTHAN P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation,2009,13(2):398-417.
[26] YANG X Sh,HE X Sh.Mathematical Foundations of Nature-Inspired Algorithms [M].Switzerland:Springer Nature Switzerland AG,2019.
[27] KARABOGA D,BASTURK B.On the performance of artificial bee colony algorithm [J].Applied Soft Computing,2008,8(1):687－697.

基于马尔科夫链的灰狼优化算法收敛性研究

Research on Convergence of Grey Wolf Optimization Algorithm Based on Markov Chain

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	胡向东, 吕高飞, 白银. 基于优化支持向量回归的工业互联网安全态势预测方法[J]. 电子学报, 2023, 51(2): 446-454.
[2]	张兴辉, 樊秀梅, 阿喜达, 樊书嘉, 武文瑜. 反向学习的灰狼算法优化及其在交通流预测中的应用[J]. 电子学报, 2021, 49(5): 879-886.
[3]	黄戈文, 蔡延光, 戚远航, 陈厚仁, 王世豪. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.
[4]	龙文, 蔡绍洪, 焦建军, 伍铁斌. 一种改进的灰狼优化算法[J]. 电子学报, 2019, 47(1): 169-175.
[5]	金宏桥, 董一鸿, 陈华辉, 钱江波. 分布式环境下基于马尔科夫链的图流三角近似计算[J]. 电子学报, 2018, 46(9): 2139-2148.
[6]	赵海军, 崔梦天, 李明东, 何先波. 基于CTMC和状态空间模型的宽带无线接入网的QoS性能研究[J]. 电子学报, 2018, 46(4): 783-790.
[7]	张新明, 王霞, 康强, 程金凤. GWO与ABC的混合优化算法及其聚类优化[J]. 电子学报, 2018, 46(10): 2430-2442.
[8]	李鑫, 孙晋, 肖甫. 基于弹性网稀疏表示的芯片参数成品率估算方法[J]. 电子学报, 2017, 45(12): 2917-2924.
[9]	姚苏, 关建峰, 潘华, 张宏科. 基于APT潜伏攻击的网络可生存性模型与分析[J]. 电子学报, 2016, 44(10): 2415-2422.
[10]	易天柱, 何志华, 董臻. 调频连续波SAR非线性误差的开环校正方法[J]. 电子学报, 2015, 43(3): 550-556.
[11]	钟凯, 彭华, 葛临东. 基于PAM分解的高阶部分响应CPM信号盲定时同步算法[J]. 电子学报, 2015, 43(11): 2255-2262.
[12]	高志伟, 姚尧, 饶飞, 刘延钊, 罗平. 基于漏洞严重程度分类的漏洞预测模型[J]. 电子学报, 2013, 41(9): 1784-1787.
[13]	张湛;刘光杰;王俊文;戴跃伟;王执铨. 基于图像高阶MARKOV链模型的扩频隐写分析[J]. 电子学报, 2010, 38(11): 2578-2584.
[14]	汪文勇;向渝;董传坤;杨挺;唐勇. 用马尔科夫模型优化分布式最小连通支配集算法[J]. 电子学报, 2010, 38(10): 2441-2446.
[15]	李红艳;李建东;曹勇. 基于IEEE 802.11的多信道多址接入协议性能分析[J]. 电子学报, 2009, 37(4): 905-908.