人工蜂群算法的研究综述

鲍韦韦，刘 婷，邹 康，张立毅，王金海

(1.天津工业大学电子与信息工程学院，天津 300387;2.天津大学电子信息工程学院，天津 300072;3.天津商业大学信息工程学院，天津 300134)

群体智能(Swarm Intelligence)是指具有简单智能的个体通过相互协作和组织表现出群体智能行为的特性，具有天然的分布式和自组织特征［1］，在没有集中控制且不提供全局模型的前提下表现出了明显的优势。虽然目前针对群体智能的研究还处于初级阶段，且存在许多困难，但群体智能的研究代表了计算机研究发展的一个重要方向。

2005 年Karaboga D［2］成功地将蜜蜂采蜜原理应用于函数的数值优化，并提出比较系统的人工蜂群算法(Artificial Bee Colony Algorithm，简称ABC算法)。目前，关于ABC算法研究与应用还处于初级阶段，但由于其控制参数少、易于实现、计算简洁、鲁棒性强等特点［3］，已成为群体智能领域的研究热点之一，被越来越多的学者所关注。

1 基本ABC算法的基本原理

ABC算法模拟蜂群采蜜过程，通过不同角色蜜蜂间的交流、转换和协作来实现群体智能。人工蜂群中有三种角色:引领蜂、跟随蜂和侦察蜂。假设有SN个食物源，每个食物源xi=|xij|(i=1，2，…，SN，j=1，2，…，D)是一个D 维向量，设置蜜蜂总的循环搜索次数为MCN。引领蜂首先对相应的食物源进行一次邻域搜索，再采用贪婪原则选择食物源，即如果新搜索到的食物源的收益度(即花蜜数量)优于以前的，则用新食物源位置代替旧食物源位置，否则保持旧食物源位置不变。所有引领蜂完成搜索之后，回到舞蹈区把食物源信息通过跳摇摆舞传达给跟随蜂。跟随蜂根据得到的信息按照概率选择食物源。收益度越高的食物源，被选择的概率越大。跟随蜂选中食物源后，也进行一次邻域搜索，并保留收益度较高的食物源。ABC算法就是通过如此重复搜索，最终来找到收益度最高的食物源。

ABC算法在求解优化问题时，食物源的位置代表优化问题的可行解，食物源的收益度代表优化问题的适应度值，人工蜂群搜索最大收益度食物源的过程代表寻找最优解的过程，最大收益度食物源代表优化问题的最优解。

初始化时，通过式(1)随机产生SN个解。

其中，(xij)max和(xij)min是xij的上、下限;rand为(0，1)之间的一个随机数。

引领蜂和跟随蜂依据式(2)进行解的更新

其中，vij代表在xij附近产生的一个新解，k∈{1，2，…，SN}，k和j 都是随机选取，k是i 邻域的一个解，所以k 不能等于i;rij∈［－1，1］是随机数，它控制xij邻域的生成范围。

跟随蜂对解的选择是通过观察引领蜂的摇摆舞来判断解的适应度值，并依据选择概率大小来选择跟随哪个引领蜂。适应度值fiti和选择概率pi计算公式如下:

其中，fi是第i个解的目标函数值。

在ABC算法中，还有一个控制参数limit，用来记录某个解被更新的次数。假定某个解连续limit 次循环之后没有得到改善，表明这个解陷入局部最优，就要被放弃。假设被放弃的解是xi，通过式(1)随机产生一个新解来代替原来解xi。

2 ABC算法的改进

2.1 初始解的改进

初始解是算法进行搜索的起点，基本ABC算法的初始解是随机生成，如果初始解不够合理，对算法的性能有很大影响，有必要对初始解的生成方法进行改进。为了使初始解具有多样性，均匀分布在搜索空间，丁海军等［4］提出了小区间生成法初始化解，保证了初始群体含有较丰富的解，增强了搜索收敛于全局最优点的可能。暴励等［5］采用反向学习的方法产生初始解，将有助于效率的提高与解质量的改善。罗钧等［6］利用混沌具有随机性、遍历性、初始条件敏感性等特点，提出使用混沌序列初始化解，提高了解的多样性和搜索的遍历性。解决约束优化问题时，为了确保所有解在ABC算法中的可行性和多样性，Bolaji A.L 等［7］提出使用回溯算法产生可行的初始解。

2.2 选择策略的改进

在基本ABC算法中，跟随蜂按轮盘赌方式选择解，易导致解多样性的下降，算法过早收敛。搜索最优解的过程中，不同阶段需要不同的选择压力，这样可以保持解的多样性和加快最优解的收敛速度。为了动态调整搜索最优解过程中的选择压力，丁海军等［4］在分析现有蜂群算法搜索机制特点的基础上，将模拟退火算法中的Bolzmann 选择策略引入到人工蜂群算法中。为了避免适应度跨度过大的问题，同时可动态调整选择压力，步登辉等［8］采用排序选择方式进行指数拉伸。

2.3 解更新公式的改进

