人工蜂群算法的收敛性分析:数形结合

doi:10.11896／j.issn.1002-137X.2018.10.039

摘要/Abstract

摘要： 现有人工蜂群算法的收敛性分析多是基于整体收敛性的分析方法,这些收敛性分析无法展现出人工蜂群算法在收敛过程中的收敛变化。文中采用数形结合的方式,结合目标函数图像,用阶段性分析的方法大致把蜂群算法的收敛过程分为全局搜索阶段和最优区域搜索阶段,利用人工蜂群算法在转移时需遵循一定程度上的平均分布的特征,逐步分析每个阶段的收敛过程和变化,最终得出人工蜂群算法的收敛结果和收敛特征。该方法可以清晰地展现出人工蜂群算法的收敛优势和缺陷以及算法收敛概率的变化过程。

关键词: 马尔可夫链, 全局收敛, 人工蜂群算法, 数形结合

Abstract: The convergence analysis of existing methods for artificial bee colony algorithm(ABC) is based on the analysis method of global convergence.But these convergence analysis methods can’t show the convergence change in the convergence process of ABC.Firstly,the method of combination of number and shape is adopted,and the objective function diagram is combined to divide the convergence process of ABC into the global search stage and the optimal region search stage by using stage analysis.Then,the convergence process and changes of each stage are analyzed one by one based on transferring character that the artificial bees follow a certain degree of average distribution.Finally,the convergence results and change of ABC are obtained.This method can clearly show the convergence advantages and defects of the ABC algorithm,and reveal the changing process of the convergence probability of the algorithm.

Key words: Artificial bee colony algorithm, Combination of number and shape, Global convergence, Markov chain

中图分类号:

TP301.6

火久元, 王野, 胡卓娅. 人工蜂群算法的收敛性分析:数形结合[J]. 计算机科学, 2018, 45(10): 212-216. https://doi.org/10.11896／j.issn.1002-137X.2018.10.039

HUO Jiu-yuan, WANG Ye, HU Zhuo-ya. Convergence Analysis of Artificial Bee Colony Algorithm:Combination of Number and Shape[J]. Computer Science, 2018, 45(10): 212-216. https://doi.org/10.11896／j.issn.1002-137X.2018.10.039

参考文献

[1]KARABOGA D.An idea based on honey bee swarm fornumerical optimization[R].Erciyes University,2005.
[2]KARABOGA D,BASTURK B.On the performance of artificial bee colony (ABC)algorithm[J].Applied Soft Computing,2008,8(1):687-697.
[3]HORNG M H.Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation[J].Expert Systems with Applications,2011,38(11):13785-13791.
[4]GAO W F,LIU S Y.A modified artificial bee colony algorithm[J].Computers & Operations Research,2012,39(3):687-697.
[5]ALKIN Y,ERDAL E.A discrete artificial bee colony algorithm for single machine scheduling problems [J].International Journal of Production Research,2016,54(22):6860-6878.
[6]YU W Y,HU D,TIAN N,et al.A novel search method based on artificial bee colony algorithm for block motion estimation[J].EURASIP Journal on Image & Video Processing,2017,2017(1):66.
[7]ONDER B,FATIH T M.An artificial bee colony algorithm for the economic lot scheduling problem[J].International Journal of Production Research,2014,52(4):1150-1170.
[8]KUANG F J,XU Y H,JIN Z.Artificial bee colony algorithm based on adaptive Tent chaotic search [J].Control Theory and Application,2014,31(11):1502-1509.(in Chinese)
匡芳君,徐蔚鸿,金忠.自适应Tent混沌搜索的人工蜂群算法[J].控制理论与应用,2014,31(11):1502-1509.
[9]LUO J,LI Y.Swarm optimization algorithm with chaotic search strategy [J].Control and Decision,2010,25(12):1913-1916.(in Chinese)
罗钧,李研.具有混沌搜索策略的蜂群优化算法[J].控制与决策,2010,25(12):1913-1916.
[10]ELKHATEEB N,BADR R.A Novel Variable Population Size Artificial Bee Colony Algorithm with Convergence Analysis for Optimal Parameter Tuning[J].International Journal of Computational Intelligence & Applications,2017,16(3):1-15.
[11]ZAZAS I,DALEY S.Stability and convergence analysis for different harmonic control algorithm implementations[J].Journal of Vibration & Control,2017,23(8):1231-1247.
[12]BONYADI,REZA M,ZBIGNIEW M.Analysis of Stability,Local Convergence,and Transformation Sensitivity of a Variant of the Particle Swarm Optimization Algorithm[J].IEEE Transactions on Evolutionary Computation,2016,20(3):370-385.
[13]KIM S E,LEE J W,SONG W J.A noise-resilient affine projection algorithm and its convergence analysis[J].Signal Proces-sing,2016,121:94-101.
[14]BONITO A,PASCIAK J E.Convergence analysis of variational and non-variational multigrid algorithms for the laplace-beltrami operator[J].Mathematics of Computation,2011,81(279):1263-1288.
[15]REN Z H,WANG J,GAO Y L.The global convergence analysis of particle swarm optimization algorithm based on Markov China[J].Control Theory and Applications,2011,28(4):462-466.(in Chinese)
任子晖,王坚,高岳林.马尔科夫链的粒子群优化算法全局收敛性分析[J].控制理论与应用,2011,28(4):462-466.
[16]CLEGHORN C W,ENGELBRECHT A P,et al.Particle swarm variants:standardized convergence analysis[J].Swarm Intelligence,2015,9(2／3):1935-3812.
[17]DANTAS A F O D A,MAITELLI A L,et al.A Modified Matricial PSO Algorithm Applied to System Identification with Convergence Analysis[J].Journal of Control,Automation and Electrical Systems,2015,26(2):149-158.
[18]NING A P,ZHANG X Y.Convergence analysis of artificial bee colony algorithm [J].Control and Decision,2013,28(10):1554-1558.(in Chinese)
宁爱平,张雪英.人工蜂群算法的收敛性分析[J].控制与决策,2013,28(10):1554-1558.
[19]KONG X Y,LIU S Y,WANG Z.Almost sure convergence of artificial bee colony algorithm:martingale method[J].Computer Science,2015,42(9):246-248.(in Chinese)
孔翔宇,刘三阳,王贞.人工蜂群算法的几乎必然强收敛性:鞅方法[J].计算机科学,2015,42(9):246-248.
[20]ZHU G,KWONG S.Gbest-guided artificial bee colony algo- rithm for numerical function optimization[J].Applied Mathematics and Conference on Computation,2010,217(2):3166-3177.
[21]陈爱江,张文良.概率论与数理统计[M].北京:中国质检出版社,2011.

