基于错位突变策略的改进人工蜂群算法

蒋 成1，汪继文2，邱剑锋1

（1.安徽大学 计算机科学与技术学院；2.安徽大学 计算智能与信号处理教育部重点实验室,安徽 合肥 230601）

摘 要：人工蜂群算法是一种模拟蜜蜂觅食行为的群智能优化算法，具有较好的全局搜索能力，但收敛速度较慢且容易陷入局部最优.针对其不足之处,提出了一种基于错位突变策略的人工蜂群算法（DMABC）.该算法在搜索蜜源的时候运用错位突变策略增强种群多样性，并使用排序选择机制和新的比较机制防止过早收敛.通过对几个标准测试函数的实验表明，改进算法具有更快的收敛速度，优化精度更高.

教育期刊网 http://www.jyqkw.com
关键词 ：人工蜂群算法；错位突变；排序选择；种群多样性；函数优化

中图分类号：TP39.6 文献标识码：A 文章编号：1673-260X（2015）01-0016-05

1 引言

群智能算法是一类模拟自然界中某些动物群体行为的智能优化算法.模拟的动物群体通常包括蚁群、鸟群和蜂群等等.这些动物群体都有一个共同的特点：当我们仅仅观察群体中的单个个体，往往是简单而杂乱无章的；但当这些个体合作形成群体的时候却可以完成复杂的任务，表现出一定的智能.比较著名的群智能算法有蚁群算法[1,2]、粒子群算法[3,4]以及蜂群算法等等.蚁群算法主要是模拟蚂蚁通过信息素搜索最佳路径.粒子群算法是模拟鸟类的集群活动.蜂群算法则是模拟蜂群寻找最佳蜜源的行为.和传统优化算法相比，这些新型的群智能优化算法收敛速度更快且易于实现，因此也引起了了很多研究者的兴趣.

人工蜂群算法是由Karaboga[5]在2005年首次提出的.该算法将蜂群分成引领蜂、跟随蜂和侦察蜂三类.不同类别的蜜蜂通过交换彼此的信息来完成觅食的任务.由于人工蜂群算法的优化效果不错，而且操作简单、控制参数少，算法提出后备受研究者们的关注.人工蜂群算法在函数优化、生产调度、神经网络以及机器人路径规划等领域得到了广泛的应用.Karaboga和Gorkemli[6]将人工蜂群算法应用于旅行商问题中.Ozturk[7]等使用了人工蜂群算法解决无线传感器网络的动态部署问题.胡中华等[8]实现了将人工蜂群算法应用于机器人路径规划问题.肖永豪等[9]提出了一种基于蜂群算法的图像边缘检测方法.

然而随着对人工蜂群算法研究的深入，人们发现该算法同样存在着缺点：算法收敛速度较慢，且容易陷入局部最优.针对这些缺点，国内外的学者们相继提出了改进的人工蜂群算法.丁海军等[10]基于Boltzmann选择机制提出了一种改进的人工蜂群算法用来优化多变量函数.暴励等[11]结合差分进化算法提出了一种新的双种群差分蜂群算法.Lee等[12]在人工蜂群算法中引入群体多样性的机制，根据群体多样性的门槛值选择采用不同的搜索公式.Alam等[13]提出了一种基于指数分布的自适应变异步长机制的人工蜂群算法，动态控制搜索过程中的探索和开发能力.

在人工蜂群算法中，全局搜索和局部开采的平衡是决定算法性能好坏的关键.本文在基本人工蜂群算法的基础上，借鉴差分进化算法的突变算子，提出了一种新型的错位突变策略，应用于蜜蜂的搜索过程中，以提高种群的多样性.同时，还用排序选择机制代替了原来的轮盘赌选择机制来防止算法的过早收敛.为了测试改进算法的性能，本文用了几个标准测试函数来做实验.实验结果表明，改进算法的性能优于基本人工蜂群算法.

2 基本人工蜂群算法

Karaboga提出的基本人工蜂群算法将蜜蜂分为三类：引领蜂、跟随蜂和观察蜂.蜂群在一个D维的空间中寻找蜜源，这里的D是在算法开始时人为设定的，在函数优化问题中D就等于目标函数的变量数.一个蜜源对应目标函数的一个可行解.在算法中，蜜源用它在D维空间的位置向量表示.例如，第i个蜜源用i表示，i=(xi1,xi2,…,xiD)，向量中每个分量的取值范围由目标函数的解空间决定.寻找最优蜜源，在本文中也就是寻找一组能让目标函数取得最小值的可行解.

