第5章--蜂群算法基本理论ppt课件.ppt

5.15.1 蜂群算法的概述蜂群算法的概述蜂群算法的概述蜂群算法的概述5.1.15.1.1蜂群算法的概念蜂群算法的概念蜂群算法的概念蜂群算法的概念5.1.25.1.2蜂群算法的的发展蜂群算法的的发展蜂群算法的的发展蜂群算法的的发展5.1.35.1.3蜂群算法的特点蜂群算法的特点蜂群算法的特点蜂群算法的特点5.1.45.1.4 蜂群算法的分类蜂群算法的分类蜂群算法的分类蜂群算法的分类5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理5.2.15.2.1基于蜜蜂繁殖行为的蜂群算法基于蜜蜂繁殖行为的蜂群算法基于蜜蜂繁殖行为的蜂群算法基于蜜蜂繁殖行为的蜂群算法5.2.25.2.2基于蜜蜂采蜜行为的蜂群算法基于蜜蜂采蜜行为的蜂群算法基于蜜蜂采蜜行为的蜂群算法基于蜜蜂采蜜行为的蜂群算法5.35.3蜂群算法的应用蜂群算法的应用蜂群算法的应用蜂群算法的应用5.45.4蜂群算法的研究方向蜂群算法的研究方向蜂群算法的研究方向蜂群算法的研究方向第第5 5章章 蜂群算法基本理论蜂群算法基本理论5.1蜂群算法概述蜂群算法概述 5.1.15.1.1蜂群算法的概念蜂群算法的概念蜂群算法的概念蜂群算法的概念蜂群算法是一种模仿蜜蜂繁殖、采蜜等行为的新兴群智蜂群算法是一种模仿蜜蜂繁殖、采蜜等行为的新兴群智蜂群算法是一种模仿蜜蜂繁殖、采蜜等行为的新兴群智蜂群算法是一种模仿蜜蜂繁殖、采蜜等行为的新兴群智能优化算法。能优化算法。能优化算法。能优化算法。5.15.1蜂群算法概述蜂群算法概述蜂群算法概述蜂群算法概述5.1.25.1.2蜂群算法的蜂群算法的蜂群算法的蜂群算法的发发发发展展展展人工蜂群算法于人工蜂群算法于人工蜂群算法于人工蜂群算法于20052005年由土耳其学者年由土耳其学者年由土耳其学者年由土耳其学者D.D.KarabogaKaraboga系系系系统统统统提出。提出。提出。提出。萌芽萌芽萌芽萌芽阶阶阶阶段段段段19461946年，德国生物学家年，德国生物学家年，德国生物学家年，德国生物学家K.V.FrischK.V.Frisch破破破破译译译译了蜜蜂采蜜了蜜蜂采蜜了蜜蜂采蜜了蜜蜂采蜜时时时时跳跳跳跳舞所舞所舞所舞所蕴蕴蕴蕴含的信息，并因此含的信息，并因此含的信息，并因此含的信息，并因此获获获获得得得得19731973年年年年诺贝诺贝诺贝诺贝尔尔尔尔生理学生理学生理学生理学奖奖奖奖。19951995年，美国年，美国年，美国年，美国CornellUniversityCornellUniversity（康奈（康奈（康奈（康奈尔尔尔尔大学）的大学）的大学）的大学）的T.D.T.D.SeeleySeeley提出蜂群的自提出蜂群的自提出蜂群的自提出蜂群的自组织组织组织组织模型。模型。模型。模型。20012001年，年，年，年，H.A.AbbassH.A.Abbass提出了蜜蜂婚配提出了蜜蜂婚配提出了蜜蜂婚配提出了蜜蜂婚配优优优优化（化（化（化（MatingMatingOptimizationOptimization，MBOMBO）算法，用于解决可）算法，用于解决可）算法，用于解决可）算法，用于解决可满满满满足性足性足性足性问题问题问题问题。20012001年，年，年，年，P.LucicP.Lucic等等等等针对针对针对针对蜜蜂行蜜蜂行蜜蜂行蜜蜂行为为为为建模，并提出一种基建模，并提出一种基建模，并提出一种基建模，并提出一种基于蜂群采蜜行于蜂群采蜜行于蜂群采蜜行于蜂群采蜜行为为为为的蜜蜂系的蜜蜂系的蜜蜂系的蜜蜂系统统统统（BeeSystemBeeSystem，BSBS）。）。）。）。5.15.1蜂群算法的概述蜂群算法的概述蜂群算法的概述蜂群算法的概述5.1.25.1.2蜂群算法的蜂群算法的蜂群算法的蜂群算法的发发发发展展展展 发发发发展展展展阶阶阶阶段段段段20052005年，土耳其埃年，土耳其埃年，土耳其埃年，土耳其埃尔尔尔尔吉耶斯大学的吉耶斯大学的吉耶斯大学的吉耶斯大学的DervisDervis KarabogaKaraboga在在在在T.D.SeeleyT.D.Seeley蜂群自蜂群自蜂群自蜂群自组织组织组织组织模型的基模型的基模型的基模型的基础础础础上，系上，系上，系上，系统统统统提出了人工蜂群提出了人工蜂群提出了人工蜂群提出了人工蜂群算法（算法（算法（算法（ArtificialBeeColonyArtificialBeeColony，简简简简称称称称ABCABC），并将其），并将其），并将其），并将其应应应应用于数用于数用于数用于数值优值优值优值优化化化化领领领领域。域。域。域。20062006年又年又年又年又扩扩扩扩展到展到展到展到约约约约束性数束性数束性数束性数值优值优值优值优化化化化领领领领域。域。域。域。此后，国内外学者此后，国内外学者此后，国内外学者此后，国内外学者针对针对针对针对基本蜂群算法提出了多种改基本蜂群算法提出了多种改基本蜂群算法提出了多种改基本蜂群算法提出了多种改进进进进算算算算法，并法，并法，并法，并应应应应用于不同用于不同用于不同用于不同领领领领域。域。域。域。目前，蜂群算法的研究目前，蜂群算法的研究目前，蜂群算法的研究目前，蜂群算法的研究还处还处还处还处于不断探索与改于不断探索与改于不断探索与改于不断探索与改进进进进的的的的阶阶阶阶段。段。段。段。5.15.1蜂群算法的概述蜂群算法的概述蜂群算法的概述蜂群算法的概述5.1.35.1.3蜂群算法的特点蜂群算法的特点蜂群算法的特点蜂群算法的特点 蜂群算法的蜂群算法的蜂群算法的蜂群算法的优优优优点点点点 全局性：蜂群算法在搜索全局性：蜂群算法在搜索全局性：蜂群算法在搜索全局性：蜂群算法在搜索过过过过程中不易陷入局部极程中不易陷入局部极程中不易陷入局部极程中不易陷入局部极值值值值点，点，点，点，即使在非即使在非即使在非即使在非连续连续连续连续和含有噪声的情况下，也能以和含有噪声的情况下，也能以和含有噪声的情况下，也能以和含有噪声的情况下，也能以较较较较大概率收大概率收大概率收大概率收敛敛敛敛到到到到最最最最优优优优解或解或解或解或满满满满意解，具有很意解，具有很意解，具有很意解，具有很强强强强的容噪能力。的容噪能力。的容噪能力。的容噪能力。并行性和高效性：蜂群算法具有大范并行性和高效性：蜂群算法具有大范并行性和高效性：蜂群算法具有大范并行性和高效性：蜂群算法具有大范围围围围全局搜索和并全局搜索和并全局搜索和并全局搜索和并行性等特点，适用于并行行性等特点，适用于并行行性等特点，适用于并行行性等特点，适用于并行计计计计算，因而算，因而算，因而算，因而执执执执行效率高。行效率高。行效率高。行效率高。鲁鲁鲁鲁棒性：棒性：棒性：棒性：鲁鲁鲁鲁棒性棒性棒性棒性强强强强意味着蜂群算法的搜索以群体意味着蜂群算法的搜索以群体意味着蜂群算法的搜索以群体意味着蜂群算法的搜索以群体为为为为基基基基本本本本单单单单元，不受初始元，不受初始元，不受初始元，不受初始选择选择选择选择的影响，不因的影响，不因的影响，不因的影响，不因实实实实例的不同而例的不同而例的不同而例的不同而蜕变蜕变蜕变蜕变；同；同；同；同时对时对时对时对于一个相同于一个相同于一个相同于一个相同问题问题问题问题，在不同的多次运行中能，在不同的多次运行中能，在不同的多次运行中能，在不同的多次运行中能够够够够得到相同得到相同得到相同得到相同结结结结果，在解的果，在解的果，在解的果，在解的质质质质量上没有很大差异。量上没有很大差异。量上没有很大差异。量上没有很大差异。这这这这已被已被已被已被许许许许多数多数多数多数值值值值所所所所证实证实证实证实。5.15.1蜂群算法的概述蜂群算法的概述蜂群算法的概述蜂群算法的概述 普适性和易普适性和易普适性和易普适性和易扩扩扩扩性：蜂群算法是一种弱方法，它采用自性：蜂群算法是一种弱方法，它采用自性：蜂群算法是一种弱方法，它采用自性：蜂群算法是一种弱方法，它采用自然然然然进进进进化机制来表示复化机制来表示复化机制来表示复化机制来表示复杂现杂现杂现杂现象，象，象，象，对对对对函数的形函数的形函数的形函数的形态态态态无要求，可解决无要求，可解决无要求，可解决无要求，可解决多种多种多种多种优优优优化搜索化搜索化搜索化搜索问题问题问题问题。针对针对针对针对不同不同不同不同实实实实例，只需适当例，只需适当例，只需适当例，只需适当调调调调整算子参数整算子参数整算子参数整算子参数等，等，等，等，进进进进行很小修改即可适行很小修改即可适行很小修改即可适行很小修改即可适应应应应新的新的新的新的问题问题问题问题，程序能，程序能，程序能，程序能够够够够通用，通用，通用，通用，这这这这是是是是现现现现行的其他大多数行的其他大多数行的其他大多数行的其他大多数优优优优化方法所做不到的。化方法所做不到的。化方法所做不到的。化方法所做不到的。简简简简明性：蜂群算法的基本思想明性：蜂群算法的基本思想明性：蜂群算法的基本思想明性：蜂群算法的基本思想简单简单简单简单明了，明了，明了，明了，实现实现实现实现步步步步骤骤骤骤通通通通俗易懂。俗易懂。俗易懂。俗易懂。5.15.1蜂群算法的概述蜂群算法的概述蜂群算法的概述蜂群算法的概述5.1.45.1.4蜂群算法的分蜂群算法的分蜂群算法的分蜂群算法的分类类类类按照机理不同，蜂群算法分按照机理不同，蜂群算法分按照机理不同，蜂群算法分按照机理不同，蜂群算法分为为为为两两两两类类类类：受婚配行受婚配行受婚配行受婚配行为为为为启启启启发发发发的蜜蜂婚配的蜜蜂婚配的蜜蜂婚配的蜜蜂婚配优优优优化算法，也称化算法，也称化算法，也称化算法，也称为为为为基于蜜基于蜜基于蜜基于蜜蜂繁殖机理的蜂群算法。蜂繁殖机理的蜂群算法。蜂繁殖机理的蜂群算法。蜂繁殖机理的蜂群算法。受采蜜行受采蜜行受采蜜行受采蜜行为为为为启启启启发发发发的蜜蜂采蜜的蜜蜂采蜜的蜜蜂采蜜的蜜蜂采蜜优优优优化算法。化算法。化算法。化算法。另外，另外，另外，另外，还还还还有模有模有模有模拟拟拟拟蜂王繁殖行蜂王繁殖行蜂王繁殖行蜂王繁殖行为为为为的蜂王的蜂王的蜂王的蜂王进进进进化算法，模化算法，模化算法，模化算法，模拟拟拟拟蜜蜜蜜蜜蜂蜂蜂蜂躲躲躲躲避障碍物的蜜蜂避障碍物的蜜蜂避障碍物的蜜蜂避障碍物的蜜蜂躲躲躲躲避算法，模避算法，模避算法，模避算法，模拟拟拟拟蜂群任蜂群任蜂群任蜂群任务务务务分配行分配行分配行分配行为为为为的可的可的可的可用于服用于服用于服用于服务务务务器器器器动态动态动态动态分配的分散蜜蜂算法，等等。分配的分散蜜蜂算法，等等。分配的分散蜜蜂算法，等等。分配的分散蜜蜂算法，等等。5.15.1蜂群算法的概述蜂群算法的概述蜂群算法的概述蜂群算法的概述5.2蜂群算法的基本原理蜂群算法的基本原理 5.2.15.2.1基于蜜蜂繁殖行为的蜂群算法基于蜜蜂繁殖行为的蜂群算法基于蜜蜂繁殖行为的蜂群算法基于蜜蜂繁殖行为的蜂群算法 生物学机理生物学机理生物学机理生物学机理 一个完整的蜂巢一般由一只蜂王、上千的雄蜂、一个完整的蜂巢一般由一只蜂王、上千的雄蜂、一个完整的蜂巢一般由一只蜂王、上千的雄蜂、一个完整的蜂巢一般由一只蜂王、上千的雄蜂、10000100006000060000工蜂和幼蜂组成。工蜂和幼蜂组成。工蜂和幼蜂组成。工蜂和幼蜂组成。这三种蜂分工明确，各司其职。蜂王是蜂群中唯一具有这三种蜂分工明确，各司其职。蜂王是蜂群中唯一具有这三种蜂分工明确，各司其职。蜂王是蜂群中唯一具有这三种蜂分工明确，各司其职。蜂王是蜂群中唯一具有生殖能力的雌蜂，主要任务是与不同的雄蜂进行交配与产卵；生殖能力的雌蜂，主要任务是与不同的雄蜂进行交配与产卵；生殖能力的雌蜂，主要任务是与不同的雄蜂进行交配与产卵；生殖能力的雌蜂，主要任务是与不同的雄蜂进行交配与产卵；雄蜂是整个蜂群的父亲和警卫，主要任务是和蜂王交配繁殖雄蜂是整个蜂群的父亲和警卫，主要任务是和蜂王交配繁殖雄蜂是整个蜂群的父亲和警卫，主要任务是和蜂王交配繁殖雄蜂是整个蜂群的父亲和警卫，主要任务是和蜂王交配繁殖后代；工蜂主要负责清洁、哺育、筑巢、守卫和采蜜等各项后代；工蜂主要负责清洁、哺育、筑巢、守卫和采蜜等各项后代；工蜂主要负责清洁、哺育、筑巢、守卫和采蜜等各项后代；工蜂主要负责清洁、哺育、筑巢、守卫和采蜜等各项工作。工作。工作。工作。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂王的求偶过程称为婚飞。蜂王在空中起舞就标志着婚蜂王的求偶过程称为婚飞。蜂王在空中起舞就标志着婚蜂王的求偶过程称为婚飞。蜂王在空中起舞就标志着婚蜂王的求偶过程称为婚飞。蜂王在空中起舞就标志着婚飞的开始，一群雄蜂追随其后。蜂王选择其中一只雄蜂进行飞的开始，一群雄蜂追随其后。蜂王选择其中一只雄蜂进行飞的开始，一群雄蜂追随其后。蜂王选择其中一只雄蜂进行飞的开始，一群雄蜂追随其后。蜂王选择其中一只雄蜂进行空中交配，每次可以与空中交配，每次可以与空中交配，每次可以与空中交配，每次可以与720720只雄蜂交配，直至纳满精子飞回只雄蜂交配，直至纳满精子飞回只雄蜂交配，直至纳满精子飞回只雄蜂交配，直至纳满精子飞回蜂巢产卵。为了避免近亲繁殖，蜂王有时会寻找其他蜂群的蜂巢产卵。为了避免近亲繁殖，蜂王有时会寻找其他蜂群的蜂巢产卵。为了避免近亲繁殖，蜂王有时会寻找其他蜂群的蜂巢产卵。为了避免近亲繁殖，蜂王有时会寻找其他蜂群的雄蜂交配。刚开始交配时，蜂王飞行速度很快，每交配一次，雄蜂交配。刚开始交配时，蜂王飞行速度很快，每交配一次，雄蜂交配。刚开始交配时，蜂王飞行速度很快，每交配一次，雄蜂交配。刚开始交配时，蜂王飞行速度很快，每交配一次，蜂王的飞行速度有所衰减。蜂王的飞行速度有所衰减。蜂王的飞行速度有所衰减。蜂王的飞行速度有所衰减。当蜂王衰弱到一定程度时，则由成熟且胜任的幼蜂替代，当蜂王衰弱到一定程度时，则由成熟且胜任的幼蜂替代，当蜂王衰弱到一定程度时，则由成熟且胜任的幼蜂替代，当蜂王衰弱到一定程度时，则由成熟且胜任的幼蜂替代，即产生新一代蜂王，此时结束原蜂王的生命周期。蜂群繁殖即产生新一代蜂王，此时结束原蜂王的生命周期。蜂群繁殖即产生新一代蜂王，此时结束原蜂王的生命周期。蜂群繁殖即产生新一代蜂王，此时结束原蜂王的生命周期。蜂群繁殖进化过程也是蜂王不断更新的过程，如图进化过程也是蜂王不断更新的过程，如图进化过程也是蜂王不断更新的过程，如图进化过程也是蜂王不断更新的过程，如图5-15-1所示。所示。所示。所示。其实，新蜂王的产生类似于进化计算中的一个优化过程，其实，新蜂王的产生类似于进化计算中的一个优化过程，其实，新蜂王的产生类似于进化计算中的一个优化过程，其实，新蜂王的产生类似于进化计算中的一个优化过程，蜂王是优化过程中待求解问题的最优解。蜂王是优化过程中待求解问题的最优解。蜂王是优化过程中待求解问题的最优解。蜂王是优化过程中待求解问题的最优解。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理图图图图5-15-1蜂群繁殖优化过程示意图蜂群繁殖优化过程示意图蜂群繁殖优化过程示意图蜂群繁殖优化过程示意图5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理 基本原理基本原理基本原理基本原理Step1Step1：蜂群初始化。首先确定种群的大小：蜂群初始化。首先确定种群的大小：蜂群初始化。首先确定种群的大小：蜂群初始化。首先确定种群的大小，然后，然后，然后，然后分分分分别别别别运用构造启运用构造启运用构造启运用构造启发发发发式算法式算法式算法式算法NEHNEH和随机和随机和随机和随机产产产产生两种方式生两种方式生两种方式生两种方式产产产产生初始生初始生初始生初始种群。初始化完成后，通种群。初始化完成后，通种群。初始化完成后，通种群。初始化完成后，通过过过过比比比比较较较较所有的种群个体，按适所有的种群个体，按适所有的种群个体，按适所有的种群个体，按适应应应应度度度度值值值值从大到小排序。排第一位的个体即从大到小排序。排第一位的个体即从大到小排序。排第一位的个体即从大到小排序。排第一位的个体即为为为为蜂王蜂王蜂王蜂王QueenQueen，其余个，其余个，其余个，其余个体体体体为为为为雄蜂集合雄蜂集合雄蜂集合雄蜂集合DronessetDronesset。Step2Step2：蜂王婚：蜂王婚：蜂王婚：蜂王婚飞飞飞飞行行行行为为为为。重复。重复。重复。重复Step2Step6Step2Step6若干次，直到若干次，直到若干次，直到若干次，直到产产产产生的子代个体数达到种群大小生的子代个体数达到种群大小生的子代个体数达到种群大小生的子代个体数达到种群大小。初始化蜂王的受精囊容量（初始化蜂王的受精囊容量（初始化蜂王的受精囊容量（初始化蜂王的受精囊容量（）和）和）和）和飞飞飞飞行速度行速度行速度行速度。蜂王的。蜂王的。蜂王的。蜂王的飞飞飞飞行速度行速度行速度行速度通常通通常通通常通通常通过过过过下式随机下式随机下式随机下式随机产产产产生生生生5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理式中，式中，式中，式中，是一个产生随机数的函数，是一个产生随机数的函数，是一个产生随机数的函数，是一个产生随机数的函数，分别是初分别是初分别是初分别是初始给定的蜂王的最大、最小速度。当蜂王的速度降低到始给定的蜂王的最大、最小速度。当蜂王的速度降低到始给定的蜂王的最大、最小速度。当蜂王的速度降低到始给定的蜂王的最大、最小速度。当蜂王的速度降低到以下时则返回蜂巢。以下时则返回蜂巢。以下时则返回蜂巢。以下时则返回蜂巢。Step3Step3：随机选择一个雄峰个体，然后计算其被蜂王选择：随机选择一个雄峰个体，然后计算其被蜂王选择：随机选择一个雄峰个体，然后计算其被蜂王选择：随机选择一个雄峰个体，然后计算其被蜂王选择的概率。一个雄蜂与蜂王进行交叉的概率的概率。一个雄蜂与蜂王进行交叉的概率的概率。一个雄蜂与蜂王进行交叉的概率的概率。一个雄蜂与蜂王进行交叉的概率的计算公的计算公的计算公的计算公式可为式可为式可为式可为式中，式中，式中，式中，分别是蜂王和雄蜂的目标函数值。分别是蜂王和雄蜂的目标函数值。分别是蜂王和雄蜂的目标函数值。分别是蜂王和雄蜂的目标函数值。Step4Step4：在（：在（：在（：在（0 0，1 1）之间随机产生一个随机数）之间随机产生一个随机数）之间随机产生一个随机数）之间随机产生一个随机数R R，如果雄，如果雄，如果雄，如果雄峰被选择的概率大于该随机数峰被选择的概率大于该随机数峰被选择的概率大于该随机数峰被选择的概率大于该随机数R R，则将该雄峰的遗传信息存，则将该雄峰的遗传信息存，则将该雄峰的遗传信息存，则将该雄峰的遗传信息存储到蜂王的受精囊中，同时将该雄峰从雄蜂集合中删除。储到蜂王的受精囊中，同时将该雄峰从雄蜂集合中删除。储到蜂王的受精囊中，同时将该雄峰从雄蜂集合中删除。储到蜂王的受精囊中，同时将该雄峰从雄蜂集合中删除。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理不管雄峰的基因是否能够存储到蜂王的搜精囊中，蜂王不管雄峰的基因是否能够存储到蜂王的搜精囊中，蜂王不管雄峰的基因是否能够存储到蜂王的搜精囊中，蜂王不管雄峰的基因是否能够存储到蜂王的搜精囊中，蜂王的飞行速度都要按照下式降低。然后返回的飞行速度都要按照下式降低。然后返回的飞行速度都要按照下式降低。然后返回的飞行速度都要按照下式降低。然后返回Step5Step5，直到蜂王的，直到蜂王的，直到蜂王的，直到蜂王的飞行速度降低到其最低速度或者其受精囊的容量已满。飞行速度降低到其最低速度或者其受精囊的容量已满。飞行速度降低到其最低速度或者其受精囊的容量已满。飞行速度降低到其最低速度或者其受精囊的容量已满。式中，式中，式中，式中，是每次蜂王速度减小的数量级。，是每次蜂王速度减小的数量级。，是每次蜂王速度减小的数量级。，是每次蜂王速度减小的数量级。Step5Step5：子代产生过程。通过对蜂王以及蜂王所存储的雄：子代产生过程。通过对蜂王以及蜂王所存储的雄：子代产生过程。通过对蜂王以及蜂王所存储的雄：子代产生过程。通过对蜂王以及蜂王所存储的雄蜂基因个体的交叉过程产生子代种群个体，可采用多种交叉蜂基因个体的交叉过程产生子代种群个体，可采用多种交叉蜂基因个体的交叉过程产生子代种群个体，可采用多种交叉蜂基因个体的交叉过程产生子代种群个体，可采用多种交叉方法来进行交叉，以使子代更好地继承父代的有效结构。方法来进行交叉，以使子代更好地继承父代的有效结构。方法来进行交叉，以使子代更好地继承父代的有效结构。方法来进行交叉，以使子代更好地继承父代的有效结构。Step6Step6：后代培育过程。产生子代后，由工蜂对子代个体：后代培育过程。产生子代后，由工蜂对子代个体：后代培育过程。产生子代后，由工蜂对子代个体：后代培育过程。产生子代后，由工蜂对子代个体进行培育。进行培育。进行培育。进行培育。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理Step7Step7：将新产生的子代种群集合替换原有种群，根据适：将新产生的子代种群集合替换原有种群，根据适：将新产生的子代种群集合替换原有种群，根据适：将新产生的子代种群集合替换原有种群，根据适应度值从大到小排列。应度值从大到小排列。应度值从大到小排列。应度值从大到小排列。Step8Step8：考查算法终止条件，如果满足，则终止算法然后：考查算法终止条件，如果满足，则终止算法然后：考查算法终止条件，如果满足，则终止算法然后：考查算法终止条件，如果满足，则终止算法然后输出所得最优解。否则，返回输出所得最优解。否则，返回输出所得最优解。否则，返回输出所得最优解。否则，返回Step2Step2。5.2.25.2.2基于蜜蜂采蜜行为的蜂群算法基于蜜蜂采蜜行为的蜂群算法基于蜜蜂采蜜行为的蜂群算法基于蜜蜂采蜜行为的蜂群算法 生物学机理生物学机理生物学机理生物学机理一般情况下，大多数的工蜂都留在蜂巢内一般情况下，大多数的工蜂都留在蜂巢内一般情况下，大多数的工蜂都留在蜂巢内一般情况下，大多数的工蜂都留在蜂巢内值值值值“内勤内勤内勤内勤”，只有少数只有少数只有少数只有少数作为作为作为作为“侦察员侦察员侦察员侦察员”四处寻找蜜源。一旦发现了有利的四处寻找蜜源。一旦发现了有利的四处寻找蜜源。一旦发现了有利的四处寻找蜜源。一旦发现了有利的采蜜地点或新的优质蜜源植物采蜜地点或新的优质蜜源植物采蜜地点或新的优质蜜源植物采蜜地点或新的优质蜜源植物，就会变成采集蜂，飞回蜂巢，就会变成采集蜂，飞回蜂巢，就会变成采集蜂，飞回蜂巢，就会变成采集蜂，飞回蜂巢并用圆舞或摇摆舞告知其他蜜蜂。并用圆舞或摇摆舞告知其他蜜蜂。并用圆舞或摇摆舞告知其他蜜蜂。并用圆舞或摇摆舞告知其他蜜蜂。圆舞或摇摆舞是蜜蜂之间进行信圆舞或摇摆舞是蜜蜂之间进行信圆舞或摇摆舞是蜜蜂之间进行信圆舞或摇摆舞是蜜蜂之间进行信息交流的一种基本形式，传达了有关息交流的一种基本形式，传达了有关息交流的一种基本形式，传达了有关息交流的一种基本形式，传达了有关蜂巢周围蜜源的重要信息（如蜜源方蜂巢周围蜜源的重要信息（如蜜源方蜂巢周围蜜源的重要信息（如蜜源方蜂巢周围蜜源的重要信息（如蜜源方向及离巢距离等）。向及离巢距离等）。向及离巢距离等）。向及离巢距离等）。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理研究表明，如果侦察蜂找到的蜜源在距蜂巢研究表明，如果侦察蜂找到的蜜源在距蜂巢研究表明，如果侦察蜂找到的蜜源在距蜂巢研究表明，如果侦察蜂找到的蜜源在距蜂巢100100米以内米以内米以内米以内时，一般以圆舞方式爬行，即在蜂巢上交替性地向左或向右时，一般以圆舞方式爬行，即在蜂巢上交替性地向左或向右时，一般以圆舞方式爬行，即在蜂巢上交替性地向左或向右时，一般以圆舞方式爬行，即在蜂巢上交替性地向左或向右转着小圆圈。转着小圆圈。转着小圆圈。转着小圆圈。如果超过如果超过如果超过如果超过100100米，则改变舞姿，先左右摆动腹部，沿直米，则改变舞姿，先左右摆动腹部，沿直米，则改变舞姿，先左右摆动腹部，沿直米，则改变舞姿，先左右摆动腹部，沿直线蹒跚地爬行一小段距离，然后往一边兜半个圆圈，再回到线蹒跚地爬行一小段距离，然后往一边兜半个圆圈，再回到线蹒跚地爬行一小段距离，然后往一边兜半个圆圈，再回到线蹒跚地爬行一小段距离，然后往一边兜半个圆圈，再回到起点，继续摆动腹部直线蹒跚爬行一小段距离，再向另一边起点，继续摆动腹部直线蹒跚爬行一小段距离，再向另一边起点，继续摆动腹部直线蹒跚爬行一小段距离，再向另一边起点，继续摆动腹部直线蹒跚爬行一小段距离，再向另一边兜半个圆圈，呈兜半个圆圈，呈兜半个圆圈，呈兜半个圆圈，呈 字，故称为字，故称为字，故称为字，故称为8 8字舞或摆尾舞。字舞或摆尾舞。字舞或摆尾舞。字舞或摆尾舞。在一定时间内，蜜蜂跳摆尾舞数量的在一定时间内，蜜蜂跳摆尾舞数量的在一定时间内，蜜蜂跳摆尾舞数量的在一定时间内，蜜蜂跳摆尾舞数量的多少，表示蜂巢到蜜源距离的远近；持续多少，表示蜂巢到蜜源距离的远近；持续多少，表示蜂巢到蜜源距离的远近；持续多少，表示蜂巢到蜜源距离的远近；持续时间的长短反映蜜源且蜜蜂头部的位置反时间的长短反映蜜源且蜜蜂头部的位置反时间的长短反映蜜源且蜜蜂头部的位置反时间的长短反映蜜源且蜜蜂头部的位置反映了蜜源的位置，还以附在身上的花粉味映了蜜源的位置，还以附在身上的花粉味映了蜜源的位置，还以附在身上的花粉味映了蜜源的位置，还以附在身上的花粉味道告知蜜源的种类。道告知蜜源的种类。道告知蜜源的种类。道告知蜜源的种类。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理卡尔卡尔卡尔卡尔 冯冯冯冯 弗里希弗里希弗里希弗里希 KarlRittervonFrischKarlRittervonFrisch1886.11.201982.06.121886.11.201982.06.12德国动物学家，行为生德国动物学家，行为生德国动物学家，行为生德国动物学家，行为生态学创始人，出生于奥态学创始人，出生于奥态学创始人，出生于奥态学创始人，出生于奥地利维也纳，逝于德国地利维也纳，逝于德国地利维也纳，逝于德国地利维也纳，逝于德国慕尼黑。慕尼黑。慕尼黑。慕尼黑。19731973年获得诺年获得诺年获得诺年获得诺贝尔生理学或医学奖贝尔生理学或医学奖贝尔生理学或医学奖贝尔生理学或医学奖 巢中的工蜂可以巢中的工蜂可以巢中的工蜂可以巢中的工蜂可以通过通过通过通过“侦察员侦察员侦察员侦察员”的舞蹈来判别蜜源的方的舞蹈来判别蜜源的方的舞蹈来判别蜜源的方的舞蹈来判别蜜源的方向和距离，以及蜜源质量。当舞蹈结束后，这些侦察员就与向和距离，以及蜜源质量。当舞蹈结束后，这些侦察员就与向和距离，以及蜜源质量。当舞蹈结束后，这些侦察员就与向和距离，以及蜜源质量。当舞蹈结束后，这些侦察员就与巢中的一些同伴一起飞回原先找到的蜜源进行采蜜。如果采巢中的一些同伴一起飞回原先找到的蜜源进行采蜜。如果采巢中的一些同伴一起飞回原先找到的蜜源进行采蜜。如果采巢中的一些同伴一起飞回原先找到的蜜源进行采蜜。如果采集后，该蜜源质量仍然很高，它们会回到蜂巢继续通过舞蹈集后，该蜜源质量仍然很高，它们会回到蜂巢继续通过舞蹈集后，该蜜源质量仍然很高，它们会回到蜂巢继续通过舞蹈集后，该蜜源质量仍然很高，它们会回到蜂巢继续通过舞蹈招募更多的同伴去采蜜。跟随采蜜的蜜蜂数量取决于蜜源质招募更多的同伴去采蜜。跟随采蜜的蜜蜂数量取决于蜜源质招募更多的同伴去采蜜。跟随采蜜的蜜蜂数量取决于蜜源质招募更多的同伴去采蜜。跟随采蜜的蜜蜂数量取决于蜜源质量。以这种方式，蜂群就能快速有效地找到高质量的蜜源。量。以这种方式，蜂群就能快速有效地找到高质量的蜜源。量。以这种方式，蜂群就能快速有效地找到高质量的蜜源。量。以这种方式，蜂群就能快速有效地找到高质量的蜜源。由此可见，蜜蜂采蜜的群体智能行为是通过不同角色间由此可见，蜜蜂采蜜的群体智能行为是通过不同角色间由此可见，蜜蜂采蜜的群体智能行为是通过不同角色间由此可见，蜜蜂采蜜的群体智能行为是通过不同角色间的交流、转换及协作来实现的。蜂群实现采蜜行为包括蜜源、的交流、转换及协作来实现的。蜂群实现采蜜行为包括蜜源、的交流、转换及协作来实现的。蜂群实现采蜜行为包括蜜源、的交流、转换及协作来实现的。蜂群实现采蜜行为包括蜜源、采蜜蜂（即侦察蜂）与待采蜜蜂（留在蜂巢中的内勤蜂）三采蜜蜂（即侦察蜂）与待采蜜蜂（留在蜂巢中的内勤蜂）三采蜜蜂（即侦察蜂）与待采蜜蜂（留在蜂巢中的内勤蜂）三采蜜蜂（即侦察蜂）与待采蜜蜂（留在蜂巢中的内勤蜂）三部分。部分。部分。部分。19461946年，德国生物学家年，德国生物学家年，德国生物学家年，德国生物学家K.V.FrischK.V.Frisch破译了蜜蜂采蜜时跳破译了蜜蜂采蜜时跳破译了蜜蜂采蜜时跳破译了蜜蜂采蜜时跳舞所蕴含的信息，并因此获得舞所蕴含的信息，并因此获得舞所蕴含的信息，并因此获得舞所蕴含的信息，并因此获得19731973年诺贝尔生理学奖。年诺贝尔生理学奖。年诺贝尔生理学奖。年诺贝尔生理学奖。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理 基本原理基本原理基本原理基本原理人工蜂群算法由三部分人工蜂群算法由三部分人工蜂群算法由三部分人工蜂群算法由三部分组组组组成：成：成：成：食物源：指可食物源：指可食物源：指可食物源：指可获获获获得食物的位置，其价得食物的位置，其价得食物的位置，其价得食物的位置，其价值值值值取决于多种因取决于多种因取决于多种因取决于多种因素，如距蜂巢的素，如距蜂巢的素，如距蜂巢的素，如距蜂巢的远远远远近、包含花蜜的丰富程度以及近、包含花蜜的丰富程度以及近、包含花蜜的丰富程度以及近、包含花蜜的丰富程度以及获获获获取花蜜的取花蜜的取花蜜的取花蜜的难难难难易程度，易程度，易程度，易程度，常用常用常用常用“食物食物食物食物浓浓浓浓度度度度”来衡量。来衡量。来衡量。来衡量。采蜜蜂：指已采蜜蜂：指已采蜜蜂：指已采蜜蜂：指已经经经经找到食物源的蜜蜂，又称引找到食物源的蜜蜂，又称引找到食物源的蜜蜂，又称引找到食物源的蜜蜂，又称引领领领领蜂，其蜂，其蜂，其蜂，其与特定食物源相与特定食物源相与特定食物源相与特定食物源相对应对应对应对应。待工蜂：指没有待工蜂：指没有待工蜂：指没有待工蜂：指没有发现发现发现发现食物源的蜜蜂，其主要任食物源的蜜蜂，其主要任食物源的蜜蜂，其主要任食物源的蜜蜂，其主要任务务务务是是是是寻寻寻寻找食物源采蜜，可分找食物源采蜜，可分找食物源采蜜，可分找食物源采蜜，可分为为为为跟随蜂和跟随蜂和跟随蜂和跟随蜂和侦侦侦侦察蜂两种。察蜂两种。察蜂两种。察蜂两种。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理因此可以将蜜蜂分为三种角色：因此可以将蜜蜂分为三种角色：因此可以将蜜蜂分为三种角色：因此可以将蜜蜂分为三种角色：引领蜂：也称为雇佣蜂。在对应食物源上采蜜，并引领蜂：也称为雇佣蜂。在对应食物源上采蜜，并引领蜂：也称为雇佣蜂。在对应食物源上采蜜，并引领蜂：也称为雇佣蜂。在对应食物源上采蜜，并通过跳摇摆舞将食物源信息分享给跟随蜂。通过跳摇摆舞将食物源信息分享给跟随蜂。通过跳摇摆舞将食物源信息分享给跟随蜂。通过跳摇摆舞将食物源信息分享给跟随蜂。跟随蜂：在蜂巢内等待，通过观察采蜜归来的引领跟随蜂：在蜂巢内等待，通过观察采蜜归来的引领跟随蜂：在蜂巢内等待，通过观察采蜜归来的引领跟随蜂：在蜂巢内等待，通过观察采蜜归来的引领蜂的摇摆舞信息选择优秀食物源进行跟随。蜂的摇摆舞信息选择优秀食物源进行跟随。蜂的摇摆舞信息选择优秀食物源进行跟随。蜂的摇摆舞信息选择优秀食物源进行跟随。侦察蜂：当某食物源的食物浓度连续侦察蜂：当某食物源的食物浓度连续侦察蜂：当某食物源的食物浓度连续侦察蜂：当某食物源的食物浓度连续limitlimit次未被更次未被更次未被更次未被更新，表明该食物源陷入局部最优，应被放弃，与之对应的引新，表明该食物源陷入局部最优，应被放弃，与之对应的引新，表明该食物源陷入局部最优，应被放弃，与之对应的引新，表明该食物源陷入局部最优，应被放弃，与之对应的引领蜂成为侦察蜂，开始寻找新的食物源。领蜂成为侦察蜂，开始寻找新的食物源。领蜂成为侦察蜂，开始寻找新的食物源。领蜂成为侦察蜂，开始寻找新的食物源。人工蜂群算法还定义了三种行为模式：搜索食物源，为人工蜂群算法还定义了三种行为模式：搜索食物源，为人工蜂群算法还定义了三种行为模式：搜索食物源，为人工蜂群算法还定义了三种行为模式：搜索食物源，为食物源招募蜜蜂和放弃食物源。招募行为形成算法正反馈，食物源招募蜜蜂和放弃食物源。招募行为形成算法正反馈，食物源招募蜜蜂和放弃食物源。招募行为形成算法正反馈，食物源招募蜜蜂和放弃食物源。招募行为形成算法正反馈，而放弃行为导致负反馈。而放弃行为导致负反馈。而放弃行为导致负反馈。而放弃行为导致负反馈。5.25.2蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理蜂群算法的基本原理初始时刻，种群由引领蜂和跟随蜂组成，引领蜂与跟随初始时刻，种群由引领蜂和跟随蜂组成，引领蜂与跟随初始时刻，种群由引领蜂和跟随蜂组成，引领蜂与跟随初始时刻，种群由引领蜂和跟随蜂组成，引领蜂与跟随蜂数量相同，都等于食物源数量。蜂数量相同，都等于食物源数量。蜂数量相同，都等于食物源数量。蜂数量相同，都等于食物源数量。引领蜂首先飞出蜂巢，在引领蜂首先飞出蜂巢，在引领蜂首先飞出蜂巢，在引领蜂首先飞出蜂巢，在对应食物源周围进行邻域搜索，并利用贪婪原则进行选择。对应食物源周围进行邻域搜索，并利用贪婪原则进行选择。对应食物源周围进行邻域搜索，并利用贪婪原则进行选择。对应食物源周围进行邻域搜索，并利用贪婪原则进行选择。回到蜂巢后，引领蜂将食物源信息通过跳摇摆舞的形式回到蜂巢后，引领蜂将食物源信息通过跳摇摆舞的形式回到蜂巢后，引领蜂将食物源信息通过跳摇摆舞的形式回到蜂巢后，引领蜂将食物源信息通过跳摇摆舞的形式传递给跟随蜂，跟随蜂观察引领蜂的食物源信息，选择优秀传递给跟随蜂，跟随蜂观察引领蜂的食物源信息，选择优秀传递给跟随蜂，跟随蜂观察引领蜂的食物源信息，选择优秀传递给跟随蜂，跟随蜂观察引领蜂的食物源信息，选择优秀食物源进行跟随，并再次在其附近进行邻域搜索和贪婪选择。食物源进行跟随，并再次在其附近进行邻域搜索和贪婪选择。食物源进行跟随，并再次在其附近进行邻域搜索和贪婪选择。食物源进行跟随，并再次在其附近进行邻域搜索和贪婪选择。若跟随蜂搜索新食物源的食物浓度大于原引领蜂的旧食若跟随蜂搜索新食物源的食物浓度大于原引领蜂的旧食若跟随蜂搜索新食物源的食物浓度大于原引领蜂的旧食若跟随蜂搜索新食物源的食物浓度大于原引领蜂的旧食物源时，新食物源替换旧食物源，同时完成角色互换；物源时，新食物源替换旧食物源，同时完成角色互换；物源时，新食物源替换旧食物源，同时完成角色互换；物源时，新食物源替换旧食物源，同时完成角色互换；反之，反之，反之，反之，保持不变。保持不变。保持不变。保持不变。当某个食物源的食物浓度连续当某个食物源的食物浓度连续当某个食物源的食物浓度连续当某个食物源的食物浓度连续limitlimit次未被更新，该食物次未被更新，该食物次未被更新，该食物次未被更新，该食物源应被放弃，与之对应的引领蜂变为侦察蜂，随机寻找新食源应被放弃，与之对应的引领蜂变为侦察蜂，随机寻找新食源应被放弃，与之对应的引领蜂变为侦察蜂，随机寻找新食源应被放弃，与之对应的引领蜂变为侦察蜂，随机寻找新食物源，找到新食物源后，侦察蜂又成为引领蜂，因此侦察蜂物源，找到新食物源后，侦察蜂又成为引