人工蜂群算法详解(附代码下载)

原创
09/15 20:03
阅读数 4.2K

一个由蜂群行为启发的算法!

本文主要内容:

  • 什么是人工蜂群算法?
  • 蜜蜂的采蜜机制
  • 蜂群算法的原理及流程
  • 小结

1. 什么是人工蜂群算法?

人工蜂群算法是模仿蜜蜂行为提出的一种优化方法,是集群智能思想的一个具体应用,它的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,通过各人工蜂个体的局部寻优行为,最终在群体中使全局最优值突现出来,有着较快的收敛速度。为了解决多变量函数优化问题,Karaboga提出了人工蜂群算法ABC模型(artificial bee colony algorithm)。

人工蜂群算法属于群智能算法的一种,其受启发于蜜蜂的寻蜜和采蜜过程,相比于常见的启发式算法,它的优点在于其使用了较少的控制参数,并且鲁棒性强,在每次迭代过程中都会进行全局和局部的最优解搜索,因此能够找到最优解的概率大大增加。

相比于遗传算法来说,人工蜂群算法在局部的收敛和寻优能力上要更为出色,不会出现遗传算法的“早熟”现象,并且算法的复杂度也较低。但由于遗传算法有交叉以及变异的操作,因此遗传算法在全局最优值的搜索上要优于人工蜂群算法。此外,人工蜂群算法适用于进行连续函数的全局优化问题,而不适用于一些离散函数。

2. 蜜蜂的采蜜机制

蜜蜂具有群智能应必备的两个条件:自组织性和分工合作性。虽然单个蜜蜂的行为很简单,但是由单个蜜蜂所组成的群体却能够表现出极其复杂的行为,它们可以在任何复杂的环境下以很高的效率从花朵中采集花蜜,同时还能够很快的适应环境的改变。

任务分工

人工蜂群算法就是模拟蜜蜂的采蜜过程而提出的一种新型智能优化算法,它也是由食物源、雇佣蜂和非雇佣蜂三部分组成。

食物源:食物源即为蜜源。在任何一个优化问题中,问题的可行解都是以一定形式给出的。在人工蜂群算法中,食物源就是待求优化问题的可行解,是人工蜂群算法中所要处理的基本对象。食物源的优劣即可行解的好坏是用蜜源花蜜量的大小即适应度来评价的。

雇佣蜂:雇佣蜂即为引领蜂(采蜜蜂)与食物源的位置相对应,一个食物源对应一个引领蜂。在人工蜂群算法中,食物源的个数与引领蜂的个数相等;引领蜂的任务是发现食物源信息并以一定的概率与跟随蜂分享;概率的计算即为人工蜂群算法中的选择策略,一般是根据适应度值以轮盘赌的方法计算。

非雇佣蜂:非雇佣蜂包括跟随蜂(观察蜂)和侦査蜂跟随蜂在蜂巢的招募区内根据引领蜂提供的蜜源信息来选择食物源,而侦查蜂是在蜂巢附近寻找新的食物源。在人工蜂群算法中,跟随蜂依据引领蜂传递的信息,在食物源附近搜索新食物源,并进行贪婪选择。若一个食物源在经过次后仍未被更新,则此引领蜂变成侦査蜂,侦查蜂寻找新的食物源代替原来的食物源。

采蜜机制

在蜜蜂群体智能形成的过程中,蜜蜂之间的信息交流是最重要的环节,而舞蹈区是蜂巢中最重要的信息交换地。采蜜蜂在舞蹈区通过跳摇摆舞与其他蜜蜂共同分享食物源的信息,观察蜂则是通过采蜜蜂所跳的摇摆舞来获得当前食物源的信息的,所以,观察蜂要以最小的资源耗费来选择到哪个食物源采蜜。因此,蜜蜂被招募到某个食物源的概率与食物源的收益率成正比。

初始时刻,蜜蜂的搜索不受任何先验知识的决定,是完全随机的。此时的蜜蜂有以下两种选择:

  • 它转变成为侦察蜂,并且由于一些内部动机或可能的外部环境自发地在蜂巢附近搜索食物源;
  • 在观看了摇摆舞之后,它可能被招募到某个食物源,并且开始开采食物源。

