布谷鸟算法的收敛性分析及性能比较

doi:10.3778/j.issn.1673-9418.1912014

摘要/Abstract

摘要：

群体智能算法是一类新兴的优化方法，它通过团队的协作和组织将简单的个体联系起来产生群体智慧，并用于解决实际问题。迄今为止，群体智能算法种类繁多，布谷鸟算法（CS）是典型的群体智能算法之一，它具有实现简单、效率较高等特点。以标准CS算法原理为基础构建Markov链模型，分析其性质，结合全局收敛准则，证明CS算法的全局收敛性。实验在两方面进行仿真：一方面，在解决相同问题的情况下，分析5种算法的复杂度；另一方面，选取18个标准测试函数分别对5种算法进行数据统计，在低维度和高维度下对比了5种算法运行的精确度、收敛速度和稳定性。实验结果表明：布谷鸟算法复杂度较低，与其他算法相比，其精度高，稳定性好。

关键词: 群体智能算法, 布谷鸟算法（CS）, Markov链, 全局收敛性, 精确度

Abstract:

Swarm intelligence algorithm is an emerging optimization method, which connects simple individuals through teamwork and organization to generate swarm intelligence and is used to solve practical problems. So far, there are many kinds of swarm intelligence algorithms. Cuckoo search (CS) is one of the typical swarm intelligence algorithms. It has the characteristics of simple implementation and high efficiency. In this paper, based on the principle of CS algorithm, a Markov chain model is constructed, its properties are analyzed, and the global convergence criterion is combined to prove the global convergence of CS algorithm. The experiment is simulated in two aspects: firstly, in the case of solving the same problem, this paper analyzes the complexity of 5 algorithms; secondly, 18 standard test functions are adopted to perform statistics on the 5 algorithms respectively. Under low and high dimension, the accuracy, convergence speed and stability of the 5 kinds of algorithms are compared. The experimental results show that cuckoo algorithm is of low complexity, and compared with other algorithms, it has high accuracy and good stability.

Key words: swarm intelligence algorithm, cuckoo search (CS), Markov chain, global convergence, accuracy

刘晓东，孙丽君，陈天飞. 布谷鸟算法的收敛性分析及性能比较[J]. 计算机科学与探索, 2020, 14(10): 1644-1655.

LIU Xiaodong, SUN Lijun, CHEN Tianfei. Convergence Analysis and Performance Comparison of Cuckoo Search Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(10): 1644-1655.

参考文献

