人工蜂群算法详解讲解学习.ppt

《人工蜂群算法详解讲解学习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工蜂群算法详解一、蜜蜂采蜜机理蜜蜂是一种群居昆虫，虽然单个昆虫的行为极其简单，但是由单个简单的个体所组成的群体却表现出极其复杂的行为。真实的蜜蜂种群能够在任何环境下，以极高的效率从食物源（花朵）中采集花蜜；同时，它们能适应环境的改变。蜂群产生群体智慧的最小搜索模型包含基本的三个组成要素：食物源、被雇佣的蜜蜂（employedforagers）和未被雇佣的蜜蜂（unemployedforagers）；两种最为基本的行为模型：为食物源招募（recruit）蜜蜂和放弃（abandon）某个食物源。一、蜜蜂采蜜机理(1)食物源：食物源的价值由多方面的因素决

2、定，如：它离蜂巢的远近，包含花蜜的丰富程度和获得花蜜的难易程度。使用单一的参数，食物源的“收益率”（profitability），来代表以上各个因素。(2)被雇用的蜜蜂：也称引领蜂（Leader），其与所采集的食物源一一对应。引领蜂储存有某一个食物源的相关信息（相对于蜂巢的距离、方向、食物源的丰富程度等）并且将这些信息以一定的概率与其他蜜蜂分享。(3)未被雇用的蜜蜂：其主要任务是寻找和开采食物源。有两种未被雇用的蜜蜂：侦查蜂（Scouter）和跟随蜂（Follower）。侦察蜂搜索蜂巢附近的新食物源；跟随蜂等在蜂巢里面并通过与引领蜂分享相关信息找到食

3、物源。一般情况下，侦察蜂的平均数目是蜂群的5%-20%。一、蜜蜂采蜜机理（4）舞蹈区：在群体智慧的形成过程中，蜜蜂间交换信息是最为重要的一环。舞蹈区是蜂巢中最为重要的信息交换地。蜜蜂的舞蹈叫做摇摆舞。食物源的信息在舞蹈区通过摇摆舞的形式与其他蜜蜂共享，引领蜂通过摇摆舞的持续时间等来表现食物源的收益率，故跟随蜂可以观察到大量的舞蹈并依据收益率来选择到哪个食物源采蜜。收益率与食物源被选择的可能性成正比。因而，蜜蜂被招募到某一个食物源的概率与食物源的收益率成正比。初始时刻，蜜蜂以侦察蜂的身份搜索。其搜索可以由系统提供的先验知识决定，也可以完全随机。经过一轮

4、侦查后，若蜜蜂找到食物源，蜜蜂利用它本身的存储能力记录位置信息并开始采蜜。此时，蜜蜂将成为“被雇用者”。蜜蜂在食物源采蜜后回到蜂巢卸下蜂蜜然后将有如下选择：(1)放弃食物源而成为非雇佣蜂。(2)跳摇摆舞为所对应的食物源招募更多的蜜蜂，然后回到食物源采蜜。(3)继续在同一个食物源采蜜而不进行招募。对于非雇佣蜂有如下选择：(1)转变成为侦察蜂并搜索蜂巢附近的食物源。其搜索可以由先验知识决定，也可以完全随机。(2)在观察完摇摆舞后被雇用成为跟随蜂，开始搜索对应食物源邻域并采蜜。二、蜜蜂采蜜过程三、ABC算法原理在基本ABC算法中，人工蜂群包含3种个体：雇佣

5、蜂、观察蜂和侦查蜂。每个雇佣蜂对应一个确定的食物源（解向量）并在迭代中对蜜源的邻域进行搜索。根据蜜源丰富程度（适应值的大小）采用轮盘赌的方式雇佣观察蜂采蜜（搜索新蜜源）如果蜜源多次更新没有改进，则放弃该蜜源，雇佣蜂转为侦查蜂随机搜索新蜜源。蜂群采蜜行为待求解问题食物源位置可行解食物源质量适应度采蜜速度收敛速度食物源质量最大值（最大收益度）最优解1.蜜源初始化初始化时，随机生成SN个可行解（等于雇佣蜂的数量）并计算适应度函数值。随机产生可行解的公式如下：(1)式中，xi(i=1,2,...,SN)为D维向量，D为优化参数的个数，j∈{1,2,…,D}。

6、2.新蜜源的更新搜索公式蜜蜂记录自己到目前为止的最优值，并在当前蜜源邻域内展开搜索，基本ABC在蜜源附近搜索新蜜源的公式为:（2）式中，j∈{1,2,…,D}，k∈{1,2,…,SN}，k为随机生成且k≠i，φik为[-1,1]之间的随机数。3.观察蜂选择雇佣蜂的概率式中，fit(xi)为第i个解的适应值对应蜜源的丰富程度。蜜源越丰富，被观察蜂选择的概率越大。4.侦察蜂的产生为防止算法陷入局部最优，当某蜜源迭代limit次没有改进时，便放弃该蜜源,并且将该蜜源记录在禁忌表中,同时该蜜源对应的雇用蜂转变为侦察蜂按式(1)随机产生一个新的位置代替原蜜源。

7、四、基本ABC算法的流程1:根据式(1)初始化种群解xi，i=1,…,SN2:计算种群中各个蜜蜂的适应值3:cycle=14:repeat5:雇佣蜂根据(2)产生新的解vi并计算适应值6:雇佣蜂根据贪心策略选择蜜源7:根据(3)式计算选择蜜源xi的概率Pi8:观察蜂根据概率Pi选择蜜源xi，根据(2)式在该蜜源附近产生新的蜜源vi，并计算新蜜源vi的适应值9:观察蜂根据贪心策略选择蜜源10:决定是否存在需要放弃的蜜源，如果存在，根据(1)式随机产生一个蜜源替代它11:记录最优解12:cycle=cycle+113:untilcycle=MCN所有城市

8、的任一种排列即是问题的一个解，解空间由若干解构成，因此初始化解空间就是随机产生多个不同的城市序列。以n个城市