一种改进的人工蜂群算法研究

来源:用户上传      作者:

　　摘  要： 针对人工蜂群算法在更新策略中精度与稳定性不高的问题，提出一种改进的人工蜂群算法。该改进的人工蜂群算法通过增加每次更新维度的个数来改善算法的精度，在文中所选择的每次更新维度的个数为可行解维数的[12];同时，该算法选择当前适应值最优的蜂蜜源在其周围进行邻域搜索，避免了由于随机性而带来的算法精度降低问题。最后，比较改进的人工蜂群算法与经典的粒子群算法，通过多个高维测试函数的仿真实验表明，改进的人工蜂群算法比粒子群算法具有更高的精度和稳定性，展现了更好的性能。
　　关键词： 人工蜂群算法; 算法改进; 数据分析; 更新维度; 领域搜索; 仿真实验
　　中图分类号： TN919?34                             文献标识码： A                      文章编号： 1004?373X（2020）12?0133?05
　　Abstract： In allusion to the problem that the artificial bee colony algorithm has low accuracy and stability in the update strategy， an improved artificial bee colony algorithm is proposed. The accuracy of the algorithm is improved by increasing the number of dimensions per update， and the selected number of dimensions per update is half of the feasible solution dimensions in this paper; the honeycomb source with the best adaptive value is chosen to conduct a neighbourhood search around it， which avoids the reducing the accuracy of the algorithm caused by the randomness. The simulation results with multi high?dimensional testing functions show that， in comparison with the classical particle swarm optimization algorithm， the improved artificial bee colony algorithm has a higher accuracy and stability， and show better performance.
　　Keywords： artificial bee colony algorithm; algorithm improvement; data analysis; update dimension; area search; simulation experiment
　　0  引 言
　　人工蜂群算法（ABC）通过模仿蜜蜂觅食时群体之间的相互作用求得最优解，是一种有效的单目标问题的解决方案。该算法在2005年由Karaboga首次提出，有三种类型的蜜蜂参与人工蜂群算法[1]，分别是雇佣蜂、跟随蜂和侦察蜂。它们参与不同的搜索过程。雇佣蜂多次通过邻域搜索在特定范围内锁定蜜源的位置，并通过摇摆舞的方式将食物的相关信息传递给跟随蜂[2]。摇摆舞中包含的信息有食物的数量和与蜂窝之间的间距等信息。蜜蜂觅食过程如图1所示，在ABC中，雇佣蜂的数量与食物位置数量相同，即食物与雇佣蜂是一一对应的。每个蜜源位置坐标即代表优化问题的解坐标。蜜源的数量对应的是蜜源的适应值。蜜源数量越大，可行解的适应值越小（单目标最小化优化问题），可行解质量越高。当雇佣蜂多次位置未更新时，说明该位置陷入了局部最优值，雇佣蜂变为侦察蜂，通过局部搜索确定新蜜源位置[3]。跟随蜂依据各个雇佣蜂所供给的关于食物的信息，按照比例与概率选择蜜源，概率越大，代表食物越多，在各个跟随蜂选定相应雇佣蜂之后，执行邻域搜索，确定蜜源位置。在重复循环多次上述步骤之后，跟随蜂中适应值最小食物源位置就是优化问题的最优可行解[4]。
　　现阶段，已有许多文献对人工蜂群算法的改进和应用进行了研究。文献[5]将人工蜂群算法与前馈人工神经网络（FF?ABC）相结合，用于混凝土中氯化物的渗透预测。文献[6]针对柔性生产线的问题，提出了一种基于帕累托的人工蜂群算法（PGABC）。该算法可以得到具有三种不同导向机构的帕累托近似最优解。文献[7]提出了一种多目标人工蜂群算法，该算法集成了两种性能增强方案，首次解决了负载平衡和传输延迟的网络编码问题。在Khan的研究论文中，采用更新规则和k?opt操作对人工蜂群算法进行了改进，解决了旅行商问题[8]。Choong在人工蜂群算法中应用了一种超启发式方法，即改进了选择函数（MCF），该算法可以自动调节雇佣蜂和跟随蜂的邻域搜索选择[9]。文献[10]针对蒸汽驱注方案的优化问題，提出了一种基于改进人工蜂群算法的蒸汽驱注方案优化方法。文献[11]基于子空间分解（ISD）和人工蜂群（ABC）算法，提出了一种称为ISD?ABC的带选择技术，解决了HSI分类中维数减少的问题。
　　1  人工蜂群算法 　　在人工蜂群算法（ABC）中，人工蜂群包含三种类别的蜜蜂。它们分别是雇佣蜂、跟随蜂和观察蜂。其中雇佣蜂和跟随蜂的数量相同，并且分别占蜂群总数的[12]。每个雇佣蜂对应一个蜂蜜源，这些雇佣蜂的主要工作是寻找并记录与之对应的蜂蜜源。然后将蜂蜜源的相关信息通过圆摆舞的方式传递给跟随蜂，跟随蜂就根据这些信息来选择蜂蜜源[12]。当雇佣蜂对应的蜂蜜源的位置多次未改变，雇佣蜂变为观察蜂，通过局部搜索确定新蜂蜜源的位置[13?15]。
　　在该算法中，每个蜂蜜源位置坐标表示一个可行解。本文给出了每个蜂蜜源的适应值[fit（i）]，该值用于评估每个蜂蜜源的花蜜量[16]。在算法每一次循环中，雇佣蜂都通过邻域搜索寻找每个蜂蜜源，并计算每个蜂蜜源对应的适应值。根据雇佣蜂传递的信息（即每个蜂蜜源的适应值），跟随蜂通过一定的概率来选择蜂蜜源，并在选择的蜂蜜源周围寻找新的蜂蜜源，并计算它们的适应值[17?19]。
　　这种学习策略使得雇佣蜂和跟随蜂在当前最优的蜂蜜源周围进行邻域搜索，提高了搜索的精度，并且每次的搜索过程是多维度的，提高了搜索的速度。图3是改进的人工蜂群算法在每一个维度上的潜在搜索空间。
　　3  仿真实验分析
　　3.1  测试函数
　　为了测试改进ABC算法的求解精度与收敛速度[20?21]，采用5个标准测试函数：Sphere函数、Rosenbrock 函数、Rastrigin函数、Griewank 函数和Ackley 函数，并与粒子群算法（PSO）进行了比较。
　　3.1.6  PSO算法
　　粒子群优化算法（PSO）是一种进化计算技术（Evolutionary Computation），1995 年由Eberhart和Kennedy提出，源于对鸟群捕食的行为研究。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。
　　3.2  实验结果
　　在仿真实验中，为了保证结果的公平与有效性，对改进的ABC算法与PSO算法进行了初值的设置，其中，蜂群数量与粒子群数量大小均设置为100，算法的运算次数均为50次。每次算法执行中，循环的次数均设置为1 500次。在这两种算法中就5个测试函数分别运行50次后，求平均值得到了改进的ABC算法与PSO算法在50维空间与100维空间的数据结果如表1和表2所示。
　　表1、表2中，均值分别代表两种算法就每个函数运行50次后的平均水平，且能最大程度地降低偶然误差的影响，因此将均值作为两种算法的评价指标，并将该结果数字在表中加粗。均值越接近理论值，则代表该算法的优化效果越好。根据表中的数据可知，在50维和100维的空间中，对于Sphere，Rosenbrock，Rastrigin，Griewank和Ackley 函数的优化结果，改进的ABC算法较PSO算法更接近理论值。由此可见，改进的ABC算法有更好的求解精度。
　　5个测试函数的仿真曲线如图4～图8所示。根据图4 ～图8运行结果可知，对于Sphere 函数，改进的ABC算法在大约第250次循环时达到1，PSO算法在大约第100次循环时稳定到1.5;对于Rosenbrock 函数，改进的ABC算法在大约第500次循环时稳定在160，PSO算法在大约第100次循环时稳定到200;对于Rastrigin 函数，改进的ABC算法在大约第500次循环时达到80，PSO算法在大约第100次循环时稳定到200;对于Griewank 函数，改进的ABC算法在大约第500次循环时达到0.01，PSO算法在大约第100次循环时稳定到0.025;对于Ackley 函数，改进的ABC算法在大约第400次循环时达到0.5，PSO算法在大约第50次循环时稳定到2。由此可见，改进的ABC算法较PSO算法展示了更好的求解精度与稳定性，但在收敛效果方面略有不足，这也是以后有待于改进的地方。
　　4  结  语
　　为了解决这个问题，本文提出了一个改进的人工蜂群算法。通过增加每次更新的维度个数来改善算法的稳定性，并且选择当前适应值最优的蜂蜜源周围进行邻域搜索来提高算法的精度，但在收敛速度方面存在不足，有待于进一步改善。总之本文将所提出的算法与粒子群算法在高维空间进行比较，通过多组测试函数的仿真表明所提出的算法具有较好的性能。
　　参考文献
　　[1] KIRAN M S， HAKLI H， GUNDUZ M， et al. Artificial bee colony algorithm with variable search strategy for continuous optimization [J]. Information sciences， 2015， 300： 140?157.
　　[2] 梁静，葛宇，冉晓娟，等.一种人工蜂群算法改进方案[J].计算机应用研究，2015，32（11）：3295?3299.
　　[3] ZHU G P， KWONG S. Gbest?guided artificial bee colony algorithm for numerical function optimization [J]. Applied mathematics & computation， 2010（7）： 3166?3173.
　　[4] 林小军，叶东毅.一种带规范知识引导的改进人工蜂群算法[J].模式识别与人工智能，2013，26（3）：307?314.
　　[5] MEYSAM N， NADER G， MEHDI N. Modeling chloride penetration in self?consolidating concrete using artificial neural network combined with artificial bee colony algorithm [J]. Journal of building engineering， 2019， 22： 216?226. 　　[6] YUE L， GUAN Z L， ZHANG L， et al. Multi?objective lotsizing and scheduling with material constraints in flexible parallel lines using a Pareto based guided artificial bee colony algorithm [J]. Computers & industrial engineering， 2018（16）： 659?680.
　　[7] XING H L， SONG F H， YAN L S， et al. On multicast routing with network coding： a multiobjective artificial bee colony algorithm [J]. China communication， 2019， 16（2）： 170?186.
　　[8] KHAN I， MAITI M K. A swap sequence based Artificial Bee Colony algorithm for traveling salesman problem [J]. Swarm and evolutionary computation， 2019， 44： 428?438.
　　[9] CHOONG S S， WONG L P， LIM C P. An artificial bee colony algorithm with a modified choice function for the traveling salesman problem [J]. Swarm and evolutionary computation， 2019， 44： 622?635.
　　[10] NI H M， LIU Y J， FAN Y C. Optimization of injection scheme to maximizing cumulative oil steam ratio based on improved artificial bee colony algorithm [J]. Journal of petroleum science and engineering， 2019， 173： 371?380.
　　[11] XIE F D， LI F F， LEI C K， et al. Unsupervised band selection based on artificial bee colony algorithm for hyper?spectral image classification [J]. Applied soft computing， 2019， 75： 428?440.
　　[12] 李华，卢静.改进人工蜂群算法的无线传感器网络覆盖优化[J].现代电子技术，2018，41（3）：14?18.
　　[13] MUSTAFA Servet Kiran， HUSEYIN Hakli， MESUT Gunduz， et al. Artificial bee colony algorithm with variable search strategy for continuous optimization [J]. Information sciences， 2015， 300： 140?157.
　　[14] 田屏.一种基于混沌搜索改进的人工蜂群算法[J].西南师范大学学报（自然科学版），2018，43（7）：39?45.
　　[15] 刘晓芳，柳培忠，骆炎民，等.一种增强局部搜索能力的改进人工蜂群算法[J].智能系统学报，2017，12（5）：684?693.
　　[16] MARJAN Mernik， SHIH Hsi Liu， DERVIS Karaboga， et al. On clarifying misconceptions when comparing variants of the artificial bee colony algorithm by offering a new implementation [J]. Information sciences， 2015， 291： 115?127.
　　[17] XUE Yu， JIANG Jiongming， ZHAO Binping， et al. Aself?adaptive  artificial bee colony algorithm  based on  global best for global optimization [J]. Soft computing， 2017（8）： 1?18.
　　[18] 王继超，李擎，崔家瑞，等.一种改进的人工蜂群算法：粒子蜂群算法[J].工程科学学报，2018，40（7）：871?881.
　　[19] LIN Qinzhen， ZHU Miaomiao， LI Genghui， et al. A novel artificial bee colony algorithm with local and global information interaction [J]. Applied soft computing journal， 2018， 62： 702?735.
　　[20] 杨慧婷，杨文忠，殷亚博，等.基于深度信念网络的K?means 聚类算法研究[J].现代电子技术，2019，42（8）：145?150.
　　[21] 张志强，鲁晓锋，孙钦东，等.一种增强开发能力的改进人工蜂群算法研究[J].计算机应用，2018（12）：1?9.
转载注明来源:https://www.xzbu.com/8/view-15248442.htm