多智能体蜂拥的研究

多智能体系统蜂拥问题的研究 1

1绪论

1.1研究背景

蜂拥是一种大数量相互影响的具有普遍群体目标的个体集体行为的一种表现。数十年来，依靠个体间基本的相互影响的涌现现象已经吸引了来自不同领域的科学家们，他们包括动物行为、物理、生物、社会学和微机科学等[1-12]。这些主体的例子一般为鸟、鱼、鸽子、蚂蚁、蜜蜂和人群。这些生物在运动能力、视觉能力等方面有限，但通过相互之间的交互构成大规模群体，能够将有限的个体能力聚集起来，克服单个个体能力上的不足，高效的完成觅食、迁徙、躲避天敌等活动。在这样的群体系统中，由于单个个体仅具有有限的局部感知能力，仅能够获取存自己能力范围内的局部信息，而无法获取整个群体的全局信息，因此系统中就不存在集中式的协调控制机制，而具有分散式、分布式系统的特点。如何通过局部信息交换产生全局的系统行为足近年来的一个研究热点。

一般将实际中具有上述现象的系统抽象为多智能体系统(Multi-Agent Systems ，MAS)，该系统具有一个有趣的性质：在许多由大量动态演化的个体组成的系统中，往往会涌现出全局协调一致的行为。一般而言，构成该系统的个体并不知道整个系统的全局信息，每个个体只能根据它所拥有和感知的局部信息（如它所能够观察到的其它个体的行为）来调整自身的行为。也就是说，整个系统是通过分布式的个体凋整而不是集中控制方式实现全局协调一致行为的。具有这样性质的系统在实际中是普遍存在的，除了生物系统会表现出全局一致的性质，一些非生物系统也会出现这种一致性现象，例如，悬挂在一个横梁上的钟摆在一段时间后会出现同步摆动，演出结束后观众的掌声发生同步，网路上的路由器最终会以同步的方式发送路由消息，从而引起的网络拥塞，以及人们通过大桥时的步伐同步，从而引起大桥的共振等。对于这类现象的产生机理，研究者将其纳入复杂网络的范畴内进行研究，得出这样的结论：在这些复杂系统中，每一个个体都是一个动力学系统，而诸多的动力学个体之间存在着某种特殊的耦合关系，这些系统中的个体根据自身能够感知的局部信息经过动态演化而达到整个系统的同步。本质上．复杂网络的同步的机理与多智能体系统协调现象是一致的。

截止目前对蜂拥动态行为的建模和分析按照研究方法来分类最常用的方法有三种：基于个体描述的方法，也称为拉格朗日方法；连续流方法，也称为欧拉方法；以及离散系统模型方法。以上三种方法中，基于个体描述的模型，是以常微分方程组来描述所有个体的运动，这是对连续变化对象建模的一个自然的方法。连续流模型则采用偏微分方程来描述蜂拥分布形成的密度场中局部的反应散现象，研究其稳定性和运动性质。离散系统模型方法是用离散时间方程组来描述，研究其互相作用下的集体行为。

第一批对蜂拥(Flocking)的从理论角度进行研究的物理学家有Vicsek[13]等，

多智能体系统蜂拥问题的研究 2

Toner&Tu[14]，Shimoyama[15]等，和Levine[16]等。Vicsek等的研究内容主要涌现在个体控制系统中速度匹配的势能（这并不意味着蜂拥），而Toner&Tu采用了连续介质力学接近。Levine等创造了一个基于个体的相互影响的系统，这种循环蜂拥系统被称作循环蚂蚁工厂。另一种连续模型是由Mogilner&Ekdstein-Keshet[17]和Topaz&Bertozzi[18]提出的。Helbing等使用经验法的基于个体的模型研究了蜂拥。

1.2群体智能理论及研究方法

1.2.1群体智能概述

群智能理论的基本原理[19-20]是以生物社会系统(Biology social system)作为依托，也就是由简单个体组成的群体与环境以及个体之间的互动行为。这种生物社会性的模拟系统利用局部信息产生难以估量的复杂群体行为。

群体智能并不是所有生物种群都具有的特性，它是那些具有社会性特征的群居生物个体合作进行某些活动时才会产生的涌现现象。关于群体智能行为的生物原型，Bonabeau描述了生物蚂蚁群体的一些行为，如觅食、劳动分工、尸体聚集、巢穴构造、合作运输等，并分别对其建模，然后设计了一系列算法、多主体系统(MAS)和多机器人系统[31]。集中介绍了社会性昆虫的行为建模和蚁群优化算法及其性能。Kennedy通过观察鸟群的协同运动，开创了微粒群优化这一新型群体智能方法的研究领域，并以此为基础提出了以下基本观点[21]：

1)人类智能的产生源于社会交往； 2)文化和认知是人类社交的结果。