蜂群分成两半，一半是引领蜂，一半是跟随蜂.引领蜂和蜜源一一对应，每个引领蜂的位置就是一个蜜源的位置.因此，在程序中，引领蜂的数目、跟随蜂的数目和蜜源的数目都相等，设为SN,则种群的规模也就是2*SN.SN也是一个需要人工设定的参数.整个算法是一个循环算法.每次循环的开始，引领蜂会在各自对应的蜜源周围进行搜索.搜索的公式如下：

其中，?渍(i,j)是-1到1的随机数，k是引领蜂 随机选择的一个邻近蜜源，作为扰动项，增强全局搜索能力.引领蜂搜索的时候只改变位置向量的一个分量，这个要被改变的分量也是随机选择出来的.通过(2)式得到一个新的蜜源位置后，引领蜂会对新蜜源进行评估，计算出适应度值与旧蜜源比较.适应度的计算公式如下：

fi是用第i个蜜源的位置向量作为可行解计算出来的目标函数值.从(3)式可以看出，目标函数值越小，该蜜源的适应度值就越大.引领蜂经过比较后，如果新蜜源的适应度值大于旧蜜源，则更新蜜源的位置；反之，则保留旧蜜源.跟随蜂则通过轮盘赌机制选择蜜源进行搜索.适应度值越高的蜜源会有更大概率被跟随蜂选中从而得到更新.跟随蜂的搜索方程与引领蜂相同.轮盘赌的选择概率使用下面的公式计算出来的：

由于人工蜂群算法有陷入局部最优的可能，因此算法中设置了侦察蜂的操作来跳出局部最优.当一个蜜源经过很多次循环仍无法得到更新，那么该蜜源对应的引领蜂就会转化为侦察蜂，舍弃旧蜜源，在搜索空间内随机生成一个新的蜜源.侦察蜂的搜索公式如下：

lj和uj分别是搜索空间的下界和上界，rand(0,1)是0到1的随机值.侦察蜂操作的触发条件是有蜜源的停滞次数达到了限定值，姑且将这个限定值设为limit.limit的值是需要人工设定的.大量的实验表明，limit的设定会影响到算法的效果，定值太小会减缓收敛速度，定值太大又起不到跳出局部最优的效果.后来研究者们发现，将limit的值设为SN*D可以得到不错的实验效果，因此本文中limit的值也是SN*D.除此之外，还有一个最大循环次数 需要人工设定，这是算法的终止条件.

3 基于错位突变策略的人工蜂群算法

基本人工蜂群算法在搜索蜜源的时候，由于其搜索方向是随机的，因此具有较好的全局搜索能力.但正因为它的搜索完全随机，没有任何启发式的引导，不能利用上一代的搜索信息，导致算法在测试单峰函数时收敛速度很慢.为了提高人工蜂群算法的收敛速度，加强局部搜索能力，首先，本文采用了错位突变策略对蜜蜂的搜索公式进行改进.既加快了优化单峰函数时的收敛速度，也能在优化多峰函数时仍保持较好的全局搜索能力.其次，基本人工蜂群算法在比较蜜源的好坏时用的衡量标准是适应度值，而根据(3)式计算适应度值会出现“大数吃小数”的情况导致后期无法准确比较蜜源好坏.因此，本文将直接通过比较函数值大小来评估蜜源以避免出现上述情况.最后，轮盘赌选择机制在适应度值相差较大的时候，只选较好蜜源而让差蜜源迟迟得不到更新，破坏了种群的多样性.本文使用排序选择机制代替轮盘赌，让蜜源被跟随蜂选中的概率只与该蜜源的序号有关，从而差的蜜源也有被选中的机会.下面是对改进之处的详细介绍.

3.1 错位突变策略

在人工蜂群算法的改进算法中，将差分进化算法与人工蜂群算法融合是一种很有效的办法.差分进化算法是一种启发式的优化算法，它和遗传算法类似，也具有交叉、选择和突变的操作.其中，差分进化算法的突变操作和人工蜂群算法中的蜜蜂搜索操作很相似.在文献[14]中，作者借鉴差分进化算法的突变策略，将人工蜂群算法的搜索公式改成：