[1] Yu J P, Zhou X M, Chen M. Research on representative alg-orithms of swarm intelligence[J]. Computer Engineering and Applications, 2010, 46(25): 1-4. 余建平, 周新民, 陈明. 群体智能典型算法研究综述[J]. 计算机工程与应用, 2010, 46(25): 1-4.
[2] Wang M, Zhu Y L, He X X. A survey of swarm intelligence[J]. Computer Engineering, 2005, 31(22): 204-206. 王玫, 朱云龙, 何小贤. 群体智能研究综述[J]. 计算机工程, 2005, 31(22): 204-206.
[3] Kang Q, Zhang Y, Wang L, et al. Application overview on swarm intelligence[J]. Metallurgical Industry Automation, 2005, 29(5): 7-10. 康琦, 张燕, 汪镭, 等. 群体智能应用综述[J]. 冶金自动化, 2005, 29(5): 7-10.
[4] Kennedy J, Eberhart R. Particle swarm optimization[C]//Proceedings of the 1995 International Conference on Neural Networks, Perth, Nov 27-Dec 1, 1995. Piscataway: IEEE, 1995: 1942-1948.
[5] Ren Z H, Wang J, Gao Y L. The global convergence analysis of particle swarm optimization algorithm based on Markov chain[J]. Control Theory & Applications, 2011(4): 17-21. 任子晖, 王坚, 高岳林. 马尔科夫链的粒子群优化算法全局收敛性分析[J]. 控制理论与应用, 2011(4): 17-21.
[6] Storn R, Price K. Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization, 1997, 11(4): 341-359.
[7] Qin Q D, Cheng S, Li L, et al. Artificial bee colony algorithm: a survey[J]. CAAI Transactions on Intelligent Systems, 2014, 9(2): 127-135. 秦全德, 程适, 李丽, 等. 人工蜂群算法研究综述[J]. 智能系统学报, 2014, 9(2): 127-135.
[8] Kong X Y, Liu S Y, Wang Z. Almost sure convergence of artificial bee colony algorithm: a martingale method[J]. Computer Science, 2015, 42(9): 246-248. 孔翔宇, 刘三阳, 王贞. 人工蜂群算法的几乎必然强收敛性: 鞅方法[J]. 计算机科学, 2015, 42(9): 246-248.
[9] Yang X S. A new metaheuristic bat-inspired algorithm[J]. Computer Knowledge & Technology, 2010, 284: 65-74.
[10] Shang J N, Cheng T, Yue K Q, et al. Markov chain model analysis of bat algorithm[J]. Computer Engineering, 2017, 43(7): 198-202. 尚俊娜, 程涛, 岳克强, 等. 蝙蝠算法的Markov链模型分析[J]. 计算机工程, 2017, 43(7): 198-202.
[11] Yang X S, Deb S. Cuckoo search via Lévy flights[C]//Pro-ceedings of the 2009 World Congress on Nature & Biologically Inspired Computing. Piscataway: IEEE, 2009: 210-214.
[12] Yang X S, Deb S. Engineering optimisation by cuckoo search[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2010, 1(4): 330-343.
[13] Lin S J, Dong C, Chen M Z, et al. Summary of new group intelligent optimization algorithms[J]. Computer Engineering and Applications, 2018, 54(12): 1-9. 林诗洁, 董晨, 陈明志, 等. 新型群智能优化算法综述[J]. 计算机工程与应用, 2018, 54(12): 1-9.
[14] Wang L, Lv S X, Zeng Y R. Literature survey of fruit fly optimization algorithm[J]. Control and Decision, 2017, 32(7): 1153-1162. 王林, 吕盛祥, 曾宇容. 果蝇优化算法研究综述[J]. 控制与决策, 2017, 32(7): 1153-1162.
[15] Zhang X F, Wang X Y. Survey of cuckoo search algorithm[J]. Computer Engineering and Applications, 2018, 54(18): 8-16. 张晓凤, 王秀英. 布谷鸟搜索算法综述[J]. 计算机工程与应用, 2018, 54(18): 8-16.
[16] Garg A, Sahu O P. Cuckoo search based optimal mask generation for noise suppression and enhancement of speech signal[J]. Journal of King Saud University-Computer and Information Sciences, 2015, 27(3): 269-277.
[17] Niu H F, Song W P, Ning A P, et al. Application of chaos cuckoo search algorithm in harmonic estimation[J]. Journal of Computer Applications, 2017, 37(1): 239-243. 牛海帆, 宋卫平, 宁爱平, 等. 混沌布谷鸟搜索算法在谐波估计中的应用[J]. 计算机应用, 2017, 37(1): 239-243.
[18] Valian E, Tavakoli S, Mohanna S, et al. Improved cuckoo search for reliability optimization problems[J]. Computers & Industrial Engineering, 2013, 64(1): 459-468.
[19] Civicioglu P, Besdok E. A conceptual comparison of the Cuckoo-search, particle swarm optimization, differential evo-lution and artificial bee colony algorithms[J]. Artificial Inte-lligence Review, 2013, 39(4): 315-346.
[20] Wang L Y, Yang S P, Zhao W G. Structural damage iden-tification of bridge erecting machine based on improved Cuckoo search algorithm[J]. Journal of Beijing Jiaotong University, 2013, 37(4): 168-173. 王利英, 杨绍普, 赵卫国. 基于改进布谷鸟搜索算法的架桥机结构损伤识别[J]. 北京交通大学学报, 2013, 37(4): 168-173.
[21] Zheng H Q, Zhou Y Q. Self-adaptive step cuckoo search algorithm[J]. Computer Engineering and Applications, 2013, 49(10): 68-71. 郑洪清, 周永权. 一种自适应步长布谷鸟搜索算法[J]. 计算机工程与应用, 2013, 49(10): 68-71.
[22] Li M, Cao D X. Hybrid optimization algorithm of cuckoo search and DE[J]. Computer Engineering and Applications, 2013, 49(9): 57-60. 李明, 曹德欣. 混合CS算法的DE算法[J]. 计算机工程与应用, 2013, 49(9): 57-60.
[23] Gherboudj A, Layeb A, Chikhi S. Solving 0-1 knapsack problems by a discrete binary version of cuckoo search alg-orithm[J]. International Journal of Bio-Inspired Computation, 2012, 4(4): 229-236.
[24] Wang C, Liu C, Mu D, et al. VRPSPDTW problem solving by discrete cuckoo search[J]. Computer Intergrated Manufac-turing Systems, 2018, 24(3): 570-582. 王超, 刘超, 穆东, 等. 基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J]. 计算机集成制造系统, 2018, 24(3): 570-582.
[25] Zhang M. Hybrid multi-objective cuckoo search with dynamical local search[J]. Memetic Computing, 2017, 10(4): 1-10.
[26] Guerrero M, Castillo O, García M. Fuzzy dynamic parameters adaptation in the cuckoo search algorithm using fuzzy logic[C]//Proceedings of the 2015 IEEE Congress on Evolu-tionary Computation. Piscataway: IEEE, 2015: 441-448.
[27] Wang F, He X S, Wang Y, et al. Markov model and conv-ergence analysis based on cuckoo search algorithm[J]. Com-puter Engineering, 2012, 38(11): 180-183. 王凡, 贺兴时, 王燕, 等. 基于CS算法的Markov模型及收敛性分析[J]. 计算机工程, 2012, 38(11): 180-183.
[28] Du L M, Ruan Q, Feng D K. Cuckoo search algorithm based on conjugate gradient method[J]. Computers and Applied Chemistry, 2013, 30(4): 406-410. 杜利敏, 阮奇, 冯登科. 基于共轭梯度的布谷鸟搜索算法[J]. 计算机与应用化学, 2013, 30(4): 406-410.
[29] Xie X Y. Cuckoo search and its application on the biclustering analysis[D]. Chengdu: University of Electronic Science and Technology of China, 2014. 解翔宇. 布谷鸟搜索及其在双聚类分析的应用研究[D]. 成都: 电子科技大学, 2014.
[30] Ning A P, Zhang X Y. Convergence analysis of artificial bee colony algorithm[J]. Control and Decision, 2013, 28(10): 1554-1558. 宁爱平, 张雪英. 人工蜂群算法的收敛性分析[J]. 控制与决策, 2013, 28(10): 1554-1558.
[31] Luo J P, Li X, Chen M R. The Markov model of shuffled frog leaping algorithm and its convergence analysis[J]. Acta Electronica Sinica, 2010, 38(12): 2875-2880.骆剑平, 李霞, 陈泯融. 混合蛙跳算法的Markov模型及其收敛性分析[J]. 电子学报, 2010, 38(12): 2875-2880.