在蜜蜂确定食物源后,它们利用自己本身的存储能力来记忆位置信息并开始采集花蜜。此时,蜜蜂将转变为“雇佣蜂”。蜜蜂在食物源处采集完花蜜,回到蜂巢并卸下花蜜后有如下选择:

  • 放弃食物源成为非雇佣蜂;
  • 跳摇摆舞为所对应的食物源招募更多的蜜蜂,然后回到食物源采蜜;
  • 继续在同一食物源采蜜而不进行招募。

蜜蜂在采蜜时所表现出来的这种自组织性和合理分配性主要由其自身的基本性质所决定的,它们所特有的基本性质如下:

  • 正反馈性:食物源的花蜜量与食物源被选择的可能性成正比;
  • 负反馈性:蜜蜂停止对较差食物源的开采过程;
  • 波动性:在某个食物源被放弃时,随机搜索一个食物源替代原食物源;
  • 互动性:蜜蜂在舞蹈区与其他蜜蜂共同分享食物源的相关信息。

3. 蜂群算法的原理及流程

标准的ABC算法通过模拟实际蜜蜂的采蜜机制将人工蜂群分为3类: 采蜜蜂、观察蜂和侦察蜂。整个蜂群的目标是寻找花蜜量最大的蜜源。在标准的ABC算法中,采蜜蜂利用先前的蜜源信息寻找新的蜜源并与观察蜂分享蜜源信息;观察蜂在蜂房中等待并依据采蜜蜂分享的信息寻找新的蜜源;侦查蜂的任务是寻找一个新的有价值的蜜源,它们在蜂房附近随机地寻找蜜源。

算法原理

假设问题的解空间是D维的,采蜜蜂与观察蜂的个数都是SN,采蜜蜂的个数或观察蜂的个数与蜜源的数量相等。则标准的ABC算法将优化问题的求解过程看成是在D维搜索空间中进行搜索。每个蜜源的位置代表问题的一个可能解,蜜源的花蜜量对应于相应的解的适应度。一个采蜜蜂与一个蜜源是相对应的。与第i个蜜源相对应的采蜜蜂依据如下公式寻找新的蜜源:

其中, , 是区间上[-1,1]的随机数, 。标准的ABC算法将新生成的可能解与原来的解作比较:

并采用贪婪选择策略保留较好的解。每一个观察蜂依据概率选择一个蜜源,概率公式为:

其中 是可能解 的适应值。对于被选择的蜜源,观察蜂根据上面概率公式搜寻新的可能解。当所有的采蜜蜂和观察蜂都搜索完整个搜索空间时,如果一个蜜源的适应值在给定的步骤内(定义为控制参数limit) 没有被提高, 则丢弃该蜜源,而与该蜜源相对应的采蜜蜂变成侦查蜂,侦查蜂通过以下公式搜索新的可能解。其中,

其中,r是区间[0,1]上的随机数, 是第d维的下界和上界。

算法流程

人工蜂群算法具体实现步骤:

  1. 初始化种群解
  2. 计算种群中各个蜜蜂的适应值;
  3. 重复一下步骤,知道满足终止条件:
  4. 采蜜蜂根据 (1)产生新的解 并计算适应值;
  5. 采蜜蜂根据贪心策略选择蜜源;
  6. 根据 (2)式计算选择蜜源 的概率
  7. 观察蜂根据概率 选择蜜源 ,根据 (3)式在该蜜源附近产生新的蜜源 ,并计算新蜜源 的适应值;
  8. 观察蜂根据贪心策略选择蜜源;
  9. 决定是否存在需要放弃的蜜源,如果存在,则随机产生一个蜜源替代它;
  10. 记录最优解直至满足终止条件输出最优解;

4.小结

在人工蜂群算法的基础上,还发展出了许多混合算法,如基于量子分布的人工蜂群算法,禁忌搜索-蜂群混合优化算法,模拟退火-蜂群混合优化算法,基于copula分布估计的改进人工蜂群算法等,它们都是针对蜜蜂在寻找新蜜源的过程中来进行基本人工蜂群算法的优化。

在应用中,人工蜂群算法的复杂度较低,因此如果目标函数满足连续或近似连续条件,那么可以优先考虑人工蜂群算法。在编写算法时,可以考虑使用遗传算法中的交叉操作来找到全局中其他的最优解来避免陷入局部最优。

点个赞再走呗

[智能算法]公众号回复“ 蜂群代码”即可下载相关代码。

本文分享自微信公众号 - 智能算法(AI_Algorithm)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
1
2 收藏
分享
加载中
更多评论
打赏
0 评论
2 收藏
1
分享
在线直播报名
返回顶部
顶部