基于马尔可夫链的人工蜂群算法

doi:10.13190/j.jbupt.2019-063

北京邮电大学学报 ›› 2020, Vol. 43 ›› Issue (1): 54-60.doi: 10.13190/j.jbupt.2019-063

基于马尔可夫链的人工蜂群算法

郭佳^1,2, 马朝斌^1,2, 苗萌萌², 张绍博²

1. 北京交通大学计算机与信息技术学院, 北京 100044;
2. 国家保密科技测评中心, 北京 100044

收稿日期:2019-04-17 出版日期:2020-02-28 发布日期:2020-03-27
作者简介:郭佳(1983-),女,工程师,E-mail:m13581902161@163.com.
基金资助:

Markov Chain Based Artificial Bee Colony Algorithm

GUO Jia^1,2, MA Chao-bin^1,2, MIAO Meng-meng², ZHANG Shao-bo²

1. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China;
2. National Secrecy Science and Technology Evaluation Center, Beijing 100044, China

Received:2019-04-17 Online:2020-02-28 Published:2020-03-27
Supported by:

摘要/Abstract

摘要： 分析了人工蜂群算法及部分国内外学者提出的改进算法，针对局部搜索能力差和容易陷入局部最优解的缺点，根据马尔可夫链预测已知解空间的发展趋势，提出了一种基于马尔可夫链的改进人工蜂群算法（MABC），通过伪代码给出了算法的运行过程，从收敛性能和算法复杂度2个方面分析了人工蜂群算法、一种典型的改进算法和MABC算法的性能.最后以10个典型函数为测试用例，从结果精度、收敛速度、分割参数和运行时间4个方面进行验证，实验结果表明，MABC算法在求解精度和收敛速度上高于ABC算法，但运行时间略长，验证了理论分析的结果.

关键词: 马尔可夫链, 人工蜂群算法, 函数优化

Abstract: To overcome the shortcomings of existing local search ability and to easily obtain the local optimal solution of artificial bee colony algorithm (ABC), a new modified artificial bee colony algorithm (MABC) is proposed using the development trend of known solution space predicted by Markov Chain. The running process of the algorithm is provided through a pseudo code. The performances of the ABC and MABC are analyzed from two aspects:convergence performance and algorithm complexity. Using 10 typical functions as test cases, Experiments are carried out in four aspects:result precision, convergence speed, segmentation parameters and running time. It is shown that the MABC algorithm is superior to the ABC algorithm in terms of accuracy and convergence speed.

Key words: Markov chain, artificial bee colony algorithm, function optimization

中图分类号:

TP389

郭佳, 马朝斌, 苗萌萌, 张绍博. 基于马尔可夫链的人工蜂群算法[J]. 北京邮电大学学报, 2020, 43(1): 54-60.

GUO Jia, MA Chao-bin, MIAO Meng-meng, ZHANG Shao-bo. Markov Chain Based Artificial Bee Colony Algorithm[J]. Journal of Beijing University of Posts and Telecommunications, 2020, 43(1): 54-60.

参考文献

