（计算机应用技术专业论文）求解qos路由优化的蚁群算法研究.pdf

求解o o s 路由优化的蚁群算法研究 摘要 目前，网络的许多应用都带有q o s 要求，q o s 路由问题已经成为 网络技术领域内的一个研究热点。研究表明，多约束条件下q o s 路 由问题是n p 完全问题，用常规方法难以求解。 蚁群算法是一种新兴的人工智能算法，具有稳健性、正反馈、分 布式计算、易于同其它算法相结合等特点。并且，网络路由优化问题 的计算分布、非静态随机动态以及异步的网络状态更新等特征与蚁群 算法的分布式计算、自组织等特征匹配得很好。因此，应用蚁群算法 来解决网络q o s 路由优化问题是一个很好的选择。 本文首先对q o s 路由的基本概念和原理作了比较系统而完整的 阐述。接着详细介绍了蚁群算法的基本原理、算法模型、算法流程等， 并深入分析了算法的参数，讨论了算法的优缺点。 针对蚁群算法存在的初期收敛速度慢、收敛时间过长、易陷入局 部最优等缺陷，结合q o s 路由优化问题，本文提出了三种改进思想： 一是引入双向分工的搜索机制，并实行路径变异策略，进行二次蚁群 寻优。二是改进节点选择策略，并根据目标函数值动态更新信息素。 三是利用最大一最小蚁群算法原理对信息素进行限制，并应用局部搜 索方法提高搜索效率。最后通过实例对所提出的改进蚁群算法在q o s 路由上进行了优化仿真验证，实验结果表明，本文提出的改进蚁群算 法是有效和可行的。 关键词：q o s 路由蚁群算法双向分工动态自适应信息素 r e s e a r cho n a n tco l o n ya l g o r i t h mf o r s o l v i n g q o sr o u t i n g o p t i m i z a t i o n a b s t r a c t a tp r e s e n t ，n e t w o r k sh a v em a n ya p p l i c a t i o n sw i t hq o s r e q u i r e m e n t s q o sr o u t i n gi s ar e s e a r c hh o t s p o ti nt o d a y sn e t w o r k t e c h n o l o g y f i e l d r e s e a r c hs h o w st h a ta san p 。c o m p l e t e p r o b l e m , m u l t i p l ec o n s t r a i n e dq o sr o u t i n g p r o b l e mc a nn o tb es o l v e de a s i l yw i t h c o n v e n t i o n a lm e t h o d s w i t ht h ef e a t u r e so f s t a b i l i t y , p o s i t i v ef e e d b a c k ，d i s t r i b u t e d c o m p u t i n g ，b e i n gc o n s t r u c t i v ea n de a s yt oc o m b i n ew i t h o t h e ra l g o r i t h m s ， a n tc o l o n ya l g o r i t h m ( a c a ) i san e wa r t i f i c i a li n t e l l i g e n c ea l g o r i t h m s i n a d d i t i o n , a n t c o l o n ya l g o r i t h m w i t hd i s t r i b u t e d c o m p u t i n g ， s e l f - o r g a n i z i n gc h a r a c t e r i s t i c sm a t c h sw e l lt h ec h a r a c t e r i s t i c so fn e t w o r k r o u t i n go p t i m i z a t i o np r o b l e m ss u c ha sc a l c u l a t i o no ft h ed i s t r i b u t i o n ， n o n - s t a t i cr a n d o md y n a m i ca n dt h eu p d a t i n go fa s y n c h r o n o u sn e t w o r k s t a t u s t h e r e f o r e ，i ti sag o o dc h o i c et ot os o l v et h en e t w o r kq o sr o u t i n g o p t i m i z a t i o np r o b l e mw i t ha n tc o l o n ya l g o r i t h m t h i sp a p e rf i r s te x p o u n d ss y s t e m a t i c a l l ya n dc o m p l e t e l yt h eb a s i c c o n c e p t sa n dp r i n c i p l e so fq o sr o u t i n g , t h e ni t d e s c r i b e si nd e t a i lt h e b a s i cp r i n c i l n e so fa n tc o l o n ya l g o r i t h m , t h ea l g o r i t h mm o d e l ，a l g o r i t h m f l o w ，e t c t h ep a p e ra l s om a k e sat h o r o u g ha n a l y s i so ft h ea l g o r i t h m p a r a m e t e r s a n dc o m p a r e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e a l g o r i t h m a st ot h ed r a w b a c k so fa c a ，s u c ha si t ss l o wc o n v e r g e c ei nt h e b e g i n n i n g ，l o n gc o n v e r g e n c et i m el a t e ra n di t sb e i n gp r o n et of a l l i n t o l o c a lo p t i m i z a t i o n ，t h r e ei m p r o v e di d e aa n ds i m u l a t e de x p e r i m e n t sh a s b e e np r o p o s e di n t h i sp a p e r f r i s to fa l l ，t h es e a r c hm e c h a n i s mf o r t w o w a yd i v i s i o no fl a b o rw a si n t r o d u c e d p a t hm u t a t i o ns t r a t e g ya n d a p p l y i n ga c a t w i c ew a si m p l e m e n t e d s e c o n d l y ，i ti m p r o v et h en o d e s e l e c t i o ns t r a t e g ya n du p d a t ep h e r o m o n ed y n a m i c a l l yb a s eo nt h e o b j e c t i v ef u n c t i o nv a l u e t h i r d l y ，p h e r o m o n eh a sa l w a y sb e e nc o n t r o l l e d w i t h i nac e r t a i nr a n g eb a s eo nt h ep r i n c i p l e so ft h em a x m i na n tc o l o n y a lg o r i t h m l o c a ls e a r c hm e t h o dw a sa ls oa p p l i e d t oi m p r o v et h e e f f i c i e n c yo ft h es e a r c h 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 sf o rt h e i m p r o v e da c ai n t h eq o sr o u t i n g r e s u l t so ft h o s es i m u l a t i o n s d e m o n s t r a t et h a tt h ei m p r o v e da c ai se f f e c t i v ea n df e a s i b l e k e y w o r d s - q o sr o u t i n g ；a n tc o l o n ya l g o r i t h m ；t w o w a y d i v i s i o no f l a b o r ；d y n a m i ca n da d a p t i v e ；p h e r o m o n 论文独创性声明 本人郑重声明：所提交的学位论文，是本人在导师的指导下， 独立撰写完成的。除文中已经注明引用的内容外，本论文不含其他个 人或其他机构已经发表或撰写过的研究成果，也没有剽窃、抄袭等违 反学术道德规范的侵权行为。对本文的研究做出重要贡献的个人和集 体，均己在文中以明确方式标明。本人愿意承担由本声明而引起的法 律责任。 研究生签名：批日期：舻 占月矽日 论文使用授权声明 本人完全了解广西民族大学有关保留、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存、汇编学位论文。 除在保密期内的保密论文外，允许学位论文被查阅和借闲，可以公布 ( 包括刊登) 论文的全部或部分内容。 研究生签名：劣童盹 p 钠戤懂哆生趴 日期如多年占月矽日 日期：缈产莎月万日 1 绪论 1 1 研究背景及意义 随着高速网络技术和多媒体技术的飞速发展，电信业正在经历着巨大的变 革，计算机网络己经逐步地深入到工业、农业、商业、医学、教育等生活的各个 领域，影响并改变着我们日常的生活方式。伴随着计算机通信网络的多元化与复 杂化的加剧，计算机用户对数据需求的质量也在朝着复杂化与多样化发展，越来 越多地提出了包括多媒体通信在内的综合服务要求。如视频会议、视频点播、p i 可视电话、远程教育、虚拟现实等，这些应用都要求“现场网络直播”，不能容 忍画面的过多“抖动”，对数据包的到达时间有严格的要求。当然，在不影响画 面质量的情况下也大都能容忍一定程度的信息丢失和错误。这就对网络提出了不 同于数据应用的服务质量要求，需要提供端至蝴的q o s 控锘i j 和保证。 而传统的网络提供的是一种“尽力而为”( b e s t - e o f f o r t ) 的服务，网络在扩展 方面较为容易实现，数据包可以在满足一定的条件下尽量往前传输。虽然p 分 组头有专门指明优先级及服务类型等属性的字段，但由于网络层是不能区分业务 的，所以路由器选择路由和处理分组时，往往忽略掉这些字段，而将网络资源几 乎平均地提供给各类业务。这种“尽力而为”的发送机制使网络层的带宽、时延 和抖动等传输参数无法得到保证，然而这些参数往往是至关重要的，“尽力而为 服务己不能满足当今各种网络应用的需要。因此，计算机网络系统作为计算和信 息等服务的提供者应该按照用户的要求提供服务质量( q u a l i t yo f s e r v i c e ，q o s ) 控制u 1 。在此背景下，通信网络的服务质量( q o s ) 这一概念被提出，并且针对此 概念，各种保障网络q o s 的技术、算法也应运而生。 1 2 国内外研究现状 上个世纪8 0 年代初，s e i t z 和w o r t e n d y k e 等人提出基于用户的性能评价问 题，这可能是关于计算机网络q o s 研究的最早文献。到了8 0 年代末期，一些实 验性系统也应运而生，如英国兰开斯特大学的q o s a 工程、美国加州伯克利大 学的t e n e t 工程、i b m 公司黑森伯格欧洲网络中心的h e i p r o j e e t 工程等。1 9 9 7 年9 月，国际组织i e t f 开始制定了有关q o s 定义与服务的一系列r f c 标准， 典型的工作是提出了两种不同的i n t e m e tq o s 体系结构：综合服务( i n t e g a t e d s e r v i c e s ，i n t s e r v ) 和区分服务( d i f f e r e n t i a t e ds e r v i c e s ，d i f f s e r v ) 。 q o s 路由是网络多媒体信息传输的关键技术之一，在这方面已有不少的研究 成果。实时应用往往会对延时，延时抖动，带宽，丢失率，业务代价等多个参数 同时提出性能要求。文献【4 中已经证明，这些参数相互独立时，选择满足多个 参数限制的q o s 路由就成为n p 完全问题。而启发式算法在解决n p 一完全问题上 具有非常明显的优势。近年来，国内外许多学者利用遗传算法璐1 、神经网络哺1 、 模拟退火算法口1 和蚁群算法陋等启发式智能算法来解决n p 完全问题，并且取得 了一定的成果，但这些算法在解决q o s 路由问题上都存在着一些难以克服的缺 陷，如计算复杂度太高、运行时间过长等。而蚁群算法具有分布式计算和自组织 等优点，这些优点与网络路由优化问题的计算分布、非静态随机动态以及异步的 网络状态更新等特征非常匹配。因此，应用蚁群算法来解决网络o o s 路由优化问 题是一个很好的选择。但是，如果网络的规模过大，将导致算法在初期收敛速度 慢、收敛时间过长、易陷入局部最优解呻1 引。这是蚁群优化算法的最为突出的缺 陷。针对这些缺陷，近年来许多国内外学者在蚁群算法的改进当中做了大量的研 究工作1 。如：基于理性的自适应蚁群算法n 酣、带精英策略的蚁群系统n 射、基 于优化排序的蚁群系统n 钉等。但许多改进措施都是专门针对t s p 问题制定的， 而t s p 问题与q o s 路由问题存在着明显的区别，所以它们并不完全适用于q o s 的路由优化问题。如何针对网络环境的特殊性对蚁群算法进行改，并将其应用于 解决多约束q o s 路由问题是一个值得研究的课题。 1 3 本文研究内容 本文主要研究了基于改进蚁群算法的多约束q o s 路由求解问题，提出了三种 改进的蚁群算法并用于解决o o s 路由问题：一是双向分工蚁群算法，二是动态自 适应蚁群算法，三是结合局部搜索的最大一最小蚁群算法，并对这三种算法在o o s 路由问题上的应用都进行了仿真实验。文章的具体内容安排如下： 第一章是文章的绪论部分，主要介绍了q o s 路由问题产生的背景、研究意义 和国内外的研究现状等。 第二章对q o s 路由问题的概念、分类、网络模型及度量等进行了分析，并讨 论了常用的q o s 路由算法。 第三章详细介绍了蚁群算法的基本原理、算法模型、算法流程等，并对算法 的参数进行了深入分析，讨论了算法的优缺点，最后介绍了几种较为常用的改进 蚁群算法。 第四章提出了三种改进的蚁群算法：双向分工蚁群算法、动态自适应蚁群算 法和结合局部搜索的最大一最小蚁群算法，并将其应用到q o s 路由问题上，给出 了仿真实验。 第五章进行了文章总结和下一步研究工作的展望。 2 2q o s 路由问题 2 1 q o s 的概念描述 q o s ( q u a l i t yo fs e r v i c e ) ，即服务质量，在r f c 2 3 8 4 n 副中用来刻画网络在 传输数据流时要求满足的一系列服务需求，具体可以量化为带宽、延迟、延迟抖 动、丢包率和跳数等性能指标。 ( 1 ) 带宽是指网络在单位时间内传输的数据总数，即数据传送率。它是最 重要的q o s 参数，对其他的q o s 指标有着重要影响。 ( 2 ) 分组丢失率是指在两个时间参考点间传输时丢失的分组( 报文) 数与己 发送的分组( 报文) 总数的比值。 ( 3 ) 端到端时间延迟指业务流的分组从发送端传输到接收端所需的平均经 过时间。 ( 4 ) 抖动即时间延迟的变化，是指同一业务流中不同分组所呈现的时延不 同。 ( 5 ) 费用：信息传输时所消耗的资源或资金 2 2o o s 路由分类 路由选择可分为四类：单播( u n i c a s t ) 、组播( m u l t i c a s t ) 、广播( b r o a d c a s t ) 和选播( a n y c a s t ) 。 ( 1 ) 单播n 引：给定一源节点s 、一目的节点t ，一组服务质量约束c 和一个 可能的最佳化目标，寻找从s 到t 满足c 的最可行路径即为单播。 ( 2 ) 组播引：给定一源节点s 、一组目的节点集r 、一组约束c 、以及可能 的最佳化目标，寻找从s 出发覆盖r 中所有目标节点且满足c 的最可行的树。 ( 3 ) 广播啪1 ：给定一源节点s 、一组约束c 、以及可能的最佳化目标，寻找 从出发覆盖网络中所有其它节点且满足c 的最可行的传播树。 ( 4 ) 选播馏：给定一源节点s 、一组目的节点集a 、一组约束c 、以及可能 的最佳化目标，寻找从s 出发到目的节点集a 中任意一个节点且满足c 的最可行 传输路径。 关于q o s 的单播、组播路由算法的研究己进行了多年，并取得了许多研究成 果，目前主要集中研究两个算法中n p 难问题的启发式或近似算法。广播路由算 法较为简单，主要考虑网络开销和信息扩散程度之间的关系。选播路由算法的研 究才刚刚起步，相关研究成果不多。目前单播路由研究仍然占主导地位，因此， 本文主要研究多约束条件下的单播路由算法。 2 3q o s 网络模型及度量 在q o s 网络模型中，常用的几种约束晗2 1 主要包括带宽、端到端时延、分组丢 失率、抖动和费用，不同的约束具有不同的性质。按照这些性质，q o s 约束可以 分为可加性约束、可乘性约束和最小性约束3 类。 ( 1 ) 可加性约束 包括时延、时延抖动、费用、转发跳数( h o p o c u n t ) 等。例如，一条路径的时 延为从源点到目的地的所有链路时延与结点时延的总和。 ( 2 ) 可乘性约束 包括分组丢失率为可加乘约束，其中链路丢失率为o 与1 之间的实数。在求 解有关可乘性约束的过程中，可以类比参照可加性约束的有关求解方法。 ( 3 ) 最小性约束 例如，带宽为最小性约束，即路径带宽为路径上瓶颈链路的带宽。 求解单个q o s 约束以及多个组合的q o s 约束，其计算的代价是不同的。例如， 求解多重最小性约束的组合可以在多项式时间内完成，而多重可加性约束的组合 通常不能在多项式时间内完成。在q o s 路由选择参数中，带宽与时延是最常用的 参数。 1 2 。5 9 。i i i ，5 三了汰、j 5 3飞 4 i1 ，p ，p 2 1 0 , - ，“ 则对常用的q o s 指标，路径p 的指标可以表示如下晦1 ： ( 1 ) 路径带宽： b ( p ) = m i n ( b i ，肛，) ，其中岛表示节点f 到的可预留带宽。 ( 2 ) 路径时延： 其中d 表示节点f 到j 的时延。 ( 3 ) 跳数： 日( p ) = p “ i = 1 _ ，= l ( 4 ) 路径费用： c o s t ( p ) = c i , j p “ i = l _ ，= l 其中c 表示节点f 到_ ，的费用。 ( 5 ) 设b 为网络中业务请求的带宽，则路径的资源消耗函数可以表示为： 尺( p ) = 砚，_ d ( p ) + s f ( p ) = 日( p ) b d ( p ) + c o s t ( p ) i = i j = l q o s 路由优化问题的关键是：找至i 一条路径p ，在满足带宽和时延的要求 下，消耗尽可能少的网络资源，并使网络的负载尽量均匀分布。 2 4o o s 路由算法 根据网络状态信息的保存方式和路由搜寻方式的不同路由算法可分为两种： 源路由算法和分布式路由算法乜叭。 1 、源路由算法 在这种算法中，网络拓扑结构信息和每条链路的状态信息等全局的网络状态 信息被每一个节点保存。收到路由请求后，源节点就可以根据这些全局信息在本 地计算出一条合适的路由。然后，在选择的路由上传送一个控制包，通知路由上 的每个节点，说明其前驱和后继。中间节点收至哆请求包后，就按照控制包的路径 列表项将包向目的转发。 2 、分布式路由算法 s 肛t 刀芦 玎硝 = ) pi 一 d 在分布式路由中，每个路由器只保存与其相邻路由器的路由信息，这与源路 由算法中每个节点均保存全局的网络状态不同，因此路由表项较小，所占的存储 空间也较小。当收到路由请求后，路由的选择是分布计算完成的。其路径上的各 节点通过交互控制消息，并结合各节点所存储的状态信息来完成路由选择的计 算。 6 3 蚁群算法及其应用 3 1 蚁群算法概述 蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现于 人类的日常生活环境中。这些昆虫的群体生物智能特征引起了一些学者的注意。 意大利学者m d o r i g o ，v m a n i e z z o 等人口幻在观察蚂蚁的觅食习惯时发现，蚂蚁 总是较为容易的找到巢穴与食物源之间的最短路径。经研究发现蚂蚁的这种群 体协作功能是通过一种遗留在其来往路径上的叫做信息素( p h e r o m o n e ) 的挥发性 化学物质来进行通信的。化学通信是蚂蚁经常采用的基本的信息交流方式之一， 在蚂蚁的生活习性中起着非常重要的作用。通过对蚂蚁觅食行为的研究，他们发 现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，使多个路径上的 蚂蚁逐渐聚集到最短的那条路径上来的。 受此启发，两位意大利学者于2 0 世纪9 0 年代初提出了一种新型的智能优 化算法一一蚂蚁算法。该算法最初被用于求解著名的旅行商问题( t r a v e l i n g s a l e s m a np r o b l e m ，简称t s p ) 并获得了较好的效果。上个世纪9 0 年代中期，这 种算法逐渐引起了很多研究者的注意，逐渐成为启发式方法范畴内一个独立的分 支，并多次作为专题在有关国际会议上加以讨论。如1 9 9 8 年、2 0 0 0 年和2 0 0 2 在比利时布鲁塞尔大学连续召开了三届国际研讨会，第四届国际研讨会于2 0 0 4 年9 月在同一地点举行，会上就s i 算法，蚁群算法和群集机器人技术进行了讨 论。历届会议的论文集都是由著名的刊物 l e c t u r en o t e si nc o m p u t e rs c i e n c e 结集出版。2 0 0 2 年，m d o r i g o 和e b o n a b e a u 等在国际顶级学术刊物 n a t u r e l 上发表了蚁群算法的研究综述，从而把这一领域的研究推向了国际学术的最前 沿。目前，该算法已在求解组合优化、函数优化、系统辨识、机器人路径规划、 数据挖掘、网络路由等问题中得到应用并取得了很好的效果。 3 2 蚁群算法原理 3 2 1 蚁群行为描述 仿生学家长期研究发现：蚂蚁虽没有视觉，但运动时会通过在路径上释放出 一种特殊的分泌物信息素来寻找路径口5 。矧。蚂蚁觅食走到一个路口时，如果 该路口没有走过，则它会随机选择一条路径，当然同时它也在该路径上释放信息 素，后面的蚂蚁再走过这个路口时，一般都会选择信息素比较大的路径，这样一 来，正反馈机制就慢慢形成了，正是依靠这种正反馈机制，使得最终整个蚁群找 到最优路径。这里用如图3 1 所示的图例来进一步说明蚁群觅食路径的搜索原 7 理。 fff l jl b i c j 图3 1 自然界中的蚂蚁觅食模拟 图3 1 中，设a 点是蚁巢，d 点为食物源，e f 是一个障碍。由于障碍物e f 阻碍了蚂蚁的通行路线，蚂蚁必须绕过该障碍物，即蚂蚁只能由a 经e 或f 到达 d 点，或由d 点到达a 点。假设每个时间单位里有6 0 只蚂蚁由a 点至i j 达d 点， 有6 0 只蚂蚁由d 到达a 点，蚂蚁经过后留下的信息量为2 。为方便计算，设该 物质停留时间为1 。在初始时刻，由于各条路径上都没有信息素，位于a 点和d 的蚂蚁可以随机选择路径，从统计学的角度可以认为蚂蚁以相同的概率选择b e 、 e c 、b f 、 f c ，如图3 1 ( b ) 所示。经过一个时问单位后，由于b e g 的距离是 b f c 的两倍，所以走b f c 的蚂蚁大约是b e c 的两倍，同样，它们在b f c 上留下的 信息量是b e c 上的2 倍。又过了一段时间，按此规律推算，将有4 0 只蚂蚁由b ， f 和c 到达d 点，如图3 1 ( c ) 所示。随着时间的流逝，蚂蚁将会以越来越大的 概率选择路径b f c ，最终蚁群将会完全选择路径b f c ，从而找到觅食的最优路径。 3 2 2 人工蚁与真实蚂蚁的异同 m d o r i g o 等意大利学者提出的蚁群算法就是模拟以上所述的蚂蚁觅食方 式，为了区别于真实蚁群，我们将蚁群算法中的蚁群称为人工蚁群。蚁群算法中 绝大多数的观点来源于真实的蚂蚁。它们具有的共同特征主要表现如下1 ： ( 1 ) 个体的相互协作。与真实蚁群类似，蚁群算法是利用非阿步的和同步 的全局协作的一个群体( 或种群) 找到所求解问题的最优解。虽然每个人工蚂蚁都 可能找到一个可行解( 即找到一条从蚁巢到食物源的路径是任何一个真实蚂蚁都 可以做到的 ，但是找到最优解必须依靠整个蚁群个体间的相互协作。 ( 2 ) 都利用信息素进行间接通讯。真实蚂蚁通过在它们经过的路径上留下 的化学物质信息素来通讯。人工蚂蚁同样能够释放信息素，蚂蚁也通过当前 路径上的信息素轨迹进行交流协作。这种交流的方式在收集可利用的知识上占据 着重要的位置。其重要的作用在于它使当前蚂蚁所经过的路径周围的环境发生改 8 变，同时也像一个函数似的使整个蚁群所存储的历史信息发生改变。通常，在蚁 群算法中有一个挥发的机制，它像真实的信息素挥发一样随着时间的消逝而改变 路径上的人工信息素。这种挥发现象使蚁群可以“慢慢”的忘记历史，从而能够 不局限于过去而选择出更优的新路径。 ( 3 ) 两者都有着共同的任务。人工蚂蚁和真实蚂蚁都要完成一个相同的任 务：寻找一条从源节点( 蚁巢) 到终点( 食物源) 的最佳路径。真实蚂蚁和人工蚂蚁 两者都没有跳跃性，即它们都只能在相邻节点间逐步的移动。 ( 4 ) 不预测将来状态概率的状态转移策略。人工蚂蚁在节点间移动的求解 方法是利用概率选择来实现的。概率选择只利用当前的有效信息去预测将来的可 能情况，而不能充分利用将来的信息。因此，这一应用策略无论在时间上还是空 间上利用的全部都是现在的有效信息。 另外，人工蚁群还拥有部分真实蚁群没有的特点： ( 1 ) 人工蚁群生活在一个离散的世界中，人工蚁群的移动包括离散状态到 离散状态之间的转换。 ( 2 ) 人工蚁群有一个内在的状态。这种私有的状态包括该蚁群以前行为的 记忆。 ( 3 ) 人工蚁群放置信息素的定时性，是随问题确定的，它不能反映真实蚁 群的行为。例如，在某些求解的例子中人工蚂蚁只有在产生一个解之后才改变信 息素轨迹，并非随时改变。 ( 4 ) 为使系统的有效性得到改善，人工蚁群算法中通常加入一些另外的特 殊性能，比如对将来的预测、优化局部、回逆等。真实蚁群没有这些性能。在很 多应用中人工蚁群可以在局部优化过程中相互交换信息，还有部分蚁群算法实现 了简单的预测。 3 3 蚁群算法模型 。 t s p 问题是典型的组合优化问题，经常用来验证某一算法的有效性，便于与 其他算法的比较。而蚁群算法最先是用于求解t s p 问题的，下面就以t s p 问题为 例来说明基本蚁群算法的实现模型硒朋。 设有玎个城市组成的集合c ；蚂蚁的数量为m ；用嘎，表示两个城市衍口，之 间的距离：( f ，) 表示r 时刻路径( f ，) 上的信息素量，以此来模拟实际蚂蚁的分 泌物。表示路径( f ，) 的能见度，反映由城市f 到城市，的启发程度，一般取 o ) 。蚂蚁k ( k = 1 , 2 ，3 ，m ) 运动过程中，根据各条路径上的信息量决定其转 移的方向，可以用禁忌表t a b u 。( 七= 1 , 2 ，3 ，聊) 来记录蚂蚁k 目前所走过的城市， 9 t a b u 。随着时间推移作动态调整。在搜索中，蚂蚁依据各路径上的信息量及路径 的启发信息来计算状态转移概率。p “( f ) 表示在f 时刻蚂蚁七由城市辟专移到城 p 七“( f ) = l t i , j 口( 慨，夕( f ) z ( t i , u o 。( f ) r l i , u p ( f ) ) 矿j a l l o w e d k u e a l l o w e d k ( f ) 0o t h e r s 市的状态转移概率，其表达式为( 3 一1 ) ： ( 3 - 1 ) 式中，a l l o w e d 。= c t a b u 。) 表示蚂蚁k 下一步允许选择的城市的集合。由 上式可p i , j 与【( f ) “】【( f ) 户】成正比。口为信息启发式因子，反映了蚂蚁在运动 过程中所积累的信息素在蚂蚁运动时所起的作用，其值越小，则该蚂蚁越倾向于 选择其他蚂蚁以前没有经过的路线，蚂蚁之间的协作性越差；矽为启发因子，反 映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中受重视程度，其值越大，则该 状态转移概率越接近于贪心规则，也即蚂蚁选择离它近的城市的可能性就越大。 为了避免残留信息素过多引起剩余的信息量“淹没”启发信息，在每只蚂蚁走完 一步或者遍历完，z 个城市( t g 即一个循环完成) 后，需对残留信息素进行更新。在 t + l 时刻路径( f ，7 ) 上的信息素量按如下规则进行更新： 式中，p 是信息素的残留因子，则卜p 是信息素挥发的系数，为避免信息 的无限积累，p 的取值范围为( 0 ，1 ) ；f ，表示该次循环中路径( i ，) 上的信息 素增量，初始时刻乃= 0 ，r ：是第k 只蚂蚁在这次循环中在路径( f ，) 上留下 的信息素量。 f 驴( f + 1 ) = ( 1 一p ) f 矿( f ) + f 驴 ( 3 2 ) a r 口= ar ； ( 3 3 ) k = i 依据信息素调整方法的差异，m d o r i g o 曾给出三种不同模型乜射，分别为蚁 周系统( a n t c y c l es y s t e m ) ，蚁量系统( a n t - q u a n t i t ys y s t e m ) ，蚁密系统 ( a n t - d e n s i t ys y s t e m ) 。这三种模型的算法流程基本一样，区别仅在于信息素的 调整方法不同，即a r ；，的计算方法有所不同。 ( 1 ) 在a n t d e s i t y 模型中： 叫k ( t , t + 1 ) = 孑黼职蚂篙。倒h 亿臃引l 力 ( 2 ) 在a n t - q u a n t i t y 模型中： 州，= p 黼尼嚣机叭亿眦趴力 ( 3 4 ) ( 3 5 ) ( 3 ) 在a n t c