对鱼群的研究，也属于群体智能的理论范畴。群体智能研究成果和理论体系，可以用来指导我们对鱼群形成、组织体系、群体行为及其涌现出的群体智能的研究。群体智能是一种通过模拟自然界生物群体行为来实现人工智能的方法。由单个简单个体完成的任务，可以涌现出复杂的智能，充分体现了整体和大于个体的叠加。群体智能利用群体优势，在没有集中控制，不提供全局模型的前提下，为复杂问题寻找解决方案[22]。普遍意义上，群体智能强调个体行为的简单性、群体的涌现特性、以及自下而上的研究策略。群体智能的本质是由许多简单个体组成的群体，群体之间能够通过简单的交互、合作和协作，来完成某一项任务。群体智能在已有的应用领域中都表现出较好的寻优性能，因而引起了相关领域研究者的极大关注。其中涌现是群体智能中一个比较重要的概念，群体智能中的智能就是大量个体在无中心控制的情况下体现出来的宏观有序的行为。这种大量个体表现出来的宏观有序行为就是涌现现象。如果没有涌现现象，就无法体现智能。因为涌现是简单的个体行为在特定组织结构下，积累到一定程度，所表现出来的整体现象，所以，对群体智能的研究必须既研究各个部分，又研究各个部分之间的相互作用关系。

Millionas M. M在1994年提出群体智能应遵循的五条基本原则[23]，分别为：

多智能体系统蜂拥问题的研究 3

1)邻近原则，动物群体能够进行简单的空间和时间计算； 2)品质原则，动物群体能够响应环境中的品质因子；

3)多样性反应原则，动物群体的行动范围不应该局限在小范围内； 4)稳定性原则，动物群体不应该在每次环境变化时都改变自身的行为；

5)适应性原则，在所需代价不太高的情况下，动物群体能够在适当的时候改变自身的行为。

1.2.2群体智能的主要优点

群体智能具有以下优点[24]：

1)群体中相互合作的智能体是分布的，这样更能够适应当前网络环境下的工作状态。

2)没有中心控制与数据，这样的系统更具有鲁棒性，不会由于某一个或者某几个智能体的故障而影响整个问题的求解。

3)可以不通过智能体间直接通信，而采用非直接通信进行合作，系统具有更好的可扩充性，使得系统中由于智能体数量的增加而增加的系统通信耗费较小。

4)系统中每个智能体的能力非常简单，以至于每个智能体的执行时间都比较短，且实现也较简单，具有简单性。

5)智能体相互作用能突现出整体的行为，系统所有上层智能行为都是通过智能体的基本规则相互作用产生的，所以在多任务情况下，对于每一子任务可以分别编制、调试、学习。

6)群体智能中，信息处理原则是基于发生在实际生命中大量并行处理过程。群体智能系统的强并行性大大地增强了系统的运算速度及能力。

7)人工生命中的一个重要原则，就是整体大于部分和的思想。由于群体智能的整体行为是由智能体行为突现而产生的，智能体在相互作用中的负关系将会因智能体自身的相互作用规则而消减，正关系将得以增强。对于智能体之间的冲突和任务协调等问题，由底层智能体相互作用的规则解决，减少上层对智能体之间的协作、协调控制，避免了上层控制干预下层动作的情况，使得每一层次的控制任务都非常清晰，增加了系统协作协调效率。

1.2.3群体智能的主要缺点

群体智能的研究还处于萌芽阶段，还存在很多不足，主要问题如下[25]：

1)群体智能的思想是根据对生物群体观察得来的，是概率算法，从数学上对于它们的正确性与可靠性的证明仍比较困难。

2)这些算法都是专用算法，一种算法只能解决某一类问题，各种算法之间的相似性很差。

3)系统高层次的行为是需要通过低层次智能体间的简单行为交互突现产生。单个个

多智能体系统蜂拥问题的研究 4

体控制的简单并不意味着整个系统设计的简单。

4)系统设计时也要保证多个智能体简单行为交互能够突现出所希望看到的高层次复杂行为。这可以说是群体智能中一个极为困难的问题。 1.2.4群体智能的底层机制研究

自组织[26]：自组织是一种动态机制，由底层单元的交互而呈现出系统的全局性的结构。交互的规则仅仅依赖于局部信息，而不依赖于全局的模式[23]。自组织是系统自身涌现出的一种性质。系统中没有一个中心控制模块，也不存在一个部分控制另一部分。自组织的特点就是通过利用同一种介质或者媒体创建时间或空间上的结构。比如蚂蚁筑的巢、寻找食物时的路径等。正反馈群体中的每个具有简单能力的个体表现出某种行为，会遵循已有的结构或者信息指引自己的行动，并且释放自身的信息素，这种不断的反馈能够使得某种行为加强。尽管一开始都是一些随机的行为，大量个体遵循正反馈的结果是呈现出一种结构。自然界通过系统的自组织来解决问题。理解了大自然中如何使生物系统自组织，就可以模仿这种策略使系统自组织。

