（控制理论与控制工程专业论文）蚁群算法及其在连续性空间优化问题中的应用.pdf

浙江大学坝j j 学位论文 摘要 蚁群算法是一种随机搜索算法，与其它模拟进化优化算法一样，通 过由候选解组成的群体的进化过程来寻求最优解，它具有许多优良性质 和实际应用价值。本文以基本蚁群算法的性能的分析为背景，探讨了蚁 群算法的构成、性能、特点其及改进措施，提出了在连续空问( 一般函 数) 优化问题中蚁群算法的模型，并通过实例分析了一般函数优化问题 中蚁群算法的性能、特点以及进一步研究的方向。f 主要内容如下： 1 综述了蚁群算法的生物学机理、发展过程：算法特点及其研究 和应用现况，指出其在解决组合优化问题方面的优越性，以及 其在解决连续空间优化问题研究方面的不足； 2 介绍了蚁群算法基本模型a s ( a n ts y s t e m ) 的原理、特点、构成 和实现方法，对基本蚁群算法参数的合理选取进行了实验分析， 对蚁群算法的性能进行了深入的讨论； 3 针对基本蚁群算法性能的不足，借鉴并提出了一系列有针对性 的算法上的改进措施，以使蚁群算法的性能更加优良； 4 提出了用于连续空间( 一般函数) 优化问题的蚁群算法模型， 为蚁群算法付之于实际应用提供了一条可行途径。通过仿真实 验证明该模型用于处理一般函数的优化效果良好，值得进一步 研究； 5 针对s i s o 离散时不变控制系统，在给出了加权矩阵q 与状态反 馈阵k 的取之范围的确定方法的基础上，利用本文提出的连续 性空间优化问题的蚁群算法模型求解了离散l q 逆问题。仿真 结果表明蚁群算法在求解控制优化问题中的有效性。 6 蚁群算法是一种随机搜索算法，它具有许多优良性质，本文的 工作表明，它比目前风行一时的遗传算法、模拟退火算法等具 有更好的适应性。蚁群算法已经在若干领域获得了成功的应用， 但仍有许多尚待研究和解决的课题。斗一一厂 i ：、硝算幸曩f 芝强，； 一十一 ， 一一塑坚盔兰堡生兰竺堡塞 旦 a b s t r a c t t h ea n tc o l o n y a l g o r i t h mi sak i n do fs t o c h a s t i ce x p l o r a t i v ea l g o r i t h m s a st h es a m eo fo t h e rk i n do f s t i m u l a t e de v o l u t i o n a r ya l g o r i t h m s i tf i n d st h e b e s ts o l u t i o no f o p t i m i z a t i o np r o b l e mb ym a k i n gu s e so ft h ee v o l u t i o n a r y p r o c e d u r eo fa s e to fc o o p e r a t i n g a g e n t s o fc a n d i d a t es o l u t i o n s i th a s s h o w e dag r e a td e a lo fs a l i e n tc h a r a c t e ra n dp e r f o r m e dg r e a tv a l u ei n i t s a p p l i c a t i o n c h o o s i n g t h e a n a l y s i s o fc h a r a t e ro fa n ts y s t e m ( t h eb a s i c a l g o r i t h m so f a n tc o l o n y ) a st h er e s e a r c hb a c k g r o u n d ，t h i s p a p e rf o c u s e so n t h em o d e l ，t h eb e h a v i o r , t h ec h a r a c t e r i s t i c sa n di t si m p r o v e m e n t s ，a n dr a i s e s am o d e lo fa n tc o l o n ya l g o r i t h mo n g e n e r a lf 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 f i n a l l y w ed i s c u s st h es a l i e n tc h a r a c t e ro fa n t c o l o n ya l g o r i t h mo nt h e c o n t i n u o u ss p a c e ( g e n e r a lf u n c t i o n ) o p t i m i z a t i o n p r o b l e m s ，a n dp r o p o s et h e r e g i o n o ff u r t h e r i n v e s t i g a t i o n t h em a i nc o n t e n t sa r ec o m p o s e do ft h e f o l l o w i n gp a n s ： 1 t h e b i o l o g i c a lm e c h a n i s m ，t h ed e v e l o p m e n ta n dt h ec h a r a c t e ro f t h ea n tc o l o n ya l g o r i t h ma r eo u t l i n e t h ec u r r e n ts i t u a t i o n so f r e s e a c ha n d a p p l i c a t i o no f t h ea n t c o l o n ya l g o r i t h mi si n t r o d u c e d t h es u r p e r i o f i t yi n s 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 s a n dt h e s h o r t a g e si ns o l v i n gt h ec o n t i n u o u ss p a c eo p t i m i z a t i o n p r o b l e m s a r ep r e s e n t e d 2 t h ep r i n c i p l e ，t h em o d e l ，t h ec h a r a c t e r i s t i c sa n d t h em a n a g e m e n t a b o u tt h eb a s i ca l g o r i t h m so fa n tc o l o n y ( a n ts y s t e m ) a r ea l s o p r e s e n t e d t h e r e a s i o n a b l es e l e c t i o na b o u tt h e p a r a m e t e r s i s d i s c u s s e di ne m u l a t e dt e s t t h ec h a r a c t e r i s t i c sa b o u tt h ea n t c o l o n ya l g o r i t h mi sa n a l y s e dt h o r o u g h l y 3 f o rt h es h o r t a g e so ft h eb a s i ca l g o r i t h m so fa n tc o l o n y , al i s to f i m p r o v e m e n t s h a v e b e e nr e f e r e n c e da n d p r e s e n t e d ，s o t h e c h a r a c t e r i s t i c so fa n t c o l o n ya l g o r i t h m t ob em a d em o r e e x c e l l e n t l y 4 t h em o d e lo fa n t c o l o n ya l g o r i t h m f o r g e n e r a l f u n c t i o n o p t i m i z a t i o np r o b l e m i sp r e s e n t e d af e a s i b l ew a yi sp r e s e n t e df o r a p p l y i n gt h ea l g o r i t h m s t op r a c t i c e t h er e s u l ta b o u tt h ee m u l a t e d 浙江火学硕士学位论文 6 t e s ti sd e m o n s t r a t e dt h a tt h ec h a r a c t e r i s t i c so fa n t c o l o n y a l g o r i t h mf o rg e n e r a lf u n c t i o no p t i m i z a t i o np r o b l e ma r es a l i e n t ， a n di ti sw e a r t h yt om a k ef u r t h e rr e s e a r c h e s t oas y s t e mw h i c hi ss i s oa n dc o n s t a n t ，am e t h e dt o g e tt h e d e f i n i t es c o p e so f w e i g h t i n gm a t r i xqa n d s t a t ef e e d b a c km a t r i x ki sp r e s e n t e d b ym a k i n gu s eo ft h ea n tc o l o n ya l g o r i t h mi nt h e c o n t i n u o u s s p a c eo p t i m i z a t i o np r o b l e m s w h i c hi sp r o p o s e di nt h i s p a p e r , t h ed i s c r e t el e i n v e r s ep r o b l e mi ss o l v e d t h er e s u l t so f t h ec o m p u t e rs i m u l a t i o ns h o wt h a tt h ea n tc o l o n ya l g o r i t h mi sa v a l i dm e t h o df o rs o l v i n gt h ec o n t r o lo p t i m i z a t i o n p r o b l e m s t h ea n t c o l o n ya l g o r i t h m i sak i n do fs t o c h a s t i c e x p l o r a t i v e a l g o r i t h m sw h i c h h a ss h o w e d m a n y e x c e l l e n tc h a r a c t e r i s t i c s i ti s d e m o n s t r a t e dt h a tt h ea n tc o l o n ya l g o r i t h mi sm o r e a d a p t i v a b l e t o t h e g e n e t i ca l g o r i t h m s a n dt h es i m u l a t e da n n e a l i n ga l g o r i t h m s w h i c hw e r ef a s i o n a b l ef o rat i m e a l t h o u g hs o m es u c c e s s f u l a p p l i c a t i o n sh a v eb e e np r e s e n t e d ，i ta l s oh a sm a n yp r o b l e m sf o r s o l v i n ga n dm a k i n g f u r t h e ri n v e s t i g a t e 浙江大学硕十学位论文 致谢 本文是在导师吴俊研究员两年多来的悉心指导下完成的。他严谨的 治学态度和勤恳的工作作风使我深受感染，他渊博的学识和无私的传授 使我获益非浅，我在此表示最衷心的感谢。 同样真诚的感谢还要致与我就读研究生期间所有的授业老师，我将 终身铭记他们的殷殷教诲。我还要感谢先进控制研究所的同学们( 特别 是牟盛静同学) 给予我的帮助和关注。 匹| 年来，我一边工作一边学习，其艰辛足以让我终身难以忘怀，直 至本文成稿之日方才稍感欣慰。在此同样要感谢我所供职单位的领导和 同事们，是他们给予了我精神上的鼓励以及科研经费上的支助。 在我求学生涯中最艰难的时期，给我严厉的督促和无微不至的关爱 的，是我的妻子和家人，我想把本文做为一份礼物，献给他们。 詹上昌 2 0 0 2 年7 月 于杭州 浙江大学坝士学位论文 第一章概述 提要 本章综述了蚁群算法的生物学机理、发展过程、算法特点及其研究和应用现况，指出其在 解决组合优化问题方面的优越性，以及其在解决连续空间优化向题研究方面的不足。 关键词：蚁群算法，模拟进化算法，随机搜索，组合优化 本世纪5 0 年代中期创立了仿生学，人们从生物进化的机理中受到启发，提出 了许多用于解决复杂优化问题的新方法。如遗传算法、进化规划、进化策略等。蚁 群算法是最近几年才提出的一种新型的模拟进化算法，在该算法中，可行解经过多 次迭代后，最终将以最大的概率逼近问题的最优解。蚁群算法是由意大利学者 d o r i g o ，m a n i e z z o 等人在2 0 世纪9 0 年代初首先提出来，并用该方法求解旅行商问 题( t s p ) 、指派问题( a s s i g n m e n tp r o b l e m ) 、j o b s h o p 调度问题等，取得了一系列较好 的实验结果。受其影响，蚁群算法逐渐引起了其他研究者的注意，并用该方法来解 决些实际问题【 “j 。虽然对此方法的研究刚刚起步，但是这些初步的研究已经显 示出一群算法在求解复杂优化问题( 特别是离散优化问题) 方面的一些优越性，证 明它是一种很有发展前景的方法。 1 1 蚁群算法的生物学基础 在昆虫的世界中，蚂蚁的组成是种群居的世袭大家庭，我们称之为蚁群( a n t c o l o n y ) 。之所以将蚁群比拟为一个家庭，是因为蚁群中除了亲缘上的互助关系外， 成蚁划分为世袭制的蚁王和工蚁两个等级，蚁群的大小从几个到几千万个不等，蚁 群又具有高度组织的社会性，彼此间的沟通不仅可以借助触觉的、视觉的联系，在 大规模的协调行动上可以借助外激素( p h e r o m o n e ) 之类的生化信息介质。虽然单 个蚂蚁的行为极为简单( 大致只有4 2 种可分辨的行为【1 】) ，但由单个简单的个体组 成的群体却表现出极其复杂的神奇的行为，因此蚁学家们将整个蚁群视为一个功能 强大的超级生物群。工蚁的觅食行为是最易观察的，工蚁捕食不是在发现食物后就 立即进食，而是将食物搬回家与其家庭成员共同分享。每个工蚁具有如下的职能： 平时在巢穴附近作无规则行走，一旦发现食物，如果独自能搬的就往回搬，否则就 回巢搬兵；一路上它会留下外激素的嗅迹。其强度通常与食物的品质和数量成正比； 若其他工蚁遇到嗅迹，就会循迹前进，但也会有一定的走失率( 选择其他路径) ， 走失率与嗅迹的强度成反比。因此，蚁群的集体行为便表现出一种信息正反馈的现 象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之 浙江大学坝：卜学位论史 问就是通过这种信息的交流达到搜索食物的目的。 人们在试验中发现，在离蚁穴等远的不同方位各放一堆品质和数量大体相同的 食物，则较小的蚁群搬运食物时两路上的兵力大体相同；而足够大的蚁群则会先集 中兵力歼灭其中之一，只有少数的兵力对付另一堆食物。这种做法在客观上是符合 蚁群整体利益的。因为在同一地区可能还有其他的蚁群与之争食。工蚁的觅食过程 可以分为搜索食物和搬运食物两个环节，觅食过程的成本主要发生在搜索环节，而 觅食过程的收益主要发生在搬运环节，成功的觅食策略是最小化搜索食物的时间。 1 2 蚁群算法简介 研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是白组织 的，在许多场合中尽管这些合作可能非常简单，但是它们却可以解决复杂的问题。 这种由群居性生物产生出来的一种集体行为，即产生的群集智能，引起了包括计算 机科学家在内的众多研究人员的兴趣。蚁群算法就是利用群集智能来解决组合优化 问题的典型例子。蚁群算法( a n tc o l o n ya l g o r i t h m ) 是由意大利学者d o r i g o ， m a n i e z z o 等人在2 0 世纪9 0 年代初首先提出来，并逐步引起广泛重视的一种新的仿 生学类算法【2 卅，。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络 算法等启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。 蚁群算法是一种模拟进化算法，d o r i g o 等人充分利用了蚁群搜索食物的过程与 著名的旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ) 之间的相似性，吸收了昆虫王国 中蚂蚁的行为特性，通过人工模拟蚂蚁搜索食物的过程( 即通过个体之间的信息交 流与相互协作最终找到从蚁穴到食物源的最短路径) 来求解t s p 问题。为了区别于 真实蚂蚁群体系统，我们称这种算法为“人工蚁群算法”。为了说明“人工蚁群算 法”的原理，我们首先简单介绍一下蚂蚁搜索食物的具体过程。 像蚂蚁这类群居昆虫，虽然视觉极其微弱，却能找到由蚁穴到食物源的最短路 径。仿生学家们经过大量细致的观察研究发现，生物世界中的蚂蚁在搜索食物时， 能在其走过的路径上释放一种信息素，使得在一定范围内的其他蚂蚁能够察觉到并 影响其搜索行为。蚂蚁个体之间是通过一种称之为外激素( p h e r o m o n e ) 的通讯介 质来相互传递信息的，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能 够在它所经过的路径上留下该物质，而且蚂蚁在运动过程中。能够感知路径上这种 物质的存在及其强度，并且以此来指导自己的运动方向，蚂蚁倾向于朝着该物质强 度高的方向移动。因此，由大量蚂蚁组成的蚁群( a n tc o l o n y ) 的集体行为便表现 出一种信息正反馈的现象：当某路径上经过的蚂蚁越多时，留在相应路径上信息素 的迹( t r a i l ) 也越多，以致信息素的强度增大，后来的蚂蚁选择该路径的概率也就 越高，从而进一步增加该路径的信息素强度，这样的选择过程被称为蚂蚁的自催化 行为( a u t o c a t a l y t i cb e h a v i o r ) 。蚂蚁个体之间就是通过这种信息的交流达到快速搜 浙江火学硕l 学位论文 索食物的目的的。 人工蚁群算法是受到人们对自然界中真实的蚁群集体行为研究成果的启发，而 提出的一种基于种群的模拟进化算法，属于随机搜索、全局优化算法。与其它模拟 进化算法一样，通过多个候选解( 可行解) 组成的群体的进化过程并以最大概率逼 近问题的最优解。该过程包括两个基本阶段：适应阶段和协作阶段。在适应阶段， 各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交 流，以期产生性能更好的解。以t s p 问题的求解为例，求解开始时，蚂蚁群各自随 机行动，以后则按概率选择留有信息素的迹且尚未走过的路径，直至完成一次搜索， 这样即构成问题的一个可行解。因而，蚂蚁群成功地搜索一轮所形成的是一组可行 解，然后记录其中的最好解，各蚂蚁所遗留下的信息索的迹也将按持久程度( 即挥 发状况) 保留到以后各轮搜索，从而为蚂蚁此后的路径搜索产生特有的生物行为影 响。 1 3 蚁群算法的特点及其应用 蚁群算法是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等 启发式搜索算法以后的又一种应用于组合优化问题的启发式随机搜索算法。众多的 研究结果已经证明，蚁群算法具有很强的发现较好解的能力，这是因为该算法不仅 利用了j f 反馈原理、在一定程度上可以加快进化过程，而且是一种本质并行的算法， 不同个体之间不断进行信息的交流和传递，从而能够相互协作，有利于发现较好的 解。蚁群算法可以解释为一种特殊的强化学习( r e i n f o r c e m e n tl e a r n i n g ) 算法1 7 j 。蚁 群算法具有如下的优点佯l ： 较强的鲁棒性：对蚁群算法模型稍加修改，便可以应用于其它问题： 分布式计算：蚁群算法是一种基于种群的进化算法，具有本质的并行性，易于 并行实现： 易于与其它方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的 性能。 蚁群算法也存在一些缺陷1 8 】： 需要较长的搜索时间：蚁群算法的时间复杂度可以说明这一点； 容易出现停滞现象( s t a g n a t i o n b e h a v i o u r ) ：即在搜索进行到一定程度后，所有个 体所发现的解完全一样，不能对解空间进一步进行搜索，不利于 发现更好的解。 对于上述两个问题，已经引起了许多研究者的注意，并提出了一些改善措施， 如m d o r i g o 提出的a n t q s y s t e m i 9 1 ，t h o m a s 等人提出的m a x - m i n a n t s y s t e m ”，郝 晋等人提出的具有扰动特性的蚁群算法1 “，吴庆洪等人提出的具有变异特征的蚁群 算法旧，陈烨提出的带杂交算子的蚁群算法【1 3 】，王颖等人提出的自适应蚁群算法川 浙江大学碳l ：学位论文 等。 蚁群算法已经在若干领域获得了成功的应用。其中最为成功的应用是在组合优 化问题中的应用，其典型代表有t s p ，q a 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 ) ，j o b s h o p 调度等经典组合优化问题。文献 2 ，4 ，1 0 ，1 4 】用蚁群算法求解t s p 问题，结果表明该 方法优于其它方法。文献 2 ，1 5 研究了指派问题( q a p ) 的蚁群算法求解效果。蚁 群算法在i o b s h o p 调度问题中的应用也得到了初步研究 2 ，1 4 ，并取得了一系列较 好的实验结果。d c o s t a 等人i l6 i 在m d o r i g o 等人研究成果的基础上，提出了一种 求解指派问题的一般模型，并用来研究图着色问题。gb i l c h e v , i c p a r m e e 【l7 1 以及 魏平等人i 引1 研究了求解连续空间优化问题的蚁群系统模型。蚁群算法在动态环境下 也表现出高度的灵活性和健壮性，如其在电信路由控制方面的应用被认为是目前较 好的算法之一【i8 1 。目前，国内也有一些学者对蚁群算法及其在电信领域的应用开展 了研究【1 9 - 2 1 】。虽然对此方法的研究刚刚起步，但是已有的一些初步研究结果已经显 示出蚁群算法在求解复杂优化问题方面的一些优越性。 在旅行商问题中，由于每一个节点( 城市) 之间的距离是己知的，从任一节点 到下一节点，有哪些节点可供选择也是已知的，当用蚁群算法解决t s p 时，若蚂蚁 处于某节点上，可以直接利用本文公式( 1 ) 来计算各条路径的选择概率，从而确定下 一个最适合选择的节点。如果蚂蚁处于某一节点时，下一步有哪些节点可供选择是 未知的，各个节点之间的距离也是未知的，在这种情况下，蚂蚁就无法直接应用公 式( 1 ) 计算选择概率从而作出路径选择的决策。比如用蚁群算法来求一个连续空间函 数的最优解时，就属于上述的情况。蚁群算法从其机理来说是一种天然的组合优化 方法，相对其它的各类启发式搜索算法，具有明显的优越性，而在求解连续空间优 化问题时，蚁群算法模型、各个参量的物理意义等必须做很大的改动才能应用，在 求解连续空间优化问题方面其优越性相对其它各类启发式搜索算法要弱，在实际工 程问题中也未见很好的应用。 在实际控制工程的优化问题中大量遇到的是连续性问题，因此，在将优化性能 良好的蚁群算法用于连续性空间优化问题时，只能利用蚁群算法的原理和人对优化 函数取得的有关先验知识来构造相应的算法模型，并对算法中许多实施细节加以修 正，从而确定在优化过程中蚁群协同决策所选择的移动方向，由此来求得最优解。 本文提出了一种运用人工蚁群搜索的规律来求解一般函数( 连续性变量空间) 优化 的蚁群算法模型。该模型在全局上表现为人工蚂蚁在某种先验知识和启发信息引导 下的优化搜索，在局部上则采用了随机性的搜索策略。该策略能提高搜索过程的效 率以及搜索状态的多样性和随机性，而且不受目标函数是否连续、可微等因素的限 制，为蚁群算法应用予实际优化问题提供了一条可行途径。 1 4 本文的主要工作 浙江人学硕l 学位论文 本文以基本蚁群算法性能的分析为背景，探讨了蚁群算法的构成、性能、特点 其及改进措旖，提出了在连续空间( 一般函数) 优化问题中蚁群算法的模型，并通 过实例分机了连续空间优化问题中蚁群算法的性能、特点以及进一步研究的方向。 主要内容如下：第一章综述了蚁群算法的生物学机理、发展过程、算法特点及其研 究和应用现况，指出其在解决组合优化问题方面的优越性，以及其在解决连续空间 优化问题研究方面的不足；第二章介绍了蚁群算法基本模型a s ( a n ts y s t e m ) 的原理、 特点、构成和实现方法，对基本蚁群算法参数的合理选取进行了实验分析，对蚁群 算法的性能进行了深入的讨论；第三章针对基本蚁群算法性能的不足，借鉴并提出 了一系列有针对性的算法上的改进措施，以使蚁群算法的性能更加优良；第四章提 出了用于连续空间( 一般函数) 优化问题的蚁群算法模型，为蚁群算法付之于实际 应用提供了一条可行途径。通过仿真实验证明该模型用于处理一般函数的优化效果 良好，值得进一步研究；蚁群算法是一种随机搜索算法，它具有许多优良性质，本 文的工作表明，它比目前风行一时的遗传算法、模拟退火算法等具有更好的适应性。 第五章针对s i s o 离散时不变控制系统，在给出了加权矩阵q 与状态反馈阵k 的取 值范围的确定方法的基础上，利用本文提出的连续性空间优化问题的蚁群算法模型 求解了离散l q 逆问题。仿真结果表明蚁群算法在求解控制优化问题中的有效性。 蚁群算法已经在若干领域获得了成功的应用，但仍有许多尚待研究和解决的课题。 在第六章中指出了蚁群算法的应用和理论研究中，今后有待深入研究的有关课题。 浙江大学坝i ? 学位论文 第二章蚁群算法基本模型及其特点 提要 本章介纠了蚁群算法基本模型a s ( a n ts y s t e m ) 的原理、特点、构成和实现方法，对基本蚁 群算法参数的合理选取进行了仿真实验研究，对蚁群算法的性能进行了深入的讨论。 关键词：蚁群算法，转移概率，可见性，组合优化，旅行商问题 2 1 引言 蚁群算法是最近几年才提出的一种新型的随机搜索模拟进化算法，由意大利学 者m d o r i g o 等人首先提出，他们称之为蚁群系统( a n tc o l o n ys y s t e m ) ，并用该方 法求解旅行商问题、指派问题、i o b s h o p 调度问题等，取得了一系列较好的实验结 果。受其影响，蚁群系统模型逐渐引起了其他研究者的关注，并用该算法来解决一 些实际问题。虽然对此方法的研究刚刚起步，但一些初步的研究结果已经显示出蚁 群算法在求解复杂优化问题，特别是离散优化问题方面的一些优越性，证明它是一 种很有发展前景的优化方法。 2 2 蚁群算法基本模型a s ( a n ts y s t e m ) 的描述 2 2 1 基本模型的原理 生物学家的研究已经表明，一只蚂蚁的记忆和智能是非常有限的，但是，由于 蚂蚁之问可以通过一些信息素进行协同作用，实现蚂蚁之间的信息交流和传递，可 以共同做出令人惊讶的行为。下面以蚂蚁搜索食物的过程为例，分析蚂蚁是如何通 过上述的信息交流和传递的协同作用，最终找到从蚁穴到食物源的最短路径的。 图l 中，a 为蚁穴，b 为食物源，从a 到b 有两条路径可走，a c b 是长路径， a d b 是短路径。蚂蚁走过一条线路以后，在其路径上会留下信息素气味，后来的蚂 蚁就是根据留在各路径上的这种气味的强度选择应该移动的方向。图1 ( a ) 表示起始 时的情况，假定蚁穴中有4 只蚂蚁，分别用l ，2 ，3 ，4 表示。开始时蚁穴中蚂蚁1 ， 2 向食物源移动，由于线路a c b 和a d b 均没有蚂蚁通过，在这两条路径上都没有 原始的信息素气味，因此蚂蚁1 和2 选择这两条线路的机会均等。不妨令蚂蚁1 选 择a c b 线路，蚂蚁2 选择a d b 线路，并且假定各个蚂蚁行走的速度相同，当蚂蚁 2 到达食物源b 时，蚂蚁1 还在途中，如图1 ( b ) 所示。蚂蚁2 到达食物源以后就返 回，这时从b 点返回也有两条线路的选择，而哪一条线路上的信息素气味重，就选 择哪一条。因为蚂蚁l 还在途中，没有到达终点，即此时在b c a 线路上靠近b 端 处，蚂蚁l 还没有留下信息素气味，所以蚂蚁2 返回蚁穴的路径只有一个选择，就 是由原路返回。当蚂蚁2 到达a 端时，蚂蚁3 开始出发，蚂蚁3 的线路选择将必定 浙江大学颂士学位论文 是a d b ，因为这时a d b 线路上信息素的气味比a c b 线路上重( a d b 路径上已有 蚂蚁两次通过) ，如图i ( c ) 所示。当蚂蚁l 到达食物源b 点时，由于同样的理由， 蚂蚁i 所选择的返回线路必将是b d a ，如图1 ( d ) 所示。如此继续下去，由大量蚂蚁 组成的蚁群的集体行为便表现出一种信息正反馈现象：沿路径a d b 移动的蚂蚁越 多，则后来者选择该路径的概率就越大， 体之问就是通过这种信息的交流达到最佳 c 这正是蚁穴到食物源的最短路径。蚂蚁个 【d l d j 图1 蚁群搜索线路 蚁群算法是受到对真实的蚁群行为研究的启发提出来的，这里所说的“蚁群算 法”更恰当的名称应为“人工蚁群算法”。下面我们引用m d o r i g o 所举的例子【4 j 来具体说明蚁群算法的原理。 如图2 所示，设a 是蚁穴，e 是食物源，h c 为一障碍物。由于障隘物的存在， 蚂蚁只能经由h 或c 由a 到达e ，或由e 到达a ，各点之间的相互距离如图所示。 e = u h 爿忉l 时秆 图2 人工蚁群行为 设每个时间单位有3 0 只蚂蚁由a 到达b ，有3 0 只蚂蚁由e 到达d 点，蚂蚁过后 留下的激素物质量( 以下称之为信息素) 为1 。为方便，假设该物质停留时间为1 。 在初始时刻，由于路径b h 、b c 、d h 、d c 上均无信息存在，位于b 和d 的蚂蚁 可以随机选择路径。从统计的角度可以认为它们以相同的概率选择b h 、b c 、d h 、 d c 。经过一个单位时间后，在b c d 上的信息量是路径b h d 上信息量的二倍。t = 1 时刻，将有2 0 只蚂蚁由b 和d 到达c ，有1 0 只蚂蚁由b 和d 到达h 。随着时间 浙江大学坝i 学位论文 的推移，蚂蚁将会以越来越大的概率选择路径b c d ，最终完全选择路径b c d 。从 而找到【b 蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息交换是一个正 反馈过程。 在i 目然界中，蚁群的这种寻找路径的过程表现为正反馈的过程，与人工蚁群的 寻优算法极为一致。如果我们将在优化求解中那些只具备简单功能的单元看作“蚂 蚁”，那么上述寻找路径的过程可以用于解释人工蚂蚁的寻优过程。 由以上分析可知，人工蚁群和自然界蚁群的相似之处在于，两者优先选择的都 是含“信息素”浓度较大的路径。人工蚁群和自然界蚁群的区别在于，人工蚂蚁具 有记忆或智能功能，它能够记忆已经访问过的节点；人工蚂蚁有一定的视觉，人工 蚁群在选择下一条路径的时候，并不是完全盲耳的，而是按一定的算法规律有意识 地寻找最短路径( 如在t s p 问题中，下一个目标的路程是可以预先知道) ：人工蚂 蚁的生活环境是时域离散的。 2 2 2 基本模型的描述 现在用求解平面上。个城市的t s p 问题( i ，2 。3 表示城市的序号) 为例说明 蚁群算法的基本模型。对于其它问题，可以对此模型稍作修改便可应用【l ”。假设将 。只蚂蚁放入一个随机选择的城市中；d ，( f = l 23 ，n ) 表示城市i 和城市之间的距 离；“( ，) 表示t 时刻在城市i 和城市，连线上残留的信息量，初始时刻，各条路径上 信息量相等，设o ( o ) ：，( c 为常数) 。蚂蚁k ( k = l 。2 ，m ) 在运动过程中，根据各条 路径上的信息量选择下一个它还没有访问的城市，同时在完成一步( 从一个城市到 达另外一个城市) 或者完成一个循环( 完成对所有一个城市的访问) 后，更新所有 路径上的残留信息量。选择下一个城市的依据主要为：( ，) ，时刻在城市f 和城 市j 连线上残留的信息量，即由蚁群算法所提供的信息；蚂蚁由城市i 转移到 城市j 的期望信息，这一启发式信息可由所要解决的问题给出，并由一定的算法来 实现，在t s p 问题中般取珊= l 如，在这里可以称为先验知识。p ；( r ) 表示在f 时 刻蚂蚁t 由城市i 转移到目标城市的概率： 弦卜 一a u 一虮 l , v e a l l o w c d + j 0 ， o t h e r w i s e 即人工蚂蚁选择下一个目标城市的可能性是题目本身所提供的启发信息珊与从“蚂 蚁”目i j 口所在城市到目标城市路径上残留信息量t o ( t ) 的函数。由公式( 1 ) 可知，蚂蚁 在选择路径时会尽量选择离自己距离较近且信息素浓度较大的方向，即j = m a x ( p ：) 概率值最大的方向。上式中： 浙江人学颂士学位论文 a l l m v e d 。= f l , 2 ，一) 一t a b u 女表示在t 时刻蚂蚁k 下一步允许选择的城市( 即还没 有访问的城市) 。与真实蚁群系统不同，人工蚁群系统具有一定的记忆 功能，这里用t a b ( 女= l 。2 m ) 记录蚂蚁目前已经走过的城市； a 残留信息量的相对重要程度； 口期望值的相对重要程度； 经过n 个时刻，蚂蚁完成一次循环，在进行下轮循环前，必须将最新的蚂蚁访问 过的各路径上留下的新信息加入到勺中。信息量要根据下式作调整： 7 ( f + h ) 2 p r ! i ( t ) + a r f ， ( 2 ) 6 0 = ( 3 ) 上两式中： ，信息残留系数。模仿人类记忆的特点，旧的信息将逐步削弱，随着时间 的推移，以前留下的信息将要逐渐消逝，用参数l p 表示信息消逝程度 ( 即挥发程度) 。 r i 第k 只蚂蚁在本次循环中( 在时间段，到( h n ) 内的访问过程中) ，留在i 到j 路径上的信息量； “一一表示本次循环中所有可能经过f * ，的蚂蚁留在f 到，路径上的信息量 的增量。 关于砖的计算，m d o r i g o 曾给出三种不同的实现方法【4 】，分别称之为a n t 。c y c l e s y s t e m ，a n t d e n s i t ys y s t e m ，a n t - q u a n t i t ys y s t e m 。它们的差别在于表达式苟的不同。 在a n t c y c l es y s t e m 模型中： 。硝； 号汴也e 她a n t u s e s e d g e t f ) i n i t s t o u 曲一一m 叭一( 。) 1 0 o t h e r w i s e 在a n t d e n s i t ys y s t e m 模型中： 妨：坛r 恤t u s e s c 姆“川n i t s l o u r b n f a n d f + 1 l0o t h e r w i s e 在a n t q u a n t i t ys y s t e m 模型中： a 苟= 撂黧竺咖”吨“门m “啪”k ”删“ 上述式( 4 ) 、( 5 ) 、( 6 ) 中： 浙江大学倾k 学位论文 1 0 0 为一常量，为蚂蚁循环一周或一个过程在经过的路径上所释放的信息素 总量。 如表示第t 只蚂蚁在本次循环中所选择路径的长度。 上述三种算法的区别在于：前者利用的是蚁群的整体信息，即走完一个循环后 才进行残留信息量的全局调整：而后两种模型中蚂蚁每走一步( 即从时间t 到( ) ) 都要更新残留信息的量，而不是等到所有的蚂蚁完成对所有”个城市的访问以后。 2 3 基本蚁群算法模型的实现 从以上的蚁群算法基本模型可以看出，其寻找最优解的过程实际上是一个有限 的递推过程，因而适合也便于在计算机上实现。其实现过程可以用以下的伪代码来 表述： b e g i n 初始化过程： n c y c l e = 1 ； b e s t c y c l e 2 1 ； f 。= c ；a r 0 = 0 ； ，7 ，( 由某种启发式算法确定) ； t a b u ；= m ： w h i l e ( n o tt e r m i n a t i o nc o n d i t i o n ) f o r ( k = 1 ；k m ；k + + ) f 将m 个蚂蚁随机放置于初始城市上；) f o r ( i n d e x = o ；i n d e x n ；i n d e x + + ) ( i n d e x 为当前循环中已经走过的城市个数) f o r ( k _ 0 ；k m ；n 斗) 以概率p & “i 。州川儿选择下一城市； ea l l o w e d k ( ，) ； ) 将刚刚选择的城市加入到t a b u 。中； 根据式( 2 ) 、( 3 ) 、( 4 ) 计算r 5 ( n c y c l e ) ，r ! t ( n c y c l e + 1 ) ； 确定并保存本次循环中找到的最佳路径； n c y c l e = n c y c l e + 1 ； 输出最佳路径及结果； e n d 浙江人学坝士学位论文 算法实现的计算机程序流程框图如图3 所示 图3 基本蚁群算法计算机程序流程图 在以上算法的实现中，算法模型( a n t c y c l es y s t e m ，a n t d e n s i t ys y s t e m ， a n t q u a n t i t ys y s t e m ) ，以及有关算法参数( q , a ，房p 等) 的最佳选择，可以由实验来 确定。算法的停止条件可以用固定循环次数或进化趋势不明显时便停止计算。 2 4 蚁群算法基本模型中有关算法参数的选择1 2 2 | 2 4 1 算法模型的选择 关于f ；：的计算，是蚁群算法中实现随机搜索和快速收敛的关键环节。m d o r i g o 曾给出三种不同的实现方法1 4 j ，分别称之为a n t c y c l es y s t e m ，a n t d e n s i t ys y s t e m ， a n t - q u a n t i t ys y s t e m ，它们的差别在于表达式6 f # 的不同。 在a n t d e n s i t y 算法中，由式( 5 ) 可见，从城市i 到j 的蚂蚁在路径上残留的信 息量为o d 。由于a l ，为城市i 到城市，的距离，因而残留信息量会随着城市间距离 的不同丽变化；在a n t q u a n t i t y 算法中，由式( 6 ) 可见，从城市f 到的蚂蚁在路径 上残留的信息量为一个与路径无关的常量q ；在a n t c y c l e 算法中，由式( 4 ) 可见， 从城市，到j 的蚂蚁在路径上残留的信息量为q “，由于“为第k 只蚂蚁在该次循环 中所走过路径的总长度，因此残留信息量的强度与该次循环中所获得解( 循环路径) 的优劣有关，更新规则会让短路径( 较优的解) 上对应的信息量逐渐增大。 可见上述三种算法模型的性能是有所差别的，后两种算法与前一种算法的区别 浙江大学坝：l 学位论义 是：后两种算法中蚂蚁每走一步，都将更新相应路径上残留信息，而并不是等到所 有蚂蚁都完成对所有一个城市的访问以后。上述三种算法模型的性能可以通过计算 机仿真实验进行研究。对此取如下的t s p 问题及算法参数进行了仿真比较： 距离矩阵取为：l = o 9 89 92 78 9 1 7 59 62 66 44 9 9 8o 5 4 9 87 31 8 7 78 96 36 4 9 95 4o6 i 3 6 6 9 4 6 5 31 3 8 1 2 7 9 86 1 o 8 67 5158 72 l8 7 8 97 33 68 6o4 61 98 76 54 6 1 7 51 86 97 54 6o2 65 32 12 3 9 67 74 61 51 92 604 63 65 4 2 68 95 38 78 75 3 4 6 o7 56 5 6 46 3 1 32 i6 52 l3 67 5o5 4 4 96 48 ls 74 62 35 46 55 4o 蚂蚁数墩为。m = 5 ，蚂蚁循环周所释放总信息量取为：0 = 1 ，信息素残留常数取