其中，best是指当前所有蜜源中的最优蜜源，r1和r2都是随机选择的临近蜜源，且best≠r1≠r2.由于新的搜索公式引入了全局最优的蜜源作为引导，不再像基本人工蜂群算法中那样盲目搜索，改进算法在单峰函数上的收敛速度明显提高.但正因为最优蜜源向导的加入，蜜蜂都往最优蜜源区域探索，削弱了种群的多样性，导致改进算法在多峰函数上的优化效果并不令人满意.为了保持种群的多样性，本文将公式(6)当中的最优蜜源向导改成随机临近蜜源向导.

另外，原来的突变策略只是在同一维上进行启发式的突变.通过观察大量的实验数据，可以发现在算法运行的后期，同一维度上的数据非常相近甚至雷同，这样的话同位突变的效果甚微.为了增强突变的效果，本文借鉴了文献[15]中的错位交叉算子，将公式(6)的同位突变改为错位突变.新的搜索公式如下：

其中，j1和j2都是随机生成的，且j1≠j2.公式(7)相比公式(6)，不再一味地向最优蜜源探索，保护了种群多样性，同时错位突变的策略的加入可以更有效地利用其它维上的有利信息.

3.2 新的比较机制

在基本人工蜂群算法中，评估蜜源好坏的方法是比较它们的适应度值.然而，通过(3)式计算出来的适应度值有时候并不能真实的反映出蜜源的好坏.通过对基本人工蜂群算法的大量实验，我们发现当函数值被优化到非常接近0的时候，用公式(3)计算会出现“大数吃小数”的情况.两个数量级有差别但都非常接近0的函数值通过(3)式计算得到的适应度值都是1.这样的话，即使找到了更小的函数值也无法进行更新.为了避免这样的情况发生，本文直接采用比较函数值来评价蜜源.

3.3 排序选择机制

基本人工蜂群算法的轮盘赌选择机制使跟随蜂更偏向于适应度高的蜜源.一旦出现超长个体，其适应度值远高于其他个体，跟随蜂很难通过轮盘赌选到较差的个体，这样很容易陷入局部最优导致过早收敛.为了克服这一缺点，本文采用了文献[16]提出的排序选择机制.引领蜂操作完成后，算法将根据所有蜜源对应的函数值排序，函数值越小的排序越靠前，序号也就越小.排序过后，每个蜜源被跟随蜂选中的概率用公式(8)计算.

其中，d(t)是随着循环次数变化的自适应参数.它的作用是保护种群多样性，不让蜜源选择概率之间的差距过大.

3.4 算法的详细步骤

（1）初始化：随机生成SN个蜜源，计算出各蜜源的函数值，记录最优蜜源的函数值以及解向量；

（2）引领蜂根据式(7)搜索新蜜源，若新蜜源更好，则更新；反之，保留旧蜜源，该蜜源停滞次数加一.

（3）对所有蜜源进行排序，函数值最小的序号为1，依次往后排到SN.

（4）根据式(8)计算出各蜜源被跟随蜂选中的概率.

（5）跟随蜂按照上面算出的概率选择蜜源，搜索方式与引领蜂相同.

（6）选出本轮循环最优蜜源，与之前记录的全局最优蜜源比较，若本轮更好，则更新全局最优蜜源；反之，无操作.

（7）检查是否有蜜源的停滞次数达到limit.若有，则舍弃该蜜源，用式(5)生成新蜜源，计算出函数值.

（8）判断是否达到最大循环次数Maxcycles.若达到，则终止；反之，返回第2步.

4 仿真实验及结果分析

本文的实验是将改进的算法应用于函数优化以测试其性能.选取的测试函数是5个常用的标准测试函数，见表1，其中UM代表单峰函数，MM代表多峰函数.

实验前需要设置初始的参数.最大循环次数 为2000，种群规模为20(SN=10)，解空间的维数 为10，limit的值等于SN*D也就是100.将基本ABC算法和改进的DMABC算法分别运行30次，结果的对比见表2.

表2中，Best是指30次结果中最好的结果，Worst是指最差的结果，Mean是30次结果的平均值.Std则是30次结果的标准偏差，其值越接近0表示算法越稳定.从表2可以看出，在单峰函数的优化上，DMABC比基本ABC的优化精度有大幅度提升；多峰函数优化方面，Ackley函数两者效果差不多，而在Griewank函数和Rastrigin函数上DMABC都达到了理论最优值.除了最终的优化结果，收敛速度也是评判算法性能的标准之一.图1中展示了基本ABC算法和DMABC算法的收敛速度对比.

