（计算机应用技术专业论文）蚁群算法的研究及其在网络路由优化上的应用.pdf

摘要 摘要 蚁群算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法，该 算法采用了正反馈并行自催化机制，具有较强的鲁棒性、优良的分布式计算机制、易于 与其它方法结合等优点，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大 的发展潜力，近几年吸引了国内外许多学者对其进行了多方面的研究工作。目前，蚁群 算法已经成为国际智能计算领域中备受关注的研究热点和前沿性课题。 本文首先综述了蚁群算法国内外的研究现状，分析了算法的主要优缺点，并且深入 研究了蚁群算法的基本原理和算法模型，介绍了a c s 算法和m m a s 算法两种改进的蚁 群算法。 然后针对蚁群算法的优缺点，提出了基于t s p 问题的q m a c o 蚁群算法，主要有 三个方面的改进：( 1 ) 针对蚁群算法前期蚂蚁比较盲目，收敛速度慢的缺点，引入了q p s o 算法思想，用q p s o 算法的快速性、全局收敛性作为前期搜索，将q p s o 算法搜索到的 各粒子的历史最优值作为后期蚁群算法的初始信息素分布，这样就使得初期蚂蚁不再盲 目；( 2 ) 针对后期蚁群算法易陷入局部最优化的缺点，引入了多种行为的蚂蚁，充分利用 蚁群算法的正反馈机制以及求解效率高等特征最终求得最优值；( 3 ) 融合了a c s 算法和 m m a s 算法的优点，对蚁群算法进行了适当的改进。并针对t s p 问题进行了仿真实验， 结果表明，q m a c o 算法提高了在解决t s p 问题上的寻优能力。 接着又将q m a c o 算法应用于网络路由问题，分别对单播和组播进行了算法设计， 提出不同的算法模型。并分别进行了仿真实验，实验结果表明了q m a c o 算法在解决 q o s 路由问题上的可行性和有效性。 最后，对本文所做工作进行了总结，并对今后的研究方向进行了展望。 关键词：蚁群算法，q o s 路由，t s p ，单播，组播，多行为，量子粒子群 a b s t r a c t a b s t r a c t a n tc o l o n ya l g o r i t h mi san o v e lc a t e g o r yo fb i o n i cm e t a h e u r i s t i cs y s t e m ，a n dp o s i t i v e f e e d b a c kw i t hp a r a l l e la u t o c a t a l y t i cm e c h a n i s ma r ea d o p t e di nt h i sa l g o r i t h m t h ea n tc o l o n y a l g o r i t h m ，w h i c hh a ss t r o n gr o b u s t i c i t y , e x c e l l e n td i s t r i b u t e dc o m p u t i n gm e c h a n i s ma n di se a s y t oc o m b i n ew i t ho t h e rm e t h o d si no p t i m i z a t i o n h a ss h o w na nt r e m e n d o u sd e v e l o p m e n t p o t e n t i a l i nv a r i o u sc o m b i n e do p t i m i z a t i o nf i e l d sf o ri t so u t s t a n d i n gp e r f o r m a n c e t h e r e s e a r c hq u e s t i o nh a sa b s o r b e dl o t so fs c h o l a r sa th o m ea n da b r o a d i tb e c o m e sai n t e r n a t i o n a l r e s e a r c hf o c u sa n df r o n t s u b j e c ti nc o m p u t a t i o n a l i n t e l l i g e n c ef i e l dn o w a d a y s i nt h i sp a p e r , f i r s tw ei n v e s t i g a t et h er e s e a r c hs t a t u so fa n tc o l o n ya l g o r i t h mi na n da b r o a d ， a n a l y s et h em a j o rm e r i t sa n ds h o r t c o m i n g so fi t ，s t u d yt h ep r i n c i p l ea n dm a t h e m a t i c a lm o d e l o fa n tc o l o n ya l g o r i t h mi nd e p t h ，a n db r i n gi nt w oi m p r o v e da n tc o l o n ya l g o r i t h m so fa c s a l g o r i t h m ( a n tc o l o n ys y s t e m ) & m m a sa l g o r i t h m ( m a x m i na n ts y s t e m ) t h e n ，a i m i n ga tt h ef l a w so fa n tc o l o n ya l g o r i t h m ，q m a c oa l g o r i t h mb a s e do nt 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 ) i sp r o p o s e dt oo p t i m i z et h es y s t e m t h ei m p r o v e m e n t sa r em a i n l yo n 3a s p e c t s ：i ，q p s oa l g o r i t h mi d e ai sb r o u g h ti nt os o l v et h ep r o b l e m sa tp r o p h a s e ，s u c ha s b l i n d f o l da n ts e a r c h i n ga n ds l o wc o n v e r g e n c es p e e d f i r s tw em a k eu s eo ft h er a p i d i t ya n d g l o b a lc o n v e r g e n c eo fq p s oa l g o r i t h mt oc a r r yo ne a r l ys t a g es e a r c h i n g ，t h e nt h el o c a t e de a c h p a r t i c a l e sh i s t o r i c a lo p t i m u mv a l u ei sr e g a r d e da st h ei n i t i a ld i s t r i b u t i o no fp h e r o m o n ei n l a t e rs t a g e t h u st h eb l i n d f o l da n ts e a r c h i n ga tp r o p h a s ec a nb ea v o i d e d i i ，i no r d e rt o o v e r c o m et h ed r a w b a c k o fb e i n gt r a p p e di nl o c a lo p t i m u m ，w ei n t r o d u c em u l t i - b e h a v e d a n t ，f u l l yu t i l i z et h ep o s i t i v ef e e d b a c km e c h a n i s ma n dh i g hs o l u t i o ne f f i c i e n c yt oo b t a i nt h e o p t i m u mv a l u e i i i ，i m p r o v ea n tc o l o n ya l g o r i t h mb ys y n t h e s i z i n gt h em e r i t so fb o t ha c s a l g o r i t h ma n dm m a sa l g o r i t h m a l s os i m u l a t i o ne x p e r i m e n t i sd o n et o t s e t h er e s u l t s d e m o n s t r a t et h a tq m a c o a l g o r i t h mh a v es t r o n go p t i m i z a t i o na b i l i t yi ns o l v i n gt s e f o l l o w e dt h a t ，w ea p p l yq m a c o a l g o r i t h mt on e t w o r kr o u t i n gp r o b l e m ，w o r ko na l g o r i t h m d e s i g no nu n i c a s tr o u t i n ga n dm u l t i c a s tr o u t i n gp r o b l e mr e s p e c t i v e l y , f i n a l l yp r o p o s e d d i f f e r e n tm o d e l so fa l g o r i t h m t h es i m u l a t i o nr e s u l t ss h o wt h a tq m a c oa l g o r i t h mi sr e l i a b l e a n de f f i c i e n ti ns o l v i n gq o s r o u t i n gp r o b l e m t h el a s ti sas u m m i n g u pa n dw ep u tf o r w a r ds o m es u g g e s t i o n sf o rt h ef u t u r es t u d i e s k e y w o r d s ：a n tc o l o n y , q o sr o u t i n g ，t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) ， u n i c a s t ，m u l t i c a s t ，m u l t i - b e h a v e d ，q u a n t u m - b e h a v e dp a r t i c l es w a r mo p t i m i z a t i o n ( q p s o ) 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名：雅浓 日 期 妒譬譬1 j 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：猿亥 导师签名： e l 期： 侧3 f ， 第一章绪论 1 课题的研究背景及意义 第一章绪论 最优化是一个重要的数学分支，也是- - i 7 应用相当广泛的学科，最优化的目的是对 于给出的实际问题，从众多方案中选择出最优方案。在最近的二、三十年中，伴随着计 算机技术的高速发展和优化计算方法的进步，各种优化问题的理论研究发展迅速，新方 法不断出现，实际应用同益广泛。 研究群居性昆虫行为特性的科学家发现，昆虫在群落级上的合作基本上是白组织 的，在许多场合中尽管这些合作可能很简单，但是它们却可以解决复杂的问题，这种由 群居性生物产生出来的一种集体行为，即产生的群集智能引起了包括计算机科学家在内 的众多研究人员的兴趣。 蚁群算法( a n tc o l o n ya l g o r i t h m ) 就是利用群集智能解决优化问题的典型例子。它是继 模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法之后的 一种新型的基于种群的启发式仿生类进化算法。该算法首先由意大利学者m d o r i g o 等 人提出，有时也称为蚁群系统【】。蚂蚁在寻找食物的运动过程中，能在其经过的路径 上分泌一定数量具有气味的被称为信息素的物质来进行信息传递，并指导自己的运动方 向。某一路径上走过的蚂蚁越多，此路径上蚂蚁留下的信息素也越多，则后来蚂蚁选择 该路径的概率也越大，从而更加增加了该路径被选择的可能性。随着时问的推移，蚂蚁 就会找到由蚁巢至0 食物源的最短路径。通过仿真模拟实际蚂蚁行为，蚁群算法在许多相 当困难的组合优化问题的求解中体现了极强的寻优能力和较好的性质。 蚁群算法在过去短短十多年的时间里，己在t s p 问趔2 4 】、分配问题l j 、路径规划问 题f 3 6 1 、网络路由【2 5 1 、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用， 并取得了较好的效果。蚁群算法特别适合求解规模较大的或问题状态随时间变化的组合 优化问题，如著名的t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) ， q u a d r a t i ca s s i g n m e n t p r o b l e m ( q a p ) ，j o b s h o ps c h e d u l i n gp r o b l e m ( j s p ) 等复杂组合优化问题。 尽管目前对蚁群优化算法的研究刚刚起步，一些思想尚处于萌芽时期，但人们己隐 隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此，越 来越多的学者丌始关注和研究蚁群优化算法，初步的研究结果已显示出该算法在求解复 杂优化问题( 特别是离散优化问题) 方面的优越性。虽然蚁群优化算法的严格理论基础尚 未确立，国内外有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种模仿 自然生物的新型系统寻优思想无疑具有十分光明的前景。 1 2 蚁群算法的国内外研究现状 ( 1 ) 模型改进 江南人学硕士学位论文 人们针对不同的具体问题提出了许多不同类型的蚁群算法改进模型，但这些蚁群 算法模型通用性不强，同时基本蚁群算法模型也不能直接应用于解决具体的优化问题。 另外，自然界中的真实蚁群还有许多其他智能行为，因此开发设计不同的蚁群算法模型 是一条新的发展思路。基于此，可从以下几个方面对其模型进行改进。 1 ) 设计一种通用的蚁群算法通用性模型i 5 _ 1 1 】。首次提出蚁群算法是用于解决t s p 问 题，后来的一些蚁群算法改进基本是针对某一类问题而设计的，而现实中的问题干差万 别，并不是每一个问题都能够很容易化归到这样一个拥有高度社会性的蚁群智能模型中， 而且系统高层次的行为是通过低层次昆虫之间简单行为的交互涌现而产生的。在算法的 通用性研究方面，应进一步探索蚁群算法模型的高层次统一机制，并结合复杂性系统展 开研究，提出更通用的蚁群算法模型。蚁群算法的正反馈机制就是一个很好的通用性模 型。 2 ) 研究自然界真实蚁群行为，提出更加智能化的蚁群混合行为模型【12 1 。从深度上 说，虽然蚁群算法是基于蚂蚁觅食行为而发展起来的，但是自然界中的真实蚂蚁觅食机 理并不那么简单，仍有许多借鉴之处，今后应继续挖掘蚂蚁觅食中一些未知的行为，得 到新的蚁群算法模型；从广度上说，蚂蚁等昆虫除了寻找食物之外，还有着任务分配、构 造墓地、建造巢穴、繁衍后代、清除垃圾、保卫领地等多种复杂的社会行为，将蚁群的 这些行为与其觅食行为进行融合、统一，提出更加智能化的蚁群算法混合行为模型，还 有待于从昆虫学、社会学、仿生学、信息学等综合角度对其进行深入研究。 3 ) 对蚁群算法的模型和相关的参数设置进行研究1 ”j 。蚁群算法作为一种新型的智 能算法，其相关的模型尚缺乏严格的数学基础；尤其是蚁群算法模型中，参数较多，且 相关参数的设置在目前的研究中主要是依靠大量的试验获取，参数设置的主观性较大， 缺乏严格的理论说明，因此如何建立蚁群算法参数之间的数学模型，并为各参数的设置 提供准确的理论依据是一个重要的研究课题。 ( 2 ) 理论分析 蚁群算法是一种概率搜索算法，相比确定性算法，从数学角度对其正确性与可靠性进 行证明较困难。自w j g u t j a h r 最先从有向图论的角度对一种改进蚁群算法的收敛性进行 理论证明至今【l4 1 ，人们在其收敛性研究方面已经取得了相当丰富的理论研究成果，但是 这些理论成果都对蚁群算法模型进行相应限制的情况下获得的，从而缩小了其应用范 围。例如w j g u t j a h r 给出了基于图的蚁群算法的收敛性证明，其理论基础是把最优路径上 的信息素强度描述为离散时间的非齐次马尔可夫随机过程，据此进行证明。其局限性在 于，为了符合这一描述，对算法作了较多的条件约束，例如算法中的优化路径仅有一条， 仅在这条最优路径上进行全局信息素更新，不支持局部更新，所有蚂蚁都从唯一的起点 出发。t s t t i e z l e f r f i m d o r i g o 也对蚁群算法的收敛性进行了理论证明i l5 。，但是仅依据信息 素进行分析，分析条件与实际情况也有一些差距。这些文献的共同特点是主要考虑了信息 素的影响，且只考虑了局部或全局信息素更新中的一种情况，关于算法的相关参数( 如启 发信息等) 对算法的影响没有进行分析，实际指导意义不强。朱庆保对蚁群算法模型的收 敛性进行了证明，同时分析了模型中各参数对模型收敛性的影响i l 州，赵霞对m a x m i n 模 2 第一苹绪论 型的收敛性给出了证吲1 。7 j 等等。 这些证明并没有将蚁群算法的理论分析统一到一个共同的框架内。此外，在蚁群算法 的理论研究方面还存在许多问题需要进一步解决，比如初始化参数选择问题、信息素分配 问题、收敛速度问题等，这些均带有经验性和直觉性，至今没有经过严格的数学论证； 同时，连续域蚁群算法的收敛性证明仍存在许多研究空白。蚁群算法的收敛性证明和理论 分析仍然是一个非常具有挑战性的研究方向。 ( 3 ) 并行实现 蚁群算法本身隐含着一定的并行性，单只蚂蚁在一次循环中独立于其他蚂蚁。因此， 本质上蚁群算法应以分布式的协同优化计算方式为特征，而在串行计算机上对蚁群算法 的进行模拟并不能真正体现蚁群算法的本质特征，进一步的研究工作应开展蚁群算法的 并行机实现。并行机实现中往往需要在计算与通信之间寻求一种平衡，蚁群算法的并行 机实现主要集中在最优的并行化。所谓最优的并行化是指使用适量的处理机以最小的代 价使得并行化蚁群算法性能达到当前情况下的最好，或者说当并行化蚁群算法性能不变 时，应竭力减少计算和通信的成本。研究蚁群算法并行机实现问题，需要解决对蚁群算 法并行化过程中并行计算模型的选择以及对蚁群算法的分解、映射方法的改进等问题， 还需要解决蚁群算法并行化过程中粒度处理标准的问题，使并行处理过程具有较好的扩 展性并具有良好的负载均衡性。主要存在以下几个问题： 1 ) 在不考虑处理机之间差异、选择同步更新方法的情况下，如何确定问题规模与加 速比之间的关系：在处理机增多的情况下，如何选择处理机的最佳数目以使计算时间减 少。 2 ) 在不考虑处理机之间差异、选择同步更新方法的情况下，当处理机一定时，如何 选择最优的蚁群规模m 以使效用函数的值最大。 3 ) 在不考虑处理机之间差异、选择异步更新方法的情况下，当问题规模一定时，如 何分配处理机数目和各处理机上的蚁群规模使效用函数值最大。 4 ) 当并行机实现时，局部迭代若干次后需要交换信息。局部迭代次数的增大也会使 得蚁群算法早熟的概率增大，而局部迭代次数减小则会增加通信时间，因此还要努力解 决如何有效避免蚁群算法的过早停滞和减少通信丌销之间的平衡问题。 ( 4 ) 应用领域 从目前公丌发表的蚁群算法相关学术论文来看，大约五分之三的论文是蚁群算法在 不同优化领域中的应用研究成果。虽然蚁群算法的应用范围已经几乎涉及到各个优化领 域，但还存在很多不足，在应用上着重从以下两方面对其进行研究 1 ) 纵向而言，蚁群算法的应用深度还不够。从公开发表的研究成果来看，大部分应 用还仅仅停留在仿真阶段，而且所做的研究大都是在对实际问题实验条件或约束条件进 行简化的前提下进行的。尤其在动态优化问题、随机优化问题、多目标优化问题等方面 研究还需要进一步深化，比如网络路由优化问题属于动态组合优化问题，目前的研究还 处于比较新的阶段，还需要作进一步的深化研究； 2 ) 横向而吉，蚁群算法的应用领域还需要进一步拓宽。不同的应用领域都有许多不 江南人学硕+ 学位论文 同的实际问题，尝试蚁群算法在不同具体问题中的实际应用是今后的一项重要研究内 容。如何抽象实际问题，使蚁群算法的求解更接近工程实际，是广大蚁群算法研究者所 共同关注的一个关键性问题。 当前，蚁群算法及其一些变形的主要应用如表1 1 。 表1 1 算法的应用 t a b 1 1t h ea p p l i c a t i o no f a l g o r i t h m 算法名称 作者算法应用 a c s ( a n tc o l o n ys y s t e m ) t 1 8 】 d o r i g o ，g a m b a r d e l l l a t s p ，v r p a n t n e t l l 9 1 1 2 0 1d ic a r o ，d o r i g on e t w o r kr o u t i n g a n t s l 2 1 1m a n i e z z o ，c a r b o n a r o q a p ，f a p a s ( a n ts y s t e m ) 1 2 2 】c o l o m i ，d o r i g o ，m a n i e z z ot s p ，q a p ，j s p g a m b a r d e l l a ，t a i l l a r d ， h a s ( h y b r i da n ts y s t e m ) 1 2 3 】q a p ，v i 冲，s o p d o r i g o m m a s l 5 1 1 8 1n o m a ss t u t z l e ， t s p ，q a p ，g c p ，s c s ( m a x m i n a n t s y s t e m )h o l g e rh h o o s 3 蚁群算法的优缺点 蚁群算法是受真实蚂蚁行为的启发而提出的，他是群体智能系统中最成功的例子之 一，已被应用到从典型的旅行商问题到数据挖掘问题等许多领域，从而体现出了这种新 思想在求解n p 难题过程的寻优能力。 众多研究已经证明蚁群算法具有很强的发现解的能力，这是因为该算法不仅利用了 正反馈原理，在一定程度上可以加快进化过程，而且本质上是一种并行算法，不同个体 之间不断进行信息交流和传递，从而能够相互合作，有利于发现解。 为了说明蚁群算法的优缺点，引用文献 2 6 中用几种不同的优化算法求解o l i v e r 3 0 问题的实验结果。表1 2 是蚁群算法与特定的用于求解t s p 问题算法的比较，取1 0 次 实验的平均值。表1 3 是蚁群算法与通用型启发算法的比较，也取1 0 次实验的平均值。 4 第一章绪论 表1 2 蚁群算法与特定的用于求解t s p 问题算法的比较 t a b 1 2c o m p a r i s i o no f a n tc o l o n ya l g o r i t h ma n do t h e ra l g o r i t h m si ns o l v i n gt s p 算法b a s i c 2 - o p t l k a n t c y c l e ( 蚁群算法) 4 2 0 n e a rn e i g h b o r ( 最近领域法)5 8 74 3 74 2 1 f a ri n s e r t ( 远插入法)4 2 84 2 l4 2 0 n e a ri n s e r t ( 近插入法)5 1 0 4 9 24 2 0 s p a c ef i l l i n gc u r v e 4 6 44 3 14 2 l ( 空间填充曲线法) s w e e p ( 清扫算法) 4 8 64 2 64 2 0 r a n d o m ( 随机算法) 1 2 1 26 6 34 2 l 上表的“b a s i c ”列为各种基本的未改进的算法所求得的结果；“2 一o p t ”列为各种基本 算法采用边交换法2 - o p t 进行改进后求得的结果；“l k ”列为结合l i n k e m i g h a n 修正法 【2 3 1 对各种基本算法进行改进后所求得的结果。 表1 3 蚁群算法与通用型启发算法的比较 t a b 1 3c o m p a r i s i o no f a n tc o l o n ya l g o r i t h ma n dh e u r i s t i ca l g o r i t h m 算法最优值平均值方差 蚁群算法 4 2 04 2 0 41 3 禁忌搜索算法4 2 0 4 2 0 61 5 模拟退火算法 4 2 24 5 9 82 5 1 由以上比较结果可以看出，蚁群算法的优点主要如下： ( 1 ) 较强的鲁棒性：对基本蚁群算法模型稍加修改，便可以应用于其他问题。 ( 2 ) 分布式计算：蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并 行实现。 ( 3 ) 蚁群算法是一种正反馈算法，路径上的信息素水平较高，将吸引更多的蚂蚁沿 这条路径运动，这又使得其信息素水平增加，这样就加快了算法的进化过程。 ( 4 ) 易于与其他方法结合：蚁群算法很容易与多种算法组合比如与遗传算法结合解 决网络路由问题等【l6 ，以改善算法的性能。 虽然蚁群算法有如上优点，但它毕竟是一种新兴算法，还存在一些缺陷，蚁群算 法存在的主要缺点有：( 1 ) 初期信息素匮乏，蚂蚁比较盲目，收敛速度慢；( 2 ) 算法容易 停滞，陷入局部优化，出现停滞现象( s t a g n a t i o nb e h a v i o r ) 。 1 4 本文主要工作 蚁群算法是一种随机搜索寻优方法，是生物界群体启发式行为，现在已经逐渐应用 到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分 布式系统，隐含的并行性更使之具有极强的发展潜力。从仿真结果来看，它比目前流行 5 江南大学硕十学位论文 的遗传算法、模拟退火算法等有更好的适应性。但是蚁群算法是一种新兴的模拟进化算 法，还缺乏坚实的数学理论基础，算法的参数选择等还有待进一步研究，而且算法本身 的寻优能力也需要进一步提高，包括收敛的速度、收敛结果的最优性等。为了能够提高 算法寻优能力，如何改进算法的一些根本性缺点，仍然很值得研究。 本文的主要研究工作有： ( 1 ) 深入分析了蚁群算法国内外的研究现状和算法的优缺点，研究了蚁群算法的机制 原理、特征和模型； ( 2 ) 针对蚁群算法的根本缺点，提出了基于t s p 问题的q m a c o 算法，主要有三个 方面的改进：1 ) 引入了q p s o 算法思想；2 ) z j l 入了多行为的蚂蚁；3 ) 融合了a c s 和m m a s 算法的优点。针对t s p 问题设计算法模型，并进行了仿真实验，结果表明q m a c o 算 法提高了蚁群算法在解决t s p 问题上的寻优能力； ( 3 ) 将q m a c o 算法应用于q o s 网络路由优化问题，分别对单播和组播路由进行了 研究，针对不同路由方式设计了算法模型，并进行了仿真实验，结果表明了q m a c o 算 法在解决网络路由优化问题上的有效性和可行性。 论文主要内容分为五章，分别如下： 第一章为绪论，介绍了课题的研究背景及意义，分析了蚁群算法的国内外研究现状， 阐述了蚁群算法的优缺点，并对当前课题的研究内容以及本文的主要工作进行了论述。 在第二章中详细介绍了蚁群算法。介绍了蚁群算法的起源和提出，论述了蚁群算法 的基本原理、数学模型、算法实现；最后介绍了a c s 和m m a s 两种改进的蚁群算法。 第三章首先分析了t s p 问题的研究现状，提出了基于t s p 问题的q m a c o 算法的 思想，包括3 个方面，并进行了分析；设计了基于t s p 问题的q m a c o 算法模型以及 算法的实现；最后进行了仿真实验验证，结果表明，在t s p 问题上，改进后的算法提高 了蚁群算法的寻优能力。 第四章首先描述了q o s 网络路由问题的背景、研究现状及意义，介绍了传统蚁群算 法在q o s 路由上的应用，说明了传统蚁群算法在解决q o s 问题上的缺点；介绍了适应 度函数，然后将q m a c o 算法分别应用于q o s 网络路由优化问题，针对单播和组播路 由分别设计了路由算法，进行了仿真实验，验证了q m a c o 算法在解决网络路由优化问 题上的可行性和有效性。 第五章对本文所做工作进行了总结，并对今后的研究方向进行了展望。 6 第二章蚁群算法 2 1 蚁群算法的起源及提出 第二章蚁群算法 2 1 1 蚁群算法的起源 n 2 0 世纪5 0 年代中期创立了仿生学以来，人们从生物进化的机理中受到启发，提出 了许多用以解决复杂优化问题的方法，如遗传算法1 2 7 】、进化规划、进化策略等。蚁群优 化算法( a n tc o l o n yo p t i m i z a t i o na c o ) 是人们对自然界中真实蚁群行为研究而提出的一 种基于种群的模拟进化算法，属于随机搜索算法。它首先由意大利学者m d o r i g o 等人提 出来，他们称之为蚂蚁系统( a n ts y s t e m ) 1 1 。蚂蚁算法充分利用了蚁群搜索食物的过程与 著名的旅行商问题( t s p ) 之间的相似性，通过人工模拟蚂蚁搜索食物的过程( 即：通过个体 之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径) 来求解t s p 问题。像蚂 蚁这类群居昆虫，虽然单个蚂蚁的行为极其简单，但由这样的单个简单个体所组成的蚁 群群体却表现出极其复杂的行为，能够完成复杂的任务。不仅如此，蚂蚁还能够适应环 境的变化，如在蚁群运动路线上突然出现障碍物时蚂蚁能够很快地重新找到最优路径 ( 如图2 - 1 所示) 。 蚁群算法来源于对自然界蚂蚁寻找从蚁巢到食物的最短路径并找到回巢路径方法 的研究，是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生进化算法。蚂蚁算法中 采用有记忆的人工蚂蚁，通过个体之间的信息交流与相互协作来找到从蚁穴到食物源的 最短路径。研究发现，蚂蚁个体之间是通过一种称为信息素( p h e r o m o n e ) 的物质进行信息 传递，从而相互协作，完成复杂任务。蚂蚁在运动过程中能够在所经过的路径上留下该 种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的 运动方向。蚂蚁是自然界中常见的一种生物，蚁群寻找食物时会派出一些蚂蚁分头在四 周游荡，它们总能找到一条从食物到巢穴之间的最优路径。 cd 图2 1 蚂蚁路径示意图 f i g 2 - 1a n tt r a i ls k e t c hm a p 7 江南火学硕+ 学位论文 2 1 2 蚁群算法的提出 蚂蚁在寻找食物时，都是以信息素作为媒介而间接进行信息传递的。当蚂蚁从食物 源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的地面上释放信息素，从而形成一 条含有信息素的路径。蚂蚁可以感觉到路径上信息素的大小，并且以更高的概率选中信 息素浓度最高的路径。 为了研究在人工控制的条件下研究蚂蚁的觅食行为，d e n e u b o u r g 和g o s s 等人设计了 对称二叉桥实验【l 】，使用双桥来连接蚂蚁的蚁穴和食物源。他们在试验中测试了一组不 同比例的r = l l l 2 的双桥，其中r 是双桥两个分支的比例，l l 是较长分支的长度，l 2 是较短 分支的长度。在第一个试验中，桥上的两个分支的长度是相同的( 即r - - 1 ，如图2 2 ( a ) 所 示) 。开始的时候，蚂蚁可以自由的在蚁穴和食物源之间移动。试验的目的就是观察蚂 蚁随时间推移选择两条路径中的一条的概率。试验的最终结果显示，尽管最初蚂蚁随机 选择一条路径，但最后所有的蚂蚁都会选择相同的一条路径。其原因是在刚开始的时候 两条路径上都不存在信息素，因此蚂蚁对这两条路径的选择不存在任何的偏向性，蚂蚁 将以相同的概率在两条路径上进行随机的选择。然而，由于随机波动的出现，选择某一 条分支的蚂蚁数量可能会比另外一条多。正是因为蚂蚁在移动的过程中会释放信息素， 那么当有更多的蚂蚁选择某条分支路径时，则此路径上的信息素将相应的增加，而这种 增加的信息素将所有的蚂蚁都吸引到此路径上，最终所有的蚂蚁都将收敛于一条路径。 而在第二个试验中，我们设定两个分支的长度比例为2 ，即一条分支的长度是另一条分 支长度的2 倍，在这种设置下，观察显示，最终所有的蚂蚁都将收敛于较短路径的分支 上，与第一个试验一致，蚂蚁离开蚁穴寻找食物源，当来到第一个决策点时，所有的蚂 蚁将随机地选择两条路径中的一条，因此两条路径对于蚂蚁来说被选中的概率是相同 的，但是，观察显示经过一段时间后所有的蚂蚁都将集中于较短的路径上，这是因为， 蚂蚁开始时是随机选择路径，但随着时间的推移，较短路径上的蚂蚁走完全程所用的时 间将较短，在相同的时间内，较短路径上的蚂蚁来回于蚁穴和食物源的次数将大于较长 路径上的蚂蚁，因此较短路径上的信息素的总量将大于较长路径上的信息素的总量，而 这种较浓的信息素将会促使更多的蚂蚁再次选择这一分支，这一过程一直进行，直到最 后所有蚂蚁都集中到某一条分支路径上，这种正反馈的过程，实际上就是蚂蚁的自组织 行为。 让人感兴趣的是，如果当蚂蚁在较短的路径上形成比较稳定的信息素的时候即当所 有的蚂蚁都集中于较短路径上，此时再为蚂蚁在蚁穴和食物源之间提供更短的路径，只 有很少的蚂蚁能寻找到这条新添加的路径，大部分蚂蚁都还将困死在先前选择的路径 上。这是因为刚才被蚁群所选中的路径上形成的信息素强度很高，对蚁群具有很强的吸 引力，而新添加的更优的路径信息素很低，因此蚁群无法摆脱高信息素的束缚，从而无 法寻找到更优的路径。 8 第二章蚁群算法 a 、两支分支具有相同的长度b 、两支分支具有不同的长度 a 、d o u b l ee q u a ll e n g t h b r i d g eb 、d o u b l ed i f f e r e n tl e n g t hb r i d g e 图2 2 双桥试验 f i g 2 - 2d o u b l eb r i d g ee x p e r i m e n t a t i o n d e n e u b o u r g 和他的同事提出了一个简单的模型一随机模型1 】【2 1 ，用以描述在双桥试 验中观察得到的蚁群动态行为，在这个模型中，每秒钟有沙只蚂蚁以恒定的速度v c m s 从某方向过桥，并在分支上释放一个单位的信息素。给定短分支长度k 和长分支长度l ， 选中短分支的蚂蚁可以用z = 厶秒通过，而选择了长分支的蚂蚁则需要用厂z 秒钟， 其中，2l i t 。 一只到达决策点f = ( 1 ，2 ) 上的蚂蚁选择分支口= ( s ，) 的概率是儿( n ，其中s ，分别 代表短路径和长路径，儿( f ) 被设置为分支上信息素总量的函数纨t ，这个函数的值与 时刻f 前使用那条分支的蚂蚁总数成正比。例如，选择短分支的概率可用如下公式 表示： 删= 而高 亿， 这个模型假设分支中的信息素总量与过去使用这条分支的蚂蚁数量成正比。换句话 说，在这个模型中并没有考虑任何的信息素蒸发。 描述随机系统演化过程的微分方程如下所示： d 邮d t = yp ，。( f 一，) + p 插( f ) ( 2 2 ) d 口，d t = 沙p ，( r f 。) + 缈p ，( ，) ( 2 3 ) 式2 2 表示：在t 时刻，决策点f 上分支s 的信息素瞬间变量的大小，等于蚂蚁的流 量沙乘以在( 7 一t s ) 时刻选择决策点上短分支的概率，加上蚂蚁的流量乘以在t 时刻选择 决策点，上短分支的概率，其中缈假设为常量。常量7 s 代表的是时间延时，也就是蚂蚁 通过短分支所需要的时间。式2 3 是针对长分支的表达方式。 2 2 蚁群算法的基本原理 蚂蚁在寻食过程中总能找到一条食源和栖息地之间的最短路经，研究发现蚂蚁之间 是通过一种体外激素来相互传递信息的，从而相互协作，完成复杂的任务。蚁群之所以 能保持有序并完成复杂的任务，信息的相互交流起着重要作用，蚂蚁能感知路径上外激 素的存在和强弱，并选择激素强的路径前进，因此，蚁群的具体行为就表现出是一种信 9 江南人学硕+ 学位论文 息的正反馈现象：即当某条路径上的蚂蚁越多，遗留的信息量就越强，后来的蚂蚁选择 此路径的概率也将越大，最终所有的蚂蚁都将收敛于一条最短的路径。蚁群算法正是仿 照蚁群的集体行为而构造的一种智能算法。 3 蚁群算法模型及实现步骤 2 3 1 旅行商问题 旅行商( t r a v e l i n gs a l e s m a np r o b l e m ，简称t s p ) i h i 题是一个典型的易于描述却难以 大规模处理的n p 一难( n p - - h a r d ) 1 口 题。有效地解决t s p 问题具有重要的理论意义和应 用价值，它己成为验证组合优化算法有效性的一个间接标准。旅行商问题可描述如下： 某旅行商打算从住地出发经过他所要去的城市恰好一次，最后返回出发地，问如何安排 其旅行路线，使走的路线的总长度最短。用g = ( 以目表示赋权图，其中y = v 1 ，v 2 ， v n ) 为图的节点集，庐( ( p i j ) ) 为图的边集，d ：_ 【( 墙) ) 表示边距离或费用。把旅行商的 住地和他所要去的城市用节点v 表示，城市之间的道路看成边e ，边上的权等于对应道 路的长d ，即对于城市仆b v ，从v i 到巧的距离记为嘞er + ，这里假设嘞= 碣i ，即 考虑对称t s p 问题。这样就得到一个赋权图，于是旅行商问题就是在赋权图上找一个权 最小的h a m i l t o n 圈。 t s p 可分为对称t s p ( s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ) 和非对称t s p ( a s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ) 两大类，若两个城市往返的距离相同，则为对称 t s p ，否则为非对称t s p ，本文研究对象为对称t s p 。 t s p 的数学描述为： m i n d o x j ( 2 4 ) i j l = 1 ( 2 5 ) 勃= 1 ( 2 6 ) t = l 而蚓sl - 1 ( 2 7 ) ，。j e s 。， 0 ，1 ) f ，= 1 ，2 ，玎f 歹 ( 2 8 ) 其中式2 8 中的决策变量x i j = l 表示商人行走的路线包含从城市f 到城市的路径。 x i j = 0 表示商人没有选择这条路径。目标函数式2 4 要求距离之和最小。式2 5 要求商人 从城市i 出来一次，式2 6 要求商人走入城市j 只有一次，式2 5 ，2 6 只能保证每个城 市经过一次，但并不能保证没有回路。式2 7 要求商人在任何一个城市子集中不形成回 路。其中i 司表示集合s 中的元素个数。 1 0 第二苹蚁群算法 2 3 2 蚁群算法模型 蚁群算法最初是在求解t s p 问题时提出的。现给定一个有珂个城市的t s p 问题， 蚁群中蚂蚁的数量为m ，以此来建立蚁群算法的模型。首先，引入如下记号：d i j ( i ，= 1 ， 2 ，刀) 为城市f 和城市，之间的距离； 6 i ( f ) 为t 时刻位于城市f 的蚂蚁的个数，m = 6 j ( f ) ； 百 ，( ，) 为，时刻在i 连线上残留的信息量； ，7 ，( ，) 为边弧( f ，力的能见度或理解为由城市f 转移到城市k 的启发信息，该启发信 息由要解决的问题给出，在t s p 问题中一般取r i j = 1 d i j ； a 为残留信息的相对重要程度； 为能见度的相对重要程度； ( f ) 表示在，时刻蚂蚁七由位置f 转移到位置的概率。 其次，每个蚂蚁的行为应符合下列规律：1 ) 根据路径上的信息素浓度，以相应的概 率来选取下一步路径；2 ) 不再选取自己在本次循环已经走过的路径为下一步路径，用一 个数据列表( t a b ul i s t ) 来控制这一点；3 )