（通信与信息系统专业论文）蜂群算法的研究与应用.pdf

摘要 蜂群算法是一种新型的元启发式仿生算法。算法中每个蜜蜂都可以看作一个 智能体( a g e n t ) ，通过蜂群个体间协同作用达到群体智能的效果。蜂群算法主要是 模仿蜜蜂采蜜与繁殖两种机理。基于繁殖的蜂群算法通过蜂后保持优良基因，使 得蜂群更加适应环境。基于采蜜的蜂群算法则通过不同蜜蜂间的分工协作、角色 转换两种机制寻找最好的解。蜂群算法为元启发式算法研究提供了一个新思路， 逐渐成为求解复杂优化问题的重要研究方向之一。本文分两部分分析了蜂群算法 的原理与模型，介绍了算法的特点和流程。 对基于繁殖机理的蜂群算法，本文实现了蜂后的寻优策略，通过函数优化实 验验证了算法的有效性。对基于采蜜机理的蜂群算法，通过实验分析了算法中几 个关键参数的选择，并在t s p 上给出了实现策略。首先，在概率选择上采用了 确定性与随机性相结合的选择原则；其次，融合了遗传算法中的算子，提高了算 法的全局搜索能力；第三，在算法中增加了保优策略，加强了算法的收敛性；最 后，引入禁忌搜索思想，控制算法中后期收敛到局部最优的问题。在应用研究上， 分析了网络路由优化问题，研究了基于采蜜机理蜂群算法的m 网络q o s 单播路 由。 通过算例对所提出两种蜂群算法分别在函数优化与t s p 问题上进行了仿真 验证，实验结果表明，本文提出模型是有效和可行的，在基于采蜜蜂群算法的网 络路由优化等应用上也进行了实验仿真。本课题旨在为推进蜂群算法的理论研究 和应用研究起到一定的作用。 关键词：蜂群算法，t s p ，网络路由，繁殖，采蜜 a b s t r a c t b e ec o l o n ya l g o r i t h m ( b c o ) i san e wk i n do fm e t a - h e u r i s t i ca l g o r i t h m e v e r y b e ec a l lb er e g a r d e d 船a l la g e n ta n dt h ea l g o r i t h me n g e n d e r ss w a r mi n t e l l i g e n c e t h r o u g hs y n e r g i e sb e t w e e ni n d i v i d u a lb e e s b c ob o r r o w st h em e c h a n i s mo fb e e c o l o n y sp r o p a g a t i n ga n dg a t h e r i n g b c ob a s e d o np r o p a g a t i n gr e l i e so nt h eq u e e nt o m a i n t a i ne x c e l l e n tg e n e s i tm a k e sb e ec o l o n ym o r ea d a p t i v et ot h ee n v i r o n m e n t b c ob a s e do ng a t h e r i n gr e l i e so nl a b o rc o o p e r a t i o na n dr o l ec o n v e r s i o no fb e e st o s e a r c hf o rt h eb e s ts o l u t i o n b c op r o v i d e san e wi d e af o r t h er e s e a r c ho f m e t a - h e u r i s t i ca l g o r i t h ma n db e , c o m e so n eo ft h ei m p o r t a n tr e s e a r c hd i r e c t i o no f s o l v i n gc o m p l e xo p t i m i z a t i o np r o b l e mg r a d u a l l y t h ep a p e ri sd i v i d e di n t ot w op a r t s t oa n a l y z et h eb a s i ct h e o r ya n dm o d e lo fb c o p a p e ra l s oi n t r o d u c e st h ef e a t h e ro f b c 0a n di t sf l o w f o rb c ob a s e do np r o p a g a t i n g ，p a p e rr e a l i z e st h eo p t i m i z a t i o ns t r a t e g yo f q u e e n , a n dv a l i d a t e st h ea l g o r i t h mb yf u n c t i o no p t i m i z a t i o ne x p e r i m e n t f o rb c ob a s e do n g a t h e r i n g ，p a p e ra n a l y z e sp a r a m e t e r so ft h ea l g o r i t h mt h r o u g he x p e r i m e n t sa n dg i v e s i m p l e m e n t a r ys t r a t e g i e so nt s ef i r s t , a d o p t st h ed e t e r m i n a t i v ea n ds t o c h a s t i c s e a r c h i n gm e t h o dt om a k es e l e c t i o n ；s e c o n d , c o m b i n e so p e r a t o ro fg a t oi m p r o v et h e c a p a b i l i t yo fg l o b a ls e a r c h ；t h i r d , a d d so p e r a t o rt om a i n t a i ng o o ds o l u t i o n a n d s t r e n g t h e nt h ec o n v e r g e n c eo fa l g o r i t h m 飙i n t r o d u c e st a b us e a r c ht od e a lw i t h p r o b l e m so fc o n v e r g i n gt ol o c a lo p t i m i z a t i o ns o l u t i o ni nt h el a t t e rp a r to f t h ep r o c e s s f o rt h er e s e a r c ho fa p p l i c a t i o n , t h ep a p e ra n a l y z e st h en e t w o r kr o u t i n go p t i m i z a t i o n a n ds t u d i e so p t i m i z a t i o no f q o su n i c a s tr o u t i n gb a s e do nb c oi ni pn e t w o r k s i m u l a t i o n sa r em a d eo ns o m ee x a m p l e so f f u n c t i o no p t i m i z a t i o na n dt s pf o r t h e t w ok i n d so fb c or e s p e c t i v e l y r e s u l t sd e m o n s t r a t et h a tt h ea l g o r i t h m so ft h i sp a p e r a r ee f f e c t i v ea n df e a s i b l e s i m u l a t i o n sa r ea l s om a d ef o rn e t w o r kr o u t i n go p t i m i z a t i o n b a s e do nb c o t h i sp a p e rc o u l dp r o m o t et h et h e o r e t i c a lr e s e a r c ha n da p p l i c a t i o no f b c o k e yw o r d s ：b e ec o l o n ya l g o d t h m ( b c o ) ，t s p , n e t w o r km u t i n g , p r o p a g a t i n g ， g a t h e r i n g i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 垄埠要彻侔乡月矿日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘 版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用 影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部 分内容的公布( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ： 垄堡墨沙脚罗月矽日 河海大学工学硕士学位论文 第一章绪论 第一章绪论 实际生活中有许多问题都可以转化成最优化问题来求解。优化问题在计算 机、通信、信息处理等学科中有着广泛的应用，比较典型的如：网络路由问题、 移动通信中的多用户检测问题。同时优化算法是现代机器学习的基础。 一个优化问题可以形式化描述为：p = $ ，厂，q ) ，其中s 是n 维解空间，q 是 约束条件，厂是问题的目标函数或适应度函数，可表示为： f = o 工s s ，且s = o 。，s ：，如，s 。) 称为解向量。 p 的目标就是寻找一个解，使得厂| 陋) 对v s s 取最值，并满足约束条件q 。 求解变量最优化问题在数学上的本质是一种求极值的问题。 根据解向量在解空间中的取值不同，将优化问题分为两类： ( 1 ) 连续函数优化问题：解向量在解空间中取连续值。 ( 2 ) 组合优化问题：解向量在解空间中取离散值。 优化算法是用于解决优化问题的方法。在传统的最优化方法中，需要己知目 标函数连续可导，且需要可导的解析表达式，然后利用函数的各阶导数和偏导数 矩阵来确定最优方向和最优步长。此类算法中，以梯度为基础的优化算法占了很 重要的位置。其基本理论是，沿着梯度方向函数值增长最快；沿着负梯度方向函 数值下降最快。早期使用梯度原理的传统优化算法占据的主要位置，由于传统优 化算法的主要是针对连续凸函数优化问题而提出，对于非凸函数往往只能求得局 部最优解，同时对组合优化问题不适用。 近年来，随着优化问题应用越来越广泛，传统方法越来越不能满足实际的需 求。为此人们提出许多现代优化算法，也称为元启发式优化算法。元启发式算法 主要受自然现象的启发而提出，比较成熟的如模拟退火算法，遗传算法，禁忌搜 索算法，离子群算法、蚁群算法等。遗传算法，离子群算法、蚁群算法等是受生 物现象或生物学原理的启发而提出，因此也称为仿生算法，下一节我们简单地回 顾一些常用的元启发式算法，然后提出引出本文的主要研究内容蜂群算法。 1 1 元启发式优化算法概述 解决优化问题的算法在不断的更新与发展：从最初的构造性方法 ( c o n s t r u c t i v em e t h o d s ) 发展到局部搜索技术( l o c a ls e a r c ht e c h n i q u e s ) ，进一步 河海大学工学硕士学位论文第一章绪论 发展到现在的元启发式优化算法。元启发式算法是使用生物群体智慧1 1 1 的基本原 理，吸收了许多看似无关的其他学科( 如生物学、物理学、人工智能等) 中的概 念和方法，以其高效的优化性能、无需问题的特殊信息、应用领域广泛等优点， 成为解决n p 问题的有效通用算法。这里，主要对启发式优化算法中的遗传算法、 模拟退火算法和蚁群算法做一简单介绍。 1 1 1 遗传算法 自然界有两类促进其发展的要素：自然选择和变异。自然选择使更强的个体 得到繁衍与发展而淘汰弱小的个体即优胜劣汰；变异产生随机因素从而使新的个 体能够出现。仿照自然界这一启发式模拟进化算法，遗传算法( g a ，g e n e t i c a l g o r i t h m ) 也有同样的情况：选择是优化的基本思想，而变异则是非确定型搜 索的基本思想。早在1 9 6 2 年，j h o l l a n d 教授就提出了遗传算法的基本思想，随 后经过不断的发展，形成了基本的遗传算法的数学框架，并出版的专著给予介绍 口】。后来，j h o l l a n d 教授和他的学生们将算法推广到函数优化及机器学习等问题 中，并正式定名为遗传算法。 遗传算法是一种基于生物界自然选择与遗传机理的随机搜索算法。种群 ( p o p u l a t i o n ) 随机产生一组初始解开始进化。种群中的个体称为染色体 ( c h r o m o s o m e ) ，它表示问题的一个可行解。染色体由一串代码( 比如二进制码) 表示，使用适应值( f i t n e s s ) 来评价其优劣。在每一代进化过程中，通过复制 ( r e p r o d u c t i o n ) 操作( 又称选择操作) ，按一定的概率，随机选出部分染色体，然 后通过交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 操作得到后代( o f f s p r i n g ) ，并根据 适应值的大小按“适者生存”的原则淘汰部分后代，以保持种群大小不变。这样， 经过若干代进化后，算法收敛于最好的染色体，它就是问题的最优解或近似最优 解。 遗传算法中常用的遗传操作包括了三个基本算子：复制、交叉、变异。这些 操作使所要解决的问题从初始解逐步地逼近最优解。复制操作用于避免基因的损 失以提高全局收敛性和计算效率；交叉操作是g a 区别于其他进化算法的重要特 征，用于组合产生新个体以实施解空间的有效搜索，并降低对有效模式的破坏概 率；变异操作用于增加种群的多样性。它的最主要的特征是：在进行问题优化时， 它不是在单点上寻优，而是从整个种群中选择生命力强的个体产生新的种群；它 使用随机转换原理而不是确定性规则来工作。遗传算法在具体实施中有多种变形 和修正，可依照问题的背景进行灵活的运用。 j h o l l a n d 的遗传算法常被称为简单遗传算法( s g a ， s i m p l eg e n e t i c a l g o r i t h m ) ，基本步骤如下【3 】： 2 河海大学工学硕士学位论文 第一章绪论 e v a l u a t e ( p ) w h i l et e r m i n a t i o nc o n d i t i o n sn o tm e td o ，卜c r o s s o v e r ( p ) ，卜m u t a t e ( y ) e v a l u a t e ( p 。， ，卜s e l e c t ( 1 1 e n dw h i l e 种群的初始化：设种群规模大小为n ，在解的定义域上随机产生n 个初 始解( 染色体) ，组成供遗传算子作用的初始种群； 评价种群：采用某种准则( 或函数) 对种群中每个个体( 染色体) 进行 评价( 评价函数值又称为适应度) ，以判断其优劣。 种群交叉：一定概率p c 从父代选出部分个体( 染色体) 随机配对，并交 换配对染色体上部分信息( 如将表示染色体的二进制字符串上某些位上的数 字进行交换) 。 种群变异：变异是按位进行，以很小概率p 。使得某个染色体上的某位发 生变异( 即0 变成l 或1 变成o ) 。 选择( 复制) ：根据染色体的适应度值，按定方法，如轮盘赌( r o s e t t e w h e e l ) 法，从当前种群中选择优良( 适应值高) 的个体组成下一代。 遗传算法通过简单的编码技术表示复杂的结构，从多个初始解出发，通过遗 传操作在复杂空间上进行快速搜索，有效地减少了局部最优解产生的可能性。遗 传算法具有智能式搜索、渐进式优化、易获得全局最优、适于并行计算和通用性 强等优点，已被成功地应用于科学、商业和工程的很多问题中。 1 1 2 模拟退火算法 模拟退火算法( s a ，s i m u l a t e da n n e a l i n g ) 的思想最早是由m e t r o p o l i s 等提 出的【7 】，1 9 8 3 年k i r k p a t r i e k 等将其用于组合优化【8 叫。s a 算法是基于m o n t ec a r l o 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程 与一般组合优化问题之间的相似性。模拟退火算法的基本思想是：s a 由某一较 高初温开始，结合概率突跳特性的m e t r o p o l i s 抽样策略在解空间中随机寻找目标 函数的全局最优解，伴随温度参数的不断下降重复抽样过程，在局部优解中能概 率性地跳出并最终趋于问题的全局最优解。 河海大学工学硕士学位论文第一章绪论 固体的物理退火过程由三个部分组成：加温过程、等温过程和冷却过程。设 组合优化问题的一个解j 及其目标函数f ( 妙分别与固体状态j 及其能量e 等价， 对于控制参数t 的每一取值，算法持续进行“产生新解一判断一接收舍弃”的迭 代过程就对应着固体在某一恒定温度下趋于热平衡的过程，也就是执行了一次 m e t r o p o l i s 准则。与m e t r o p o l i s 准则从某一初始状态出发，通过计算系统的时间 演化过程，求出系统最终达到的状态相似，模拟退火算法从某个初始解出发，经 过大量解的变换后，可以求得给定控制参数值时组合优化问题的相对最优解。然 后减少控制参数t 的值，重复执行m e t r o p o l i s 准则，就可以在控制参数t 趋于 零时，最终求得组合优化问题的整体最优解。由于固体退火必须“徐徐”降温，才 能使固体在每一温度下都达到热平衡，最终趋于能量最小的基态，控制参数的值 也必须缓慢衰减，才能确保模拟退火算法最终趋于问题的整体最优解集。 模拟退火算法的主要步骤 3 1 如下： s + - g e n e r a t e i n i t i a l s o l u t i o n 0 r - 瓦 臃矗0t e r m i n a t i o nc o n d i t i o n sn o tm e td o i ff b f ( q u e e i l ) t h e n q u e e n - q u e e n e l s e a c c e p tq u e e n a sn e wq u e e nw i t h p o s s i b i l i t yp q ，q u e e n t ，q u e e n ) e n d r u p a a t e ( r ) e n dw h i l e 在当前蜂后的邻域白“p p ) 内随机选择候选蜂后q u e e r ，如果q u e e n 较目前 的蜂后基因更优良，那么使用q u e e n 替代口“p p 以；否则，以概率p 仃，q u e e n ，q u e e n ) 使用解q u e e n 替代q u e e n 。 p ( t , q u e e n , q h 文盘等掣盟 2 2 2 蜂后选择雄蜂的过程 ( 2 1 ) 在蜂群繁殖过程中，蜂后的婚飞起着关键的作用。婚飞可看作是在空间区域 的一系列状态转移，蜂后以一定的速率穿梭于空间中的不同区域，并在各个区域 内随机地与碰到的雄蜂交配。在婚飞的开始时刻，给蜂后赋予一定量的能量和速 度，在能量消耗至接近于零或在受精囊装满时，蜂后返回蜂巢。 每次交配前，雄蜂随机产生，而蜂后可以认为被放置在雄蜂所在空间。蜂后 的空间运动则取决于其速度，这也决定了基因进入受精囊中的几率。开始时，蜂 后速度很快，能量很高，在空间内是大范围跳跃。当能量逐渐降低时，蜂后开始 低速寻找雄蜂。在空间搜索的每一步，使用概率公式( 2 2 ) 来计算蜂后和雄蜂 交配的几率。如果配对成功，雄蜂的基因型将被存储在蜂后的受精囊内。总的来 说，算法由蜂后根据概率公式选择雄蜂开始，并通过与雄蜂基因谱的交叉，产生 新的幼蜂( b r o o d ) 。 1 0 河海大学工学硕士学位论文第二章基于繁殖机理的蜂群算法 蜂后与雄蜂配对采用式( 2 2 ) 的选择概率 p r o b ( q ，d ) = e x p 卜s ( f ) 】 ( 2 2 ) 其中p r o b ( q ，d ) 代表了雄蜂d 与蜂后q 成功交配的几率；a 代表了d 和 q 之间基因适应度的差值；s ( t ) 是蜂后在时刻t 的速率。从形式上看，这个函数 有些类似退火算法。当蜂后在开始婚飞后，速率很大时或是雄蜂的适应度和蜂后 的一样高时，交配的概率很大。随着时间的推移，蜂后的速率和能量以下面的方 式衰减： s o + 1 ) = s o ) ( 2 3 ) z ( t + 1 ) = e ( f ) 一， ( 2 4 ) 这里r 是每次转移后能量的消耗量，a 【o ，1 】为每次速度的衰减因子。由式( 2 3 ) 可知，在雄蜂所构成的空间内，初始时蜂后速度较大，跟多种雄蜂交配，种群的 多样性能较好的保留下来；后期蜂后速度较小，雄蜂的适应度起主要作用，蜂群 的良好基因得以保留。 2 3 3 对幼蜂群体的局部搜索 对幼蜂群体( 即新的工蜂群体) ，本文采用了局部攫累的策略： 设第i 个幼蜂的值为f 。，其适应度为几。) ，对其进行局部搜索： t ，一= t ，+ p ，+ t ，一tt ) ( 2 5 ) e ，为一个随机数，定义在( o ，1 ) 内；t 。从目前所有的幼蜂中随机选择，f l i t i ； t i n c a 是计算所得幼蜂j 的新值。x c t 。一与r ，分别计算其适应度 ，”) 和丸，) ， 若人，”) 丸，) ，则使用f ，替换f ，称为幼蜂j 的新值；反之，则保留原值不变。 在局部搜索后的幼蜂种群中，选择适应度最好的幼蜂作为候选蜂后，与蜂后 的适应度进行比较，若适应度大，则取代蜂后；否则，保留原蜂后。 2 3 算法实现 根据上述的分析，算法实现框架如下： 河海大学工学硕士学位论文第二章基于繁殖机理的蜂群算法 定义受精囊的大小m 虢机地产生幼蜂扶中选出最优的为蜂后 秘甬蜂后的选优策略优化蜂后豹基因型 w h 弛未达翔停止的限壹 t = o 髓枧魄初始化e ( t ) 和s ( t ) 初始化能量衰减的步长r = 0 s e ( t ) m 随机产生雄蜂 w h i l e e “) e 评估雄蜂的基因型 i f 该雄蜂超过7 概率选择的条件式f 2 2 ) a n d 蜂后的受精囊未满 t h e n 雄蜂的精子翻入飘受精囊 e n d 矿 t = t + ? e m = e m r ： s m = o 9 s m ： 以s m 概率对雄蜂基因型每一位取反； e n d w h 妇 而r b r o o d s = lt o m 虢机地旋蜂舌的受精囊中选出精子通过将e 选的精子s 蜂后的基因型交 叉而产生幼蜂； 变异幼蜂的基函型； e n d f o r 耨幼蜂群体局部搜索 h 最垂 的幼蜂的适应瘦比蜂后高t h e n 甬最好的幼蜂取代蜂后 杀死瞬有的幼蜂 e n dw h i l e 算法开始时随机地初始化蜂群并选出蜂后，然后使用优化函数式( 2 1 ) 来提高 蜂后的基因型，以保证蜂后总是适应度高的蜜蜂。随后，开始进行一系列的婚飞。 在每一次婚飞中，蜂后的速率都被随机地初始化为某个值。随着时间的推移，蜂 后以式( 2 2 ) 的概率与雄蜂交配。如果一只雄蜂与蜂后成功地交配，那么它的精子 就被加入到蜂后的受精囊中。蜂后在完成婚飞后，回到蜂巢开始繁殖。它从受精 囊中随机地选择精子，然后将精子的基因与蜂后的基因交叉来补全所选精子的基 因。随后变异开始作用于幼蜂，因此，就算同样的精子被多次用来产生后代，也 会因为变异作用而产生不同的幼蜂。 对幼蜂进行局部搜索的作用在于，若在幼蜂中存在适应度高于当前蜂后的， 那么前者将取代后者。剩下的幼蜂全部被杀死，然后重新开始新一轮的婚飞。 1 2 河海大学工学硕士学位论文第二章基于繁殖机理的蜂群算法 2 4 仿真结果 函数优化是遗传算法的经典应用领域，也是对遗传算法性能评价的常用手段 之一。1 9 7 5 年，d ej o n g 根据函数优化问题的复杂性提出了多种函数最小化问题， 并已经成为函数优化的衡量标准。 我们在m a t l a b 环境下实现上述算法，对连续函数的优化问题进行了测试， 并将它们的结果与基本遗传算法进行了比较。结果表明，蜂群算法能以较小的幼 代数目、较小的进化代数而比基本遗传算法高得多的命中率搜索出最优解。 在以下的测试中，设定基本遗传算法的运行参数如下： 群体大小：m = 8 0 ，终止代数：1 = 2 0 0 ，交叉概率：p c = o 6 ；变异概率：p m = o 0 0 1 ； 设定蜂群算法的运行参数如下： 群体大小：m = 1 5 ；终止代数：t _ = 6 0 ；变异概率：p m = o o o l 采用二进制串编码方式，每个决策变量编码长度是2 0 位。 算例i ( 椭球函数) 几) = 砰 l 耐 一1 x 1 函数最小值为0 ，在x = 0 处取得。基本遗传算法收敛较慢，采用同样的简单交 叉算子和联赛选择算子，最优解仅为0 0 2 。而本文基于繁殖机理的蜂群算法在 实验中最优解的数量级可达1 0 一，更加接近最优解0 ，性能明显好于基本遗传算 法。图2 1 是蜂群算法的收敛曲线： 图2 1 蜂群算法收敛曲线 河海大学工学硕士学位论文 第二章基于繁殖机理的蜂群算法 算例2r o s e n b r o c k 函数 ，g ) = 1 0 0 g ：一x ；) 2 + ( 1 一一) 2 2 0 4 8 x 7 时，蜜蜂从节点一可行的邻居节点中选择v ，即转 移到新的状态 r 。转移过程中既要使用随机状态转移规则，又要考虑 如下因素：问题约束条件q ；t a b u k 中存储已访问的节点；启发信息t ，。 依据所扮演的角色不同，蜜蜂构建路径的方式有所不同。引领蜂仅是重走上 一次迭代过程的路径，即保持解而不做任何改变。侦察蜂和跟随蜂依据概率转移 规则选择下一个节点，其计算如下： ( f ) =器州叫， , , e l d l o w 4 0o t h e r w 括e 其中戎o ) 表示第k 个蜜蜂在时刻t 由节点f 转移到节点j 的概率； a t t o w a ：= v f ) q - t a b u 。, 。a l l o w d k , 表示第| j 个蜜蜂在节点i 的可行邻居节点， 由所有满足约束条件，且蜜蜂还未访问过的节点组成。t a b u 。为第k 只蜜蜂的禁 忌表，用于记录蜜蜂k 已经走过的节点，以保证没有重复访问同一个节点，同时 在某些应用中( 如：路由优化) 方便蜜蜂按原路返回。 s 。( ，) ，f 。( f ) 分别表示蜂群的控制信息和问题的启发式信息。a ，卢分别是 其权重参数。 蜜蜂控制信息上的区别在于： 侦察蜂，( r ) = ； 1 8 ( 3 2 ) 河海大学工学硕士学位论文第三章基于采蜜机理的蜂群算法 其中，为集合a l l o w d ? 的元素数目，即蜜蜂未走过的节点个数； 跟随蜂： j 。( f ) = 选择引领蜂的道路 不选择引领蜂的道路 可选路径含引领蜂走过道路 ( 3 3 ) ； 可选择径不含引领蜂走过道路 其中，表示引领蜂的引导性强弱，z 同样指蜜蜂未走过的节点个数。 3 4 算法框架 蜂群算法伪代码： g e n e r a t e l n i t i a l r o l e ( b e e ) c o n s t r u c t w a y ( s c o u t e r ) e v a l u a t e ( b e e ) w h 钍et e r m i n a t i o nc o n d i t i o n sn o tm e td o w h i l en o ta r r i v e da tl a s t p o i n td o c o n s t r u c t w a y ( s c o u t e r ) c o n s t r u c t w a y ( f o l l o w e r ) e n dw h i l e e v a l u a t e ( b e e ) d e c i d e r o l e ( b e e ) e n dw h i l e 算法中，b e e 代表三种角色的蜜蜂：侦察蜂s c o u t e r ，引领蜂l e a d e r ，跟 随蜂f o l l o w e r 。 g e n e r a t e l n i t i a l r o l e ：初始化蜜蜂角色为侦察蜂s c o u t e r ； c o n s t r u c t w a y ：根据3 3 节的分析，对不同角色的蜜蜂选择不同的方式构建 道路； e v a l u a t e ：计算蜜蜂路径的收益率( 即目标函数的值) 。 综上所述，可以看出蜂群算法具有如下的特点： 1 9 河海大学工学硕士学位论文 第三章基于采蜜机理的蜂群算法 1 ) 一种自然算法。基于蜂群高效率寻找食物源的机理。 2 ) 多角色分工机制。蜜蜂按照自己角色采用不同的方法搜索，并根据所得 解的质量自发的调整角色，以适应下一次搜索过程。 3 ) 协同工作机制。蜜蜂在选择路径时，依据角色决定是否选用以前蜜蜂留 下的信息和利用信息的方式，能以较大概率找到优化问题的最优解。 4 ) 鲁棒性。使用概率规则而不是确定性规则指导搜索，不必知道其他先验 的信息，有极好的鲁棒性和广泛的适用性。 5 ) 易于与其他启发式算法结合。 蜂群算法具有很强的发现优解的能力，这是因为算法利用了引领蜂和跟随蜂 寻路的正反馈机制，在一定程度上可以加快进化进程。而且蜜蜂间不断进行信息 交流和传递，从而能够相互协作，有利于发现较好解。 3 5 本章小结 本章在深入分析蜜蜂采蜜生物学机理基础上，对路径问题进行了深入的分 析，并给出解空间构造的思路和数学表达，最后给出了算法框架流程和蜂群模型 的特点。为下一章蜂群算法在t s p 问题上的研究提供了基础。 河海大学工学硕士学位论文第四章基于采蜜机理的蜂群算法在t s p 问题上的应用 第四章基于采蜜机理的蜂群算法在t s p 问 题上的应用 4 1t s p 问题概述 旅行商问题( t s p ，t r a v e l i n gs a l e s m a np r o b l e m ) 是一个为学术界广泛研究的 问题，长期以来它吸引了众多学者对其进行研究【3 3 】。选择t s p 作为诠释算法性 能的平台原因众多：它是一个涉及多种实际应用领域的重要n p 难问题；也是一 个可以使用蜂群算法解答的问题；更是一个特征明显的问题，算法的行为不会被 具体的应用技术细节所掩盖；它是新算法思想的标准测试平台一个算法能在 t s p 上展现出良好的性能往往成为该算法有效性的证明。此外，t s p 测试平台的 使用历程也告诉我们，应用在t s p 上有效的算法，通常也是解决其他组合优化 问题的有效算法。 直观的说，t s p 问题就是指一位商人，从自己的家乡出发，希望能找到一条 最短路径，途经给定的城市集合中所有城市，最后返回家乡，并且每个城市都被 访问一次且仅一次。在形式上，t s p 问题可以用一个带权完全图g = 缈，e ) 来描 述，其中矿是城市的结点集合，三是所有边的集合( 如果本身g 并非完全图， 仍可以向其添加边构成一个完全图g 7 ，并使得所附加边的权值足够大保证其不 会出现在任何优化的解中，这样g 和g 得到的最优解完全相同) 对于每一条边 e ( i ，_ ，) e ，都至少分配一个权值西用于代表城市f 与_ ，之间的距离大小，其中 u v 。t s p 的目标就是寻找图中的一条具有最小成本值的汉密尔顿回路。t s p 的一个最优解就对应于节点标号为 l ，2 ，n 的一个排列x 并且使得长度，b ) 最 小。厂g ) 定义为： n - | 厂g ) = 九。) + d 0 m 。) ( 4 1 ) t = l t s p l i b 是t s p 的标准测试库，其中的实例已经被广泛研究文献引用【舯5 1 ， 同时也渗透到t s p 问题的算法设计和应用中【3 7 1 。大部分t s p 实例都是几何实 例，即预先定义的一系列坐标点的集合，并且各点之间的距离可以通过某种度量 方式进行计算。下文将使用t s pl i b 中的实例分析算法的性能。 2 l 河海大学工学硕士学位论文第四章基于采蜜机理的蜂群算法在t s p 问题上的应用 4 2 蜂群算法在t s p 上实现 4 2 1 蜜蜂的寻路过程 t s p 的解可以用城市序号的一个有向环状排列 来表示。每一 个t s p 的解都是由起点城市出发，每运行一步就向解集合中添加一个还没有访 问过的城市，解的构建在所有城市都被蜜蜂访问过之后终止。t s p 上无特殊的约 束条件q 的要求。 定义t a b u 。为路径记录矩阵( 即禁忌表) 。t a b u 。根据蜜蜂角色的不同而有不同 的构建方式。蜜蜂为侦查蜂时，随机搜索路径；为跟随蜂时，使用轮盘赌的方式 选择引领蜂跟随其路径；为引领蜂时，直接重走上一轮走过的路径，t a b u 。中的 路径不改变。下文详细介绍侦察蜂和跟随蜂的路径构建过程。 当前侦察蜂所在城市为f ，未访问城市的集合为a l l o w d , ，则侦察蜂选择城市 ，4 肋w 钟完全依据城市之间的启发信息e 。来确定，其转移概率由式( 3 1 ) 、式 1 ( 3 2 ) 确定。其中= ，西为城市i 到城市，的距离。距离越短，城市被选择的 口口 可能性越大。跟随蜂构建城市的过程可用图4 1 、图4 2 来描述。图中，跟随蜂 走到了a 城市，在分叉路口决定前往下一个访问城市前，它会先检查所跟随的 引领蜂路径。在图4 1 中，跟随蜂的待选城市中包含b 城市，即跟随蜂待选路径 中包含a b ，而其对应的引领蜂路径包含a b ，此时跟随蜂有比较高的概率重走 a b ；在图4 2 中，跟随蜂待选路径包括a b 、a c 、a d ，而其对应的引领蜂路径 为a z ，此时跟随蜂以等概率选择上述三条路径。跟随蜂的转移概率由式( 3 1 ) 、 式( 3 3 ) 确定。 河海大学工学硕士学位论文第四章基于采蜜机理的蜂群算法在t s p 问题上的应用 t 1 8 l 顿蚌路径 图4 1 引领蜂后续路径含跟随蜂可选路径图4 2 引领蜂后续路径不含跟随蜂可选路径 4 2 2 确定性与随机性的选择机制 蜂群算法中，依据蜜蜂角色的不同，使用不同的计算公式确定下一个被选城 市的概率，并选择概率值最大的城市为下一城市。但在问题规模( 如t s p 的城 市数目) 较大时很难找到最优解，这是因为算法很容易陷入局部最优；同时这样 使算法失去随机性，有可能丢失某些较好解，以致最终找不到真正最优解。因此， 在蜜蜂选择道路前，采用轮盘赌方法，将由各个选择概率做累计概率统计，然后 产生一个随机数，该