（应用数学专业论文）蚁群优化算法及其在若干问题中的应用.pdf

摘要摘要蚁群优化算法作为一类启发式算法，已经成功地应用于求解n p 难问题。蚂蚁通过分泌信息素来加强较好路径上的信息素的强度，同时按照路径上的信息素强度来选择下一步的路径，好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径，最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。蚁群优化算法寻优性能优良，但搜索时间长、收敛速度慢、容易收敛到局部最优解，从而使其进一步推广应用受到局限。我们对算法的全局收敛性以及算法的全局搜索能力进行了讨论；同时对蚁群算法中参数掰、口、p 的作用作了理论上的研究，对算法参数的最优化配置进行了分析，并利用o l i v e r 3 0 这一典型的t s p 问题进行了仿真实验，获得了比较适当的参数配嚣方案，而且得出了一条比较重要的结论：当信息启发式因子口增大时，算法迭代次数明显减少，收敛速度加快；期望值启发式因子增大时同样如此：而信息素保留度p 增大时，情况恰恰相反，迭代次数增加，收敛速度大幅度减缓。将最大最小蚁群优化算法( i v i m a s ) 应用于解决有时间窗车辆路径问题( v r p t w ) 。i v i m a s 通过采取限制路径上信息素在f 。和r 。之间的措施，较好地解决了蚁群优化算法容易陷入局部最优解的问题，但在获得全局性最优解方面有所欠缺，而且在收敛速度上仍然比较慢。鉴于此，在不增加算法复杂度的情况下，我们对m m a s 在信息素的更新策略方面做出了改进，并在路径选择策略中加入随机因子，以提高了其全局搜索性能；引入最近邻域选择策略，可以大幅度减少算法运行时间：引入局部优化策略，即最优路径变异策略，以加快其收敛速度。考虑到时间窗因素是解决v r p t w 的主要瓶颈之一，对其影响做出认真分析之后，我们在路径选择的概率公式中给出了能较好解决时间窗问题的算子。结合一种比较好的快速产生初始解的算法，将m m a s 和改进后的m i v i a s 运用于s o l o m o n 的基准v r p t w 实例，试验表明改进后的算法获得了更好的结果。在本文的最后，提出一种多类蚁群优化算法( m a c o ) ，并将之应用于解决网络路由问题。蚁群优化算法在解决这一问题时相比传统网络路由算法获得了可观的结果，但存在局部停滞和缺乏可适应度的问题。当某条路径，被相当部分蚂蚁选中时，这条路径将会反复重复利用，这会导致该路径的拥塞以及选择其他路径的概率大大减少。而对于动态的网络而言，这是不希望出现的现象。因为：( 1 )当，拥塞之后它可能不再是最优的，而且由于网络拓扑的变化，其他非优的路径可能会变成最优的路径；( 2 ) 由于网络故障，可能会掉线，而新的更好的路径应该被发现。本文提出的m a c o ，具有对动态网络快速适应的能力。通过在n e t w o r k华南理工大学硕上学位论文s i m u l a t o r 仿真平台上对m a c o 进行仿真试验，结果表明，该算法相比a c 0 和链路状态路由算法具有更小的数据包传输时延和数据包丢失率。关键词蚁群优化算法：收敛性；m m a s ；v r p t w ；网络路由i ia b s t r a c ta b s t r a c ta n tc o l o n yo p t i m i z a t i o na l g o r i t h m s ( a c o ) a h e u r i s t i cs e a r c ha l g o r i t h m st h a th a v eb e e ns u c c e s s f u l l ya p p l i e dt os o l v i n gn ph a r dp r o b l e m s a c oa r eb i o l o g i c a l l yi n s p i r e df r o mt h eb e h a v i o ro fc o l o n i e so fr e a la n t s ，a n di np a r t i c u l a rh o wt h e yf o r a g ef o rf o o d w ec a nf i n dt h a tw h e na n t sa r el o o k i n gf o rf o o df r o mn e s t ，s o m ec h e m i c a lt r a i l s ( w ec a l lt h i st r a i la sp h e r o m o n e ) a r el a i db ya l la n t s ，t h ea n t sm o v i n ga r o u n df o r man e t w o r ko ft h e s et r a i l s ，a n di n f o r m a t i o ni sl a y i n ga r o u n d ，w a i t i n gt ob eu s e d g o o di n f o r m a t i o nt e n d st ob er e u s e do v e ra n do v e ra g a i n ，l e a d i n gt om o r er e i n f o r c e m e n ta n dm o r eu s e t h i si saf o r mo fb e h a v i o rc a l l e da u t o c a t a l y t i cb e h a v i o r a n di ti st h ek e yt ot h es u c c e s so f t h ea n tc o l o n y a c oh a sm a n yg o o df e a t u r e si no p t i m i z a t i o n ，b u ti th a st h el i m i t a t i o n so fs t a g n a t i o na n dp o o rc o n v e r g e n c e ，a n di se a s yt of a l li nl o c a lo p t i m a ，w h i c ha r et h eb o r l e n e c k so fi t sw i d ea p p l i c a t i o n ad e t a i l e dt h e o r e t i c a lr e s e a r c ho nt h eg l o b a lc o n v e r g e n c eo fa n tc o l o n ya l g o r i t h mi sp e r f o r m e d m e a n w h i l e ，t h i sp a p e rs t u d i e sa n da n a l y s e st h ef u n c t i o na n di n f l u e n c eo fp a r a m e t e r 口、口、pi nt h em o d e lo fa n ta l g o r i t h mt h e o r e t i c a l l y , a n dt h e nat y p i c a le x a m p l eo ft s po l i v e r 3 0i sc a l c u l a t e d a n dai m p o r t a n tc o n c l u s i o nh a sb e e nd r a w nf r o mt h i se x p e r i m e n t ：w h e nw ei n c r e a s e 口t h ei t e r a t et i m e so fa l g o r i t h md e c r e a s ea n dt h es p e e do fc o n v e r g e n c ei n c r e a s eg r e a t l y ；w h e n i n c r e a s i n g ，t h es a m et l l i n gh a p p e n s ；b u tw h e nw ei n c r e a s ep ，o nt h ec o n t r a r y ，t h ei t e r a t et i m e so fa l g o r i t h mi n c r e a s ea n dt h es p e e do fc o n v e r g e n c ed e c r e a s e u s em a x m i na n ts y s t e m ( m m a s ) t os o l v et h ev e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w ( v r p t w ) m m a sr e d u c e dt h ep r o b a b i l i t yo fa n ts y s t e mb e i n gd r o p p e di n t ot h el o c a lt r a pv i am a x m i ns t r a t e g y b u tm m a si sd e f i c i e n ti ng e t t i n gt h eg l o b a lo p t i m a lr e s u l t ，a n dt h ec o n v e r g e n c es p e e do fi ti sn o tf a s te n o u g h w ei m p r o v et h em a x m i ns t r a t e g ya n dt h ew a yo fu p d a t i n gp h e r o m o n e ，a n da d dt h er a n d o mf a c t o rt ot h es t r a t e g yo f r o u t ec h o o s i n g ，a sar e s u l t , t h eg l o b a ls e a r c ha b i l i t yi si m p r o v e d a tt h es a m et i m e ，w eu s et h en e a r e s tn e i g h b o rn o d ec h o o s i n gs t r a t e g ya n dm u t m i o ns t r a t e g yt od e c r e a s et h er u nt i m eo fa l g o r i t h ma n di n c r e a s et h es p e e do fc o n v e r g e n c e t h et i m ew i n d o wl i m i t a t i o ni st h eb o t t l e n e c ko fv r p t w a f t e rt h ed e t a i l e da n a l y s i so fu st oi t ，ao p e r a t o rt h a tc o u l dp r e f e r a b l ed e a lt h eb o t t l e n e c kh a sb e e np r o p o s e da n da d dt ot h ep r o b a b i l i t yf o r m u l aw h i c hu s e dt oc h o o s er o u t e t h ee x p e r i m e n th a sb e e nd o n eo nt h es o l o m o n ss t a n d a r di n s t a n c e so fv r p t w t h ei i i华南理工大学硕上学位论文e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mc a ng e tb e t t e rr e s u l t s a tt h el a s tp a r to ft h i sp a p e r , am u l t i p l ea c o ( m a c o ) a p p r o a c hh a sb e e np r o p o s e dt os o l v et h en e t w o r kr o u t i n gp r o b l e m t h ea c oa l g o r i t h mi se m p i r i c a l l yc o m p a r e dt om a n yt r a d i t i o n a lr o u t i n ga l g o r i t h m sa n do b t a i n e df a v o r a b l er e s u l t s n e v e r t h e l e s s ，t w oi s s u e sa r i s ef r o mt h ea t t e m p tt oi m p l e m e n tt h ea c 0a l g o r i t h m ：s t a g n a t i o na n dp o o ra d a p t a b i l i t y s t a g n a t i o no c c u r sw h e nan e t w o r kr e a c h e si t sc o n v e r g e n c e ；a no p t i m a lp a t h ，i sc h o s e nb ya l la n t sa n dt h i sr e c u r s i v e l yi n c r e a s e sa na n t sp r e f e r e n c ef o rz t h i sm a yl e a dt oc o n g e s t i o no f ，a n dd r a m a t i c a l l yr e d u c i n gt h ep r o b a b i l i t yo fs e l e c t i n go t h e rp a t h s t h e ya r eu n d e s i r a b l ef o rad y n a m i cn e t w o r k s i n c e ：i ) 1m a yb e c o m en o n o p t i m a li fi ti sc o n g e s t e d ，o t h e rn o n - o p t i m a lp a t h sm a yb e c o m eo p t i m a ld u et oc h a n g e si nn e t w o r kt o p o l o g y ；i i ) 1m a yb ed i s c o n n e c t e dd u et on e t w o r kf a i l u r e ，n e wo rb e t t e rp a t h sm a yb ed i s c o v e r e d a d a p t a b i l i t yr e f e r st ot h ed e g r e eo fs e n s i t i v i t yo fn e t w o r kd y n a m i c s ( t o p o l o g yc h a n g e so rl i n kf a i l u r e s ) m a c oc o u l da d a p tt od y n a m i cn e t w o r kq u i c k l y ，a n dh a v et h eg r e a ta d a p t a b i l i t y t h ee x p e r i m e n th a sb e e nd o n eo nt h en e t w o r ks i m u l a t o r ，t h er e s u l t ss h o wt h a tm a c 0i ss u p e r i o rt oo t h e rm u t i n ga l g o r i t h m ss u c ha sa c oa n dl i n ks t a t e ( l s ) i nt e r m so fp a c k e td e l a ya n dl o s sp r o b a b i l i t y k e y w o r d sa n tc o l o n yo p t i m i z a t i o n ；c o n v e r g e n c e ；m m a s ：v r p t w ；n e t w o r kr o u t i n gi v华南理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期r年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华南理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口，在年解密后适用本授权书。本学位论文属于不保密口。( 请在以上相应方框内打“4 ”)作者签名：导师签名；日期：日期：年月曰年月日第一章绪论第一章绪论1 1 研究背景1 1 1 组合优化及时间复杂性理论组合优化i ij 是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域。它研究的是具有有限个可行解的优化问题。该问题可用数学模型描述为：m i n f i x )s t g ( x ) 0 ，x d其中，f ( x ) 为目标函数，g ( x ) 为约束函数，x 为决策变量，d 表示有限个点组成的集合。一个组合最优化问题可以用三个参数( d ，f ，f ) 表示，其中d 表示决策变量的定义域，f 表示可行解区域f = x i x e d ，g ( x ) - 0 ，f 中的任何一个元素称为该问题的可行解。f 表示目标函数。满足f ( x + ) = m i n f ( x ) p ( f ) 的可行解j + 称为该问题的最优解。现实生活中大量问题都是组合优化问题，如o l 背包问题，t s p ，装箱问题，车辆路径，网络设计等。组合优化的特点是可行解集合为有限点集。由经验可知，若d 非空，则只要将d 中有限个点逐一判别是否满足g ( ) ( ) 0的约束和比较目标值的大小，该问题的最优解一定存在和可以找到。然而枚举是以时间为代价的，有的枚举时间还可以接受，有的则不能接受。因此对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到最有效的算法求得一个最优解。时问复杂性函数是衡量算法有效性的一个重要标准川，它指的是算法对输入长度( 当问题的参数给定时，即成为一个实例，参数在计算机中的所占空间称为实例的输入长度) 为1 1 的实例需要执行的基本运算次数的一个上界f “1 ) ，也就是考虑最坏的情况。若一个算法的复杂性f ( n ) 时n 的多项式函数，则称这个算法是有效的或有多项式界的，即所谓的多项式算法。而不是有效的算法称为无效算法，我们称之为指数算法，即复杂性f ) 是1 1 的指数函数的算法。因为，对于任意给定的正数口和口 1 ，当n 足够大时，n 。 口”，所以当实例输入长度n 增大时，任意一个多项式算法终将变得比任何指数算法更有效。这就是把多项式算法称为有效算法的原因之一。1 1 2 蚁群算法的提出1 9 8 9 年，g o s s 等通过著名的双桥实验bj 对阿根廷蚂蚁的觅食行为进行了研华南理工大学硕士学位论文究。给定从巢穴到食物的两条路径：o a b 和o b 。其中，路径o a b 较长，o b较短。两条路径均是双向连通的，且从点。到b 只有这两条路径。段时间后，蚁群中大部分蚂蚁都选择了较短路径o b 。另外，实验还证明：蚂蚁选择较短路径的可能性和两条路径的距离差有关，随着距离差距增加，选择较短路径的可能性也在增加。信息素遗留和跟踪理论对蚂蚁的这种行为作出了解释：1 、每只蚂蚁行走过程中都会在自己走过的道路上留下一定数量的信息素；2 、信息素是一种易于挥发、可累加的化学物质；3 、道路上的信息素浓度越大，蚂蚁选择这条道路的可能性就越大。在初始状态，蚂蚁随机地选择一条道路。由于相同时间内，较短的路径上会积聚较多的信息素，因而后面出发的蚂蚁倾向于选择路径o b ，这样又进一步增加了o b 上的信息素。一段时间后，大部分蚂蚁都选择了道路o b 。根据蚂蚁群体具有这种智能的特点，意大利学者m d o r i g o ，v m a n i e z z o ，a c o l o m i 等人首先提出了蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n a c o ) ，当时他们称之为蚁群系统( a n ts y s t e m ) ，并利用该方法去解决t s p 等问题【4 - 7 】，取得了较好的实验结果，后来m d o r i g o 等为了其他学者研究的方便，将各种蚂蚁算法统称为蚁群优化算法，并为该算法提出了一个统一的框架结构模型。蚁群优化算法是9 0 年代初期才提出的一种新型的进化算法，虽然其起步较晚，但是对蚁群优化算法的研究已引起了国际上学者们的广泛关注，其主要原因是蚁群优化算法不仅在前面所提的离散优化问题上显示出了卓越的性能，而且在解决连续性优化问题上也显露锋芒。该算法模仿蚂蚁觅食时的行为，按照启发式思想，通过信息传媒一外激素( p h e r o m o n e ) 的诱发作用，逐渐收敛到问题的全局最优解。蚁群算法自问世以来表现出了强大的生命力，较之以往的启发式算法不论在搜索效率上，还是在算法的时间复杂度方面都取得了令人满意的效果。该算法已被其它领域的专家所接受，并运用到诸如分类、任务分配、机器人合作规划、图着色、车辆调度、大规模集成电路设计、通信网络中的负载平衡等许多方面。1 2 研究现状蚁群优化算法是模拟自然界中真实蚁群的觅食行为而形成的一种模拟进化算法，由于取得了较好的实验结果，蚁群优化算法激起了其他学者的研究热情，并取得了很多研究和应用成果i s - t 2j 。近1 0 年来的研究结果已经表明：蚁群算法用于组合优化具有很强的发现较好解的能力，具有分布式计算、易于与其他方法相结合、鲁棒性强等优点，在动态环境下也表现出高度的灵活性和健壮性。然而，蚁群算法存在搜索时间过长、易于停滞的问题。为了克服这些缺点，不少学者提出了改进的蚁群算法”j 。例如，文献 1 3 】提出了一种m m a s ( m a x m i n a n ts y s t e m )2第1 章绪论算法其基本思想是对路径上的信息素进行限制，以期克服停滞问题，并月仅让每一代中最好的个体所走的路径上的信息作调整，以加快收敛速度。文献 1 4 】则提出了一种新的改进的信息素更新策略：其一，局部信息素修改时，挥发系数动态改变；其二，全局信息素更新时，则将蚂蚁所走路的较短的那些路径上的信息加强，而较差的那些路径上的信息减弱。文献【1 5 】提出了一种基于蚂蚁进化规则的算法，文献【1 6 】主要提出了一种相遇算法，其基本思想是在求解t s p 问题中，用两只蚂蚁共同完成对一条路径的搜索，以使搜索速度提高。文献【1 7 】提出了一种变异策略，以加快局部搜索。还有不少其他文献作了改进，例如，引入交叉算子以提高搜索多样性；引入分支因子r 作为衡量群体多样性的指标，当r 低于某一值时，对各路径上的信息作动态调整，以期望克服停滞现象等等。这些研究对算法有一定程度的改进，但对提高收敛速度的效果不是特别明显，速度慢仍然是制约蚁群算法在大规模优化问题中的应用的瓶颈。1 3 蚁群算法与其他基于种群进化算法的比较蚁群算法和遗传算法均是基于种群的自然启发式方法，q u i n a n 把机器学习领域的自然启发式方法分为两类：基于实体( i n s t a n c eb a s e d ) 方法以及基于模型( m o d e lb a s e d ) 的方法。基于实体的方法用当前的解或解的种群本身来产生新的候选解，大部分的自然启发式搜索算法都属于基于实体的方法，遗传算法、模拟退火算法以及迭代搜索方法就是其中的代表。基于模型的搜索方法通过一个解空间的参数化概率分布模型来产生候选解，此模型的参数用以前产生的解来进行更新，使得在新模型上的搜索能集中在高质量的解搜索空间内。遗传算法等基于实体的搜索算法由于出现的较早，其研究也相对来说比较成熟，而蚁群算法等基于模型的方法正处在快速的发展阶段，也还没有形成成熟的理论框架。除蚁群算法外，还有许多从遗传算法或其它进化计算方法衍生出的基于模型的搜索算法。典型的遗传算法的有效性建立在构造块( b u i l d i n gb l o c k s ) 的基础上，即高质量的解总是包含这些块，此外，遗传算法还假设通过选择合适的交叉( c r o s s o v e r ) 操作，这些构造块能逐渐被发现并让其保留在种群中，同时选择( s e l e c t i o n ) 操作能够使搜索趋向更高质量的解空间。实际上，要找到一个合适的交叉算子是很困难的，特别是在处理具有复杂约束的问题时，为了保证不会产生华南理工大学硕士学位论文不可行解，交叉操作设计得极为复杂，甚至有时使得部分高质量的可行解不可达，或概率很小。此外遗传算法还存在所谓的基因飘移现象( g e n e t i cd r i f t ) ，即由于有限的种群大小牺牲了种群中个体的多样性( d i v e r s i t y ) ，使得某些好的构造块并不包含在该种群中，从而使算法容易收敛于局部最优解。蚁群算法等基于模型方法较遗传算法等基于实体的算法而言，其优点是学习的知识分布在解构成元素上，或者说学习的是解构成元素与这些元素装配在一起后形成的解的质量之间存在的相关关系，而遗传算法虽然也能隐含地学习构造块的知识，但由于以上介绍的遗传算法的几个问题，这种学习有时是不可靠的。不过对于蚁群算法等基于模型方法来说，必须建立一个好的参数化概率模型f 在蚁群算法中为解构造图，模型的参数为图上分布的信息素1 ，模型的参数必须t j 由此模型产生的解的质量问具有很强的相关性。此外，蚁群算法中，由于解是在解构造过程中一步步用解构成元素组合而成的，在这个过程中可以方便地利用基于问题本身的启发式信息，比如t s p 问题的蚁群算法。本论文后几章的研究结果也表明，利用启发式信息对改进算法性能是很有效的。而遗传算法的交叉，变异机制就不能有效的利用问题的启发式信息，蚁群算法的解构造机制还有个非常好的优点，就是能够方便地处理约束条件，即可以在解构造过程中动态的调整蚂蚁下一步可访问的结点从而保证解的可行性，而处理复杂约束则是遗传算法的一个薄弱环节。但蚁群算法也有几个主要的缺点：l 、在每次解构造过程的计算量较大，算法的计算复杂度主要在解构造过程，比如t s p 问题为o ( m - n 2 ) ，其中m 为算法迭代次数，n 为问题的规模；2 、蚁群算法对复杂问题的描述能力不强，解构造图模型实际上是一种序列决策模型，很多问题比较难以描述为解构造图，目前组合优化问题中应用蚊群算法较多的有两类，即排序问题( t s v ，f l o w s h o p ) 和分配问题( q a p ) ；3 、蚁群算法的信息素模型必须与由此模型产生的解的质量间具有很强的相关性。1 4 本文研究的内容及组织1 4 1 对蚁群算法运行机制的研究本文给出了对一种简单蚁群算法的收敛性分析，这种简单蚁群算法具备了传统蚂蚁算法的基本特征，得出的结论是该算法将已概率1 收敛于全局最优，从而4第一章绪论初步在理论上证实了该算法的有效性和可行性。经过我们多次试验以及研究发现，蚁群算法中口、卢、尸等参数对算法性能有很大的影响，故在本文中我们对算法中参数的设置进行了深入的探讨。研究参数o f 、卢、p 的最佳配置，对发挥蚁群算法在实际问题中的作用有很重要的意义。信息素的更新策略一直是研究蚁群算法的学者们所热衷的问题，我们也在本文当中对其进行了深入探讨，并针对具体问题给出了我们创造性的信息素更新策略，如在m m a s 在有时间窗车辆路径中的应用中，并且获得了较好的结果。1 4 2 讨论蚁群算法在具体问题中的应用在本文中，我们针对有时间窗车辆路径问题的特性以及最大最小蚁群优化算法( m m a s ) 的性能优势，将m m a s 应用于这一问题，并给出了具体的应用模式，在这一模式中，力图解决时间窗因素给问题所带来的复杂性；进而在不增加算法复杂度的情况下，我们将对m m a s 在信息素的更新策略方面做出了改进，并运用局部优化策略，即最优路径变异策略，以加快其收敛速度；为了保证在加快收敛速度的同时，不影响其全局搜索能力，在路径选择策略中加入随机因子，使得算法具有较大的解空间。考虑到对于较大规模的有时间窗车辆路径问题，每次迭代将需要较长的运行时间，如何减少运行时间而又不至于影响寻优性能，也是我们要力图解决的问题。同时，注意到用m m a s 解决有时间窗车辆路径问题时，初始化过程相当重要，如果能对某些关键参数给出好的初始化，能对算法性能有较大改善，我们认为这种能够获得一定程度上较好初始解而且时间复杂度可接受的初始化算法是很重要的。随着i n t e m e t 上广泛的分布式多媒体应用对服务质量( q o s ) 需求的增长，各种服务应用对网络所能提供的q o s 提出了不同的要求，所以高效率的q o s 支持越来越显示出其重要性，而路由机制是实现q o s 保证的关键之一。首先将对一般性的路由选择问题进行了讨论。考虑到比较常用的链路状态路由算法彳i 能充分利用网络资源，而传统的蚁群优化路由算法对动态变化的网络的可适应度较差。提出一种基于蚁群优化算法的解决路由问题的多类蚁群优化路由算法，具有比传统蚁群优化路由算法具有更大的可适应度，而且可以较好的利用网络资源。华南理工大学硕上学位论文第二章蚁群优化算法及其收敛性分析2 1 蚁群优化算法由第一章我们已经获悉：蚂蚁在觅食过程中能够在所经过的路径上留下一种称为信息素的物质，而且蚂蚊在觅食过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，它们倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的集体觅食行为就表现出一种信息正反馈现象：某路径越短，该路径上走过的蚂蚁就越多，所留下的信息素强度也就越大，后来者选择该路径的概率因此就越大。蚂蚁个体之间通过这种信息交流来选择最短路径并达到搜索食物的目的。蚁群优化算法就是模拟蚁群这一觅食行为的优化算法。m d o r l g o等人已先后提出了模拟蚁群这一觅食行为的a s ( a n ts y s t e m ) 算法和a c s ( a n tc o l o n ys y s t e m ) 算法，并将a s 算法和a c s 算法定义为a c o ( a n tc o l o n yo p t i m i z a t i o n )算法。2 1 1 蚁群系统模型( a s 算法)为了便于理解，以求解平面上n 个城市的t 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 ) ，即旅行商问题，是一类已被证明具有n p c 计算复杂性的组合优化难题，它的提法是：给定n 个城市，有一旅行商从某一城市出发，访问各城市一次且仅一次后返回原出发城市，要求找出一条最短的巡回路径。为了模拟实际蚂蚁的行为，首先引进如下记号：设m 是蚁群中蚂蚊的数量，吃( i j = l 一2 ，n ) 表示城市i 和城市j 之间的距离，6 巾) 表示t 时刻位于城市i 的蚂蚁的个数，则有n f b a t )( 2 1 )f 。( f ) 表示t 时刻在城市i ，j 路径上残留的信息量。初始时刻，各条路径上信息量相等，设气( 0 ) = c ( c 为常数) 。蚂蚁k ( k = 1 2 。m ) 在运动过程中，根据各条路径上的信息量决定转移方向。露( t ) 表示在t 时刻蚂蚁k 由城市i 转移到城市j的概率：e ；：j 孺，女a 果，若，h a z “。2 一：，学= k ( o ) “k 尸”一+( 2 2 r “o，否则其中：玎。为先验知识或称为能见度，在t s p 问题中为城市i 转移到城市j6第一二章蚁群优化算法及其收敛性的启发信息，一般取= l d 。：瑾为在路径i j 上残留信息的重要程度；声为启发信息的重要程度；与实际蚁群不同，人工蚁群系统具有记忆功能，t a b u 。( k = l ，2 ，i n )用以记录蚂蚁k 以前所走过的城市，称为禁忌表( 下一步不允许选择的城市) 。集合t a b u 随着进化过程作动态调整。经过n 个时刻，所有蚂蚁都完成了一次周游。它们本次周游的禁忌表将满，此时应将其清空，再将当前蚂蚁所在城市置入t a b u 。，准备下一次周游。这时，计算每一只蚂蚁所走过的路径上。，并保存最短路径的长度k 。( 厶。2 r a i n l 。，k = l ，。，m ) 。随着时间的推移，以前留下的信息素逐渐消逝，用参数p 表示信息素挥发程度，蚂蚁完成一次循环以后，各路径上的信息量要根据式( 2 - 3 ) 作调整：i g ( f + 1 ) = ( 1 一p ) r ( f ) + p ( 2 3 )a r = a r f 。( 2 4 )； 詈，当第盘只蚂蚁在时刻f 和f + 1 之间经过 ，时( 2 5 )10 ，否则其中，r ：表示第k 只蚂蚁在本次循环中留在路径i j 上的信息量，a r 。表示本次循环中路径i j 上的信息量的增量，q 为常数，丘表示第k 只蚂蚁在本次循环中所走过的路径的长度。一般设置周游次数计数器n u m ，当达到设定值时结束。最短路径为m 制n 三。羽2 l ，2 “, n u m ) 。2 1 2 a c s 算法a c s 算法也是一种a c o 算法，算法描述如下：s t e p1 初始化。将每个边上的信息素初始化为一个很小的常数值：将1 1 1 只蚂蚁随机地分配到n 个城市( 或1 1 个节点，以下同) ，同时，出发点城市设置到禁忌表中。s t e p2 下一个节点的选择。每只蚂蚁按式( 2 6 ) ) 或式( 2 2 ) 选择下一个城市，并修改禁忌表。j - a r g 胁i t i a x h如果。( 2 - 6 )is ，否则其中：0 q 。1 ，是初始设定的参数：q 是一个随机数，q 【o ，l 】；s 是根据式( 2 2 ) 决定的随机变量( 在a c s 算法中，式( 2 2 ) 中的口被取消) 。很显然，该策略华南理工大学硕士学位论文增强了搜索的多样性，以避免过早地陷于搜索停滞。s t e p3 信息素局部更新。每只蚂蚁选择一个城市( 走完一个边) 以后，按式( 2 7 ) 更新该边上的信息素。r 。o + 1 ) = ( i p ) r ) + 卢7 ( 2 - 7 )a r ：詈，当第七只蚂蚁走过城市扩时( 2 8 )；= i j 昂 、煳戳止u 坝”叫叫( 2 8 )10 ，否则其中，丘是蚂蚁k 从开始城市到当前城市已走过的路径长度。其余参数与式( 2 3 ) 相同。s t e p4 计算最佳路径。当m 只蚂蚁走完所有城市以后，按式( 2 9 ) 计算最佳路径长度并保留：，= r a i n l k ， = 1 , 2 ，m( 2 - 9 )其中，是第k 只蚂蚁所走的路径长度。s t e p5 信息素全局更新。当所有蚂蚁走完全部城市以后，仅对最佳路径上的信息素按式( 2 - 1 0 ) 进行更新。r ；刑= ( 1 一p ) f ；艋+ 户f f( 2 1 0 )： 亡2 当扩全局最优路径( 2 - 1 1 )。r0否则其中，p 为信息素挥发系数，屯为最佳路径的长度。s t e p6 设置的搜索次数如果未完，则清空禁忌表，重复上述过程。2 1 3 一种优化的a c o 算法朱庆保等人 i 7j 基于t s p 问题的优化应用，研究了一种基于最近邻居选择、动态信息素更新和变异策略的高速收敛算法，简称n d m a c o 算法( a c oa l g o r i t h mb a s e do nt h en e a r e s tn e i g h b o rn o d ec h o o s i n g ，d y n a m i cp h e r o m o n eu p d a t i n ga n dm u t a t i o n ) 。该算法以最近的邻居节点选择和动态信息素更新策略来加速全局收敛，以一种独特的变异策略来加快局部寻优，使收敛速度大幅度地提高。实验结果表明，此算法与其他最新的改进算法相比，其收敛速度提高数倍以上，结果也大幅度优于其他改进蚁群优化算法。1 n d m a c o 基本原理( 1 ) 最近节点选择策略考察t s p 问题，商人要遍历n 个城市( 每个城市只走一次1 ，且使总路径最短。第二章蚁群优化算法及其收敛性在a c s 算法中，当从城市i 选择下一个城市j 时，需要将n _ 1 个城市与禁忌表比较，再计算n - 1 个城市的转移概率，需要较长的计算时间。将下。个城市的选择范围局限于离当前城市i 较近的部分城市，仅对这部分城市的转移概率进行计算即可。f 2 ) 信息素动态更新策略根据实验，当蚂蚁从一个具有很多城市的复杂地图的边部城市出发时，它在出发点附近的局部区域走的路径往往是较优的，走到地图中心区，路径错综复杂，与其他蚂蚁走的路径重叠增多，互相影响加大，走出较优路径的概率降低。根据这一实验结果，为了避免中心区信息素堆积过多以及体现众多蚂蚁的共同影响，每只从边部城市出发的蚂蚁留下的信息素应随着向中心区的延伸而逐渐减弱，当走到最远处时，已渗透到另一边部其他蚂蚁的领地，为了不过大地干扰其他蚂蚁开始走出的较优结果，其信息素应减到最小。由于蚂蚁间的相互联系以及对搜索的主要贡献是留下信息素，因此，信息素的更新策略是决定收敛速度的关键之一。f 3 ) 最优个体变异策略实验表明，应用上述两种策略改进后的蚁群算法的全局搜索能力相当强，可迅速收敛到一个较优解。但从较优解到最优解所花费的收敛时间所占比重很大。利用变异算法局部寻优能力强的特点，在收敛到一定代数时，对最优个体进行变异，可大大加快局部寻优速度。综合以上几点，研究了一种基于求解t s p 问题的最近邻居节点选择、动态信息更新和变异策略的高速收敛蚁群优化算法，简称n d m a c o 算法。2 n d m a c o 算法步骤根据上面的原理，n d m a c 0 算法步骤如下：s t e p1 初始化。将n 个城市分别按x ，y 坐标排序，均匀地在地图周围找出n 个边部城市，n = w h ，其中h 为各选的邻域城市个数，一般取h ef l ，2 0 ，n 越大，h 取值可越大，若n 较小时，h 取较小的值。将m 只蚂蚁分别固定地放置在n 个边部城市上( 一般取m = n ，每个城市放置一只蚂蚁) 。并将该蚂蚁所在城市设置到该蚂蚁的禁忌表中。同时，设置代数计数器n c = m a x ，其余初始化与a c s法相同。s t e p2 对于每一只蚂蚁，以当前城市i 为中心，按最近邻居原则选取离蚂蚁所在当前城市i 最近的h 个城市中的一个作为下一个城市i 的选择范围。从h 个城市中找出z 个未走过的城市 一，：，_ ，_ ，：) ，即_ ，硭t a b u 。s t e p 3 在z 个城市中，按式( 2 1 2 ) 选择节点i ：9华南理工大学硕士学位论文，一r g m a x 。，( f ) k ( f ) 如果g 吼p ：= i r , j ( t 丽) ( r l o ( t 刀) ) pj 仨t a b u k否则2 1 2 其中，q 为随机数( o q o 时，计算z 个城市的转移概率p j ，并根据赌轮盘规则选择城市j 。将j 加入禁忌表t a b u ，。s t e p4 局部信息素动态更新。当每只蚂蚁走完一个边以后，即按式( 2 一1 3 )进行局部信息更新。f “( f + 1 ) = ( 1 一p ) f o ) + 硝o( 2 1 3 )na r ，= 警( 2 - 1 4 )。l ：f ：= d 。1 + 霞+ + = 影( 2 1 5 )f i屯lmk f f i ll = 1d l d 0 , ，= 1 , 2 ，x ，v i ，j = 1 , 2 ，3 ，n ( 2 - 1 6 )其中，q l 为一个较大的常数，x 是蚂蚁k 在本次周游中己走过的城市边数；d 是蚂蚁k 己走过的边的边长，m 是蚂蚁总数，就是所有蚂蚁在本次周游中己走过的边的累加总长。该策略保证了各蚂蚁所留信息素的均衡性，保证了对搜索的均衡贡献和相互协作，体现出了群体的力量，这是本文的算法能够大幅度地提高收敛速度的关键之一。s t e p 5 当m 只蚂蚁选择完节点j 以后，令i 。= j ；l 。= ，“+ 1 ；返回s t e p2 ，开始选择下一个节点，直到所有蚂蚁完成一次周游为止。s t e p6 当m 只蚂蚁完成一次周游以后，计算和7 ，并保辩k 。和本次禁忌表t a b u ，。k = l 2 ，m ；一2 m i n l k ；i k 是蚂蚁k 完成一次周游的路径长度。s t e p7 变异运算。令n c = n c 一1 ，若m a x - n c m ，转s t e p8 ，否则进行下面的变异运算，m 为设定的开始变异界限值。变异策略如下：以蚂蚁k 走过的一周路径表为染色体个体，设由s t e p6 得到的最优个体为f 1 1a 2 ，码，8 ，罐。，其中口，为城市编号。适应度函数为：，：= d l ，其中4 为边长l = 1变异算法的伪代码如下：f o r ( i _ 2 ；i n ；i + + ) a ，与口，。交换，评价适应度，：1 0第二章蚁群优化算法及其收敛性i f ( 1 ： - - n ) f o r ( i = 2 ；i n 一1 ；i + + )口。与口。交换，评价适应度，i f ( ，： ，