（模式识别与智能系统专业论文）蚁群算法及其在移动机器人路径规划中的应用.pdf

中南大学硕士学位论文摘要 摘要 蚁群算法是一种新颖的进化算法，其主要特征足采用正反馈搜索 机制、分布式计算方法以及贪婪的启发式策略( g r e e d yh e u r i s t i c ) 。 迄今为止，蚁群算法已解决了许多实际问题，显示出蚁群算法在求解 复杂问题( 特别是离散优化问题) 方面的优越性。 本文综述了蚁群算法的产生和发展历程；从群居昆虫的集体行为 出发，详细阐述了其生物学机理；介绍了基本蚁群算法的原理、模型、 特点、实现，并通过查阅文献说明了基本蚁群算法模型中各参数的合 理选择方法；同时针对蚁群算法的一些缺点，列举了当前的一些典型 的蚁群算法的改进算法，并对其在各领域的应用做了简要的叙述。在 此基础上，根据移动机器人路径规划问题中的特性，提出了一种静态 环境下基于蚁群算法的移动机器人路径规划方法。该方法包括三个步 骤：第一步是采用链接图理论建立移动机器人的自由空间模型，第二 步是采用n i j k s t r a 算法改进的d i j k s t r a 算法在自由空间中搜索出一条 无碰撞次优路径，第三步是采用改进a s 算法a c s 算法对次优路径 的位置进行调整和优化，从而得到机器人的全局最优路径。通过仿真 结果对比，证实了本文所提出的方法无论是收敛速度、解的波动性、 动态收敛特征、还是计算效率都比基于实值g a 的全局路径规划方法 更好一些。 关键字：蚁群算法，自组织理论，遗传算法，路径规划 中南大学硕十学位论文a b s t r a e t a b s t r a c t a n ts y s t e ma l g o r i t h mi sak i n do fn o v e l t ye v o l u t i o na l g o r i t h m t h e m a i nc h a r a c t e r i s t i c so ft h i sm o d e la r ep o s i t i v ef e e d b a c k , d i s t r i b u t e d c o m p u t a t i o n , a n dt h eu s eo fac o n s t r u c t i v eg r e e d yh e u r i s t i c s of a r , a n t s y s t e ma l g o r i t h mh a ss o l v e dm a n yp r a c t i c a lp r o b l e m s i t ss u p e r i o r i t yi n s o l v i n gc o m p l e xp r o b l e m , e s p e c i a l l yi nt h ed i s c r e t ea s p e c t s ，h a sb e e n m a n i f e s t e d t h eo r i g i na n dt h ed e v e l o p m e n to fa n ts y s t e ma l g o r i t h mi so u t l i n e d i nt h i sp a p e r d e r i v e df r o mt h ec o l l e c t i v eb e h a v i o ro fs o c i a li n s e c t s , w e e x p a n d t h e b i o l o g i c a l m e c h a n i s m s t h ep r i n c i p a l ，t h em o d e l ，t h e c h a r a c t e r i s t i c sa n dt h ea p p l i c a t i o no ft h ea n ts y s t e ma l g o r i t h ma r e p r e s e n t e d ，m e t h o d so ft h er e a s o n a b l es e l e c t i o no fp a r a m e t e r sa r ea l s o m e n t i o n e da c c o r d i n gt os o m er e f e r e n c e s m e a n w h i l e ，s o m ec l a s s i c a l i m p r o v e da n ts y s t e ma l g o r i t h m st om a k eu pf o rt h es h o r t c o m i n g so f a n t s y s t e ma l g o r i t h ma n d i t sw i d e s p r e a da p p l i c a t i o n sh a v eb e e ni n 仃o d u c e d o nt h eb a s i so ft h a t , a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h ep a t hp l a n n i n g o fm o b i l er o b o t si nt h es t a t i ce n v i r o n m e n t ，an e wm e t h o db a s e do l la n t a l g o r i t h mw a sp r o p o s e d t h i sm e t h o di n c l u d e st h r e es t e p s ：t h ef i r s ts t e pi s a d o p t i n gt h em a k l i n kg r a p ht h e o r yt oe s t a b l i s ht h ef l e es p a c em o d e lo f t h em o b i l e r o b o t , t h e s e c o n d s t e p i s a d o p t i n g t h e d i j k s t r a a l g o r i t h m i m p r o v e dd i j k s t r aa l g o r i t h m t of r e do u ta s u b - o p t i m a l c o l l i s i o n - f r e e p a t h , a n dt h et h i r ds t e p i s u s i n gi m p r o v e da s a c s a l g o r i t h mt oa d j u s ta n do p t i m i z et h es u b - o p t i m a lp a t hs oa st oo b t a i nt h e g l o b a lo p t i m a lp a t h b yc o m p a r i n gw i t ht h ep a t hp l a n n i n gm e t h o db a s e d o nt h er e a l c o d e dg e n e t i ca l g o r i t h m ，i th a sb e e nc o n f i r m e dt h a tt h e p r o p o s e dm e t h o dh a sb e t t e rp e r f o r m a n c ei nc o n v e r g e n c es p e e d , s o l u t i o n v a r i a t i o n , d y n a m i cc o n v e r g e n c eb e h a v i o r , a n dc o m p u t a t i o ne f f i c i e n c y k e yw o r d s ：a n ts y s t e m a l g o r i t h m , s e l f - o r g a n i z a t i o n ，g e n e t i c a l g o r i t h m , p a t hp l a n n i n g 中南大学硕十学位论文第一章绪论 第一章绪论 1 1 蚁群算法的产生和发展 生命在长期进化过程中，积累了很多奇特的功能，人类很早就从中得到启发 而改进自己的工具，如史书中记载飞蓬草是菊科植物，生长在山坡、草地、牧场 或林带边缘。它的茎直立高达6 0 厘米。由于它枯后根断，遇风飞旋，因此叫飞 蓬。传说古人是受飞蓬的启示后发明轮子的；相传我国古代的著名工匠鲁班，他 在土木工程方面有许多创造发明。有一次，鲁班上山伐木被野草划破了手。他摘 下草叶轻轻一摸，发现叶子边缘有许多锋利的小齿。于是鲁班就在铁片上做出小 齿，经过反复试验和改进，终于发明了当时急需的木工用锯子也许人们对于早 先的发明，只是偶然的模仿和发现，但是后来人们逐渐有意识地进行这方面的研 究，这就产生了“仿生学” 仿生学( b i o n i c s ) 这个名词来源于希腊文“b i o n ”，其含义是生命的单位， 并不是大家所想象的那样认为仿生学就是把生物学和电子学两门学科合并起来。 事实上，仿生学的研究涉及到其它许多学科。具体的讲，仿生学主要是观察、研 究和模拟自然界各种各样的特异本领，诸如生物本身特殊的结构、各种器官的功 能、体内的物理和化学过程、能量的供给、信息的加工、记忆与传递等，以便将 这些优异的性能移植到科学技术中去，来改善旧的、创造新的各式各样的自动装 置和调节系统；提供效率高、可靠性好、动作灵活、结构简单、体积小、价格低、 最接近于生命系统的技术装置。这样的例子有很多，如海豚和潜水艇：海豚是游 泳能手，时速可达5 3 千米，在追捕食物和逃避敌害时，速度还能增大一倍。主 要原因是海豚的体形呈良好的流线型，还有特殊的皮肤结构像个很好的消振器， 所以海豚在水中受到的阻力很小。现代潜水艇的外形很像海豚，还在潜水艇表面 上覆盖人造海豚皮，使潜水艇在水中受到的阻力至少降低一半，潜水艇的速度大 大提高，也节约了燃料。又如蝙蝠和雷达：蝙蝠采用回声定位的方式来探测目标。 它在喉内产生超声波，通过口或鼻孔发射出来。被物体反射回来的超声信号，由 蝙蝠的耳朵接收，蝙蝠就根据反射信号判定目标的性质和距离。雷达的工作原理 和蝙蝠的回声定位方式相似。再如蜻蜓翅膀和飞机：蜻蜒在长期的进化中有一种 抗颤振的结构，那就是在翅膀末端前缘长有“翅痣”，如果把它们切除，蜻蜒就 飞不好。现代飞机机翼末端前缘也有类似的“配重区”，用来消除颤振。还如人 和机器人：机器人早已由科学幻想变成现实，目前世界上成千上万的机器人在各 行各业大显身手。它们模仿人的动作、人的感觉甚至人的思维，代替人在恶劣环 中南大学硕士学位论文第一章绪论 境、危险场所或动作要求精细复杂的工作岗位上不知疲劳地工作着。新一代的机 器人还将模仿人的自学本领，更好地代替人的劳动。 目前，这种仿生学的思想同样的也被应用到了优化算法设计中，如人们模拟 人类智能，产生了进化编程( e v o l u t i o n a r yp r o g r a m m i n g ) ：模拟对金属材料的淬 火进程产生了模拟退火( s i m u l a t e da n n e a l i n g ) 算法；在模拟鸟群社会的基础上， 产生了粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n , p s o ) 算法；模拟生物免疫学和 基因进化机理，产生了免疫算法( i m m u n ea l g o r i t h m ) 等“1 。2 0 世纪9 0 年代，意 大利学者d o r i g o ，m a h i e z z o ，c o l o m i 等人受到自然界中真实的蚁群集体行为的 启发而首先提出来了蚂蚁算法( a n ts y s u n n a l g o r i t h m ) 。 近年来，研究人员发现，蚂蚁能够将。几何信息学”有效地“应用”在认路 上。群体生活的蚂蚁经常独自外出寻找食物，有时走很远的路。从很远的地方回 到蚁穴，不是一件简单的事情。但小小的蚂蚁却有一套杰出的认路本领，即使浓 云密布，或者地面上被破坏，它们仍旧会找到蚁巢，只不过要多走些弯路而已。 为什么蚂蚁能够准确寻找归途，这个问题像谜团一样，长久吸引着动物学家的兴 趣。在探索过程中，研究者也找到了蚂蚁用来辨别方向的、行之有效的方法。比 方说，发挥超常的记忆力，利用气味信息等。科学家肯定，化学信息在蚂蚁识途 中发挥着重要作用。研究结果显示，当蚂蚁外出觅食或在回家的途中，一般情况 下它们都会释放特殊的气味来标示行进的轨迹当行进路线出现一定角度的 转弯，它们便会释放这种微量的特殊气味作为路口路标，同时标示出来的路口角 度还会暗示是否有食物源存在，或仅仅就是一条普通的岔路口。研究人员在文章 中介绍称，在对野外蚂蚁活动的研究过程中研究者发现，当专职负责侦察任务的 侦察蚂蚁从蚁穴出发后，它们会运用一种有特殊气味的信息激素全面标示出其行 进的轨迹，而后续出洞的工蚁们将依照这些信息素的指示向有食物的目的地不断 迸发。 模拟群体智能解决问题已成为近几年来的一个热点话题。这种方法由相对简 单的智能体( a g e n t ) 之间直接通信或间接通信，合作进行分布式问题求解，强 调分布性，灵活性和鲁棒性。在组合优化、网络通信和机器人学等领域中，该方 法成功应用的实例呈指数增长。越来越多的研究者致力于该新兴的人工智能方 法，群智能一一简单的智能体( a g e n t ) 群体通过合作表现出智能行为的特性。 群智能在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题的 解决方案提供了基础。当世界变得越来越复杂，任一个人都无法对其完全理解， 当信息多得影响我们的生活，软件系统复杂得不能让某一个人完成，群智能便为 我们提供了一种设计智能系统的方法，实现了从控制的( c o n t r 0 1 ) ，预编程的 ( p r e p r o g r a 蛐n i n g ) 、集中式( c e n t r a l i z a t i o n ) 的方式向自主性( a u t o n o m y ) 、自 2 中南丈学硕士学位论文 第一章绪论 发性( e m e r g e n t ) 、分布式计算( d i s t r i b u t e df u n c t i o n i n g ) 转换，为此，群 智能系统吸引着越来越多的研究人员。群智能研究领域中很大程度上依赖于各知 识碎片( f r a g m e n t e dk n o w l e d g e ) ，但目前还没有方法将这些知识碎片组合在一 起所以，现在是综合该领域知识，进行有组织的调研的大好时机“ 蚁群算法是群智能方法之一，是一种新型的模拟进化算法。 目前对蚁群算 法的研究，不仅有算法意义上的研究，还有从仿真模型角度的研究，并且不断有 学者提出对蚁群算法的改进方案：有的将蚁群算法与遗传算法相结合，有的给蚁 群系统加入变异特征，还有的提出所谓最大最小蚁群算法( 砌a s ) 。虽然对蚁群算 法研究时间不长，对其的初步研究已经显示出了蚁群优化算法在求解复杂优化 问题( 特别时离散优化问题) 方面的优越性，其应用前景非常广泛。例如交通网 络中的最佳路径选择问题，电信网络中的流量负载分配问题等等都可以应用该 算法来解决，证明它是一种很有发展前景的方法。1 。应当指出，现阶段对蚁群算 法的研究还只是停留在仿真阶段，尚未能提出一个完善的理论分析，对它的有效 性也没有给出严格的数学解释。蚁群算法还不像其它的启发式算法那样已形成系 统的分析方法和具有坚实的数学基础。参数的选择更多的是依靠实验和经验，没 有定理来确定，而且它的计算时阎偏长。这些都表明其在理论和实践方面尚有许 多问题需要更深入的研究与解决。但是，从以前模糊控制所碰到的情况看，理论 上的不完善并不妨碍应用，有时应用还会超前于理论，并推动理论研究，蚁群算 法也是如此 必须指出的是，蚁群算法是一种概率算法，从数学上对它们的正确性与可靠 性的证明还是比较困难的，所做的工作也比较少。而且蚁群算法在解决问题的时 候，算法系统的高层次的行为是需要通过低层次的蚂蚁之间的简单行为交互涌现 ( e m e r g e n c e ) 产生的。单个蚂蚁控制的简单并不意味着真个系统设计的简单， 设计者必须能够将高层次的复杂行为( 也就是系统所要执行的功能，如旅行商问 题、车辆调度问题、图着色问题) 映射到低层次的蚂蚁的简单行为( 例如信息素 的释放) 上面，而这两者之间是存在较大差别的。并且在系统设计时也要保证多 个个体简单行为的交互能够涌现出我们所希望看到的高层次的复杂行为。这可以 说是蚁群算法乃至群智能中一个极为困难的问题。 对蚁群算法而言，在基本原理已经明确的条件下，重要的就是开发出求解问 题的算法模型，使求解问题更加切实有效而在工程实际的应用中，算法模型的 收敛性和算法的复杂度是值得深入研究的问题。 1 2 本文的主要工作 以上对蚁群算法的产生、发展及现状进行了简单的介绍。以下从蚁群的生物 中南大学硕士学位论文第一章绪论 机理出发，以基本蚁群算法原理为基础，探讨了蚁群算法的模型、性能、特点、 改进措施及在各领域内的应用，并提出了一种改进a s 算法a c s 算法在机器人 路径规划中的应用方法，通过与基于实数编码的遗传算法进行比较，说明了该改 进算法在收敛速度、解的波动性、动态收敛特征及计算效率上都优于基于实数编 码的遗传算法的机器人全局路径规划。主要内容如下：第一章综述了蚁群算法的 产生和发展，指出了其在求解复杂优化问题( 特别时离散优化问题) 方面的优越 性，蚁群算法的发展方向，及开发出基于蚁群的求解问题的算法模型的重要性。 第二章从群居昆虫的集体行为出发，阐述了蚁群算法的生物机理、自组织理论， 以及对群居昆虫的集体行为进行建模的必要性。第三章介绍了基本蚁群算法的原 理、模型、特点、实现，并通过查阅大量的文献说明了基本蚁群算法模型中各参 数的合理选择方法。第四章针对第三章中所阐明的蚁群算法的缺点，列举了当前 的一些典型的蚁群算法的改进算法；并对蚁群算法在各领域的应用做了简要的叙 述。第五章针对移动机器人路径规划问题中的特性，提出了一种静态环境下基于 改进a s 算法a c s 算法的移动机器人路径规划方法。并将该方法和基于实数编码 的遗传算法进行比较，仿真结果表明基于蚁群算法的路径规划方法要优于基于实 数编码的遗传算法的路径规划方法。第六章指出了蚁群算法的应用和理论研究 中，今后有待深入研究的有关课题，及其发展前景。 4 中南大学硕士学位论文第：事蚁群算法的生物学机理 第二章蚁群算法的生物学机理 2 1 群居昆虫 多年来，自然学家、诗人对群居的昆虫，如：蚂蚁、蜜蜂、黄蜂、白蚁有着 极大的兴趣。m a e t e r l i n c k 曾写到，是什么统治着这些群体? 又是什么发出命令、 预见未来、详细拟定计划，并保持着群体内部的平衡呢啪? 这确实足些令人费解 的问题。每个群居的群体中的任一单一个体似乎都有它们自己的议程，但整个群 体都是那么井然有序。所有个体之间天衣无缝般的合作似乎不需要任何领导者。 比如，南美切叶蚁( l e a f c u t t e r ) 搬运树叶时，它们在距巢数百米远的地方 搜寻树叶，就像建造了一条来往于巢穴与搜寻地点的“高速公路”当大群蚂蚁 在搜集大量“猎物”时，在其行进阶段，如埃西顿( e c i m n ) 蚁，有多达2 0 0 0 0 0 只 蚂蚁参与到这一壮观的“捕猎”行动中。研究表明，在这种群居的昆虫中，每只 蚂蚁并没有完成所有的工作，而是根据自身的年龄形态或随机地( m o r p h o l o g y , a g e o r c h a n c e ) 专门从事某一任务集。蚁群问劳动力的分工，使得各种活动能在 这种专业化的群体之间并发的执行，而且这种方法比起由非专业化群体中的每个 个体顺序完成整个任务的方法更加有效。 从蚂蚁物种形态来说，由两种不同的类型的蚂蚁并存。类如大头蚁属 ( p h e i d o l e ) 中可分为主要的和次要的两类，它们完成不同的任务。其中，主要 类蚂蚁用它们巨大的上颚分割捕获的食物、保护巢穴；而次要类蚂蚁的任务是抚 养幼虫和打扫巢穴。次要类蚂蚁的减少会促使主要类蚂蚁完成本该由次要类蚂蚁 完成的任务。研究表明，许多昆虫物种中，某一类型数量的减少，将会迅速由另 一类来弥补以获取平衡，其劳动力分工具有高度的可塑性。 昆虫是一种很复杂的生物：它能处理许多感观输入，它能根据大量刺激物调 整其相应的行为，并能在大量信息的基础上进行决策。然而，单个昆虫个体的复 杂性也不足以解释昆虫群体所能完成的工作的复杂性。或许最困难的问题是如何 将个体的行为与集体能力( c o l l e c t i v ep e r f o r m a n c e ) 联系起来。也即解释合作是 如何产生的? 有些合作机制是天生的：如根据个体之间的解剖结构的不同( a n a t o m i c a l d i f f e r e n c e s ) 进行劳动力的分工，就像根据蚂蚁的物种形态划分的主要类和次要 类。但是昆虫的许多集体活动是自组织的( s e l f - o r g a n i z a t i o n , s o ) 自组织理论 起源于物理学和化学领域，用于描述在微观级的加工和处理过程中出现的宏观模 式。该理论也能应用到群居昆虫中，以说明简单行为的个体之间的相互合作也能 形成复杂的合作行为近期的研究表明：自组织是群居昆虫中大范围合作行为中 中南大学硕士学位论文第二章蚊群算法的生物学机理 的一个重要的组成部分。 基于自组织的模型并不排除个体的复杂性：它只是说明在某些描述级，可通 过假设昆虫是相对简单的交互实体，并以此来解释复杂的集体行为。例如：从食 物源到巢穴包括一系列的复杂的感知驱动机理。在研究蜜蜂选择食物源的集体行 为时，模型中用到的原始概念并不会涉及到蜜蜂是如何飞舞的，而将其认为是一 个简单的行为，即使从神经生物学来说，这不是一个简单的行为。再者，基于自 组织的模型在逻辑上是合理的：它假设可根据简单的交互过程解释那些看上去复 杂的现象。如果可以简单的解释某事物时，那为什么又让它变得更复杂呢? 只有 当这种解释行不通的时候，才需要在模型中建立更复杂的假设。 研究者发现：自组织应用于群居昆虫，不仅有助于对群居昆虫的研究，还为 我们将关于群居昆虫的知识应用到智能系统的设计领域提供了有力的工具。事实 上，昆虫群体无疑是一个分散的问题解决系统，由许多相对简单的交互实体组成。 群体每天解决的日常事务有觅食、筑巢或扩展巢穴、个体之间有效分工、抚养幼 虫、对外界变化的反应、报警等。这些问题在工程学和计算机科学中都有与之相 应的部分。群居昆虫的一个最重要的特点是：它们能以很灵活的、鲁棒性很强的 方式解决问题。灵活是指昆虫能适应环境的变化，而鲁棒性是指昆虫能正常完成 工作的能力，即使其它的某些个体没能完成其任务。再者，群居昆虫具有有限的 认知能力，所以可以简单的通过在描述级别上模拟群居昆虫行为的方法设计智能 体( a g e n t ) 。 简而言之，借助自组织的方法对群居昆虫建模可有助于分布式问题求解设备 即群智能系统的设计。但是，现在对群智能的应用还没有发展起来，其中的主要 原因是问题解决的方法不能被预先定义，解决的方法不仅取决于个体本身的行 为，还取决于该系统的个体之间、个体与环境之间交互作用。这一特点使得群居 昆虫智能系统很难由程序实现。所以，利用群智能系统解决问题不仅需要关于个 体行为的完整知识，还需要知道它们之间的交互行为从而产生这样或那样的全局 行为。 其中一种可能的方法就是给出所有a g e n t 之间的简单交互所能产生的集体行 为的目录集( c a t a l o g ) 。该目录集非常有助于建立人工群体与它们所能完成的任务 之间的关联，但是这种方法十分的繁琐。另一种更可能的方法是研究群居昆虫是 如何合作完成某些特定的任务，对其行为进行建模，在该模型的基础上，通过在 生物范围之外调整模型参数或给该模型附加一些非生物特征的基础上开发人工 模型。这种方法十分类似于模仿自然界( 物理方面或化学方面) 解决问题的方法， 即仿生学的方法。 “群智能”这个说法最先是 扫b e n i ，h a c k w o o d 年t l w a n g 在细胞机器人系统中 6 中南大学硕七学位论文 第一二章蚁群算法的牛物学机理 提出的。在细胞机器人系统中，每个a g e n t 占据了一个一维或二维空间，通过与 其最相邻的a g e n t 相互作用形成一定的模式和自组织结构。受群居昆虫群体和其 它动物群体集体行为的启发，用群智能来描述这种情况，似乎无需必要的限制： 这就是扩展此定义，设计分布式问题求解设备和算法的原因。但奇怪的是，该定 义仅涉及到细胞机器人系统( c e l l u l a rr o b o t i cs y s t e m s ) 的研究，并没有大量借鉴 群居昆虫行为。 历史上，根据简单a g e n t 的合作和自动机( a u t o m a t a ) 求解优化问题、实现对 图形、网格、网络的控制早在b u t r i m e n k o 。t s e t l i n , s t e f a n y u k 和r a b i n 的著作中提到 过。r a b i n f l 绍了移动自动机( m o v i n g a u t o m a t a ) 通过与前一行为的交互解决图形学 和网格的问题。k t l i n 提到了受生物启发的自动机的重要特征。这种受生物启发 的自动机使基于群体的方法具有强大的功能：随机性、分散性、a g e n t 之间的间 接相互作用及自组织性。b u t r i m e n k o 将该思想应用到电信网络的控制当中，而 s t e f a n y u k 鬃 该方法应用到广播电台之间合作中 2 2 群居昆虫集体行为的建模 2 2 1 建模与设计 本文强调的是模拟群居昆虫，如何设计一个自适应的、分散的、灵活的及鲁 棒性强的问题求解人工系统。但实现该目杯的第一步是要理解昆虫中集体行为的 形成机制。这也是建模所起的作用。建模不同于人工系统的设计，建模即对自然 系统( 在此是指昆虫群) 中会发生的事务进行抽象。模型不仅要具备它所描述的 自然系统的特征，同时还需与其描述的系统相一致：参数不能是任意值，模型的 结构和机理从生物角度上看必须是可行性。此外，该模型必须具有可预见性，在 理想状态下各变量和参数在实验中必须是可取的。 显然，无需过多的认知论知识我们就可以知道，对于一个工程师来说，解决 某一问题并没有考虑生物上的合理性，他们所关注的标准是：高效性、灵活性、 鲁棒性及成本。虽然自然选择是最有效、最灵活、鲁棒性最好的生物组织形式， 但进化的制约却不是一个“工程师”：如果将进化视为是必然的调整过程，新的 结构的出现必然会受到旧的结构的制约，而个工程师应是采取尽可能的方法改 变它。尽管如此群居昆虫最成功之处是可作为工程与计算机科学模拟的一个新的 起点。 在设计人工神经网络求解问题、利用遗传算法进行优化求解也用到了这个方 法。如果把大脑和进化作为模拟的起点，绝大部分应用到工程中的神经网络和遗 传算法的实例都可以从它们潜在的隐含性( m e t a p h o r ) 中分离出来在所有的这 些方法中，仍然包含着大脑工作和进化过程的基本原则，但一个好的问题求解设 7 中南大学硕士学位论文 第二章蚊群算法的生物学机理 备应与生物特性无关。 2 2 2 群居昆虫的自组织 系统自组织的形成要具备4 个条件：( 1 ) 系统必须是开放的，且能保持与外界 环境的物质、能量、信息的交换；( 2 ) 系统的外部作用( 或称外界控制参量) ，通过 其内部机制产生效用；( 3 ) 系统内部要素之间的非线性相互作用是系统自组织产 生的必要条件；( 4 ) 涨落催化着系统自组织有序结构( 或耗散结构) 的产生及发展。 只要4 个条件具备，系统内部会在没有外部指令的情况下形成自组织。自组织是 通过系统内在动力形成的结构。 自组织是低级构件的相互作用而呈现的全局级的动态机理的集合。规则则详 细说明了在系统各组成单元之间的相互作用。各组成单元完全根据局部信息，而 与全局模式无关。全局模式是系统的一个自发( e m e r g e n t ) 特性，而不是由外界 命令附加于该系统的属性。例如：蚂蚁觅食的自发结构包括由信息素轨迹形成的 时空网络结构。自组织是基于以下四个基本组成成分： 1 正反馈( 放大) 是本文的形态形成的基础，是仅凭经验的简单行为规则， 并能促使结构的建立。正反馈的实例有增加新的成员及行为强度的加强。例如： 招募新成员到食物源是正反馈，它依赖于蚂蚁铺设的轨迹和及其对轨迹的跟随， 或蜜蜂的舞姿。 例如蜜蜂，当某只蜜蜂找到花蜜源，她就会回到蜂窝存放花蜜。然后，她或 许开始飞舞告诉其它的伙伴蜜源的方向和距离，或许继续寻觅食物源而不招募其 它的伙伴，又或许是放弃她的食物源而随机飞舞。如果在蜂窝附近提供两个距离 相等的食物源，蜜蜂发现食物源的机会是相等的。但是，如果其中某一食物源要 好于另一食物源，蜜蜂能发现较好的食物源，或者即使晚些时候发现好的食物源， 也能在随后转向好的食物源。文献 2 中提到这样一个实验：在上午8 ：o o 时，在 距蜂窝相同距离的两处分别给蜜蜂提供食物源：食物源a 处的糖的浓度是i m o l l ， b 处的浓度是2 5 m o l l 。在8 ：o o 到中午之间a 处被访问了1 2 次，而b 处被访问了9 1 次。到中午的时候食物源的浓度发生了改变，食物源a 处的糖的浓度是2 5 m o l l ， b 处的浓度是0 7 5 l 1 。此时，在中午到下午4 ：0 0 之间，a 处被访问了1 2 1 次， 而b 处仅被访问了l o 次。 实验表明，蜜蜂很有可能通过舞姿告诉同伴更好的食物源而放弃更差的食物 源。这些简单的行为规则使得群体具有更强的食物源的选择能力。s e e i e ye ta 1 和c a m a z i n e - 与s n e y d 嘲观察发现觅食者能通过不同速率的舞姿形成正反馈，将 更好的食物运回家，而放弃较差的食物，并通过简单的数学模型证明了此理论。 2 负反馈与正反馈相平衡，并有助于平衡集体模式。负反馈有饱和、耗尽枯 竭或竞争等形式。类如在觅食活动中，负反馈的表现形式有：有限的觅食者、觅 8 中南大学颂士擘位论文第二章蚊群算法的乍物学机理 食者的厌倦、食物源的殆尽、食物源的拥挤现象及食物源之问的竞争行为等。 3 自组织取决于扰动的放大( 随机走动、差错、任务的随机变更等等) 。呈 现的结构具有随机性，这是十分重要的，因为它可促成新方法的发现，而且扰动 可作为结构改进的出发点。例如：觅食者可能因为跟踪错误的轨迹而迷离了其群 体，但是迷失的觅食者却可因此而发现新的、未被开采的更好的食物源，并招募 新的伙伴到颓的食物源。 4 所有的自组织的实例都是依赖于多次的相互作用。假若信息素的生命周期 足够长，一个单一个体也能产生类似于由于轨迹跟踪事件与轨迹释放事件之间的 相互交互而产生的稳定的轨迹这样的自组织结构。但是，自组织常常需要一个尽 可能小的个体之间的容忍密度。此外，个体除能利用它人的活动外，还要能利用 自身的活动( 虽然不同的个体所感知同一事务时会有所不同) 例如：如果每个 个体能够利用它人的信息素，那么轨迹网络就能够成为自组织结构，被共同使用。 但这也不排除个体的化学标志和个体的记忆能力使之能更有效的辅助甚至是替 代集体标记。 当一个现象可被称为自组织时，它通常具有以下主要特征： 1 在初始相类似的媒介中，建立时空结构。这些结构包括：巢结构、轨迹搜 寻或社会组织。类如：一个典型的好的蜂巢组织模式应包括3 个中心区域( 中心 的幼虫区域、环绕的花粉环及周边大量的蜂蜜) ( 如图1 - 1 ) 伽。这都应归功于 基于局部信息的自组织过程 图1 - 1 人工蜂巢结构：能清楚的看到3 个中心区域 2 多稳态的并存。因为结构是由随机的偏移所产生的，任何一点偏移都可能 被放大，而系统根据初始条件在几种可能的稳定状态中收敛为其中的一种状态。 类如：当两个相同的食物源a 和b 被放置在距离巢相等距离的两处时，其中个食 9 中南大学硕七学位论文第二章蚊群算法的生物学机理 物源被大量开采，而另一食物源将会被忽略。两个食物源被开采的机率是相等的， 但是只有其中的一个被开采，蜜蜂只是从中任选了一个食物源。所以在此例中有 两种可能，食物源a 的大量开采或食物源b 的大量开采，而收敛于哪种状态取决于 初始的随机事件。 3 不同的参数对应不同的阶段。自组织系统的行为是动态改变的。类如白蚁 在用土粒和信息素搭建柱子时，可分为两个连续的阶段。首先，非协调阶段，其 主要特征是土粒的随机放置。该阶段会持续到土粒堆积到一定程度。然后，就是 协调阶段。此阶段中，白蚁数目有足够多，土堆呈现出一定的柱状或带状。初始 情况下，土粒的放置是通过正反馈机制让搭建者不断的堆积更多的土粒。因为随 着土粒的堆积，土粒中信息素浓度进一步的扩散，从而再次加强了白蚁堆积土粒 的行为。这种白催化的“雪球”效应( s n o w b a l le f f e c t ) 会促使协调阶段的形 成。当建造群体的数量过小，信息素会在相继的两个阶段之间消失，所以放大机 制不能起作用，只存在非协调阶段。因而没有必要在非协调阶段向协调阶段的过 渡过程中增加促使变化的行为，这仅是群体个体数量增加到一定程度的结果。 2 2 3 外激素 群居昆虫间的自组织要求昆虫之间的相互作用，这种作用可以是直接的，也 可以是间接的。直接相互作用是显而易见的作用：如触须、交哺( 食物或水的交 换) 、上颚的接触、视觉的接触和通过化学物质的联 系( 如附近伙伴所散发的气味) 等等。间接的相互作 用将更加敏锐，当某个体改变了环境，而另一个体 将对相应的改变做出相应的反应，此时两个个体即发 生了间接的相互作用。这种相互作用就是外激素 ( s t i g m e r g y ) 的一个实例。除自组织外，外激素是本 文中另一重要的基本概念。s t i g m e r g y - - 词源自于希腊 语s t i g m a ( 其意为刺激( s t m g ) ) 和e r g o n ( 其意为工 作( w o r k ) ) ，由g r a s s e 提出，以表示白蚁在筑巢时 的任务协作和控制。研究表明筑巢活动并不依赖于筑 巢者本身，绝大部分还是取决于巢的结构：刺激性结 构( s f i m d a t i n gc o n f i g u r a t i o n ) 能引发白蚁将某一结构 转化为另一结构，而这一新产生的结构又会引发这些 白蚁其它的行为。筑巢过程应包括一下过程：首先用 土粒和灰泥建造成柱状或带状，然后在柱子之间搭建 拱门，最后就是在柱子间搭建墙。图1 2 即概略描述了 g r a s s e 认为外激素是如何应用到柱子结构的过程。 1 0 搿魄净鳓 i u 图1 2 白蚁搭柱子过程 、。即 涉 必痧 e a 中南大学硕十学位论史第二章蚁群算法的生物学机理 外激素很容易被人们所忽略，因为它并没有详细的说明个体是如何协调它们 之间活动的机理。但它确实是为我们提供了一个关于个体行为和群体级行为之间 相互关系的普遍机理：个体行为改变环境，而环境又会反作用于其它个体的行为。 白蚁搭建柱子的实例就可说明外激素是如何通过自组织对白蚁的建造活动 进行协调的。另一个可说明外激素和自组织是相互关联的例子就是蚂蚁告知伙伴 食物源的行为个体自组织地沿途释放信息素就是改变环境的方法之一，以告知 同伴跟随该轨迹。同时我们也可看到蚂蚁某种的工作能力的提高就会降低对该工 作的需求。如蚂蚁将蚁巢打扫干净就减少了对清扫蚁巢的需求。蚂蚁通过改变环 境( 打扫蚁巢) 与同伴相互通信，而同伴对改变的环境做出相应的反应( 不再打 扫蚁巢) 在蚂蚁堆建沙堆、尸体、幼虫时，外激素也同样在起着作用。起始， 这些都是随机堆放的。但是当蚂蚁发现某物体时，它就会因此而受激励将物品放 置在被发现物体的周边。上述的每个例子中，环境都是个体之间交流的中间媒介。 上述所有例子都说明了外激素是很容易被操作的。设计一个人i a g m t 的最 有可能实现的就是：用间接通信代替直接通信之间的合作。以减少a g e n 晓间的 通信。还说明了群居昆虫之间的另一特征就是：渐增构造。例如：白蚁的建造行 为都是建立在其它白蚁建造的基础上的。在优化问题求解中，逐步改进是常用的 方法之一，新的解是建立在原有解的基础上的。再者，外激素都具有灵活性。当 环境因为外界的扰动而发生了变化时，昆虫都能恰当地对外界扰动做出相应的响 应，就像环境的变化是由群体的行为所产生的。也就是说，群体能在个体行为不 改变的情况下，对外界的扰动作出集体性行为的响应。对于人i a g e m t 来说，这 种灵活性是十分重要的：也就是说无需对特定的扰动事件先编好程序，a g e m s 就 能对外界的扰动做出相应的响应。 2 3 模型接口 正如前面所讨论的，理解自然与设计一个有用的系统是两个不同的任务。理 解自然需要观察和做实验，以及根据观察和实验的数据进行建模。相反，设计一 个有用系统时的建模仅局限于一个人的想象及目前的技术水平。在这两种情况 中，虽然模型有时是隐含的即非明确表达的，也就是说这些模型不是建立在数学 基础上，但是这些模型都是十分重要的。虽然在本文中讨论建模的重要性已超出 了本文的范围，但是还是有必要说明建模的重要性，因为它是我们工作的核心部 分。确实，群居昆虫的自然现象为人工系统的设计提供了平台。一个模型就是对 现实场景的简化，是将少数相互关联的可观察的属性抽象为变量的过程；模型就 是将这些变量联系起来的方法。通常，一个模型应包括可测量的参数，隐含变量 这些变量是基于不可观察的属性的假设的基础上的，而这些变量对于建立与 中南大学硕十学位论文第二章蚊群算法的生物学机理 可观察行为相一致的变量之间的关系又是必须的。任何时候，调整参数的值常会 改变模型的行为和输出结果。当模型的输出与自然系统的行为一致时，参数的值 都应与自然系统中相应部分的值相对应。一个好的模型应具有以下属性；经济性、 连贯性和互斥性等等。 模型常包括一些解释各类现象所必需的基本成分，从这种意义上来说，建模 需要开阔想象力。这样，建立一个对感兴趣现象的模型，而不是胡乱一通的开始 是十分有意义的。建立一个超越现实范围的模型就等于是使用一个超出其原有目 的的工具。在了解到群居昆虫擅长于问题求解之后，可对其进行抽象、形成系统 的描述，也就是说，算法语句使得对群居昆虫的问题求解方法进行建模极具吸引 力。建立一个群居昆虫的问题解决模型可作为我们研究问题的起点，但又可在原 有范围之外进行进一步的扩展、开发。例如：基于觅食模型的优化算法主要依赖 于信息素的挥发，其时间规模是如此之短，在自然界中是完全不可能的。在此例 中，模型的开发超出了生物范围，并产生了一类新的有趣的算法。这些算法的潜 在原则在很大程度上都是受到群居昆虫集体工作行为的启发，但其中的一些参数 值并不限定在经验范围之内。所以，在本文中，模型就作为理解自然和设计人工 系统的一个接口：一个是源自对现象的观察，试图完成其生物建模，而另一个是 开发一个没有限制条件的模型。 2 4 基于群居昆虫模型的机器人学 基于群的机器人学发展如此迅速，以致于很难明了现在是发展到什么程度， 难于与现今的最新技术保持同步。在机器人领域内的主要期刊已出版或正在刊登 相关的文章。研究人员们己通过分布式控制机理的设计，各类型协作机理的实现 及机器人完成任务的方法实现了基于群的对于群居昆虫的模拟。这些就足以对一 个关于应变分布式机器入学( r e a c t i v e d i s t r i b u t e d r o b o t i c s ) 即基于群的机器人学 的优点和缺点给出个定义。 我们将基于群的机器人学定义为应变式集体机器人学。基于群的机器人学将 是机器人学领域中另一经典方法呢? 具有灵活性、鲁棒性、分散性和自组织性的 群居昆虫的问题求解方法的特征属性是其中的主要原因。某些任务本来就很复 杂，由单个机器人来完成该任务是不可能的。虽然若干机器人一起工作可以提高 工作速率，但是它们之间没有必要的合作机制。让机器人一起工作的潜在机理是： 最小干扰原则。设计、建立和使用几个简单的机器人比设计一个复杂、功能强大 的机器人会更简单，因为它们用的是更简单的传感装置；价格更优，因为它们简 单、更灵活而无需对机器人进行预编程；可靠性更高、容错能力更强，因为一个 或几个机器人没能完成工作，只是会影响到它们完成工作进度，但是不会影响整 中南大学硕士学位论文 第二章蚊群算法的生物学机理 个任务的完成。再者，自组织理论告诉我们：特定模式的集体行为与由单个a g e n t 或机器人完成的任务在性质上是不同。在集体行为中，单个个体行为的随机性和 波动性远不能构成威胁，反而会极大的促使系统开发出新行为、找到新的解的能 力。另外，自组织性、分散十t 及a g e n t 之间的相互作用无需直接联系，而可以通 过环境进行联系，以达到有效减少机器人之间的直接通信的目的。因为随着机器 人数量的增加，机器人与机器人之间的快速通信将会成为亟待解决的主要问题之 一。从更大程度上来说，该问题可通过减少机器人之间的通信来实现。再者，中 心控制常不适用于处理大规模的a g e n t ，这不仅是因为要处理机器人到控制器及 控制器到机器入的通信，而且一旦控制器的出错将会导致整个系统的瘫痪。 当然，用基于群的机器人也有一定的缺点例如：拥塞，由于缺乏全局信息， 一组机器人可能会陷入死锁，不能有任何进展。另一个问题就是如何对这些所谓 的简单的机器人进行编程使其能完成用户设计的任务。解决问题的方法常常不能 预先设定，而是突现的。解决一个问题也就是为系统及其环境找到一个变化轨迹， 使得系统和环境的状态构成问题的解。虽然该方法极具吸引力，但该方法并不易 于编程实现。到目前为止，我们都隐含地假设了，所有的机器人都是相同的个体。 假若要求机器人能对不同的激励条件完成不同的任务，或在相同的激励条件下也 能做出不同的反应等情况时，这种情况就变得更复杂了。倘若关于同类机器人的 机器入学的理论是有限的，