[1] Karaboga D, Kaya E. An adaptive and hybrid artificial bee colony algorithm(aABC) for ANFIS training[J]. Neural Computing and Applications, 2014, 25(7-8):1967-1978.
[2] Goel S, Singh J, Ojha N. Intelligent aircraft landing decision support system using artificial bee colony[C]//Proc of the 3th International Conference on Computing for Sustainable Global Development. Piscataway:IEEE, 2016:2412-2416.
[3] Li X N, Yang G F. Artificial bee colony algorithm with memory[J]. Applied Soft Computing, 2016, 41(4):362-372.
[4] Zhu G, Kwong S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7):3166-3173.
[5] Banharnsakun A, Sirinaovakul B, Achalakul T. The performance and sensitivity of the parameters setting on the best-so-far ABC[C]//International Conference on Simulated Evolution & Learning.[S.l.]:Springer-Verlag, 2012:248-257.
[6] Jadon S S, Bansal J C, Tiwari R, et al. Artificial bee colony algorithm with global and local neighborhoods[J]. International Journal of System Assurance Engineering and Management, 2010, 1(3):189-200.
[7] Sharma H, Sharma S, Kumar S. Lbest Gbest artificial bee colony algorithm[C]//International Conference on Advances in Computing. NY:IEEE, 2016:119-124.
[8] 周新宇, 吴志健, 王文明. 基于正交实验设计的人工蜂群算法[J]. 软件学报, 2015, 26(9):2167-2190. Zhou X Y, Wu Z J, Wang W M. Artificial bee colony algorithm based on orthogonal experimental design[J]. Journal of Software, 2015, 26(9):2167-2190.
[9] Kiran M S, Findik O. A directed artificial bee colony algorithm[J]. Applied Soft Computing, 2015, 46(2):534-546.
[10] Du Z, Han D, Li K C. Improving the performance of feature selection and data clustering with novel global search and elite-guided artificial bee colony algorithm[J]. The Journal of Supercomputing, 2019, 75(2):5189-5226.
[11] Rajasingam N, Rasi D, Deepa S N. Optimized deep learning neural network model for doubly fed induction generator in wind energy conversion systems[J]. Soft Computing-A Fusion of Foundations, Methodologies and Applications, 2019, 23(8):8453-8470.
[12] Mala D J, Kamalapriya M, Shobana R, et al. A non-pheromone based intelligent Swarm Optimization Technique in Software Test Suite Optimization[C]//International Conference on Intelligent Agent & Multi-agent Systems.[S.l.]:IEEE Press, 2009:1-5.
[13] Tuba M, Bacanin N. Artificial bee colony algorithm hybridized with firefly algorithm for cardinality constrained mean-variance portfolio selection problem[J]. Applied Mathematics & Informaion Sciences, 2014, 8(6):2831-2844.
[14] Neelima S, Satyanarayana N, Murthy P K. Optimization of association rule mining using hybridized artificial bee colony (ABC) with BAT algorithm[C]//Advance Computing Conference.[S.l.]:IEEE, 2017:831-834.
[15] Zhiyan Shi, Dan Bao, Yan Fan, et al. The asymptotic equipartition property of Markov chains in single infinite Markovian environment on countable state space[J]. Stochastics, 2019, 91(1):1-13.
[16] Komorowski T, Peszat S, Szare K. On ergodicity of some Markov processes[J]. Annals of Probability, 2010, 38(4):1401-1443.
[17] Suganthan P N, Hansen N, Liang J J, et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[R]. Singapore:Nanyang Technological University, 2005.
[18] Zhou X, Wu Z, Wang H, et al. Enhancing differential evolution with role assignment scheme[J]. Soft Computing, 2014, 18(11):2209-2225.
[19] Xiong G, Shi D, Duan X. Enhancing the performance of biogeography-based optimization using polyphyletic migration operator and orthogonal learning[J]. Computers & Operations Research, 2014, 41(1):125-139.
[20] 杜振鑫, 刘广钟, 韩德志. 改进基于记忆的人工蜂群算法[J]. 北京邮电大学学报, 2017, 40(5):61-66. Du Z X, Liu G Z, Han D Z. An improved artificial bee colony algorithm with memory[J]. Journal of Beijing University of Posts and Telecommunications, 2017, 40(5):61-66.

基于马尔可夫链的人工蜂群算法

Markov Chain Based Artificial Bee Colony Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价

[1]	陈发堂, 韩才君, 张航, 李欣超. 一种时空混合的位置管理方案[J]. 北京邮电大学学报, 2023, 46(3): 67-72.
[2]	宋成, 金彤, 贺军义. 多值预测位置隐私保护机制[J]. 北京邮电大学学报, 2021, 44(6): 103-108.
[3]	朱德庆, 田贤忠, 栾慎吉. 多个移动节点同时切换场景下代理移动IPv6建模与性能分析[J]. 北京邮电大学学报, 2019, 42(4): 43-49.
[4]	赵国喜, 金顺福, 马聪变, 曹建宇, 许利军. 服务台数量可变的云服务系统分析[J]. 北京邮电大学学报, 2019, 42(4): 114-120.
[5]	杜振鑫, 刘广钟, 韩德志. 改进基于记忆的人工蜂群算法[J]. 北京邮电大学学报, 2017, 40(5): 61-66.
[6]	靳晓艳, 周希元, 张琬琳. 多径衰落信道中基于自适应MCMC的调制识别[J]. 北京邮电大学学报, 2014, 37(1): 31-34.
[7]	王斌, 王文鼐. 高性能电信级以太环网保护[J]. 北京邮电大学学报, 2013, 36(5): 71-75.
[8]	徐超, 盛敏, 张琰. 多业务混合模型下的蜂窝系统性能分析[J]. 北京邮电大学学报, 2013, 36(3): 102-107.
[9]	张国斌, 李明, 柯峰. 认知无线电系统转移接入概率的动态子载波分配[J]. 北京邮电大学学报, 2012, 35(6): 78-82.
[10]	高圣国,王汉兴. IEEE 80216带宽请求的性能分析[J]. 北京邮电大学学报, 2011, 34(1): 40-44.
[11]	马东超陈雪王宁张楠. 优化P2P业务传输的新型EPON接入网[J]. 北京邮电大学学报, 2010, 33(2): 88-93.
[12]	杨天剑吕廷杰. 基于广义随机petri网的供应链订货提前期建模与分析[J]. 北京邮电大学学报, 2007, 30(3): 40-44.