简单描述蜜蜂寻找食物源的过程:
一群小蜜蜂来到一个陌生的环境,要采蜜,怎么破?比方先派出三只蜜蜂a,b, c出去转一圈,咦,运气不错,三只都找到了蜜源A,B,C,然后这三只蜜蜂飞回来了,告诉其他在蜂巢的蜜蜂关于蜜源的有关信息,(注:蜜蜂通过摆动尾巴来实现“告诉”这个动作,蜜源的有关信息包括距离蜂巢远近,采集难度等等,用收益率(profitability)来表示),蜂巢中的其他小蜜蜂一看他们三个带回来的信息,心中自有了判断,有些觉得A不错,然后a带着这些蜜蜂去A蜜源了,同理,b,c带着一些蜜蜂去了B,C。当然也有别的情况,比方说,蜜蜂a出去转了一圈后,没找到蜜源或者蜜源觉得不合格,他回来告诉大家,你们别跟我去了,我还得再找找。这里涉及到了蜜蜂的不同角色的变换,相关资料都会有解释,这个不做重点。
现在开始:
1、ABC模型 有3个基本元素,雇佣蜂,非雇佣蜂,食物源。2种行为引导方式,一、食物源不错,因为招来更多的蜜蜂(正反馈),二、就是食物源不好,蜜蜂放弃找到的食物源(负反馈)。
2、人工蜂群包含3种类型的蜜蜂,雇佣蜂(Employed Bees)、跟随蜂(Onlooker Bees)、侦查蜂(Scout Bees),其中,跟随蜂和侦查蜂一起被称为非雇佣蜂。
雇佣蜂:跟特定的食物源打交道,一个雇佣蜂对应一个食物源。
跟随蜂:观察雇佣蜂的舞蹈来选择食物源
侦查蜂:随机寻找食物源。
3、在ABC算法中,其实要做的工作就是全局优化问题(global optimization)。
食物源的位置 对应着一个问题的解;
寻找食物源的过程 对应 最优解的过程;
食物源的好坏 对应着解的质量(适应度,Fitness)
4、ABC算法的设计模式:初始化;
进入循环:
雇佣蜂;
跟随蜂;
侦查蜂;
保留当前最好的解;
满足某条件,退出循环。
4.1初始化阶段
初始化所有的食物源向量Xm|(排版的问题,用|表示向量)(m=1,2...SN,SN代表多少个食物源)。由于每个食物源Xm|就是一个解向量,每个解向量含有n个变量,(Xmi,m=1,2...SN, i=1,2...n)所以,就简单了,目的就是最小化目标函数(minimize the objective function)。
用下列公式进行初始化:
其中,Ui和li 分别是Xmi的最大最小边界值。
4.2雇佣蜂阶段
雇佣蜂在已有的食物源Xm|附近继续寻找新的食物源Vm|,当找到一个食物源之后,估计该食物源的适应度(好坏程度),如何找新的食物源Vm|,公式如下:
其中Xk|是个随机选取的食物源,i也是随机选取的,ϕ是个介于[-a,a]的随机数。选出新的食物源之后,计算该食物源
的适应度,利用greedy selection在新旧食物源进行选择。
适应度计算公式,如下:
其中,fm是解向量Xm的目标函数,(适应度函数由目标函数变换而成,不解释!)
4.3跟随蜂阶段
跟随蜂根据雇佣蜂带回蜂巢的信息,从而选择心仪的食物源。在ABC算法中,跟随蜂根据雇佣蜂找到的食物源的适应度来进行选择。如何根据适应度进行选择呢,这里有个常用的方法:轮盘赌!
跟随蜂选择某个食物源的概率Pm,使用如下公式进行计算:
跟随蜂选取好食物源之后,使用公式6在确定个相邻的食物源Vm|,然后计算他的适应度。正如在雇佣蜂阶段所述,使用greedy selection在新旧食物源进行选择。从而,更多的跟随蜂被招募进来,并且有了更好的正反馈。
4.4 侦查蜂阶段
如果说雇佣蜂带来的食物源不是太好,那么该食物源就需要被扔掉(abandonment),在此,雇佣蜂摇身一变成为侦查蜂,接着出去找食物源!仍然是一头扎进花丛中,随机地找!比方说,食物源Xm|被扔掉后,侦查蜂(之前还称呼为雇佣蜂)找到一个新的食物源Vm|。这样,一开始找到的不好的食物源就能够被放弃,这就形成了负反馈,正好跟正反馈组成个平衡。