第5章 蜂群算法基本理论

5.1蜂群算法的概述5.1.1蜂群算法的概念5.1.2蜂群算法的的发展5.1.3蜂群算法的特点5.1.4蜂群算法的分类5.2蜂群算法的基本原理5.2.1基于蜜蜂繁殖行为的蜂群算法5.2.2基于蜜蜂采蜜行为的蜂群算法5.3蜂群算法的应用5.4蜂群算法的研究方向第5章蜂群算法基本理论5.1蜂群算法概述5.1.1蜂群算法的概念蜂群算法是一种模仿蜜蜂繁殖、采蜜等行为的新兴群智能优化算法。5.1蜂群算法概述5.1.2蜂群算法的发展人工蜂群算法于2005年由土耳其学者D.Karaboga系统提出。萌芽阶段1946年，德国生物学家K.V.Frisch破译了蜜蜂采蜜时跳舞所蕴含的信息，并因此获得1973年诺贝尔生理学奖。1995年，美国CornellUniversity（康奈尔大学）的T.D.Seeley提出蜂群的自组织模型。2001年，H.A.Abbass提出了蜜蜂婚配优化（MatingOptimization，MBO）算法，用于解决可满足性问题。2001年，P.Lucic等针对蜜蜂行为建模，并提出一种基于蜂群采蜜行为的蜜蜂系统（BeeSystem，BS）。5.1蜂群算法的概述5.1.2蜂群算法的发展发展阶段2005年，土耳其埃尔吉耶斯大学的DervisKaraboga在T.D.Seeley蜂群自组织模型的基础上，系统提出了人工蜂群算法（ArtificialBeeColony，简称ABC），并将其应用于数值优化领域。2006年又扩展到约束性数值优化领域。此后，国内外学者针对基本蜂群算法提出了多种改进算法，并应用于不同领域。目前，蜂群算法的研究还处于不断探索与改进的阶段。5.1蜂群算法的概述5.1.3蜂群算法的特点蜂群算法的优点①全局性：蜂群算法在搜索过程中不易陷入局部极值点，即使在非连续和含有噪声的情况下，也能以较大概率收敛到最优解或满意解，具有很强的容噪能力。②并行性和高效性：蜂群算法具有大范围全局搜索和并行性等特点，适用于并行计算，因而执行效率高。③鲁棒性：鲁棒性强意味着蜂群算法的搜索以群体为基本单元，不受初始选择的影响，不因实例的不同而蜕变；同时对于一个相同问题，在不同的多次运行中能够得到相同结果，在解的质量上没有很大差异。这已被许多数值所证实。5.1蜂群算法的概述④普适性和易扩性：蜂群算法是一种弱方法，它采用自然进化机制来表示复杂现象，对函数的形态无要求，可解决多种优化搜索问题。针对不同实例，只需适当调整算子参数等，进行很小修改即可适应新的问题，程序能够通用，这是现行的其他大多数优化方法所做不到的。⑤简明性：蜂群算法的基本思想简单明了，实现步骤通俗易懂。5.1蜂群算法的概述5.1.4蜂群算法的分类按照机理不同，蜂群算法分为两类：受婚配行为启发的蜜蜂婚配优化算法，也称为基于蜜蜂繁殖机理的蜂群算法。受采蜜行为启发的蜜蜂采蜜优化算法。另外，还有模拟蜂王繁殖行为的蜂王进化算法，模拟蜜蜂躲避障碍物的蜜蜂躲避算法，模拟蜂群任务分配行为的可用于服务器动态分配的分散蜜蜂算法，等等。5.1蜂群算法的概述5.2蜂群算法的基本原理5.2.1基于蜜蜂繁殖行为的蜂群算法生物学机理一个完整的蜂巢一般由一只蜂王、上千的雄蜂、10000~60000工蜂和幼蜂组成。这三种蜂分工明确，各司其职。蜂王是蜂群中唯一具有生殖能力的雌蜂，主要任务是与不同的雄蜂进行交配与产卵；雄蜂是整个蜂群的父亲和警卫，主要任务是和蜂王交配繁殖后代；工蜂主要负责清洁、哺育、筑巢、守卫和采蜜等各项工作。5.2蜂群算法的基本原理5.2蜂群算法的基本原理蜂王的求偶过程称为婚飞。蜂王在空中起舞就标志着婚飞的开始，一群雄蜂追随其后。蜂王选择其中一只雄蜂进行空中交配，每次可以与7~20只雄蜂交配，直至纳满精子飞回蜂巢产卵。为了避免近亲繁殖，蜂王有时会寻找其他蜂群的雄蜂交配。刚开始交配时，蜂王飞行速度很快，每交配一次，蜂王的飞行速度有所衰减。当蜂王衰弱到一定程度时，则由成熟且胜任的幼蜂替代，即产生新一代蜂王，此时结束原蜂王的生命周期。蜂群繁殖进化过程也是蜂王不断更新的过程，如图5-1所示。其实，新蜂王的产生类似于进化计算中的一个优化过程，蜂王是优化过程中待求解问题的最优解。5.2蜂群算法的基本原理图5-1蜂群繁殖优化过程示意图5.2蜂群算法的基本原理基本原理Step1：蜂群初始化。首先确定种群的大小，然后分别运用构造启发式算法NEH和随机产生两种方式产生初始种群。初始化完成后，通过比较所有的种群个体，按适应度值从大到小排序。排第一位的个体即为蜂王Queen，其余个体为雄蜂集合Drones'set。Step2：蜂王婚飞行为。重复Step2~Step6若干次，直到产生的子代个体数达到种群大小。初始化蜂王的受精囊容量（）和飞行速度。蜂王的飞行速度通常通过下式随机产生popNpopNspenmNSpeedSqueenminminmaxSSS()randSqueen5.2蜂群算法的基本原理式中，是一个产生随机数的函数，分别是初始给定的蜂王的最大、最小速度。当蜂王的速度降低到以下时则返回蜂巢。Step3：随机选择一个雄峰个体，然后计算其被蜂王选择的概率。一个雄蜂与蜂王进行交叉的概率的计算公式可为式中，分别是蜂王和雄蜂的目标函数值。Step4：在（0，1）之间随机产生一个随机数R，如果雄峰被选择的概率大于该随机数R，则将该雄峰的遗传信息存储到蜂王的受精囊中，同时将该雄峰从雄蜂集合中删除。()randminmaxSS、minSDobPrtSpeed/ffexpDobPrdronequeendronequeenff、5.2蜂群算法的基本原理不管雄峰的基因是否能够存储到蜂王的搜精囊中，蜂王的飞行速度都要按照下式降低。然后返回Step5，直到蜂王的飞行速度降低到其最低速度或者其受精囊的容量已满。式中，，是每次蜂王速度减小的数量级。Step5：子代产生过程。通过对蜂王以及蜂王所存储的雄蜂基因个体的交叉过程产生子代种群个体，可采用多种交叉方法来进行交叉，以使子代更好地继承父代的有效结构。Step6：后代培育过程。产生子代后，由工蜂对子代个体进行培育。tSpeedtSpeed11,05.2蜂群算法的基本原理Step7：将新产生的子代种群集合替换原有种群，根据适应度值从大到小排列。Step8：考查算法终止条件，如果满足，则终止算法然后输出所得最优解。否则，返回Step2。5.2.2基于蜜蜂采蜜行为的蜂群算法生物学机理一般情况下，大多数的工蜂都留在蜂巢内值“内勤”，只有少数作为“侦察员”四处寻找蜜源。一旦发现了有利的采蜜地点或新的优质蜜源植物，就会变成采集蜂，飞回蜂巢并用圆舞或摇摆舞告知其他蜜蜂。圆舞或摇摆舞是蜜蜂之间进行信息交流的一种基本形式，传达了有关蜂巢周围蜜源的重要信息（如蜜源方向及离巢距离等）。5.2蜂群算法的基本原理研究表明，如果侦察蜂找到的蜜源在距蜂巢100米以内时，一般以圆舞方式爬行，即在蜂巢上交替性地向左或向右转着小圆圈。如果超过100米，则改变舞姿，先左右摆动腹部，沿直线蹒跚地爬行一小段距离，然后往一边兜半个圆圈，再回到起点，继续摆动腹部直线蹒跚爬行一小段距离，再向另一边兜半个圆圈，呈∞字，故称为8字舞或摆尾舞。在一定时间内，蜜蜂跳摆尾舞数量的多少，表示蜂巢到蜜源距离的远近；持续时间的长短反映蜜源且蜜蜂头部的位置反映了蜜源的位置，还以附在身上的花粉味道告知蜜源的种类。5.2蜂群算法的基本原理5.2蜂群算法的基本原理卡尔·冯·弗里希KarlRittervonFrisch1886.11.20~1982.06.12德国动物学家，行为生态学创始人，出生于奥地利维也纳，逝于德国慕尼黑。1973年获得诺贝尔生理学或医学奖巢中的工蜂可以通过“侦察员”的舞蹈来判别蜜源的方向和距离，以及蜜源质量。当舞蹈结束后，这些侦察员就与巢中的一些同伴一起飞回原先找到的蜜源进行采蜜。如果采集后，该蜜源质量仍然很高，它们会回到蜂巢继续通过舞蹈招募更多的同伴去采蜜。跟随采蜜的蜜蜂数量取决于蜜源质量。以这种方式，蜂群就能快速有效地找到高质量的蜜源。由此可见，蜜蜂采蜜的群体智能行为是通过不同角色间的交流、转换及协作来实现的。蜂群实现采蜜行为包括蜜源、采蜜蜂（即侦察蜂）与待采蜜蜂（留在蜂巢中的内勤蜂）三部分。1946年，德国生物学家K.V.Frisch破译了蜜蜂采蜜时跳舞所蕴含的信息，并因此获得1973年诺贝尔生理学奖。5.2蜂群算法的基本原理5.2蜂群算法的基本原理基本原理人工蜂群算法由三部分组成：①食物源：指可获得食物的位置，其价值取决于多种因素，如距蜂巢的远近、包含花蜜的丰富程度以及获取花蜜的难易程度，常用“食物浓度”来衡量。②采蜜蜂：指已经找到食物源的蜜蜂，又称引领蜂，其与特定食物源相对应。③待工蜂：指没有发现食物源的蜜蜂，其主要任务是寻找食物源采蜜，可分为跟随蜂和侦察蜂两种。5.2蜂群算法的基本原理因此可以将蜜蜂分为三种角色：①引领蜂：也称为雇佣蜂。在对应食物源上采蜜，并通过跳摇摆舞将食物源信息分享给跟随蜂。②跟随蜂：在蜂巢内等待，通过观察采蜜归来的引领蜂的摇摆舞信息选择优秀食物源进行跟随。③侦察蜂：当某食物源的食物浓度连续limit次未被更新，表明该食物源陷入局部最优，应被放弃，与之对应的引领蜂成为侦察蜂，开始寻找新的食物源。人工蜂群算法还定义了三种行为模式：搜索食物源，为食物源招募蜜蜂和放弃食物源。招募行为形成算法正反馈，而放弃行为导致负反馈。5.2蜂群算法的基本原理初始时刻，种群由引领蜂和跟随蜂组成，引领蜂与跟随蜂数量相同，都等于食物源数量。引领蜂首先飞出蜂巢，在对应食物源周围进行邻域搜索，并利用贪婪原则进行选择。回到蜂巢后，引领蜂将食物源信息通过跳摇摆舞的形式传递给跟随蜂，跟随蜂观察引领蜂的食物源信息，选择优秀食物源进行跟随，并再次在其附近进行邻域搜索和贪婪选择。若跟随蜂搜索新食物源的食物浓度大于原引领蜂的旧食物源时，新食物源替换旧食物源，同时完成角色互换；反之，保持不变。当某个食物源的食物浓度连续limit次未被更新，该食物源应被放弃，与之对应的引领蜂变为侦察蜂，随机寻找新食物源，找到新食物源后，侦察蜂又成为引领蜂，因此侦察蜂是一种临时角色，其数量应为1。5.2蜂群算法的基本原理人工蜂群算法就是通过不断地角色转换和执行行为模式，最终找到最丰富食物源。在ABC算法中，引领蜂有保持优良食物源的作用，具有精英特性；跟随蜂增加较好食物源对应的蜜蜂数，加快算法的收敛；侦察蜂随机搜索新食物源，帮助算法跳出局部最优。ABC算法的算法流程如图2-1所示。利用ABC算法求解全局最大化问题时，蜜蜂采蜜与函数优化间的对应关系如表5-1所示。从表5-1可以看出，每个食物源代表优化问题的一个可行解，蜜蜂寻找丰富食物源的过程对应于优化问题搜索优秀解的过程，食物源的食物浓度对应于解的质量，即适应度值，采蜜过程对应于计算适应度值的过程。5.2蜂群算法的基本原理5.3蜂群算法的应用5.3蜂群算法的应用目前，ABC算法的应用研究已经从最初的函数优化领域发展到神经网络训练、图像处理、无线通信、数据挖掘、组合优化、电子学、软件和控制工程等领域。5.3.1在神经网络训练中的应用人工神经网络训练是一种寻找最佳权矢量集的优化过程。为了克服传统训练算法收敛速度缓慢且易陷入局部最优的缺点，具有较强全局寻优能力的各种智能算法，如粒子群、蚁群等都被尝试用于人工神经网络的训练中。ABC算法在寻找最优解方面具有良好的探索和开采能力，已被广泛用于神经网络训练中。5.3蜂群算法的应用5.3.2在图像处理中的应用目前，蜂群算法已用于图像中的目标识别、图像增强、图像分割以及边缘检测。5.3.3在通信领域中的应用目前，蜂群算法已用于无线传感网络、正交频分复用、信道分配技术、语音信号识别等领域。5.3.4在通信领域中的应用数据挖掘的方法多种多样，包括关联规则挖掘、聚类、特征选择和统计分析等。近年来，研究者们尝试设计了各种基于智能优化算法的数据挖掘技术，包括蜂群聚类算法等。5.4蜂群算法的研究方向5.4蜂群算法的研究方