人工蜂群算法的应用

-1-人工蜂群算法的应用【摘要】人工蜂群算法（ABC）是建立在蜜蜂自组织型和群体智能基础上的一种非数值优化计算方法。自1995年提出蜂群算法后，该算法引起了学者们的极大关注，并已在组合优化、网络路由、函数优化、机器人路径规划等领域获得了广泛应用。本文首先介绍了蜂群算法的研究背景、基本原理、要素构成、算法流程和优缺点，然后，介绍蜂群算法在实际中的应用，并且最后用Matlab实现人工蜂群算法对Griewank函数的优化，最后，本文对蜂群算法领域存在的问题进行了总结，并提出了未来蜂群算法的研究方向。【关键词】人工蜂群算法；函数优化；Matlab；研究方向一、研究背景群体智能（SwarmIntelligence）是指具有简单智能的个体通过相互协作和组织表现出群体智能行为的特性，具有天然的分布式和自组织特征，在没有集中控制且不提供全局模型的前提下表现出了明显的优势。虽然目前针对群体智能的研究还处于初级阶段，且存在许多困难，但群体智能的研究代表了计算机研究发展的一个重要方向。2005年Karaboga成功地将蜜蜂采蜜原理应用于函数的数值优化，并提出比较系统的人工蜂群算法（ArtificialBeeColonyAlgorithm，简称ABC算法）。目前，关于ABC算法研究与应用还处于初级阶段，但由于其控制参数少、易于实现、计算简洁、鲁棒性强等特点，已成为群体智能领域的研究热点之一，被越来越多的学者所关注。二、基本原理自然界中的蜂群总是能自如发现优良蜜源（或花粉）。VonFrisch研究揭示蜜蜂以跳舞的方式来传达蜜源的信息。采集到花粉的蜜蜂，返回后在蜂巢上翩然起舞；蜜蜂沿直线爬行，然后再转向左这一种舞蹈，其动线呈“8”字形，并摇摆其腹部，舞蹈的中轴线与地心引力的夹角正好表示蜜源的方向和太阳的夹角。这种舞被称为“摇摆舞”，蜂群实现采蜜的集体智能行为包含3个基本-2-部分：蜜源、采蜜蜂EF、待工蜂UF。此外引入3种基本的行为模式：搜索蜜源、为蜜源招募和放弃蜜源。蜂群采蜜工作图见图1.1。图1.1蜜蜂采蜜工作图模仿蜂群的算法原理(1)食物源初始化初始化时，随机生成SN个可行解（等于雇佣蜂的数量）并计算适应度函数值。随机产生可行解的公式如下：式中，xi(i=1,2,...,SN)为D维向量，D为优化参数的个数，j∈{1,2,…,D}。(2)新蜜源的更新搜索蜜蜂记录自己到目前为止的最优值，并在当前蜜源邻域内展开搜索，基本ABC在蜜源附近搜索新蜜源的公式为:-3-式中，j∈{1,2,…,D}，k∈{1,2,…,SN}，k为随机生成且k≠i，为[-1,1]之间的随机数。(3)跟随蜂选择引领蜂跟随蜂选择引领蜂的概率公式：式中，fit(xi)为第i个解的适应值对应蜜源的丰富程度。蜜源越丰富，被跟随蜂选择的概率越大。(4)产生侦查蜂当某蜜源迭代limit次没有改进时，便放弃该蜜源,并且将该蜜源记录在禁忌表中,同时该蜜源对应的雇用蜂转变为侦察蜂按式(1)随机产生一个新的位置代替原蜜源。基本ABC算法的流程为：•1:根据式(1)初始化种群解xi，i=1,…,SN•2:计算种群中各个蜜蜂的适应值•3:cycle=1•4:repeat•5:雇佣蜂根据(2)产生新的解vi并计算适应值•6:雇佣蜂根据贪心策略选择蜜源•7:根据(3)式计算选择蜜源xi的概率Pi•8:跟随蜂根据概率Pi选择蜜源xi，根据(2)式在该蜜源附近产生新的蜜源vi，并计算新蜜源vi的适应值•9:跟随蜂根据贪心策略选择蜜源•10:决定是否存在需要放弃的蜜源，如果存在，根据(1)式随机产生一个蜜源替代它•11:记录最优解•12:cycle=cycle+1•13:untilcycle=MCN-4-三、人工蜂群算法在函数优化中的应用函数优化：函数优化问题是蜂群算法的经典应用领域，也是对各种蜂群算法性能评测的常用算例。很多人构造出了各种各样的复杂形势的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有单峰函数也有多峰函数等。而对于这些函数优化问题，用其他优化方法较难求解，蜂群算法却可以方便地得到较好的结果。下图是用Matlab实现ABC算法对Griewank函数的优化所得到的误差随着迭代次数增加的变化曲线：由上图可以看出，ABC算法对Griewank函数的优化前期的收敛速度较快，而在后期就陷入了局部最优，此时的算法出现了停滞现象直到最大迭代次数。所以ABC算法能够对函数实现一定程度的优化。四、算法的优缺点优点（1）多角色分工机制。蜜蜂按照自己角色采用不同的方法搜索，并根据所得的解的质量自发的调整角色，以适应下一次搜索过程。-5-（2）协同工作机制。蜜蜂在选择路径时，依据角色决定是否选用以前蜜蜂留下的信息和利用信息的方式，能以较大概率找到优化问题的最优解。（3）鲁棒性强。使用概率规则而不是确定性规则指导搜索，不必指导其它先验的信息，有极好的鲁棒性和广泛的适用性。（4）稳健性。即使个体失败，整个群体仍能完成任务。（5）易于与其它方法相结合。很容易与多种启发式算法结合，以改善算法的性能。缺点（1）限于局部最优解。从算法解的性质而言，蜂群算法是在寻找一个比较好的局部最优解，而不是强求是全局最优解。（2）工作过程的中间停滞问题。在算法工作过程当中那个，迭代到一定次数后，蜜蜂可能在某个或某些局部最优解的邻域附近发生停滞。（3）需要较长的搜索时间。虽然计算机计算速度的提高和蜂群算法的优化在一定程度上可以缓解这一问题，但是对于大规模优化问题，还是很大的障碍。参考文献[1]李峰磊,丁海军.蜂群算法的研究与应用[D].南京:河海大学,2008.[2]康飞,李俊杰,许青,等.改进人工蜂群算法及其在反演分析中的应用[J].水电能源科学,2009,27(1):126-129.[3]吴迪，崔荣一．蜂群遗传算法[C]／／中国人工智能学会第11届全国学术年会论文集．北京：北京邮电大学出版社，2005：733～736．[4]李瑞明,程八一.基于人工蜂群算法求解不同尺寸工件单机批调度问题[J].四川大学学报,2009,46(3):657-662.[5]郑伟，刘静，曾建潮.人工蜂群算法及其在组合优化中的应用研究，31(06):467-471,2010.[6]胡珂，李迅波，王振林，改进的人工蜂群算法性能，计算机应用，31(04):1108-1110,2011.[7]胡中华,赵敏.基于人工蜂群算法的机器人路径规划[J].电焊机,39(4):93–96,2009.-6-[8]丁海军，冯庆娴，基于boltzmann选择策略的人工蜂群算法，计算机工程与应用,45(31):53-55,2009.[9]袁浩，基于改进蜂群算法无线传感器感知节点部署优化，计算机应用研究,27(07):2704-2708,2010.[10]王兴伟，邹荣珠，黄敏，一种基于蜂群算法的ABC支持型QoS组播路由机制，计算机科学,36(06):47-52,2009.