生物群体中蚂蚁跟随问题的研究.doc

目 录摘 要.IAbstract .II1 绪论.11.1 引言.11.2 编队控制国内外研究概况.31.3 课题意义.62 蚂蚁跟随问题的仿真设计.102.1 预期结果.102.2 实现方案.102.3 任务意义.133 蚂蚁跟随问题的仿真实现.173.1 蚂蚁跟随问题的算法描述.173.2 程序描述.183.3 程序框图.193.4 运行程序23 3.5 仿真分析.314 总结与展望.33致谢.34参考文献.351 绪论1.1 引言自古以来，自然界就是人类各种科学技术原理及重大发明的源泉。生物界有着种类繁多的动植物及物质存在，它们在漫长的进化过程中，为了求得生存与发展，逐渐具备了适应自然界变化的本领。人类生活在自然界中，与周围的生物作“邻居”，这些生物各种各样的奇异本领，吸引着人们去想象和模仿。人类运用其观察、思维和设计能力，开始了对生物的模仿，并通过创造性的劳动，制造出简单的工具，增强了自己与自然界斗争的本领和能力。例如飞机是模仿鸟类的飞行结构特点制造的；雷达是模仿蝙蝠的回声定位制造的；荧光灯是模仿萤火虫制造的；照相机是模仿蝇的复眼制造的；电子蛙眼是模仿蛙眼制造的；许多建筑的建造模仿了动物的甲壳等等。自然界以及人类社会的活动都可以看作是由个体组成的群体行为。生物个体可以是细菌，昆虫，鸟，鱼等。人类社会是由物性个体及人性个体组成。一定数量的自主个体通过相互交流与协作，在集体层面上呈现出更为有效、更为强大功能的行为，并能实现个体不可能实现的目标。自然界以及人类社会呈现的群体行为是与个体属性有关，但群体表现的行为、功能往往绝非个体能力的总和，人类的社会活动说明了这个事实。这类群体行为的例子在自然界中有很多，例如，鸟能成群结队的飞翔雨迁徙，鱼群能聚集在一起有序地在不同的江海区域修养、生息、繁衍生殖。蚂蚁、白蚁、蜜蜂的群居。脱离群体的生物个体在自然界是很难生存的。群体所形成的活动能力、战斗力。保证了族群在恶劣的自然环境和与生物种群的争斗中繁衍生息。从系统科学的观点看，群体行为的研究对于理解自然与社会中的复杂现象具有非常重要的意义。一方面，该研究的重大进展能更深刻地阐释、了解、揭示自然的秘密，能够帮助人们深入理解人类社会活动、经济活动的规律。另一方面，该研究的重大进展将会帮助人类不断完善、发展新技术。近年来，群体的协同控制研究直接为多移动机器人系统，无人驾驶飞行器群、军事应用中的战术编队、调控，交通系统的控制、对突发事件的应对、传染病的防治、生态的维护、可持续发展战略的制定与提供理论指导。同时对解释生命的起源，意识的形成等也具有极其重要的意义。人们研究群体行为往往从观察自然现象开始。当人们观察自然现象时很容易发现鸟群、鱼群并没有一个统一指挥系统，依靠个别鸟之间的联系以及一些本能的反应形成一定的飞行队形，达到运动的一致性。一致性问题在分布式计算科学方面早有研究。1987年，Reynolds 1介绍了一个模型并且写下了模仿飞行中的一群鸟的boids算法；它们聚在一起飞翔，有着共同的平均航向并且避开了相互之间的碰撞。每只鸟都有着一个局部的控制战略，然而它们却可以完成令人满意的全体集群行为。每只鸟的局部的控制战略都由三部分组成：分离，控制避免拥挤；队列，控制与相邻的鸟保持接近的平均航向；凝聚，控制与相邻的鸟保持接近的平均位置。通过计算机模拟可以发现这些无统一指挥的群体通过个体之间的相互交换信息以及本能的反应，最终会形成有序的、协调一致的行为。系统科学中Consensus这个词理解为群体中的成员通过与其他成员的信息交流及共同约定的简单相互作用，使群体达成共同的意向。Consensus是保留在英文中的拉丁词汇。Con=共同，sensus=感觉,Consensus=共同的感知，共同的认识，共谋。在中文文献中将它译为一致性。实际上，Consensus的含义要比汉语的一致性更广泛、更多义。Boid模型引起了计算机和物理学家、生物学家和数学家的关注。系统科学家对这种计算机模拟的呈现现象力图给出严格的理论解释。根据作者的了解，第一批用严格的数学方法给出一类群体行为一致问题的数学描述，并给出实现这类群体一致性的精确条件的论文大约出现于20022004年间。这些文献中用简单的线性动力系统描述个体的行为，个体之间的信息交换用某些能够测量的量，例如个体间的距离、相对位置等来描述。个体之间的相互作用有各种表现：如两个个体之间有信息交换则这两个个体就相互靠近；一些比较复杂行为规定表现为两个个体太靠近，它们会排斥，以保持合理的各自活动的距离. 个体的行为还可用非线性动力学模型来描述。2004年，Jadbabaie 2等人明确表达了一个Reynolds设置的二维版本同时研究出了一个控制战略。他们证明了编队战略的航向，在一定的假设条件下（图代表的自主体与另一个邻居总是连接，或者定期连接），结果是所有的自主体汇聚到了一个共同的航向。除了存在于生物学的兴趣，Reynolds的想法与多车队形的主题有关。一般来说，这一控制战略的目标使一组移动自主体（机器人组火星探路者，无人驾驶飞行器，或无人水下航行器）要么实现自主体组在形成或移动的同时保持一个编队，要么实现把自主体从一个编队重新配置到另一个编队。同年，一些研究人员3调查了多主体系统的分布算法。一组模拟机器人形成近似圆形和简单多边形，使用每个机器人本身的情况来定位自己，例如，最远和最近的机器人是哪个。另外有人提出了一个类似的设计，但正仍然在考虑避免碰撞和团体运动间的问题，例如，一个矩阵的编队进行右转。并且有另一些人4，对分布式算法的研究中那些把一套机器人错误地描绘成在平面上应该收敛到一起的点；这是被称为协议的问题。除了在一个公共点会合客观事实，收敛的另一个重要原因是：如果收敛到一个点是可行的，那么更多的普通编队也是可以实现的，这是可以证明的。用系统的科学的观点与方法研究群体行为目前仅处于起步阶段。用功能强大的计算机及相关软件对群体行为进行模拟，是一种有效的研究方法。但模拟的结果往往事先无法预测，结果的正确性也无法用解析的手段来验证，只能与现实中的类似现象作比较。但是人们往往更希望了解群体能够形成或具有各种各样能力、行为的机理，并建立恰当的数学模型来说明、演绎这种能力与行为以及群体行为形成的机理，再通过计算来预测并调控群体的行为。到目前为止，在各种复杂的群体行为中，对群体行为的一致性及可实现性的条件，科学家们研究的比较深入，已经形成了相对完整的系统理论，而对更复杂行为的数学理论，除了个别例子及一些特殊情况，一般来说，还没有系统的理论结果。1.2 编队控制国内外研究概况近些年，对于生物的群体性行为的研究越来越多，比如蚁群觅食，鱼群的共轴圆运动，鸟群的各种队列运动等等。这些群体行为给了研究者很多的启发。显然，这些群体中个体的智商都很低，那么它们是如何完成这些精密的群体行为的呢？基于此，就有了对多机器人的编队控制的研究，用数量众多的功能简单的机器人来模拟生物的群体运动。1.2.1 基础编队2004年Zhiyun Lin等5研究了三种编队战略：循环追赶编队、星型无向图编队和星型有向图编队。在机器人之间不进行任何动态通信的情况下，最后所有的机器人都聚合于一个未知的点。首先是循环追赶。循环追赶是一个每个自主体都按顺序追赶下一个自主体的局部战略，它是没有中心并要求最低数量的通讯线路（自主体的链接），以实现编队。众所周知自主体在这个战略下收敛到一点，他们仍然在研究编队发展的动机是解决碰撞是否会出现的问题。星型无向图编队的自主体最初排列成一个逆时针方向的星形编队或顺时针方向的星形编队。每个自主体只有一个有限视野的传感器，因此这个传感器所对应的自主体可以看见并知道那些与自己距离在一定程度以内的自主体们，这些被看到的自主体被称作邻居自主体。每个自主体都将以自己所有邻居自主体的形心为目标移动，他们证明在这个战略下视野恰当的话所有自主体将最终收敛到一点。同样星型有向图编队的自主体最初排列成一个逆时针方向的星形编队或顺时针方向的星形编队。每个自主体只有一个有限视野的传感器，但是这个传感器拥有九十度角的锥形视野而不是圆形视野，而当视野内没有其他自主体时它将在程序控制下顺时针旋转视野90度。同样的每个自主体都将以自己所有邻居自主体的形心为目标移动，他们证明在这个战略下视野恰当的话所有自主体将同样最终收敛到一点。1.2.2多边形编队2007年M. Cao等6研究了运动自主体的三角形编队问题。它实现了三个运动自主体组成三角形编队同步运动。这是多边形编队的基础，经常应用于飞机的编队飞行。2009年，zhiyun lin等7研究了有向无环图中多运动自主体的编队控制问题。在一个有向无环图中没有邻居的自主体是领导者而其他的是追随者。领导者以不断变化的速度编队运动，追随者知道与邻居间的相对位置和领导者的速度。于是在追赶战略和三角形编队的基础上实现了多自主体的同步运动，实现了有条件的多边形编队同步运动，这是多边形编队在理论上的重大突破。2010年，zhiyun lin等8研究了自适应编队控制问题。对于一个自主式移动机器人网络，其中只有两位领导者知道规定的速度，而其他的追随者与固定的两个邻居以一种自适应控制率形成特定的三角形编队，因此无需知道邻居的速度。一组任意的几何图案都可以由两个领导者与N个追随者通过特定的邻居关系与指定的跟随编队实现。这样实现了多自主体的任意多边形编队的同步运动,使得多边形编队有了更大的现实意义。1.2.3圆形编队2009年，Gangfeng Yan等9研究了一群自由运动的自主体协调跟踪目标的问题。他们提出了一种基于混合控制的新方法和协调跟踪目标的可达性规范。当自主体远离目标时它们会接近目标，然后切换到协调移动状态，最终自主体们环绕在目标四周并在相互之间保持相等的角距离来合作地捕获目标。2010年，Gangfeng Yan等10研究了一群自由运动的自主体的对运动目标的围合问题，这可以看做实现一个围绕一个事先不知道它的运动的移动目标的编队的必要的条件。需要一个局部控制规律，仅仅利用目标和它的邻居间的先对位置的信息，来解决这个问题。这个控制器是基于对目标追踪这个任务和交互机器人的协调这个任务去耦。经过证明，一群自主移动智能体协作的估计目标的速度，然后渐渐形成一个正多边形的编队，保持移动目标在他们的图心。它实现了环绕一个运动目标的圆形编队，其中目标的速度是不知道的。而且，这些自主体可以在目标的速度改变时自适应的维持编队。2009年，Wei Ding等11研究了平面内的群体自主体的分层追赶策略。通过了一个简单的两层追赶策略形成了多种多样的编队，包括集合、匀速圆周运动、复杂的圆周运动、同轴圆周运动、同轴对数螺线运动。其中高层和低层都以圆形拓扑循环追赶的战略可以实现集合、匀速圆周运动和复杂的圆周运动。而高层以圆形拓扑循环追赶，低层以链状拓扑追赶的战略可以实现集合、同轴圆周运动和同轴对数螺线运动。1.2.4跟随编队2009年，Ying Lan等12研究了协调路径跟踪问题，也就是操作一群分散的自主体聚集到一条给定的路径上，实现一个交互式的编队。一个新的混合控制策略被用来解决由于感知范围不足导致邻居随着时间的推移可能会改变的问题：每个自主体的状态空间以与目标路径的相对位置分化为几个区域。一个区域的控制战略引导所有自主体进入下一个区域，直到实现所有自主体的路径跟踪和协调运动。因此随着状态切换控制规律，所有自主体在路径上均匀间隔排列和最终作为一个整体向前移动。最近几年，协调路径追踪已经成为了一个热门话题，由于军事方面的应用，以前关于这个问题的研究局限于机器人，航天器等等。协调路径追踪的控制规律一般分成两部分：路径追踪以及多机器人协调。尽管很对方案对路径追踪有效，然而对于多机器人协调却没有完整的解决方案。 以前的方案在不管载具离路径多远的情况下同时考虑路径追踪以及多机器人协调。然而，由于受限的传感距离以及通信容量，并不是所有的载具都有可能一直知道目标路径以及它的邻居。因此，对于远离路径的载具，仅仅知道它的几个邻居的位置，而不知道路径的信息，是可以的。对于已经靠近目标路径的载具，知道路径以及它的邻居的信息，这样他们就能追踪路径以及和其他同样靠近路径的载具协调行动以形成期望的编队。这样，远离路径的载具，他们的目标就是靠近路径。对于靠近路径的载具，他们能感知路径以及更多的靠经路径的其他载具，这样，它们的主要目标就是沿着路径运动，并且实现期望的编队。 一种基于可到达性说明的新的方法以及混合控制被用来解决这个问题。每个载具的状态空间根据路径被分成几块。一个控制规律操纵所有的载具进入一块区域，另一个就实现路径追踪和行动协调。这样，在状态依赖的转换规律的作用下，所有的载具最终都处在路径上，并且整体的向前运动。由于受限的传感范围，每个载具的邻居其间都可能改变。在处理这个问题的时候，尽管每个载具可以感知几个邻居，但其仅仅测量一个邻居的信息。这样在协调控制时，使用的测量信息最少。 这篇文章提出个一种新的基于混合控制的方法来解决路径追踪问题。它综合了分散式的控制规律。它考虑了载具的感知范围，并且证明仅仅使用局部信息以及最少的连接就能解决协调式路径追踪问题。 1.3 课题意义在多自主机器人系统中，很多时候要求多个自主机器人在协作的过程中保持一定的队形，以便更好的协作，即多机器人编队控制。编队控制问题主要包括队形形成和队形控制两个问题。队形形成问题问题主要是研究如何使机器人系统从一个杂乱无章的状态形成一个整体具有规律性或符合设计者要求的稳定状态，这对于一队多自主机器人协作完成一项特定任务提供了支持。队形控制主要是研究在自主机器人系统朝着目标行进的过程中，既要遵循一定的队形约束，又要适应当前工作环境的约束(如障碍物)的控制技术，这是多自主机器人编队控制的核心问题。多自主机器人保持一定的队形至少有以下几点好处：（1） 充分获取当前环境信息。单个机器人的传感器获取信息的能力是有限的，如果多个机器人保持一定的队形，而每个机器人的传感器负责获取自己周围的环境信息，这样就可以保证比较完整的获得机器人群体当前活动区域内的环境信息，对于实现侦查、搜寻、排雷及安全巡逻等任务是有利的。（2） 可以增强抵御外界入侵的能力，作战过程中，机器人士兵通过保持队形，可以抵抗多方向的入侵，增加自身安全性，群居动物按一定队形行进可以有效抵抗掠食者的现象就是一例。（3） 可以提高工作效率，如果选择恰当队形可以加快任务的完成。例如多个机器人推箱子，机器人与箱子必须保持一定的几何关系才能够将箱子推向期望的方向，类似的任务还有农作物收割、播种等。多自主机器人系统的编队控制是目前控制和机器人研究领域的研究热点之一。多自主机器人系统通过模拟生物之间的某些群体行为从而完成特定的任务。在多自主机器人系统中,每个机器人按照预定规则检测周围环境,与其邻近机器人通讯,并根据自身获得的信息来决定下一步的行动。虽然每个机器人只使用了其能获得的局部信息,但是整个系统却能实现一些全局性的任务。多机器人系统编队控制与单个机器人相比：（1） 可以显著提高系统的效率，大大节约时间。（2） 能够有效提高系统的鲁棒性和容错能力。（3） 同时设计和制造多个简单机器人比单个复杂机器人更容易、成本更低（4） 通过共享资源可以弥补单个机器人的不足，完成单个机器人难以完成或无法完成的任务。多机器人系统编队控制在军事监测、抢险救援、空间及海洋开发、智能交通系统、工农业生产、服务行业等领域中有广泛的应用前景并已经得到了一定的实际应用。例如在行星探测、煤矿、火山口等高危环境下作业以及在水下作业等需要远程操作的的场合；在需要短时间内完成灾难搜索、营救以及危险物品清除的场合等；在军事领域，无人侦察机甚至无人战斗机、无人潜航器、无人战车、排雷机器人、巡航导弹等智能武器已经出现并将发挥重要作用。因此我研究的课题就是用编队控制的思想来仿真研究生物群体中的蚂蚁跟随问题。蚂蚁是大家司空见惯的一种昆虫，而他们的群体合作的精神令人钦佩。他们的觅食行为、劳动分配、孵化分类、协作运输、构造墓地等行为之精巧令人惊叹。若我们是能从他们身上学习到一些什么的话，也将是一件非常有益的事请。关于蜜蜂觅食，人们已经做过很彻底地了解，据说它们是用飞行的舞姿（兜圈圈）来传递信息，圈子的轴方向表示花蜜的方向，用飞行的圈数表示有花蜜地方的距离，别的蜜蜂得此信号，就纷拥向该方向飞去。而蚂蚁觅食的方法，却另有一番世界，据研究当蚂蚁找到食物并将它搬回来时，就会在其经过的路径上留下一种“信息素”，其他蚂蚁嗅到这个激素的“味道”，就沿该路奋勇向前，觅食而去。不但如此而且还会沿着最短的路径奔向食物，当大量蚂蚁这么做时，蚁群就会一只跟着一只形成一条最短的线来搬运食物。但是如果我们用手划过蚂蚁的行进队伍，干扰了蚂蚁的信息素，蚂蚁就会失去方向感，到处乱爬。那么我们又如何利用多自主机器人来模拟蚂蚁跟随这一行为呢？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物；其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小；而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。 然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！2 蚂蚁跟随问题的仿真设计2.1 预期结果本文旨在使用计算机模拟自然界蚂蚁的寻径方式，仿真实现蚂蚁跟随编队。假设在一个存在障碍物的环境中有一个蚂蚁窝和一处食物，各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。2.2 实现方案蚂蚁在运动过程中，能够在它所经过的路径上留下信息素来进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时。就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低。当后来的蚂蚁再次碰到这个路口的时候。选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大。而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。于是令蚂蚁依据以下规则移动：(1) 范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。(2) 环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。(3) 觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。(4) 移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。(5) 避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。(6) 播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。蚂蚁究竟是怎么找到食物的呢？在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。 当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。而蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路径的，为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。所以经过一段很长的时间后，最终蚂蚁们的路线将是全局最短路径。2.3 任务意义模拟自然界蚂蚁寻找食物这一群体行为的编队控制算法又可以称作蚂蚁算法，或蚁群算法，是一种用来在图中寻找优化路径的机率型技术，它由Marco Dorigo于1992年在他的博士论文中引入。蚁群算法是一种模拟进化算法。初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法的特点如下：（1）蚁群算法是一种自组织的算法。在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特定干预，我们便说系统是自组织的。在抽象意义上讲，自组织就是在没有外界作用下使得系统墒增加的过程(即是系统从无序到有序的变化过程)。蚁群算法充分休现了这个过程，以蚂蚁群体优化为例子说明。当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用，自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程。 （2）蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多自主体系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。 （3）蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。因此， 正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行。 （4）蚁群算法具有较强的鲁棒性。相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。 这种算法有别于传统编程模式的算法，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。也就是说，当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。但是，程序却可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，也就是说，程序执行的时间越长，所获得的路径就越可能接近最优路径。这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。实际上好似是程序的一个自我学习的过程。这种优化过程的本质在于：（1）选择机制：信息素越多的路径，被选择的概率越大。（2）更新机制：路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。（3）协调机制：蚂蚁间实际上是通过分泌物来互相通信、协同工作的。蚁群算法正是充分利用了选择、更新和协调的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有群体智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：多样性和正反馈。多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得群体智能行为涌现出来了。 引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。 既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我个人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！ 多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发，如今该算法现己被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通等领域。主要解决的问题包括：（1）旅行商问题：旅行商问题就是寻找通过n个城市各一次且最后回到出发点的最短路径。（2）二次分配问题：二次分配问题是指分配n个设备到n个地点，从而使得分配的代价最小。其中代价是设备被分配到位置上方式的函数。（3）车间任务调度问题：已知一组m台机器和一组t个任务，任务由一组指定的将在这些机器上执行的操作序列组成。车间任务调度问题就是给机器分配操作和时间间隔，从而使所有操作完成的时间最短，并且规定两个工作不能于同一时间在同一台机器上进行。（4）车辆路线问题：车辆路线问题来源于交通运输。已知m辆车，每辆车的容量为d，目的是找出最佳行车路线在满足某些约束条件下使得运输成本最小。同样蚁群算法还可以应用于很多其他的实际问题，例如用于图着色问题、大规模集成电路设计、通讯网络中的路由问题、及负载平衡问题以及管理公司的电话网，对用户记帐、收费等工作。进一步，将每个蚂蚁看成是一个神经元，它们之间的通讯联络，看成是各神经元之间的连接，只不过这时的连接不是固定的，而是随机的。即用一个随机连接的神经网络来描述一个群体。这种神经网络所具有的性质，就是群体的智能。3 蚂蚁跟随问题的仿真实现3.1 蚂蚁跟随问题的算法描述开始移动，检查四周障碍物，观察感知范围内是否有目标或信息素。If 蚂蚁找到目标 找食物的蚂蚁找到食物就搬起食物，转而播撒食物信息素； 回窝的蚂蚁找到窝就放下食物，转而播撒窝信息素；Else if 蚂蚁犯错误 蚂蚁前进方向变更为随机可移动的方向；Else if 蚂蚁感知到信息素 蚂蚁前进方向变更为信息素最浓处所在方向；Else switch（障碍物） case 前方无障碍物：方向不变； case 前方有障碍物，左右均没有：50%几率左转，50%几率右转； case 前方和左边有障碍物，右边没有：右转； case 前方和右边有障碍物，左边没有：左转； case 前方和左右均有障碍物：后转； Switch （蚂蚁前进方向） case 上：y-； case 下：y+； case 左：x-； case 右：x+；移动完毕后播撒信息素。3.2 程序描述本程序使用c语言编写，运行程序将创造一个拥有障碍物、蚂蚁、窝和食物的环境。程序运行之初，蚂蚁从家里出来随机移动以寻找食物（寻找食物或食物信息素），同时播撒窝信息素，每只蚂蚁在窝（或者刚找到食物）的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。当某只蚂蚁感知到食物后它将搬起一份食物，转而播撒食物信息素并开始寻找回窝的路径（寻找窝或窝信息素）。于是越来越多的蚂蚁将沿着食物信息素找到食物，并沿着窝的信息素回窝，蚂蚁们就找到了一条从窝到食物的路径。随着时间的推移，越来越多的蚂蚁会被信息素吸引而走上这条路径，尽管这条路可能不是最短的。但是蚂蚁也可能会以小概率犯错而走出其他的路径，如果某条路径用时更短，那么这条路径上的信息素浓度就会更高，吸引其他蚂蚁走上这条更短的路径。于是长时间的运行最终会产生一条最短路径而且大部分蚂蚁将沿着这条路径搬运食物。同时我们也不能忽略障碍物的因素，如果处于封闭的环境中，蚂蚁将不能找到食物；而如果窝到食物的路径过于复杂，蚂蚁们只有很小的概率可以将食物搬运到窝，却不能再次完成搬运食物的过程，那么也不会形成一条路径。3.3 程序框图3.3.1 主程序框图开始运行环境初始化程序运行；蚂蚁移动；环境变化。运行60秒且家中没有食物显示找不到食物 是 否运行180秒且家中没有足够食物 显示难以找到食物 是 显示找到足够食物并显示运行时间 否找到足够食物 是 否 是否有按键处理按键 是 否按下Ese键 否 显示运行时间并结束运行 图3.1：主程序框图3.3.2 蚂蚁行为框图开始移动找到食物就搬起食物；找到窝就将食物放进窝里是否找到目标 是 否随机选择一个可移动的方向转向是否犯错误 是 否向信息素浓度最高的方向移动是否感知到信息素 是是否左右也是障碍物 否前方是否碰到障碍物掉头 是 是 否 否随机转向左右可移动的方向前进播撒信息素并结束移动图3.2：蚂蚁行为框图3.3.3 按键处理框图读入按键Switch（key）P T 1 2 3 S L 暂停并显示窝信息素浓度暂停实时显示信息素暂停并显示食物信息素浓度暂停并读取环境暂停并保存环境暂停并显示所有信息素浓度结束处理图3.3：按键处理框图3.3.4 信息素浓度框图确认空格位置信息素浓度恒为最大值，显示#是否与食物或窝相邻 是 否信息素浓度等级变更为较大值是否有携带更高浓度信息素的蚂蚁到达 是 是否经过足够时间挥发导致信息素浓度降低 否是否存在信息素信息素浓度等级减1 是 是 否无信息素信息素浓度等级不变 否（注：蚂蚁所携带信息素也会随时间 的流逝而挥发导致浓度降低。）图3.4：信息素浓度框图3.4 运行程序3.4.1 环境简介在环境中，黑色的是空地；阴影代表障碍物；红色的“H”代表窝；红色的“F”代表食物；白色的“+”代表没有搬运食物的蚂蚁（同时为了关注蚂蚁的具体运动，将一只蚂蚁标为紫色）；“”代表正在搬运食物的蚂蚁。同时在程序运行过程中左下角将实时显示剩余食物数与已经搬运到窝的食物数。图3.5：环境简介3.4.2 操作介绍（1）按下“p”键将暂停并显示程序运行的时间。图3.6：按下P键的显示（2）按下“1”键将暂停并显示食物信息素的浓度图3.7：按下1键的显示（3）按下“2”键将暂停并显示窝信息素的浓度图3.8：按下2键的显示（4）按下“3”键将暂停并显示窝所有信息素的浓度图3.9：按下3键的显示（5）按下“T”键将实时显示所有信息素的浓度（优先显示蚂蚁的行动）。图3.10：按下T键的显示（6） 按下“S”键将暂停并在左下角显示“Save to file .”保存环境。图3.11：按下S键的显示（7） 按下“L”键将暂停并在左下角显示“Load file .”读取环境。图3.12：按下L键的显示（8） 按下“Esc”将结束运行程序并显示运行时间。图3.13：按下Esc键的显示3.4.3 结果介绍（1）当程序运行了60秒而没有蚂蚁将食物搬回窝的话，将结束运行并显示“Can not find food，maybe a block world.”。图3.14：没有找到食物（2） 当程序运行了180秒而没有足够的蚂蚁将食物搬回窝的话，将显示“God! it is so difficult to find a path.”。图3.15：难以找到食物（3） 当搬运到窝的食物达到目标（目前设为200）时，程序将停止运行并等待指令，点击回车键将显示运行时间，再次点击回车键将重新建立随机环境。图3.16：没找到足够食物3.5 仿真分析（1）在障碍物较多但不复杂的环境下，蚂蚁可以有效地找到最短路径并自发的沿着路径搬运食物。图3.17：障碍物较多但不复杂的情况（2）在障碍物较多并且复杂的环境下，蚂蚁难以有效地找到最短路径。图3.18：障碍物较多并且复杂的情况（3）在障碍物不多的环境下，蚂蚁能够有效地找到最短路径并自发的沿着路径搬运食物。图3.19：障碍物不多的情况（4）在障碍物很少的环境下，蚂蚁能够轻易地找到最短路径并且绝大多数蚂蚁自发的沿着路径搬运食物。图3.20：障碍物很少的情况4 总结与展望本次仿真成功地模拟了自然界蚂蚁寻找食物这一群体行为，实现了简单的蚂蚁跟随。使得蚂蚁可以在大部分环境中成功找到并走上最短路径（或近似最短路径）。但是同时也体现出了一些不足之处，比如说蚂蚁难以辨别近似最短路径与真正的最短路