基本ABC算法解更新公式中，rij是一个［－1，1］之间的随机数，Alam M.S 等［9］提出为rij找到一个合适的缩放因子，使之能够动态自适应地改变步长，更好地搜索最优解。为了克服基本ABC算法本身随机性大的缺陷，胡珂等［10］利用不同解适应度值大小差异来引导优化方向。在搜索后期，解非常接近最优解甚至在有效位数内都是相同的，因此解更新公式后加上一个摄动因子，通过搜索后期的局部微调，提高进化的收敛速度。基本ABC算法的解更新公式并没有采用任何对比信息，这很有可能导致算法的局部搜索能力差。王慧颖［11］将全局最优解和个体极值的信息引入到引领蜂的搜索模式中进一步提高算法的局部搜索能力，而且增加了异步变化学习因子，用于调整蜜蜂自身经验和社会群体经验在整个寻优过程中所起的作用。

2.4 与其它算法相结合

ABC算法由于存在局部收敛问题，在复杂问题中往往很难得到满意解。为了解决此不足，可以与其它算法相结合形成混合算法。

ABC算法是单维更新算法，会导致单维与单维更新之间的矛盾，其主要原因在于解的各维之间单独更新，缺乏信息交流。El－Abd M［12］将粒子群算法整体更新的思想融入蜂群算法，在蜂群算法的单维更新公式中加入全局信息的影响。步登辉等［9］在单维更新之后加入基于整体更新的试探机制，并且依据单维更新成功率动态调整单维和整体更新的比重。罗钧等［13］借鉴遗传算法中组合交叉和变异思想，提出了一种基于遗传交叉因子的改进蜂群优化算法，通过采用交叉因子产生出新的解集，增加解的多样性，跳出局部最优，更快搜索到问题的全局最优解。禁忌搜索算法的禁忌策略是利用禁忌表存储已经搜索到的局部最优解并进行标记，避免在以后搜索过程中再搜索到这些解，以此来跳出局部最优点。罗钧等［14］借鉴禁忌策略提出了一种具有禁忌策略的蜂群算法。此外，学者还提出把模拟退火算法、差分进化算法等与ABC算法相结合，改善算法性能。

3 ABC算法的应用

由于ABC算法控制参数少、易于实现、计算简洁、收敛速度快、全局搜索能力强等优点，在一些领域中得到了很好的应用。目前，ABC算法的应用可以分为以下几个方面:连续函数优化问题、车辆路径问题、作业车间调度问题、人工神经网络训练等。

4 总结与展望

ABC是一种基于群体智能的新兴进化算法，目前对其研究尚处于初期阶段，已有的研究成果还相当分散，许多问题有待于进一步研究。未来的研究方向主要有以下几个方面:ABC算法基础理论的研究、与其它算法相结合的混合算法研究、ABC算法应用研究等。

［1］E.Bonabeau，M.Dorigo，G.Theraulaz.Swarm Intelligence:Fromnatural to Artificial Systems［M］.New York:Oxford University Press，1999:40－58.

［2］D.Karaboga.An Idea Based on Honey Bee Swarm for Numerical Optimization［R］.Technical Report－ TR06，Erciyes University，2005.

［3］S.Bitam，M.Batouche and E.Talbi.A Survey on Bee Colony Algorithms［C］.2011 IEEE International Symposium on Parallel ＆ Distributed Processing，Workshops and PhdForum，2010:1－8.

［4］丁海军，冯庆娴.基于boltzmann 选择策略的人工蜂群算法［J］.计算机工程与应用，2009，45(31):53－55.

［5］暴励，曾建潮.一种双种群差分蜂群算法［J］.控制理论与应用，2011，28(2):266－272.

［6］罗钧，李研.具有混沌搜索策略的蜂群优化算法［J］.控制与决策，2010，25(12):1913－1916.

［7］A.L.Bolaji，A.T.Khader，M.A.Al－betar et al.An Improved Artificial Bee Colony for Course Timetabling［C］.2011 Sixth International Conference on Bio－ Inspired Computing:Theories Applications.IEEE Press，2011:9－14.

［8］步登辉，李景.基于动态整体更新和试探机制的蜂群算法［J］.计算机应用研究，2011，28(7):2508－2511.

［9］M.S.Alam ，M.W.Kabir and M.M.Islam.Self－adaptation of Mutation Step Size in Artificial Bee Colony Algorithm for Continuous Function Optimization［C］.201013th International Conference on Computer and Information Technology，2010:69－74.

［10］胡珂，李迅波，王振林.改进的人工蜂群算法性能［J］.计算机应用，2011，31(4):1107－1110.

［11］王慧颖，刘建军，王全洲.改进的人工蜂群算法在函数优化问题中的应用［J］.计算机工程与应用，2011，7(13).

［12］M.El-Abd.A Hybrid ABC-SPSO Algorithm for Cintinuous Function Optimization［C］.2011 IEEE Symposium on Swarm Intelligence，2011:1－6.

［13］罗钧，樊鹏程.基于遗传交叉因子的改进蜂群优化算法［J］.计算机应用研究，2009，26(10):3716－3717，3753.

［14］罗钧，卢嘉江，陈伟民，等.具有禁忌策略的蜂群算法评定圆柱度误差［J］.重庆大学学报，2009，32(12):1482－148.