（计算机应用技术专业论文）基于蚁群优化算法的tsp问题研究.pdf

武汉理工大学硕士学位论文 中文摘要 t s p 问题( 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 问题，而且还可以求出该问题的最优解。但是对现有的计算机来说，使用常舰的 穷举法在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求t s p 问 题近似解的优化算法应运而生了，本文所用到的蚁群优化算法也在其中。 蚁群算法作为一类启发式算法，已经成功地应用于求解t s p 问题。蚂蚁通过分泌 信息素来加强较好路径上的信息素的强度，同时按照路径上的信息索强度来选择下一 步所选择的路径，好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖 较好的路径，最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反 馈原理正是整个算法的关键所在。 首先，本文对蚁群系统算法( a c s ) 的全局收敛性和关键参数的设置进行了深入 的研究。a c s 寻优性质优良，但搜索时间长、收敛速度慢、容易收敛到局部最优解， 从而使其进一步推广应用受到局限。我们通过对算法的全局收敛性以及算法的全局搜 索能力进行深入的理论研究，从改善算法全局收敛性的角度提出了一系列改良途径： 同时对蚁群算法中参数a 、p 、p 的作用作了理论上的研究，对算法参数的最优化配置 进行了分析，并利用e i l 5 1 这一典型的t s p i 司题进行了仿真实验，得出了比较适当参数 配置方案。 在此之后，本文介绍了蚁群算法中一种新的信息紊更新和路径选择机制并应用于 求解t s p 问题。在a c s 基础上，改良的蚁群算法采用了更为高效的信息素更新和路 径选择机制，使得改进后算法的全局收敛速度得到明显的提高；通过增加全局最小信 息素强度的设置以及对权函数进行自适应调整改进了算法的搜索能力，扩宽了算法的 搜索空间，使改进后算法更容易收敛到全局最优解：并通过实验证明了其有效性。 最后，本文对改进后的蚁群算法的实现进行了简单阐述，并针对蚁群算法的前景 进行了展望。 关键字：人工智能，蚁群优化算法，群体智能，t s p 问题信息素 武汉理工大学硕士学位论文 a b s t r a c t 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 ) i sap r o b l e mo fc o m b i n a t i o no p t i m i z a t i o n 耐t h s i m p l ed e f i n i t i o n b u td i f 王i c u l tt ob es o l v e d w h i c ha t t r a c t sm a n yr e s e a l c h e r si nv a r i o u s f i e l d s i n c l u d i n gm a t h e m a t i c s ，p h y s i c s ，b i o l o g y a n da r t i f i c i a l i n t e l l i g e n c e ( a i ) i t h a s b e c o m ea n dw i l lc o n t i n u et ob e c o m eas t a n d a r dp r o b l e mt ot e s tan e wa l g o r i t h mo f c o m b i n a t i o n o p t i m i z a t i o n t h e o r e t i c a l l ys p e a k i n g ，t h ee n u m e r a t i o n n o to n l yc a r ls o l v et s p , b ma l s oc a ng e tt h eb e s ta n s w e r b u tt oa l lc o m p u t e r s n o w a d a y s ，i t sh a r d l y t oo b t a i ni t sb e s t a n s w e ri ns u c hh u g e r e s e a r c h i n gs p a c eb yu s i n gc o m i l o ne n u m e r a t i o n t h e r e f o r e ，a l lk i n d s o fa l g o r i t h m st os o l v et s pe m e r g e db e c a u s eo fd e m a n d a m o n go ft h e m ，a n tc o l o n y a l g o r i t h m ( a c a ) i so n eo fa d v a n c e dt e c h n o l o g i e s a n t c o l o n ya l g o r i t h m i sac l a s so fh e u r i s t i cs e a r c h a l g o r i t h m s t h a th a v eb e e n s u c c e s s f u l l ya p p l i e dt os o l v i n gn p h a r dp r o b l e m s a n ta l g o r i t h m sa r eb i o l o g i c a l l yi n s p i r e d f 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 w t h e yf o r a g ef o rf o o d w e c 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 s t 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 e t 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 e r 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 e r e i n f o r c e m e n t ，l e a d i n gt om o r eu s e t h i si sa f 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 t i st h ek e yt ot h es u c c e s so ft h ea n t c o l o n y a c ah a sm a n y g 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 n a n d p 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 t t l e n e c k so fi t s w i d e a 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 n t h eg l o b a lc o n v e r g e n c eo f a c ai s p e r f o r m e d as e r i e so fi m p r o v e m e n ts c h e m e sa r ea l s op r o p o s e d m e a n w h i l e ，t h i sp a p e r s t u d i e sa n d a 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 f p a r a m e t e r ，d ，pi nt h em o d e lo f a n t a 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 f t s pe i l 51 i sc a l c u l a t e d t h e n ，t h i sp a p e rp r e s e n t san e w p h e r o m o n eu p d a t i n gs t r a t e g yw h i c h i su s e dt o o p t i m i z ea c s ( a n tc o l o n ys y s t e m ) i ns o l v i n gt h et r a v e l i n gs a l e s m a np r o b l e m t h e i m p r o v e d a n tc o l o n yo p t i m i z a t i o n a l g o r i t h mi su s i n g an e w p h e r o m o n eu p d a t i n gs t r a t e g y t h e p h e r o m o n e t r a i lo f e a c h e d g e i ss e tw i t hal o w e rl i m i ta tt h eb e g i n n i n gi t e r a t i o n so f t h e 武汉理工大学硕士学位论文 a l g o r i t h m ，a n dt h ew o r s ta n t j u d g e db y i t st o u rl e n g t hl i k et h eb e s ta n tu s e di na c oi s a l l o w e dt op e r f o r mg l o b a lt r a i lu p d a t i n g a n dw ed e m o n s t r a t et h ee f f i c i e n c yo f t h e a l g o r i t h mb ym e a r l so f e x p e r i m e n t a ls t u d y f i n a l l y ，t h ep a p e re x p l m n e d t h ei m p l e m e n to ft h ei m p r o v e d a l g o r i t h m a n dw e i n d i c a t e t h ef u t u r er e s e a r c hd i r e c t i o n s k e y w o r d s ：a r t i f i c i a li n t e l l i g e n c e ，a n tc o l o n yo p t i m i z a t i o n ，s w a r mi n t e l l i g e n c e t r a v e l i n gs a l e s m a np r o b l e m ，p h e r o m o n e 此页若属实，请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：乏企缝日期圣受 ：研 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：翻：缝导师签名 注：请将此声明装订在论文的目录前。 z p o 复、 r 武汉理工大学硕士学位论文 1 1 问题的提出 第1 章引言 许多实际工程问题可以抽象为相应的组合优化问题。采用常规方法对于大 规模组合优化问题的有效解决往往存在着许多障碍。近年来，人们对于将自然 界的许多有益特性应用于工程实际。目前已经有很多启发式算法用于解决复杂 的系统优化问题，如电信网络路由，交通运输网络中最佳路径选择，网络导航 等问题。与传统算法相比较，启发式算法的优点在于其有较好的全局搜索能力， 避免过早收敛于局部最优解。 蚁群算法就是借鉴自然界中群居性昆虫通过自组织的合作能力所产生的群 集智能解决组合优化问题的典型例子。蚁群算法( a n tc o l o n y a l g o r i t h m ) 是由 意大利学者m a c r od o r i g o 等人在2 0 世纪9 0 年代初首先提出来的【1 】。它是继模拟退 火算法、遗传算法、禁思搜索算法、人工神经网络算法等元启发式搜索算法以 后的又一种应用于组合优化问题的启发式搜索算法。然而，最初的蚁群算法( a s ： a n t s y s t e m ) 在解决t s p ( t r a v e l i n g s a l e s m a np r o b l e m ) 问题时存在着两个主要缺 陷：收敛速度较慢，容易出现停滞。为此，不少研究者提出了一些改进算法如： 蚁群优化算法( a c o ：a n tc o l o n yo p t i m i z a t i o n ) ，最大最小蚁群系统( m m a s ： m a x m i n a n ts y s t e m ) 等，这些改进的算法在一定程度上提高了收敛速度，但效 果并不明显。 通过对蚁群之间合作机制的研究发现：蚁群之间传递信息的媒介信息 素的设置和更新策略对蚁群算法整体性能起着至关重要的作用：蚂蚁个体的路 径选择机制决定了蚁群算法的搜索空间范围。通过对信息素的设置和更新策略 以及蚂蚁个体的路径选择机制的改进，有可能使算法的搜索能力和收敛速度得 到显著提高。 1 2 本文研究内容 本文基于a c o 算法的整体框架，借鉴了m m a s 算法中利用控制信息素取值 武汉理工大学硕士学位论文 范围来提高算法的开发能力的思想，并在此基础之上通过改进信息素的全局更 新机制和蚂蚁个体的路径选择机制来弥补算法在开发上的消耗，使算法能够更 快的收敛到全局最优解。通过实验证明新的算法更好的平衡了探索新路径和利 用已有知识之间的关系，使算法的搜索能力和性能都得到了显著提高。 由于蚁群算法中a 、b 、p 等参数对算法性能有很大的影响，如果参数n 、 p 、p 设置不当，导致求解速度很慢且所得解的质量特别差：同时，蚁群算法 中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路，但在实 际计算中，在给定一定循环次数的条件下很难实现这种情况，因此改善算法的 收敛性也是一个很关键的问题。本文在改良后的算法模型上对参数的设置以及 改善收敛性的途径进行了理论和实验两方面的研究，提出了相关的改进策略， 并通过改良算法性能的提高证明了该策略的有效性。 1 3 本文的组织 本文后续章节组织如下：第二章介绍了什么是蚁群系统，以及相关的基本 概念和术语。t s p 问题作为一种组合优化问题的范例也进行了介绍。第三、四章 是全文的重点，第三章介绍了如何通过改进信息素的设置和更新策略以及蚂蚁 个体的路径选择机制来提高蚁群算法整体性能，在此对改良途径进行了详细讨 论，并通过一些标准的t s p 问题的试验数据对比，讨论了算法的优缺点和适用范 围。第四章在结合改良后蚁群算法的模型下对算法参数的设置及收敛性进行了 理论研究并提出了相关的策略，然后通过试验证实了该策略的有效性。第五章 描述了算法的实现过程，并对实现过程中遇到的相关难点和重点进行了详细分 析和讨论。第六章对该研究工作进行了总结，提出了对进一步研究工作的设想。 武汉理_ 亡大学硕士学位论文 2 1 优化算法 第2 章蚁群优化算法 2 1 1 基本概念和术语 优化问题是人们在改造世界时经常会遇到的一类普遍问题。人们日常生活 工作中对自己行为的指导实际上就是对某些利益的最大化过程。直观的，当我 们考虑一个优化问题时，我们的目标就是求得最好的可能的解，也就是最优解。 术语优化包括最大化也包括最小化问题，最小化问题可以转化为最大化问题， 这里我们讨论非约束的最大化问题。我们给出如下的形式化定义。 d e f 1 ( 全局优化) 假设x 为一个搜索空间，x ，x 为其可行域，厂为该 适应值函数。优化问题就是寻找i x ，使得对于任何歹x ，“i ) f ( y ) 。 这里，i 为全局最优解。适应值函数f 或者是n u m e r i c a k 厂：x r ) 或者是o r d i n a l ( f ：xx x 专x ) 。如果厂是n u m e r i c a l ，则该定义描述了n u m e r i c a l 优化问题。 d e f 2 ( 局部优化) 首先定义两个解的距离度量如下：d i s t ：x x r 。则 对于i s ，i 的邻域可定义为： ( i ) = 歹xid i s t ( i ，歹) 占) 公式2 1 一个解i x 被称为局部最优解如果f ( x ) ，( 刃对所有的歹( i ) 。 2 1 2 优化算法 对于解决一个现实的优化问题，实际上是由两个独立的步骤组成【1 6 ： 创建问题的模型 使用该模型解得最终的解。 对于第二个步骤，有两类解决的方法：精确的传统方法和现代的近似算法。 对于后一类方法，不能保证输入精确的输入得到精确的输出：对前一类方法， 虽然可得到精确解，但不能保证对所有的问题运算会在有意义的时间内完成。 武汉理工大学硕士学位论文 而这一类问题在现实世界中非常常见，其时闻复杂度呈现指数形式，典型地属 于n p h a r d 问题。 我们可以归纳出解决现实世界优化问题的两类方法：建模得到一个近似的 模型，以便于利用传统方法获得精确的解：建模得到个较精确的模型，利用 近似算法获得近似的解。对于实际的应用，后者各方面的性能往往超过了前者。 这一小节，我们基于前面的定义，描述解决优化问题的不同类算法。首先， 我们介绍传统的算法，然后详尽描述现代的启发式算法。 d i r e e t a n a l y t i c a la n d l i n e a rp r o g r a m m i n gl o c a ls e a r c h ： n a d i t i o n a lw o r k o ng r a d i e n tm e t h o d s m e t h o d s c o m p l e t e n e w t o n sm e t l l o da n d | e x a c ts o l u t i o n s c o n s t r u c tb r a n c ha n db o u n d d y n a m i cp r o g r a m m i n g s o l u t i o n sd i v i d ea n dc o n q u e r d e t e r m i n i s t i ct a b us e a r c h s i n g l e s i m u l a t e d a n n e a l i n g s 0 1 ) a t i o ns t o c h a s t i ch i l l - c l i m b e r m o d e r r vp a r t i c l es w a r m s a p p r o x i m a t e p r o b a b i l i s f i c e v o l u t i o n a r ya l g o r i t h m s ： h e u r i s t i c s p o p u l a t i o n g e n e t i ca l g o r i t h m s b a s e dg e n e t i cp r o g r a m m i n g e v o l u t i o n a r yp r o g r a m m i n g e v o l u t i o ns t r a t e g i e s 2 1 2 1 传统方法 表2 - 1 优化算法分类 传统方法对某些优化问题非常适用，而且它们的确定、快速、获得精确解 的性质也正是人们所期望的。这一些方法中有一类是基于穷尽搜索法。对于一 些小的搜索空问可以很方便的运用该类方法，而对于较大的搜索空间可以运用 一些其它方法来减小搜索空间，从而在有效的时间内完成任务。这种方法得到 的解多为全局最优解。还有一类是局部搜索的梯度方法。在局部搜索中，由当 武汉理工大学硕士学位论文 前的可能解求得该解的下一个可能( 暂称为下一代解) ，并比较下一代的解和当 前解的关系，选取较好者取代当前解，从而反复迭代。梯度法和不动点法( f i xp o i n t m e t h o d s ) ，比如牛顿法，就是属于分析型的局部搜索方法。梯度方法计算函数的 梯度或其近似值，然后朝梯度方向进行下一步搜索。不动点法首先构造一个辅 助函数然后再进行迭代从而发现不动点来获得最终的解。 可以发现，这些局部策略仅能保证返回一个局部最优解。为了避免陷入局部 最优，扩大邻域的大小是个常见的想法。但是随着邻域增大，对于n p h a r d 问题， 算法的复杂性也会呈现出指数次方的增加。 另外，许多传统方法的仅能运用于小的问题集，推广性较差。对于一个现 实世界中的优化问题，必须尝试很多不同的方法，甚至要发明相应的新的方法 来解决，这显然是不现实的。我们需要另外的方法来克服这样的困难。 2 1 2 2 现代启发式方法 如前所述，传统的方法，例如分支定界法( b r a n da n db o u n d ) ，分治法( d i v i d e a n dc o n q u e r ) ，会得到全局优化，但是需要大量的运行时间，或者不能解决实际 问题。如果我们使用传统的局部搜索方法，则很容易陷入局部优化。由于我们 不能改变n p h a r d 问题的时间复杂度( 从指数形式转化为多项式形式) ，现代启 发式方法把重点放在避免局部优化这样的问题上。现代启发式算法的另一个特 点是推广性很强，鲁棒性很高。打个比方，虽然林克尼根( l i n k e m i 【g h a n ) 方 法可以比现代启发式算法更好的解决t s p 问题，但是该方法也仅适用于t s p 问题， 然而像e a 这样的算法却可以适用于很多其它的问题。也就是说，现代启发式算 法不会束缚到一个具体的问题域，这样的性质显然更适合实际问题处理。 模拟退火算法( s i m u l a t e da n n e a l i n g ) 就是一个典型的现代启发式方法算法。 算法中有当前点v 。，根据该点评价其邻域中的某一点v 。如果v 。较好，则用其 代替v 。；否则，其会按照概率p 来替换u 。其中： 一i ，( v 。) 一，( v 。) i p=g i 。公式2 2 该概率公式由晶体结晶的物理过程得到，其与初始值无关，算法求得的解 与初始解状态s ( 是算法迭代的起点) 无关；模拟退火算法具有渐近收敛性，已在 理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算 武汉理工大学硕士学位论文 法具有并行性。 另一种现代启发式算法为禁忌算法。在每次迭代中，也是由某当代点的邻 域来得到下一代最优可能点。不同的是，该算法保存一个禁忌表，在禁忌表中 出现的点不允许出现在下一代点中，这样就可以避免算法陷入局部最优。 另一类很重要的算法为基于群体( p o p u l a t i o n ) 的算法。该类算法属于概率 算法，候选解作为群体中的个体被保存下来。典型的，粒子群算法和演化算法 都属于这类算法。 2 2 群体智能简介 群体智能( s w a r mi n t e l l i g e n c e ) 是受社会性昆虫的启发，通过对其行为的模 拟出一系列用于解决传统复杂问题的新方法。群体中存在众多无智能个体，它 们通过相互之间的简单合作表现出来的智能行为即称为群体智能。群体中简单 个体是指具有简单能力( 如搬运、通信等) 的个体，这种能力可以用某一简单 的功能函数来表示。简单合作是指个体只能与其邻近的个体进行某种简单的协 同动作( 如几只蚂蚁共同搬动一个物体) ，或通过改变环境间接的与其它个体之 间进行简单通信( 如一只蚂蚁将信息素留在环境中，为其它蚂蚁提供了一种可 选择路径的信息) 。 群体智能是近年来人工智能研究的一个热点课题，对于没有集中控制并且 不提供全局模型的问题，提供了一种复杂的分布式解决方案。群体智能有以下 几个方面的特点： 由于系统中单个个体的能力比较简单，这样单个个体的执行时间比较 短，实现起来比较方便，具有简单性( s i r n p l i c i t y ) ； 单个个体具有改变环境的能力和系统自调节性； 无中心控制。这样的系统更具有鲁棒性( r o b u s t ) ，不会由于某一个或 者某几个个体的故障而影响整个问题的求解： 群体中相互合作的个体是分布的( d i s t r i b u t e d ) 。这个特点与计算机网络 的工作环境非常类似： 各个体通过对环境的感知进行合作，个体的增加或减少都可使系统的通 信开销非常小。这样的系统具有更好的可扩充性，同时也具有更好的安 全性，可以用来建立网络系统的防火墙体系。 武汉理工大学硕士学位论文 2 3 蚁群系统及其研究概述 2 3 1 蚁群系统简介 蚁群系统( a n ts y s t e m ) 是由意大利学者m d o r i g o 等人于2 0 世纪9 0 年代初提 出的一种新型模拟进化算法，它通过模拟自然界蚂蚁寻食过程中通过信息素 ( p h e r o m o n e ) 的相互交流从而找到由蚁巢至食物的最短路径的现象，提出了一 种基于信息正反馈原理的蚁群优化算法并用于解决t s p 问题( t r a v e l i n g s a l e s m a n p r o b l e m ) a 根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有 任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化( 如 原有路径上有了障碍物) 后，自适应地搜索新的最佳路径。蚂蚁在走过的路上会 释放一种特殊的分泌物信息素( p h e r o m o n e ) ，使得一定范围内其它的蚂蚁能 够觉察到并由此影响他们的行为，当一条路上的信息激素越来越多( 当然，随时间 的推移会逐渐减弱) ，后来的蚂蚁选择这条路径的概率也越来越大，从而增加该 路径的信息激素强度，这种选择过程称为蚂蚁的自催化过程，其原理是一种正反 馈机制，所以蚂蚁系统也称为增强型学习系统。这里我们举一个例子来说明蚂蚁 的搜索机制。 武汉理工大学硕士学位论文 e a b ) a c ) 图2 一l 图2 i 中有一条蚂蚁经过的路径，我们假设a 点是食物，而e 点是蚂蚁的巢穴， 如图2 1a ) 所示。在某一个时刻忽然有一个障碍物出现在蚂蚁经过的路径中，原 有的路径被切断，从a 点到e 点的蚂蚁就必须在b 点决定应该往左还是往右走。 而从e 点到a 点的蚂蚁也必须在d 点决定选择哪条路径。这种决定会受到各条路 径上以往蚂蚁留下的信息素浓度( 即残留信息浓度) 的影响。如果向右的路径上的 信息素浓度比较大，那么向右的路径被蚂蚁选中的可能性也就比较大一些。但 是对障碍出现届第一个到达b 点或d 点的蚂蚁而言，因为没有信息紊的影响，所 以它们选择向左或者向右的可能性是一样的，如图2 1b 1 所示。若以从a 点到e 点 的蚂蚁为例进行说明，对于从e 点到a 点的蚂蚁而言过程基本是一样的。由于路 径b c d 比路径b h d 要短，因此选择b c d 路径的第一只蚂蚁要比选择b h d 的第一 只蚂蚁早到达d 点。此时，从d 点向b 点看，指向路径d c b 的信息素浓度要比指 向路径d h b 的信息索浓度大。因此从下一时刻开始，从e 点经d 点达到a 点的蚂 蚁选择d c b 路径比选择d h b 路径的可能性要大得多。从而使路径b c d ( 或d c b ) 上信息素浓度与路径b h d ( 或d h b ) 上信息素浓度的差变大。而信息素浓度差变大 的结果是选择路径b h d ( 或d r m ) 路径的蚂蚁进一步增加，这又导致信息素浓度差 e搬蜷蒋绺鼙： 武汉理工大学硬士学位论文 进一步加大。 在自然界中，蚁群的这种寻找路径的过程表现为一种正反馈的过程，与人 工蚁群的寻优算法极为一致。如我们把只具备了简单功能的工作单元视为“蚂 蚁”，那么上述寻找路径的过程可以用于解释人工蚁群的寻优过程。由以上分析 可知，人工蚁群和自然界蚁群的相似之处在于，两者优先选择的都是含“信息 素”浓度较大的路径：这在两种情况下，较短的路径上都能聚集比较多的信息素； 两者的工作单元( 蚂蚁) 都是通过在其所经过的路径上留下一定信息的方法进行 间接的信息传递。而人工蚁群和自然界蚁群的区别在于，人工蚁群具有一定的 记忆能力。它能够记忆已经访问过的节点；另外，人工蚁群在选择下一条路径 的时候并不是完全盲目的，而是按一定的算法规律有意识地寻找最短路径( 如在 t s p 问题中，可以预先知道下一个目标的距离) 。 2 3 2 蚁群系统研究现状 为了克服蚁群算法存在的收敛慢、容易出现停滞现象、算法的运算时间长 等缺点，人们提出了许多改进算法。 1 9 9 6 年，m d o r i g o 又提出一种修正的蚁群算法，他们称之为蚁群优化算法 ( a n t c o l o n yo p t i m i z a t i o n ，a c o ) 【2 】。它与前面提到的蚁群算法有三点不 同： a 蚂蚁选择城市时遵循的规则不同，这里使用的是所谓的状态转移规则 ( s t a t et r a n s i t i o nr u l e ) ； b 全局更新规则不同。全局更新不再是对所有的蚂蚁，而是仅对一次循环中 最优的蚂蚁使用： c 增加了局部更新规则，局部更新规则是在所有蚂蚁完成一次转移后执行。 德国学者t h o m a s t u z l e 和h o l e r h o o s 提出的一种改进的算法，最大最小系统 ( m a x m i n a n t s y s t e m ，m m a s ) 是比较好的一个算法，在解决t s p ，q a p 等问题时结果要优于一般的类a c a 算法【3 】。m m a s 与a c s 两者的共同点是 在算法的每次迭代中只允许表现最好的蚂蚁更新路径上的信息素；其不同之 处主要在于如何防止过早的停滞现象( s t a g n a t i o n ) 。m m a s 限定了信息素浓 度允许值的上下限，并且采用了平滑机制，m m a s 在算法启动时将所有支路 上的信息素浓度初始化为最大值r 。，每次迭代后，按挥发系统p 降低信息 武汉理工大学硕士学位沦文 素浓度，只有最佳路径上的支路才允许增加其浓度，并保持在高水平上。但 是，仅仅采用最大最小信息素浓度的限制还不足以在较长的运行时间里消除 停滞现象，因此采用了平滑机制：信息素浓度的增加正比于r 和当前浓度 r 。【f ) 之差。 一些学者还把蚁群算法与其他的算法相结合。意大利学者f a b i 0 ，a b b a t t i s t a 等人受遗传算法的启发提出蚁群算法和遗传法相结合的思路。鉴于在蚁群算 法中参数d ，b ( 分别对应信息素和能见度对决策的权重) 和q ( 对应蚂蚁 在一个周期中留下的信息素量) 的选择对算法的性能有很大影响，可以将 n ，b 和q 看成代表蚂蚁典型特征的染色体g 中的三段代码。在g 中，g 。和g 口 将n ，b 编码为实数，g 。将q 编码为整数，然后将此染色体通过遗传算子交 由一个进化过程处理。这样就把蚁群系统的协作效应与遗传算法的进化效应 结合起来。 吴庆洪等提出了具有变异特征的蚁群算法【4 】。其核心思想是为了克服蚁群算 法收敛较慢的问题，采用逆转变异方式，随机地进行变异，以增大进化时所 需的信息量。这种变异机制充分利用了2 一o p t 交换法简洁高效的特点，因而 具有较快的收敛速度。 2 3 3 蚁群系统的应用领域 蚁群算法在解决很多组合问题( c o m b i n a t o r i a lp r o b l e m ) 上都取得比较理想的 效果。其中有两个比较著名的组合问题，q a p 问题( q u a d r a t i c a s s i g n m e n t p r o b l e m l 和j s p i 题( j o b s h o ps c h e d u l i n gp r o b l e m ) 。作相应调整的蚁群算法可以比较好地 解决这两个组合问题。另外，将蚁群算法对实际问题的解决也取得一定的进展， 如大规模集成电路中的综合布线、电信网络中的路由以及网络路径导航等方面 的应用。 q a p 问题的目标函数可以用一个疗”的对称矩阵来描述。蚁群算法基 于它和t s p 问题这方面的相似性来解决问题的。q a p 问题的目标函数 矩阵s 通过距离向量d 和流向量f 的组合组成，s 。= d 。+ 厶。蚂蚁根 据可见度信息刁油来选择下一个节点，其中t 7 油= l s 讷。矩阵s 的元 素值用作启发因子 5 。 j s p 问题可以用一个加权图描述。每条边的权值用参数对ff 叩t 1 ) 武汉理工大学硕士学位论文 表示。信息r i i 和可见度是通过最长进程时间或者最短完成时间等要 求决定。蚂蚁遍历节点的顺序就是相应的解决答案。在解决1 0 1 0 和 1 0 1 5 的j s p 问题中，蚂蚁算法的解与最优解的误差在1 0 之内，这是 一个相当不错的结果 6 。 大规模集成电路综合布线大规模集成电路中的综合布线可以采用蚁群 算法的思想来进行。在布线过程中，各个引脚对蚂蚁的引力可根据引力 函数来计算。各个线网a g e n t 根据启发策略，像蚁群一样在开关盒网格 上爬行，所经之处便布上一条金属线，历经一个线网的所有引脚之后， 线网便布通了。给定一个开关盒布线问题，问题的计算量是固定不变的， 主要由算法的迭代次数决定，而迭代次数由a g e n t s 的智能和开关盒问 题本身的性质确定。蚁群算法本身的并行法，使之比较适合于解决布线 问题【7 。 电信网络路由电信网络中的路由是通过路由表进行的。在每个节点的路 由表中，对每个目的节点都列出了与该节点相连的节点，当有数据包到 达时，通过查询路由表可知道下一个将要到达的节点。首先对路由表中 的信息素强度进行初始化。在节点x ，以节点i 为目的地址，邻节点为 j 处的信息素强度为，7 l = 1 d * ，d 。为从x 经节点j 到节点i 路径的 最小费用值。然后周期性地释放蚂蚁来进行路由。并修改相应的信息素 的值。仿真结果表明，无论呼叫是均匀分布还是集中分布，利用蚁群算 法所得呼叫拒绝率和平均路径长度均小于最小负载法结果：在呼叫符合 集中分布时，蚁群算法所得呼叫拒绝率低于最短路径法 8 】。 2 4 t s p 问题简介 2 4 1 t s p 问题的定义 t s p 问题的英文名为( t r a v e l i n gs a l e s m a n p r o b l e m ) ，中文译为货郎担问题。 问题的定义很简单，即为一个货郎要走访n 个城市，每个城市必须经过一次且 只能经过一次，最后回到出发的城市就算是完成了一次旅行，问如何能找到一 条最短的路径。其相应的数学描述如下：设有一城市集合c = c ，旬，c 3 ， 武汉理 二大学硕士学位论文 c 。 ，其每对城市c 。，0 c 间的距离为d ( c 。c ) z + 。求一条经过c 中每个城 市正好一次的路径( c ，c ，驯，c 。8 j ，c m 一) ，使得 d ( c 州) ，c 州川) + d ( c 巾) ，c 州) ) 公式2 2 f = 1 最小。这里的( n ( 1 ) ，( 2 ) ，( n ) ) 是( 1 ，2 ，n ) 的一个置换a 2 4 2t s p 问题的实用价值 t s p 问题广泛的存在于许多领域，而且问题的规模( 城市的数目) 都很大。 比如说，电路板钻孔问题，x 射线结晶学问题，v l s i ( 超大规模集成电路) 制 造问题等等。总之，凡是可以抽象成为遍历全部城市次且仅一次，求代价最 小的路径的问题，都可以当作t s p 问题来解决。 以电路板钻孔问题为例，在参考文献【2 3 中描述了一个有1 7 0 0 0 个城市的电 路板钻孔的t s p 应用，该应用所考虑的问题就在于如何布线才能节约材料达到 节省成本的目的。 2 4 3t s p 问题的理论意义 同实用价值相比，t s p 问题的理论意义更加重大。事实上，该问题是作为所 有组合优化问题的范例而存在的。它已经成为并将继续成为测试新算法的标准 问题。这是因为，t s p 问题展示了组合优化的所有方面。它从概念上来讲非常简 单，但是其求解的难度是很大的。如果针对t s p 问题提出的某种算法能够取得 比较好的实算效果，那么对其进行修改，就可以应用于其它类型的组合优化问 题并取得良好的效果。基于上述原因该问题吸引了许多不同领域的研究者， 包括数学、运筹学、物理、生物和人工智能等领域。 2 4 4 所有求解t s p 问题的方法的简介 显然：从理论上讲是可以通过穷举法解决t s p 问题的，只要搜索全部的旅 武汉理【大学硕士学位论文 行路径，一定能够找到最短的一条。也就是说，使用穷举法一定能找到最优解。 但要知道的是，t s p 问题的搜索空间会随着城市数n 的增加而急剧增加，所有旅 行的组合数是( n 1 ) ! 2 。那么，5 个城市的t s p 问题对应1 2 个旅行方案，1 0 个城 市则对应1 8 1 4 4 0 个旅行方案，1 0 0 个城市就要对应4 6 6 6 3 1 0 1 5 5 个旅行方案。 使用常规的穷举法在如此庞大的搜索空间中寻求最优解，对于现有的计算机而 占，存在很大的困难。 既然寻找最优解一直以来存在难以解决的问题，那么各种求近似解的优化 算法就成了比较现实可行的解决方法。几十年来，出现了很多近似优化算法， 如近邻法( n e a r e s tn e i 【g h h o r ) 、贪婪算法( g r e e d ya l g o r i t h m ) 、最近插入法( n e a r e s t i n s e r t i o n ) 、最远插入法( f a r t h e s ti n s e r t i o n ) 、双最小生成树法( d o u b l em i n i m u m s p a n n i n gt r e e ) 等等。近年来，出现了一些解决该问题更为有效的算法，例如神 经网络方法、模拟退火方法，演化计算方法也在其中。这些算法都是以求近似 解为目的的。 2 5 基本蚁群优化算法模型 最初的蚁群系统分为三个不同的模型，分别称之为：a l l 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 1 。9 】。它们的差别在于蚂蚁对信息素 ( p h e r o m o n e ) 的更新方式的不同。为了便于理解，我们以平面上求解t s p 问题 为例来说明。在求解t s p 问题是，为了充分利用整体信息，一般采用a n t q u a n t i t y s y s t e m 。 首先引进如下的记号：设m 为蚂蚁群体的数目，d 。( f ，j = 1 , 2 ，行) 表示城市 i 和j 之间的距离，r 足) 表示t 时刻在城市i 、j 间路径上残留的信息素。初始时 刻各条路径上的信息素相等，设r ，( 0 ) = c 。蚂蚁七伍= 1 , 2 ，删) 在运动过程中， 根据各条路径上的信息素决定下一步要转移的城市，s 表示在t 时刻蚂蚁k 由城 市i 转移到城市j 的概率： l _ 上掣暑岛i f 歹a l l o w e d s = 川。c d f 州f ) 】q 4 。4 公式2 2 l 0e l s e 武汉理工大学硕士学位论文 其中：a l l o w e d = 1 ，2 ，n 卜t a b u 。，表示蚂蚁k 下一步允许选择的城市。 与实际蚁群不同，人工蚁群系统具有记忆功能，集合t a b u 。用以记录蚂蚁k 当前 已经走过的城市，t a b u 。将随着蚂蚁的搜索进程作动态调整。，7 。表示由城市i 转 移到城市 的期望程度，可以根据某种