间接通信[26]：群体系统中个体之间如何进行交互是个关键问题。个体之间有直接的交流，如触角的碰触、食物的交换、视觉接触等， 但个体之间的间接接触更为微妙，已有研究者用Stigmergy来描述这种机制：也就是个体感知环境，对此做出反应，又作用于环境。Grasse首先引入Stigmergy来解释白蚁筑巢中的任务协调[27]。Stigmergy在宏观上提供了一种将个体行为和群体行为联系起来的机制。个体行为影响着环境，又因此而影响着其它个体的行为。个体之间通过作用于环境并对环境的变化做出反应来进行合作。总而言之，环境是个体之间交流、交互的媒介。从蚂蚁觅食到蚂蚁聚集尸体到蚂蚁搬运、筑巢，个体之间的通信机制总是离不开Stigmery机制，对于环境的作用，通常由各种各样的信息素来体现。

涌现[26]：群体智能中的智能就是大量个体在无中心控制的情况下体现出来的宏观有序的行为。这种大量个体表现出来的宏观有序行为称之为涌现现象。没有涌现现象，就无法体现出智能。因此，涌现是群体智能系统的本质特征。只知道孤立的个体行为并不能了解整个系统的情况，仅仅研究孤立的部分无法有效地研究整体性质，因此，对涌现现象的研究必须既研究各个部分，又研究各个部分之间的相互作用[28]。“遗传算法之父”约翰·霍兰在文献[29]中对涌现现象进行了较为深入的探索。他认为涌现现象的本质是“由小生大，由简入繁’’，并且把细胞组成生命体，简单的走棋规则衍生出复杂的棋局等现象都视为涌现现象。他认为神经网络、元胞自动机等可以算作涌现现象的模型。群体智能的涌现现象与系统论和复杂系统中阐述的涌现本质上是相同的，它是基于主体的涌现。1979年霍夫施塔特对基于主体的涌现作了描述，整个系统的灵活的行为依赖于相对较少的规则支配的大量主体的行为。研究群体智能系统，要弄清涌现现象的普遍原理，建立由简单规则控制的模型来描述涌现现象的规律。

多智能体系统蜂拥问题的研究 5

1.3MAS（Multi-Agent System）系统

如果说对单个智能体的研究是将传统人工智能研究领域的方法集成在一个实体上进行的话，那么，对多智能体系统（Multi-Agent system，MAS)的研究，则是对群体智能的更进一步的拓展。在MAS中，整个系统所表现出来的智能或者说行为，不仅仅是多个智能体行为的简单叠加，它所显示出来的整个社会的行为存在更多的不确定因素，更为复杂，难以预测。

1.3.1MAS（Multi-Agent System）概念

对于MAS[30]的研究起源于上个世纪七十年代后期的分布式人工智能Distributed Artificial Intelligence，DAI)，它有两大研究方向：分布式问题求解(Distributed Problem solving，DPS)与MAS。DPS主要研究的是对于一个给定的问题，如何将任务在一组节点之间进行分配。这些问题求解节点可能因为所拥有的资源、能力、信息等的不足，而需要相互合作，以期共同完成任务。这是一种从系统的观点、在设计阶段就进行问题分解、求解规划及解答合成的方式。而在近年来得到越来越多关注的MAS，则更加强调了问题求解节点的自治性。

研究由多个自治的智能体组成的MAS，更重要的在于研究智能体之间的联系以及整个系统所表现出来的特性。正是由于智能体之间的联系的多样性，使得整个系统呈现出复杂、难以预测的现象。这是一个高度交叉的研究领域。无论是从其理论方面，还是应用方面，均涉及到众多领域的相关内容，如计算机学科、经济学、哲学、社会学、心理学、生态学和组织科学，而研究者从不同的方面给予不同的侧重。

计算机科学：这是MAS的起源领域，从而有着广泛的研究内容。从MAS的计算理论出发，研究在分布式/并发环境下，任务的分解与分配，智能体之间的协调、协作、通信、死锁预防与解决等。在人工智能方面，有智能体的规划、调度以及智能体之间的协商。

经济学：主要是应用经济学中的对策论(Game Theory)来研究智能体之间的交互问题，如规划、协商、学习等问题。当被认为是理性的多个智能体因为某项任务进行协商时，从各自的利益出发，对其他智能体的信念、意图进行推理，选择最优策略。传统的对策论中参预者之间没有通信，只是根据完全的或者是不完全的信息进行决策。当应用到智能体的协商过程中时，则相应地进行了很多改进，如将通信行为引入协商过程。

社会学：包含有两个方面——以人类社会研究来对MAS中存在的现象进行研究，以及以MAS来仿真人类社会中可能的现象。对于前者可包括众多的内容，如对伦理、规范、组织等的研究：而对于后者，包括对于人类社会秩序、合作、冲突、协商等的仿真，主要讨论某种特定的社会现象在某种情况下是如何涌现出来的，并以观察到的规律来解释和理解人类社会中的现象，并加以预测。同时，对社会伦理、规范、承诺、义务、权利等约束概念的研究，智能体在社会体系中遵循的规范、以防止恶意欺诈、使得社会

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库多智能体蜂拥的研究在线全文阅读。