（通信与信息系统专业论文）蚁群算法的研究及在网络路由优化上的应用.pdf

摘要蚁群算法是一种新型的用于求解组合优化或函数优化问题的元启发式算法，其基本思想是借用生物界的蚂蚁群体觅食机理，将每个蚂蚁看作一个智能体，作为智能群体的蚁群，其觅食过程显现出高度的并行性、正反馈性和鲁棒性以此为基础的蚁群算法也具有这样一些特点。因此，蚁群算法的研究无论从理论上还是实用上，都具有较高的价值。本文首先分析了蚁群算法的原理与模型，介绍了算法的特点和研究现状，通过实验分析了算法中几个关键参数的选择。针对基本蚁群算法的主要缺陷，如收敛速度慢和易于陷入局部最优等问题，将用于求解组合优化问题的基本蚁群算法进行了改进。首先，在概率选择上采用了确定性与随机性相结合的选择原则：其次，由于基本蚁群算法初期时各条路径上的信息素数量相同，导致算法的初期求解速度缓慢，因此提出了分区搜索的思想，使各条路径上的信息素在初期有所差别，加速算法的收敛：第三结合局部与全局信息素调整策略对路径上的信息素进行动态更新；第四，对与信息素相关的一些参数进行了自适应改变；最后，引入遗传算法中的变异思想，以扩大解的搜索空间。针对蚁群算法在求解连续优化问题上相对较弱的特点，提出了基于网格划分的蚁群算法，将传统的用于求解离散空间优化问题的蚁群算法进行了扩展。在应用研究上，分析了网络路由优化问题，研究了基于蚁群算法的口网络q o s 单播路由；讨论了基于蚁群算法的一些其它应用。通过算例对所提出的改进的蚁群算法进行了仿真验证，实验结果表明，本文提出的改进算法是有效和可行的；在连续函数优化上和基于蚁群算法的网络路由优化等应用上也进行了实验仿真。本课题旨在为推进蚁群算法的理论研究和应用研究起到一定的作用。关键词：蚁群算法，信息素，组合优化，连续函数优化，网络路由a b s t r a c ta n tc o l o n ya l g o r i t h m ( a c a ) i san e wk i n do fm c t a - h e u r i s t i ca l g o r i t h m sf o rs o l v i n gc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m so rc o n t i n u o u sf u n c t i o no p t i m i z a t i o np r o b l e m s , a n di tb o r r o w st h em e c h a n i s mo fa n tc o l o n y sf o r a g e ，a n de v e r ya n ti sl o o k e df o ra sa l la g e n t n ec h a r a c t e r i s t i co fp a r a l l e l p o s i t i v ef e e d b a c ka n dr o b u s ti ss t r o n g l ys h o w e dd u r i n ga n tc o l o n y sf o r a g e , a c aa l s oh a st h e s ec h a r a c t e r i s t i c s ，s ot h er e s e a r c ho ft h e o r ya n du t i l i t yo f a c a h a sg r e a tm e r i t t h i sp a p e ra n a l y z e st h eb a s i ct h e o r ya n dm o d e lo fa c a ；i n t r o d u c e st h ef e a t u r e so fa c aa n di t sr e s e a r c hs t a t e ；s e l e c t ss o m ek e yp a r a m e t e r s v a l u eo fa c ab ys i m u l a t i o n s t h es l o wc o n v e r g e n c ea n ds t a g n a t i o nb e h a v i o ra r et h em a i nd r a w b a c ko fb a s i ca c a , s ow ep r o p o s es o m em e t h o d st oo v e r c o m et h e s es h o r t c o m i n g s f 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 cs 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 ，p r o p o s e st h ei d e ao fs u b a r e a ss e a r c h i n gt op r o d u c ed i f f e r e n tq u a n t i t yo fp h e r o m o n ei ne v e r yr o u t e ，a c c e l e r a t e st h ec o n v e r g e n c eo fa l g o r i t h mq u i c k l yi ni n i t i a lp h a s e ；t h i r d ，c o m b i n e sw i t hl o c a la n dg l o b a lp h e r o m o n e sa d j u s t m e n tt ou p d a t er o u t e sp h e r o m o n ed y n a m i c a l l y ；f o u r t h ，a l t e rs o m ec o r r e l a t i v ep a r a m e t e r so fp h e r o m o n ea d a p t i v e l y ；l a s t ，t h ei d e ao fm u t a t i o ni su s e dt oe x t e n ds e a r c h i n gs p a c e p u t sf o r w a r dan e wa c ab a s e do ng r i dd i v i s i o nt oo v e r c o m et h ew e a k n e s so fa c ai ns o l v i n gc o n t i n u o u sf u n c t i o no p t i m i z a t i o np r o b l e m ，a n de x p a n d st h ed i s c r e t es p a c et ot h ec o n t i n u o u ss p a c e f o rt h er e s e a r c ho fa p p l i c a t i o n ，a 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 ，s t u d i e so p t i m i z a t i o no fq o sr o u t i n gb a s e do na c ai ni pn e t w o r k ；s o m eo t h e ra p p l i c a t i o n su s e db ya c aa r ea l s ob e e nd i s c u s s e d 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 ei m p r o v e da c ap r o p o s e d r e s u l t so fs i m u l a t i o n sd 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 ；s i m u l a t i o n sa r ea l s om a d ef o rc o n t i n u o u sf u n c t i o no p t i m i z a t i o na n dn e t w o r kr o u t i n go p t i m i z a t i o nb a s e do na c ae t c t h i sp a p e rc o u l dp r o m o t et h er e s e a r c ho ft h e o r ya n da p p l i c a t i o no fa c a k e yw o r d s ：a n tc o l o n ya l g o r i t h m ( a c a ) ，p h e r o m o n e ，c o m b i n a t o r i a lo p t i m i z a t i o n ，c o n t i n u o u sf u n c t i o no p t i m i z a t i o n ，n e t w o r kr o u t i n gi l学位论文独创性声明：本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。论文作者( 签名) ：睦堕鱼力哨年弓月z g 日学位论文使用授权说明河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河海大学研究生院办理。论文作者( 签名) ：匪堡建z 呓年弓月? g 日河海大学颂士学位论文第一章绪论第一章绪论自然界的许多自适应优化现象不断地给人类以启示：生物体和自然生态系统可以通过自身的演化就使许多在人类看起来高度复杂的优化问题得到完美的解决。近十几年来一些与经典的数学规划原理截然不同的、试图通过模拟自然生态系统机制求解复杂优化问题的新型智能计算方法相继出现，大大丰富了最优化技术，也为那些传统最优化技术难以处理的组合优化问题提供了切实可行的解决方案。这些通过模拟人、自然及其它生物种群的结构特点、进化规律、行为方式及思维结构而发展起来的，用于求解各类规划优化问题的计算技术和方法称为元启发式( m c t a h e u r i s t i c )算法，如遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、模拟退火算法( s i m u l a t c da n n e a l i n g ，s a ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、禁忌搜索算法( t a b us e a r c h ，t s ) 、蚁群算法( a n tc o l o n y a l g o r i t h m ，a c a ) 等。元启发式算法已经在一些经典的组合优化问题的求解和实际运用中显示出了强大的生命力和潜力。它具有与传统优化算法( 如数学规划、动态规划等) 不同的如下特点：一、它是一类不确定性的方法。不确定性体现了自然界的生理机制，并且在求解某些特定问题方面优于确定性算法。二、它是一类概率型的全局最优搜索方法。非确定性算法的优点在于算法能有更多机会求得全局最优解。三、它在优化过程中不依赖于优化问题本身的严格数学性质，如连续性、可导性及目标函数和约束条件的精确数学描述。四、它是一类基于多个智能体的智能算法。各智能体通过自学习不断提高自身的适应性，同时通过相互之间的协作来更好地适应环境。五、它具有潜在的并行性。搜索过程不是从一个点出发，而是同时从多个点同时进行。这种分布式的多个智能体的协作过程是异步并发进行的，分布并行模式将大大提高整个算法的运行效率和收敛速度。本文所研究的内容就是一种新型的启发式仿生算法一蚁群算法，及其在最优化问题方面的应用研究。1 1 最优化问题及其分类最优化问题有三个基本要素：变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数。最优化问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间内的连续变量，而组合优化的对象是解空间中的离散状态。下面分别加以介绍。蚁群算法的研究及在刚络路由优化上的应用函数优化问题通常可描述为：令s 为r “上的有界子集( 即变量的定义域) ，5 根为n 为实值函数，所谓函数，在s 域上全局最小化就是寻求点工。s ，使得f ( x 。) 在s 域上全局最小，即橱e s ：f ( x 。i 。) s f ( x ) 。组合优化问题通常可描述为：令q 。 s i , s ：，s 。) 为所有状态构成的解空间，c ( s ；) 为状态s ，对应的目标函数值，要求寻找最优解s + ，使得协j q ，c ( s ) im i n c ( s ，) 。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。典型的组合优化问题有旅行商问题( 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 ) 、加工调度问题( s c h e d u l i n gp r o b l e m ，如f l o w s h o p ，j o b s h o p ) 、0 - 1 背包问题( k n a p s a c kp r o b l e m ) 、装箱问题( b i np a c k i n gp r o b l e m ) 、图着色问题( g r a p hc o l o r i n gp r o b l e m ) 、聚类问题( c l u s t e r i n gp r o b l e m ) 等。最优化的主要内容是研究最优化问题的计算方法，把可解决某个问题的计算方法称为适用于该问题的算法。算法的性能比较通常是基于一些称为b e n c h m a r k 的典型问题展开的。优化问题的一些b e n c h m a r k 问题见附录。1 2 算法的复杂性与n p 问题1 2 1 算法的复杂性由于有些优化算法所需的计算时间和存储空间难以承受，因此算法可解的问题在实践中并不一定可解。如对称t s p 问题( 规模为) ，可能路径为( _ 1 ) ! 2 ，若以路径比较为基本操作，则需1 ) t 2 1 次基本操作。对于每秒执行一百万次操作的计算机，当n = 2 0 时就需1 9 2 9 年才能找到最优解。表1 1 中列举了一些复杂性函数随增加所需计算时间的比较。由上可知，我们必须对计算复杂性理论有所了解，这也是最优化的理论基础。只有了解所研究问题的复杂性，才能有针对性的设计和改进算法，进而提高优化效率。表1 1 增加n 的过程中几种复杂性函数计算时间的比较泌nn l o g nn 22 。n !n = 1 01 0 n s1 0 n s1 0 0 n s1 0 “s3 6 m sn = 3 03 0 n s4 4 3 n s9 0 0 1 1 s1 1 s8 4 1 0 ”世纪n = 1 0 0l o o n s2 0 0 n s1 0 “s4 0 世纪3 0 1 0 世纪河海大学硕l + 学位论文第一章绪论算法对时间和空间的需要量称为算法的时间复杂性和空间复杂性【”。问题的时间复杂性是指求解该问题的所有算法中时间复杂性最小的算法的时间复杂性，问题的空间复杂性也可类似定义。算法或问题的复杂性一般表示为问题规模，l ( 如t s p 问题中的城市数) 的函数，时间复杂性汜为踊z ) ，空间复杂性记为s o ) 。在算法分析和设计中，沿用实用性的复杂性概念，即把求解问题的关键操作，如加、减、乘、比较等运算指定为基本操作，算法执行基本操作的次数则定义为算法的时间复杂性，算法执行期间占用的存储单元则定义为算法的空间复杂性。通常说的算法复杂性是指时间复杂性，它的衡量指标是复杂性函数鼬) ，其定义为对规模为n 的实例( 所谓实例是指给描述问题特性的所有参数都赋予了具体值时所得到的例子，它是问题的特殊表现) 需要执行基本运算总次数的一个上界。在分析算法复杂性时，可以求出算法的复杂性函数，即) ，也可用复杂性函数的主要项的阶0 0 叹n ) ) 来表示，如5 “+ 3 “+ n 1 册= o ( 5 “) ，n l o g n + 5 a = o ( r a o g a ) 。若算法的时间复杂性为丁u ) = 0 ( p ( n ) ) ，且p 0 ) 是，l 的多项式函数，则称该算法为多项式( p o l y n o m i a j ) 时间算法，这样的算法是有效的。时间复杂性不属于多项式时间的算法统称为指数( e x p o n e n t i a l ) 时间算法，这样的算法是无效的。因为，对于任何指数的芦 o 和口 1 ，当n 足够大时，行，t g “，所以任意一个多项式算法都比任何指数算法更为有效。1 2 2 n p 问题按照计算复杂性理论研究问题求解的难易程度，可把问题分为p 类、n p 类、n p 完全类和n p 难问题【2 】。p 类问题是指具有多项式时间求解算法的问题类。在多项式时间内能被不确定图灵机f r u r i n gm a c h i n e ) 解决的判定问题的集合叫做n p ( n o n - d e t e r m i n i s t i cp o l y n o m i a l ) 类问题。n p 类问题可以在多项式时间里检验，许多组合优化属于n p 类问题。若问题a n p ，所有n p 问题都可以通过多项式时间转换为a ，则a 称为属于n p 完全类0 盱c o m p l e t e ，即n p q 。n p 完全问题必然属于n p 类，其含义是只要有一个n p 完全问题存在多项式时间算法，则整个n p 类问题都存在多项式算法。若所有的n p 类问题都可以转换为问题，则称为n p 难问题( n p h a r d ) 。是n p 难问题不要求属于n p 类。n p 完全问题一定是n p 难问题，但n p 难问题不一定是n p 完全问题，比如说旅行商问题便是不属于n p 完全的n p 难问题。四者之间的关系见图1 _ 1 。蚁群算法的研究及在网络路由优化上的应用pn pn f cn p - h a r d圈1 1 四类问题的关系图一些重要的组合优化问题实际上是n p 难问题，精确求解此类问题的一类方法都是基于对可行解进行穷举，因此，在最坏的情况下，需要指数级的操作步骤，从另一方面来说，在现实世界的应用中，当问题规模n 变得越来越大时，任何指数级算法都不可能有实际的用处。因此，这类问题的求解需要兼顾质量和求解时间来设计好的算法。一种方法是设计平均性态良好的概率算法，这种算法在多项式时间里几乎总是产生最优解，但在最坏的情况下，仍然需要指数界的时间。另一种方法是设计求近似最优解的算法，这种算法采用的策略、规则和启发方式简单、直接，而且对于某些问题产生了意想不到的好结果。因此，随着指数级的算法在大规模问题上的失效，人们就退而求其次，转向寻求近似算法或启发式算法，经过几十年的努力，取得了相当的进展。1 3 几种主要的元启发式优化算法用于解决复杂组合优化问题的算法，从最初的构造性方法( 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 ) ，再发展到现在的元启发式优化算法，这一过程是和信息交换技术的发展相平行的。这类优化算法是从生物进化的机理中发展而来的，吸收了许多看似无关的其他学科( 如生物学、物理学、人工智能等)中的概念和方法，因其高效的优化性能、无需问题的特殊信息、应用领域广泛等优点，成为解决n p 问题的有效的通用算法。这里，主要对启发式优化算法中的遗传算法、模拟退火算法和蚁群算法做一简单介绍。1 3 1 遗传算法自然界有两类促进其发展的要素：自然选择和变异。自然选择使更强的个体得到更好的发展但却惩罚弱者，即优胜劣汰；变异产生随机因素从而使新的个体能够出现。来自大自然机制的这一启发式模拟进化算法一遗传算法也有同样的情况：选择是优化的基本思想，而变异则是非确定型搜索的基本思想。旱在i 9 6 2 年，j h o l l a n d 教授就提出了遗传算法的基本思想，随后经过不断的d日海大学硕士学位论文第一章绪论发展，形成了基本的遗传算法的数学框架，并在其1 9 7 5 年出版的专著中给予了介绍【3 】3 。后来，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 ) 来评价其优劣。在每一代进化过程中，通过复伟e j ( r e p r o d u c t i o n )操作，按一定的概率，随机选出部分染色体，然后通过交1 3 l ( 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 i m p t eg e n e t i ca 1 9 0 f i t h m ，简称s g a ) ，其基本步骤如下1 4 】：步1 编码：为了便于遗传算法操作，给出一种编码形式，使问题解空间中的解数据与遗传算法中遗传空间的基因型串结构数据( 通常采用二进制串形式) 相对应。比如，若可行点工为行维实向量，则每个分量用一个二进制串表示，从而可行点工的编码由，1 个二进制串构成；步2 种群初始化：给定种群规模大小，在可行域上随机产生个初始解( 染色体) ，组成供遗传操作作用的初始种群：步3 染色体评价：采用某种准则( 或函数) 对种群中每个个体( 染色体) 进行评价( 评价函数值又称为适应度) ，以判断其优劣。若满足终止条件，则输出最优解( 即适应度高的染色体) ；否则，转向步4 ：步4 选择( 复制) ：根据染色体的适应度值，按定方法，如赌轮( r o u l e t t e w h e e l )法，从当前种群中选择优良( 适应值高) 的个体组成父代；步5 交叉和变异：交叉是以一定概率m 从父代选出部分个体( 染色体) 随机配对，并交换配对染色体上部分信息( 如将表示染色体的二进制字符串上某些位上的数字进行交换) ；变异是按位进行，以很小概率砌使得某个染色体上的莱位发生变异( 即。一1 或1 一o ) 。这样通过遗传操作便形成新的种群，即新一代。转向步3 。蚁群算法的研究及在网络路由优化上的应用遗传算法通过简单的编码技术表示复杂的结构，从多个初始解出发，通过遗传操作在复杂空间上进行快速搜索，有效地避免了局部最优解的产生。遗传算法具有智能式搜索、渐进式优化、易获得全局最优、适于并行计算和通用性强等优点，己被成功地应用于许多理论和实际问题中，如机器学习、布线路径设计、自适应控制、图像处理、工业优化控制等。1 3 2 模拟退火算法模拟退火算法的思想最早是由m e t r o p o l i s 等提出的【”，1 9 8 3 年k i r k p a t r i c k 等将其用于组合优化。s a 算法是基于m o n t ec a r l o 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法的基本思想是：s a 由某一较高初温开始，结合概率突跳特性的m e t r o p o l i s 抽样策略在解空间中随机寻找目标函数的全局最优解，伴随温度参数的不断下降重复抽样过程，在局部优解中能概率性地跳出并最终趋于问题的全局最优解。固体的物理退火过程由三个部分组成：加温过程、等温过程和冷却过程。设组合优化问题的一个解f 及其目标函数兵f ) 分别与固体状态f 及其能量e f 等价，令随算法进程递减其值的控制参数t 担当固体退火过程中的温度t 的角色，则对于控制参数f 的每一取值，算法持续进行“产生新解判断一接冕舍弃”的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程，也就是执行了一次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 趋于零时，最终求得组合优化问题的整体最优解。由于固体退火必须“徐徐”降温，才能使固体在每一温度下都达到热平衡，最终趋于能量最小的基态，控制参数的值也必须缓慢衰减，才能确保模拟退火算法最终趋于组合优化问题的整体最优解集。模拟退火算法由与m e t r o p o l i s 准则对应的转移概率只：j f 椎一j ) =1 ，兰| ，( ，) sf ( i )e x p ( 盟掣庙则确定是否接受从当前解f 到新解，的转移。t 表示控制参数。开始让t 取较大的值( 与固体的溶解温度相对应) ，在进行足够的转移后，缓慢减少t 的值( 与固体退火时“徐徐”降温相对应) ，如此重复，直到某个停止准则时算法终止。模拟退火算法的一般步骤可描述为：67 可海大学硕士学位论文第一章绪论步1 给定初始温度、降温次数，随机产生初始状态h ( 初始解) 等；步2 生成h 的邻域状态h7 ，并计算两种状态下目标函数值的变化；步3 按接受概率置换h 为h ；步4 重复第2 和第3 步直到停机条件满足，输出结果。模拟退火算法是一种串行优化算法，每步仅随机尝试当前状态邻域中的一个状态，同时通过控制“温度”来控制状态更新概率，从而在搜索过程中具有避免局部极小的能力并最终趋于全局最优。它的概率性的扰动能使之跳出局部极值点，故而得到的解常常很好。模拟退火算法具有质量高、初值鲁棒性强、通用易实现的优点，克服了传统优化方法易于陷入局部最优和过分依赖初值的缺点。但是，为寻到最优解，算法通常要求较高的初温、较慢的降温速率、较低的终止温度以及各温度下足够多次的抽样，因而模拟退火算法往往优化过程较长，这也是s a 算法最大的缺点。目前，该算法已在生产调度、控制工程、机器学习、图像处理等领域中得到广泛应用。1 3 3 蚁群算法蚁群算法是受到自然界的蚁群行为的研究启发而提出的，是一种用于求解组合优化问题的新型的模拟进化算法，该算法首先由意大利学者m d o r i g o 等人提出，有时也称之为蚁群系统【6 】r ”。蚂蚁在寻找食物的运动过程中，能在其经过的路径上分泌一定数量具有气味的被称为信息素( p h e r o m o n e ) 的物质来进行信息传递，并指导自己的运动方向。某一路径上走过的蚂蚁越多，此路径上蚂蚁留下的信息素轨迹( t r a i l ) 也越多，则后来蚂蚁选择该路径的概率也越大，从而更增加了该路径被选择的可能性。随着时间的推移，蚂蚁就会找到由蚁巢到食物源的最短路径。通过仿真模拟实际蚂蚁行为，蚂蚁算法在许多相当困难的组合优化问题的求解中体现了极强的寻优能力和较好的性质。在后续章节中将详细介绍和分析研究蚁群算法及其应用。1 4 本文的主要工作蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现已陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。但是蚁群算法毕竟是一种新兴的模拟进化算法，还缺乏坚实的数学理论基础，算法的参数选择、收敛性等还有待进一步研究，算法的最优停止条件也是值得研究的地方。目前，关于算法的参数选择大都与具体问题的应用结合，通过实验进行确定：而算法的停止条件则采用固定循环次数或当进化不明显时停止迭代作为条件。本文蚁群算法的研究驶任网络路由优化上的应用的主要工作有：探讨了蚁群算法的原理、特点及功能；对基本蚁群算法的有关参数的合理选择进行实验分析；提出了相应的改进策略，并通过大量的仿真实验，验证了改进算法的有效性，提高了原有算法的效率和收敛速度；将离散空间的蚁群算法加以扩展，研究了连续空间优化问题；分析了基于蚁群算法的网络路由优化等。在第二章中详细介绍了蚁群算法。论述了蚁群算法的原理、数学模型、特点和算法步骤；举例说明了蚁群算法的迭代过程：对算法的优缺点进行了分析，最后介绍了算法的研究进展。在第三章中对基本蚁群算法的一些参数的合理选择进行了实验仿真，得出了参数的基本选择范围；针对基本算法的收敛速度缓慢、容易过早的陷入局部最优等不足之处提出了一些改进策略，主要从以下几个方面进行：第一、从概率选择规则上：第二、从信息素初始分布上；第三、从信息素的挥发机制上；第四、与其它方法相结合。提出了分区搜索和变异的思想。改进的主要目的是提高算法的收敛速度和全局搜索能力，在经典的组合优化问题t s p 上通过一些算例进行验证，实验结果是令人满意的。最后对蚁群算法在连续空间优化问题进行了初步研究，提出了基于网格划分的蚁群算法，实验结果较好。在第四章中在介绍网络路由优化相关知识的基础上，将蚁群算法应用于口网络的路由优化中。首先讨论了基本路由算法和路由协议；接着通过例子说明了蚁群算法在网络路由优化中的应用；最后分析了基于蚁群算法的口网络q o s 单播路由。在第五章中将蚁群算法的实际应用加以推广。主要讨论了两类实际问题：立体仓库固定货架拣选路径的优化问题和电力系统配电网网络规划问题。针对具体问题提出相应的数学模型，并通过算例加以验证，表明算法在求解这些问题上是可行的。河海大学硕土学位论文第一帝蚁群算法的原理与模型第二章蚁群算法的原理与模型组合优化问题很早就引起人们的兴趣，但是许多组合优化问题都是n p 难( n p h a r d ) 问题，对于此类问题至今尚无很好的解析算法，一般采用启发式算法来解决。自从仿生学创立以来，科学家们就先后从生物进化的机理中发展了适合于现实世界复杂问题优化的启发式模拟进化算法，如：模拟退火算法( s a ) 、遗传算法( g a ) 、进化算法( e a ) 、进化规划( e p ) 、禁忌搜索算法( t s ) 、蚁群算法( a c a )等。它们的出现为解决n p 难问题提供了一条新的途径。蚁群算法( a c a ) 是2 0 世纪9 0 年代才提出的一种新型的模拟进化算法，它是由意大利学者m d o r i g o 等人首先提出来的【8 】【9 】1 1 0 】，称之为蚁群系统( a n tc o l o n ys y s t e m ) 。用该算法求解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 ) 旅行商问题【1 0 1 1 1 1 、q a p ( q u a d r a t i ca s s i g n m e n tp m b l e m ) 分配问题【1 2 】、j s p o o b 。s h o ps c h e d u l i n gp r o b l e m ) 调度问题【8 1 等，取得了一系列较好的实验结果。虽然研究时间不长，但是初步研究已显示算法在求解复杂优化问题( 特别是离散优化问题) 方面具有一定的优势，表明它是一种很有发展前景的方法。蚁群算法的主要特点是：正反馈、分布式计算。正反馈过程使得该方法能较快地发现问题的较好解；分布式易于并行实现，与启发式算法相结合，使得该方法易于发现较好解。2 1 蚁群算法的原理蚁群算法是模仿真实世界蚁群的行为而提出的。为了说明蚁群算法的原理，先从蚂蚁搜索食物的过程谈起。像蚂蚁、蜜蜂等群居昆虫，虽然单个昆虫的行为极其简单，但是由单个简单的个体所组成的群体却表现出极其复杂的行为。真实的蚂蚁在没有视觉的情况下，能够找到从食物源到蚁巢的最短路径；同时，它们能适应环境的改变，例如，由于原最短路径中出现障碍物时能够重新发现一条新的最短路径。究其原因是因为蚂蚁个体之间是通过一种称为信息素( p h e r o m o n e 或s t i g m e r g y t l 3 】1 的物质进行信息传递的。蚂蚁在运动过程中，能够在它所经过的路径上留下该物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流进行路径的最优选择从而达到搜索食物的目的。真实蚂蚁寻找最优路径的过程可用图2 1 来描述。在a 图中，蚂蚁在到达分岔口时将决定是往上一条路径走还是往下一条路径走。因为它们没有关于最好路径的线索，所以此时的选择是随机的。从统计的角度它们中有一半的蚂蚁向上走，另一半的蚂蚁向下走，这是按相同概率选择的。这样的选择对从左到右移动的蚂蚁( 图蚁群算法的研究及在网络路由优化上的应用中标示为l 1 、l 2 ) ，还是对从右到左移动的蚂蚁( 图中标示为r 1 、r 2 ) 都是一样的。假定所有的蚂蚁以同样的速度移动，图b 和图c 显示的是随后所发生的情况。虚线表示蚂蚁分泌在路径上的信息素，线条数与信息素的数量成正比。因为下一条路径比上一条路径短，按概率将有更多的蚂蚁经过它，因此，下一条路径上的信息素也就积累地更多。经过一段时间两条路径上的信息素数量的差距增大，如图d ，这样新来的蚂蚁将更有可能选择下一条路径，因为在分岔口它们能够觉察到在下一条路径上有大量的信息素。这个过程反复进行，形成了信息正反馈。最终所有的蚂蚁将选择下一条路径，也就是最短路径。ac日图2 1 真实蚂蚁寻找最优路径的过程d蚁群算法正是对上述蚂蚁运动行为的研究而提出的，算法中的蚂蚁称为“人工蚂蚁”。下面通过例子来具体说明蚁群算法的原理。如图2 2 所示，设a 是蚁巢，e是食物源，h c 为一障碍物，由于障碍物的存在，蚂蚁只能经由h 或c 到达e ，或者由e 到达a 。各点之间的距离如图中所示。设每个时间单位有3 0 只蚂蚁由a 到达b ，有3 0 只蚂蚁由e 到达d ，蚂蚁经过后留下的信息素溶度为1 。为方便，设信息素停留时间为1 。在初始时刻t = 0 时，由于路径b h 、b c 、d h 、d c 上均无信息素存在，位于b 和d 的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择b h 、b c 、d h 、d c 。由此可得：t = l 时刻：3 0 只蚂蚁在b ，3 0 只蚂蚁在d ：t = 2 时刻：1 5 只蚂蚁在d ，1 5 只蚂蚁在b ，3 0 只蚂蚁在h ；每条路径上信息素浓度的分布：a b = 3 0 ，e d = 3 0 ，b h = 1 5 ，d h = 1 5 ，b c = 3 0 ，c d = 3 0 。可见，此时b c d 路径上的信息量是b h d 路径上的两倍。则将各有2 0 只蚂蚁由b 和d 到达c ，各有1 0 只蚂蚁由b 和d 到达h 。这样一来，随着时间的推移，蚂1 0河海大学硕士学位论文第二章蚁群算法的原理与模型蚁就会以越来越大的概率选择b c d 路径，直到最终选择b c d 路径，实现寻优过程。由此可见，蚂蚁之间的信息交换是一个正反馈的过程。heeet=l时刻t=2时刻图2 2 蚁群算法的原理示意图c每只人工蚂蚁在候选解的空间中独立地搜索解，并在所寻得的解上留下一定的信息量。解的性能越好蚂蚁留在其上的信息量越大，而信息量越大的解被再次选择的可能性也越大。在算法的初始阶段所有解上的信息量是相同的，随着算法的推进较优解上的信息量逐渐增加，算法最终收敛到最优解或近似最优解。由上述分析可知，人工蚂蚁具有记忆功能，能够记忆已经访问过的节点；人工蚂蚁并不是完全盲目的，而是具有一定的视觉，在选择下一条路径的时候能够按一定的规则进行：人工蚂蚁的生活环境的时间是离散的。2 2 蚁群算法的模型及实现步骤2 2 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 ) 问题是一个典型的易于描述却难以大规模处理的n p 难( n p h a r d ) i a 题。有效地解决t s p 问题具有重要的理论意义和应用价值，它己成为验证缎合优化算法有效性的一个间接标准。旅行商问题可描述如下：某公司的商品推销员打算从住地出发经过他所要去的城市恰好一次，最后返回出发地，问如何安排其旅行路线，使走的路线的总长度最短。用g = ( v ，e ) 表示赋权图，其中v = v l ，v 2 ，h 为图的节点集，e = 嘞) ) 为图的边集，d = ) 表示边距离或费用。把推销员的住地和他所要去的城市用节点v 表示，城市之间的道路看成边e ，边上的权等于对应道路的长d ，即对于城市f i 、v ，从v f 到竹的距离汜为d q r + ，这里假设幽= 幽，即考虑对称t s p 问题。这样就得到一个赋权图，于是旅行商问题就是在赋权图上找一个权最小的h a m i l t o n 圈。肆肆串蚁群算法的研究及在网络路由优化上的应用2 2 2 蚁群算法的模型蚁群算法最初是在求解旅行商问题时而提出的。现给定一个有n 个城市的t s p问题，蚁群中蚂蚁的数量为m ，以此来建立蚁群算法的模型。首先，引入如下记号：d 。( i j = l ，2 ，i ) 为城市i 和城市j 之间的距离；b i ( t ) 为r 时刻位于城市i 的蚂蚁的个数，川= 6 t ( f ) ；r 。， 为t 时刻在牙连线上残留的信息量；，7 。， 为边弧q j ) 的能见度( v i s i b i l i t y ) 或理解为由城市i 转移到城市，的启发信息，该启发信息由要解决的问题给出，在t s pf o l 题* - - 般取玑= l 由；a 为残留信息的相对重要程度( a = 0 ) ；卢为能见度的相对重要程度( 芦- - o ) ；p ：表示在t 时刻蚂蚁k 由位置f 转移到位置f 的概率。其次，每个蚂蚁的行为应符合下列规律；1 ) 根据路径上的信息素浓度，以相应的概率来选取下一步路径：2 1 不再选取自己本次循环已经走过的路径为下一步路径，用一个数据列表( t a b ul i s 0 来控制这一点；3 1 当完成了一次循环后，根据整个路径长度来释放相应浓度的信息素，并更新走过的路径上的信息素浓度。蚂蚁开始搜索的初始时刻，各条路径上分布的信息量相等，即f ；f ( o ) = c ( c 为常数) 。蚂蚁k ( k = 1 ，2 ，柙) 在运动过程中，根据各条路径上的信息量决定转移方向，f 时刻位于某一城市的蚂蚁k 一次只能选择其中一个目标城市，n 次后回到起点，完成一次循环。那么，t 时刻位于城市f 的蚂蚁k 选择城市，为目标城市的概率是：，：=魄o ) 】口魄o ) r。蠢h ( f ) 】1 啪) 】a , j e 口l l o w e d 。式( 2 1 )0 ，o t h e r w i s e其中，a l l o w e d 。= 1 ， ，l 卜一t a b u 。表示蚂蚁k 下一步允许选择的城市。与实际蚁群不同，人工蚁群系统具有记忆功能，t a b u 。0 c = l ，2 , - - - 朋) 用以记录蚂蚁k 当前所走过的城市，集合t a b u 。随着进化过程作动态调整。随着时间的推移，以前留下的信息渐渐消失，经过，1 个时刻，蚂蚁完成一个循环，各路径上的信息量要根据如下做调整：r 矿( f + h ) = px f u ( t ) + a ri ，p ( o ，1 )式( 2 2 )1 2河海大学硕士学位论文第二晕蚁群算法的原理与模型峨2 荟缸：式( 2 3 )公式( 2 2 ) 、( 2 3 ) 中_ r ：表示第t 只蚂蚁在本次循环中留在路径玎上的信息量，r 口表示本次循环中路径玎上的信息量的增量，p 表示残留信息的持久程度( o = p 1 ) ，i - - p则为信息的挥发程度。根据具体算法的不同，r o ( t ) ，r # ( r ) 及骺k ( f ) 表达形式可以不同，要根据具体问题而定。叫：詹若第职蚂蚁在本次循种经过玎式( 2 4 )b 否则公式( 2 4 ) 中q 是常数，为蚂蚁循环一周时释放在所经过路径上的信息素总量，即总信息量；l 。表示第k 只蚂蚁在本次循环中所走路径的长度。初始时刻，rq ( o ) = c ，f i = o ( i j = l ，1 ) 。以上是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 9 1 。在a n t q u a n t i t ys y s t e