蜂群算法
来源:用户上传
作者: 乔舒杰
摘 要：蜂群算法是一种非数值优化计算方法，建立在蜜蜂自组织型与群体智能基础之上，是近几年比较热门的智能算法。本文主要介绍了蜂群算法的研究背景、基本原理、要素构成、算法流程和优缺点等现状，并对蜂群算法存在的问题进行了一些讨论，在此基础上提出了未来蜂群算法的发展方向。
关键词：蜂群算法；人工智能；现状；发展方向
中图分类号：TP18
蜂群算法（BCA），是一种非数值优化计算方法，以蜜蜂自组织型与群体智能基础上建立的。自1995年提出蜂群算法后，该算法引起了学者们的极大关注，并已在组合优化、网络路由、函数优化、机器人路径规划等领域获得了广泛应用。
1 基本原理
在自然界中，当蜜蜂蜂群发现优良蜜源（或花粉）时，它们会以一种跳舞方式传达发现的蜜源信息。这种舞蹈过程是：蜜蜂初次采集到花粉后，会在蜂巢上翩然起舞，舞蹈动线呈现“8”的字形，蜜蜂首先沿着直线爬行，随后再转向左，摇摆腹部，舞蹈动线的中轴线和地心引力的夹角表示的是蜜源方向和太阳夹角，此舞蹈也可称为“摇摆舞”。蜂群采蜜的集体智能行为由蜜源、采蜜蜂、待工蜂3个基本部分组成。
此外，蜂群的智能行为有引入搜索蜜源、为蜜源招募、放弃蜜源3种基本的行为模式。假如蜂群发现有两个密源A和B，在蜂巢的等工蜂没有收到关于蜂巢附近蜜源的信息的时候，它们有两种选择：一是在等工蜂根据观察到其它蜜蜂的摇摆舞后，它们被招募并开始按照获得的信息去寻找密源；二是等工蜂可作为侦察蜂，因蜂群内部激励行为或其他的可能因素，它们自发地搜寻蜂巢附近的密源。等工蜂若发现新的蜜源，蜜蜂依靠自身的记忆能力锁定蜜源地理位置，并迅速开始采蜜。所以，等工蜂变成采蜜蜜蜂，采蜜回到蜂箱后，它们有三种选择：一是放弃侦察到新蜜源，成为待工的跟随蜜蜂；二是跳“摇摆舞”招募蜂巢其它等工蜂，然后一起去蜜源采蜜；三是不招募其它的蜜蜂，继续去采蜜。
开始，蜂群的蜜蜂都是侦察蜂，没有任何先验知识，当它们搜索到蜜源后，即返回蜂巢的舞蹈区，根据蜜源收益度的相对大小，侦察蜂可以转变为上述任何一种蜜蜂，转变的原则有三种：一是当采集蜜源的收益度很低时，它再次成为侦察蜂去搜寻附近的蜜源；转变结果是放弃上次采集的蜜源。二是所采集蜜源的收益度排名小于临界值时，例如排名在后50%，它可以在观察完舞蹈后转变成为跟随蜜蜂，结果是前往相应的蜜源采蜜。三是所采集蜜源的收益度排名高于临界值时，它们转变为引领蜂，在舞蹈区招募更多的蜜蜂，其结果是带领招募的蜂群继续在同一蜜源采蜜。
2 要素构成
通过在上述中对蜂群算法的基本原理的介绍，可以看出蜂群算法是由3个基本要素构成：（1）蜜源。蜜源代表各种可能的解；蜜源值取决于多种因素，例如能量的大小和集中程度、提取该能量的容易程度、蜜源和蜂巢的接近度。考虑简单性，以数字量“收益度”来衡量蜜源的特点；（2）采蜜蜂。采蜜蜂与具体的蜜源紧密联系，这些蜜源是当前正在采集的。采蜜蜂携带了具体的蜜源信息，主要信息为蜜源与蜂巢的距离、蜜源的收益度、蜜源方向；采蜜蜂通过“摇摆舞”和其它蜜蜂分享蜜源信息，按照路径长度排序和蜜源的收益度，一定比例的成为引领蜂；（3）待工蜂。当采蜜蜂正在采集寻找蜜源时，按工作性质分为跟随蜂、侦察蜂。跟随蜂是在蜂巢内等待，通过分享采蜜蜂侦察到的信息，寻找合适的蜜源；侦察蜂是去搜索蜂巢附近的新蜜源。
3 优缺点
优点：（1）多角色分工机制。蜜蜂按照自己角色采用不同的方法搜索，并根据所得的解的蜜的质量自发的调整角色，以适应下一次搜索过程；（2）协同工作机制。蜜蜂在选择路径时，依据角色决定是否选用以前蜜蜂留下的信息和利用信息的方式，能以较大概率找到优化问题的最优解；（3）鲁棒性强。使用概率规则而不是确定性规则指导搜索，不必指导其它先验的信息，有极好的鲁棒性和广泛的适用性；（4）稳健性。即使个体失败，整个群体仍能完成任务；（5）易于与其它方法相结合。很容易与多种启发式算法结合，以改善算法的性能。
缺点：（1）限于局部最优解。从算法解的性质而言，蜂群算法是在寻找一个比较好的局部最优解，而不是强求是全局最优解；（2）工作过程的中间停滞问题。在算法工作过程当中那个，迭代到一定次数后，蜜蜂可能在某个或某些局部最优解的邻域附近发生停滞。（3）需要较长的搜索时间。虽然计算机计算速度的提高和蜂群算法的优化在一定程度上可以缓解这一问题，但是对于大规模优化问题，还是很大的障碍。
4 蜂群算法的应用
（1）函数优化。函数优化问题是对各种蜂群算法性能评测的常用算例，是蜂群算法的经典应用领域。根据群峰算法构造出各种复杂形势的测试函数，优化问题，用其他优化方法比较难求解，而蜂群算法可以方便地得到较好的结果；（2）组合优化。问题规模的扩大，组合优化问题的搜索空间急剧扩大。由于用枚举法在目前的计算机上很难或者不可能得到其准确最优解，对于这类复杂的问题，应把精力放在寻求其满意解上，而蜂群算法则是寻求这种满意解的最佳工具之一；（3）数据挖掘。数据挖掘数据库技术，即是从大型数据库中提取先前未知的、隐含的、有潜在应用价值的知识和规划。故此数据挖掘可比作是搜索问题，数据库可比作搜索空间，挖掘算法可比作搜索策略。所以，使用蜂群算法在数据库中进行搜索，对随机产生的一组规则进行优化从而可挖掘出隐含在数据库中的规则；（4）机器学习。基于蜂群算法的机器学习具备高级自适应系统所具备的学习能力，在很多领域中都得到了应用，特别是在分类器系统应用更为广泛；（5）图像处理和模式识别。图像处理和模式识别是计算机应用专业中视觉方面一个重要研究领域。在当前视觉应用领域主要是在图像压缩、图像恢复、图像分割、几何形状识别等方面得到了应用。
5 蜂群算法存在的局限性
蜂群算法的理论依据是源于对生物群落社会性的模拟，因此其相关数学分析还比较薄弱，导致了蜂群算法存在一些问题：（1）蜂群算法增加了时间复杂度。作为全局随机搜索算法，能够以一定的概率避免陷入局部最优。然而针对复杂空间的全局搜索，无法避免地增加了时间复杂度，耗费了大量时间；（2）蜂群算法的定量计算依据少。蜂群算法的数学理论基础相对薄弱，缺乏具备普遍意义的理论性分析，算法中涉及的各种参数设置一直没有确切的理论依据，大多是按照经验型方法确定，对具体问题和应用环境依赖性比较大，没有办法像其他智能算法一样定量计算；（3）蜂群算法的可靠性有待验证。蜂群算法同其它的自适应问题处理方法一样，蜂群算法也不具备绝对的可信性，处理突发事件，系统的反应是不可测的，一定程度上增加了应用风险；（4）蜂群算法和其它群智能方法与先进技术的融合还不足。
6 研究方向
蜂群算法的思维方法，其在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了良好基础。已研究验证过的蜂群算法理论及应用研究证明蜂群算法是一种能够解决大多数优化问题的新思维方法，且蜂群算法潜在的并行性和分布式特点，其为处理大量的以数据库形式存在的数据提供了技术基础。从理论研究还及应用研究的不同角度分析，蜂群算法理论及应用研究都是具有重要学术意义和现实应用价值的一种理论。
蜂群算法未来的研究方向：（1）为了更好、更快的找到问题的最优解，在算法进行全局搜索的过程中，针对要解决的实际问题，加入局部搜索算法也是很好的思想。利用算法的全局性搜索防止陷入局部最优，利用局部搜索来加快算法的收敛速度，降低时间复杂度，在下一步研究中应该去解决如何更好地将二者完美的结合；（2）目前，蜂群算法理论研究现状是还在基本思想的描述摸索阶段，若能够取得比较大的研究发现，需要提出一些较为明确的思维方法和严格定义，且还必须总结出构造一些蜂群算法应用的规则，并以此为基础建立及开发有实用价值的一些基于蜂群理论的算法和方法；（3）加快蜂群算法领域对概念进行严格定义，使蜂群算法有坚实地科学性和可信性，当处理突发事件时候，使系统的反应是可测的，这样就会在一定程度上减少其应用的风险；（4）蜂群算法还是刚起步，对她的应用还不多，与其它智能算法和先进的技术融合的还不够好，未来还有很大的发展空间，将蜂群算法更多地与启发式算法相结合将会得到更好的应用。
参考文献：
[1]葛宇，梁静，王学平.求解函数优化问题的改进的人工蜂群算法[J].计算机科学，2013（08）.
作者简介：乔舒杰，男，山东淄博人，计算机软件工程（嵌入式）专业。
作者单位：华东师范大学 软件学院，上海 200062
转载注明来源:https://www.xzbu.com/8/view-6472963.htm