相关文章 15

[1]	刘凯祥, 谢永芳, 陈新, 吕飞, 刘俊矫. 基于DTMC的工业串行协议状态检测算法 Industrial Serial Protocol State Detection Algorithm Based on DTMC 计算机科学, 2022, 49(3): 301-307. https://doi.org/10.11896/jsjkx.210200078
[2]	石克翔, 保利勇, 丁洪伟, 官铮, 赵雷. 基于生成时间序列均匀优化的混沌人工蜂群算法 Chaos Artificial Bee Colony Algorithm Based on Homogenizing Optimization of Generated Time Series 计算机科学, 2021, 48(7): 270-280. https://doi.org/10.11896/jsjkx.200800087
[3]	吴培培, 吴兆贤, 唐文兵. 基于吸收态马尔可夫链的智能无人车系统实时性能分析 Real-time Performance Analysis of Intelligent Unmanned Vehicle System Based on Absorbing Markov Chain 计算机科学, 2021, 48(11A): 147-153. https://doi.org/10.11896/jsjkx.210300050
[4]	郑友莲, 雷德明, 郑巧仙. 求解高维多目标调度的新型人工蜂群算法 Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling 计算机科学, 2020, 47(7): 186-191. https://doi.org/10.11896/jsjkx.190600089
[5]	魏德宾,杨鹏,杨力,石怀峰. 一种基于卫星网络的虚拟网络功能快速映射算法 Virtual Network Function Fast Mapping Algorithm over Satellite Network 计算机科学, 2020, 47(3): 248-254. https://doi.org/10.11896/jsjkx.190300383
[6]	黄光球,陆秋琴. 保护区种群迁移动力学优化算法 Protected Zone-based Population Migration Dynamics Optimization Algorithm 计算机科学, 2020, 47(2): 186-194. https://doi.org/10.11896/jsjkx.181202338
[7]	郭佳. 基于改进的人工神经网络对存储系统性能进行预测的方法 Method of Predicting Performance of Storage System Based on Improved Artificial Neural Network 计算机科学, 2019, 46(6A): 52-55.
[8]	穆晓芳, 邓红霞, 李晓宾, 赵鹏. 基于人工蜂群算法的两阶段图像隐写分析算法 Two-phase Image Steganalysis Algorithm Based on Artificial Bee Colony Algorithm 计算机科学, 2019, 46(6): 174-179. https://doi.org/10.11896/j.issn.1002-137X.2019.06.026
[9]	马闻锴, 李贵, 李征宇, 韩子扬, 曹科研. 一种基于标签的Top-N个性化推荐算法 Top-N Personalized Recommendation Algorithm Based on Tag 计算机科学, 2019, 46(11A): 224-229.
[10]	袁培燕, 张豪. 一种面向移动机会网络的能效性路由算法 Energy Efficient Routing Algorithm in Mobile Opportunistic Networks 计算机科学, 2019, 46(11A): 387-392.
[11]	符晓. 云计算中基于共享机制和群体智能优化算法的任务调度方案 Task Scheduling Scheme Based on Sharing Mechanism and Swarm Intelligence Optimization Algorithm in Cloud Computing 计算机科学, 2018, 45(6A): 290-294.
[12]	范兴刚, 刘涛, 胡凤丹, 蒿翔. 一种延长目标覆盖网络寿命的群智能算法 Swarm Intelligence Algorithm for Prolonging Target Coverage Network Lifetime 计算机科学, 2018, 45(12): 86-91. https://doi.org/10.11896／j.issn.1002-137X.2018.12.013
[13]	刘志锋,陈凯,李雷,周从华. 一种多种攻击并发下的WSN生存性评估模型 Survivability Evaluation Model for Wireless Sensor Network under Multiple Attacks 计算机科学, 2017, 44(8): 129-133. https://doi.org/10.11896/j.issn.1002-137X.2017.08.023
[14]	杨华,张杭,张江,杨柳,李炯. 初始分离矩阵优化的在线盲源分离算法 Initial Separating-matrix Optimized Online Blind Source Separation Algorithm 计算机科学, 2016, 43(Z6): 265-267. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.063
[15]	邢熔华,黄海燕. 基于改进全局人工蜂群算法的WSN节点定位研究 Researches on Wireless Sensor Network Localization Based on Improved Gbest-guided Artificial Bee Colony Algorithm 计算机科学, 2016, 43(12): 273-276. https://doi.org/10.11896/j.issn.1002-137X.2016.12.050

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed