论文部分内容阅读
作为一种有效计算范式和设计理念,多Agent系统(Multi-Agent System,MAS)已被人们广泛认同、接受和使用。多Agent系统由具有自主性、反应性、能动性和社会性等属性的计算实体(即Agent)所构成。通过微观或局部(即Agent及它们之间的交互)的行为或机制,MAS期望获得需要的宏观全局(即整个多Agent系统)功能。因此,多Agent系统微观层面和宏观层面的联系,便成为MAS系统分析的要旨和主题。但是,与传统的计算系统相比,MAS系统中微观和宏观之间的联系具有很大的特殊性。识别这种特殊性,并将其应用于MAS分析,对于研究MAS具有重要的理论和实践价值。以“涌现”为MAS的分析和设计范式,本文以涌现表征MAS系统微-宏观联系方面的特殊性,提出了基于涌现的MAS分析框架和方法;进而,研究了MAS的典型系统和机制,包括BitTorrent系统、蚁群算法系统、流言机制和信任/声誉机制。首先,针对涌现概念难以理解的现实情况,本文提出了理解涌现概念的多个视角和相关问题。在考察涌现概念的历史演化基础上,赋予涌现全新的整体观念、层次观念和动态生成观念;这些观念构成了涌现概念的基本骨架,成为理解涌现概念的基础。提出了理解涌现概念的几个关键问题,包括涌现所涉及的关系、涌现性判据、涌现所指称的对象、涌现的客观性和主观性等问题;这些问题以涌现所涉及的关系为中心,以涌现性判据为重点,回答了界定涌现概念所涉及的基本要素。给出了区分涌现和总成、综合以及自组织等几个易混概念的关键点,并第一次将涌现与综合区分开来。进而基于对涌现概念的这些剖析,指出了MAS中涌现性的根源及其规定性。其次,鉴于涌现可以表征MAS微-宏观联系的特殊性,本文提出了基于涌现视角的MAS分析框架和方法。基于对涌现性的理解,提出了基于涌现视角MAS分析的基本流程,定义了分析过程中涉及的相关概念,明确了分析过程中的一般性问题及可能的解决方案。进而,提出了三类微-宏观分析方法,即基于逻辑推理的分析方法、基于数学解析的分析方法和基于仿真运行的分析方法;给出了它们实现微-宏观分析任务的途径,考察了相关研究,明确了各个方法的有效性和局限性。再次,流言机制是大规模MAS中常用的一种信息传递机制,而已有的研究主要是分析其时间复杂度,并没有对这一机制导致的系统宏观动态特性进行研究。基于平均场方法,本文提出了一个流言机制分析模型,以用于系统动态性分析。通过对平均场方法基本思想的分析,给出了这一方法的分析步骤和使用的手段,指出了这一方法在系统微-宏观分析中的作用。进而利用这一方法,为一个基于流言的分布求和平均系统建立了微-宏观分析模型。与既有的工作相比,这一模型不仅能够给出基于流言的分布求和平均系统收敛的时间复杂性,还可以刻画系统的动态过程,展现系统在不同条件下的系统演化。再次,P2P系统是目前极有代表性的一类MAS系统。作为一个典型的实际P2P系统,BitTorrent在理论和实践中引起了广泛关注,人们希望通过建立起数学模型,来理解通过测量观察到的宏观特性。本文基于涌现视角提出了类BitTorrent系统的分析模型。模型从相对清晰的系统微观状态和行为入手,选取表征BitTorrent结点的微观参数;根据BitTorrent的结点行为,基于这些微观参数,给出了系统的微观行为描述;选取表征BitTorrent宏观态的宏观变量;然后依据宏观变量与微观变量的关系,基于微观行为描述,建立起系统的宏观演化方程。与既有的宏观模型相比,这一微-宏观模型能够更好地揭示BitTorrent系统特性的内在机理。再次,蚁群系统是一个简单的MAS系统,但是根源于这一自然系统的蚁群算法,仍有一些比较复杂的理论问题难以认清。本文基于涌现视角指出了蚁群算法分析中复杂性产生的根源。首先分析了蚁群算法的微观过程和宏观过程,利用预测信息对算法的过程复杂性进行了度量,结果表明其复杂性非常大,这正是蚁群算法分析的困难之所在。基于涌现视角分析蚁群算法当前最优解的状态转移过程,明确了保证算法收敛的一些充分条件,提出了算法收敛速度分析的一种可能方法。基于涌现视角,指出欺局是一些蚁群算法运行中存在的宏观现象,有其微观根源,这就是偏置;同时总结分析了三种偏置及其产生欺局的途径。与既有的工作相比,基于涌现视角的蚁群算法分析,更能把握算法的本质。最后,信任管理被认为是许多具体多Agent系统领域的关键问题之一。而信任机制往往会带来涌现性,其宏观行为通常比较难以认清。为此,本文基于涌现视角提出了一种信任模型仿真分析方法,用以对它们进行研究。该方法从相对清晰的微观层面入手建立仿真运行模型,在宏观约束下,研究系统宏观层面的问题以及微观和宏观之间的联系。在微观层面上,在总结分析信任模型微观机制设计图式的基础上,提出了仿真Agent的设计框架。在宏观层面上,给出了信任模型仿真分析中应考虑的宏观问题,包括宏观约束、威胁模型、评价指标,以及仿真执行中的问题。通过对一个局部信任模型的分析,证明了该方法在揭示信任模型的微-宏观联系和宏观行为方面的有效性,同时也揭示了信任模型的微-宏观联系的难以预测性和宏观行为的复杂性。