从图1中，可以看出，DMABC的收敛速度明显优于基本ABC.为了进一步测试DMABC的性能，本文还将DMABC和其他的ABC改进算法进行对比，初始参数与表2一致.选择的ABC改进算法为基于DE差分进化算法的ABC/current_to_best以及基于反向轮盘赌机制的MABC算法，实验的参数设置与之前一致.种群规模为20，维数为10，limit为100，最大循环次数为2000.实验结果见表3.

从表3可以看出，与其他ABC改进算法相比，DMABC在Sphere函数和Griewank函数上表现最

好，其他函数也有较好表现.综合来看，DMABC算法在函数优化方面表现不错，具有一定的实用性.

5 结论

针对基本人工蜂群算法收敛速度较慢、容易陷入局部最优的缺点，本文借鉴差分进化算法的突变策略，在蜜蜂搜索过程中引入了错位突变策略，并改进了基本人工蜂群算法的比较机制和选择机制.通过对5个基准函数的测试，证明改进的DMABC算法在收敛速度和结果精度上均优于基本ABC算法.笔者下一步准备将DMABC算法应用于实际问题中，例如TSP问题、调度问题等等.

——————————

教育期刊网 http://www.jyqkw.com
参考文献：

〔1〕Colorni A, Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies[A]. Proc of European Conf on Artificial Life[C].Paris,1991:134-142.

〔2〕Dorigo M, Maniezzo V, Colorni A. The ant system: optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B(S1083-4419),1996,26(1):29-41.

〔3〕Fukuyama Y. Fundamentals of particle swarm techniques [A]. Lee K Y, EI-Sharkawi M A. Modern Heuristic Optimization Techniques With Applications to Power Systems [M].IEEE Power Engineering Society,2002:45-51.

〔4〕Eberhart R C, Shi Y. Particle swarm optimization: developments, applications and resources [A]. Proceedings of the IEEE Congress on Evolutionary Computation [C]. Piscataway, NJ: IEEE Service Center,2001: 81-86.

〔5〕Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Kayseri: Engineering Faculty Computer Engineering Department, Ereiyes University,2005.

〔6〕Karaboga D, Gorkemli B. A combinatorial artificial bee colony algorithm for travelling salesman problem [C]. International Symposium on Innovations in Intelligent Systems and Applications, Istanbul,2011:50-53.

〔7〕Ozturk C, Karaboga D, Gorkemli B. Probabilistic dynamic deployment of wireless sensor networksby artificial bee colony algorithm[J].Sensors, 2011,11(6):6056-6065.

〔8〕胡中华,赵敏.基于人工蜂群算法的机器人路径规划[J].电焊机，2009，39(4)：93-96.

〔9〕肖永豪，余卫宇.基于蜂群算法的图像边缘检测[J].计算机应用研究，2010，27(7):2748-2750.

〔10〕丁海军，冯庆娴.基于boltzmann选择策略的人工蜂群算法[J].计算机工程与应用，2009，45(1)：53-55.

〔11〕暴励，曾建潮.一种双种群差分蜂群算法[J].控制理论与应用，2011，28(2):266-272.

〔12〕Lee W P, CAI W T. A novel artificial bee colony algorithm with diversity strategy[C]. The 2011 7th International Cofnference on Natural Computation, Shanghai, 2011:1441-1444.

〔13〕Alam M S, Uikabir M W, Islam M M. Self-adaption of mutation step size in artificial bee colony algorithm for continuous function optimization[C]. The 2010 13th International Conference on Computer and Information Technology, Dhaka, Bangladesh, 2010:69-74.

〔14〕Gao W F, Liu S Y. Improved artificial bee colony algorithm for global optimization. Information Process Letters[J]. 2011,111(17):871-882.

〔15〕陈国龙，陈火旺，郭文忠，等.基于随机错位算术交叉的遗传算法及其应用[J].模式识别与人工智能，2014,17(2):250-256.

〔16〕Bao L, Zeng J C. Comparison and analysis of the selection mechanism in the artificial bee colony algorithm[C]. The 9th Int Conf on Hybrid Intelligent Systems. Shenyang: IEEE Press,2009:411-416.