【作者】 叶超群；

【导师】 金士尧；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2006， 博士

【摘要】 随着人类步入21世纪,复杂系统与复杂性科学问题变得日益突出,其中包括环境、资源、经济、人口、健康、灾害、甚至和平与安全等困扰人类生存和社会可持续发展的重大问题,这些问题必须依靠多学科的交叉和综合从整体上寻找解决方案。在复杂适应系统理论的指导下,多Agent建模与仿真方法提供了一种研究复杂系统的新思路,是目前研究复杂系统的主要方法。本文从大规模复杂系统仿真的需求出发,研究多Agent复杂系统分布仿真平台的体系结构和关键技术。首先,根据复杂适应系统理论的要求,阐述了多Agent复杂系统仿真方法;对多Agent复杂系统分布仿真的实现途径进行了形式化描述;从分布计算支撑技术、仿真支撑技术、多Agent建模支持技术、仿真过程观察和干预手段四个方面概述了多Agent复杂系统仿真平台中的支撑技术;提出了多Agent复杂系统分布仿真平台的体系结构。其次,研究了环境的分布建模与划分问题。区分了不同的环境概念,分析了环境在多Agent复杂系统分布仿真中的关键影响,指出了环境分布仿真的必要性;介绍了具体的分布式环境模型,把环境空间划分为网格单独建模,提出了确定网格大小的方法;用环境模型负载图的划分问题描述了多Agent分布仿真中的环境划分问题,并说明了这个问题是NP难的,证明了当P≠NP时该问题不存在具有有限近似比率的多项式时间复杂性近似算法;利用启发信息提出了准贪心对分算法,用于近似求解环境的对分问题;基于分而治之的思想,给出了k路准贪心递归对分算法,用于近似求解一般情况下的环境划分问题;通过性能评测验证了近似算法能够以较小的时间开销取得理想的划分结果。研究并提出了一种层次式的因果序时间管理算法。指出了时间管理在分布仿真中的必要性,介绍了多Agent复杂系统分布仿真的特殊需求;分析了时戳序时间管理算法存在的不足,阐述了现有因果序时间管理算法的研究进展;在现有的因果序时间管理算法MSES算法的基础上,提出了改进的基于有效直接因果前驱的因果序时间管理算法;为了适应大规模分布仿真的要求,对算法进行了层次式扩展;通过测试对算法的有效性进行了评测。实现了多Agent复杂系统分布仿真平台——Advanced JCass,解决了仿真平台实现过程中的关键难点。为了验证本文的工作,研究并实现了湖南省公众科学素养趋势预测与对策系统的仿真。分析了公众科学素养趋势预测与对策研究是典型的复杂性问题,指出了现有研究方法存在的不足;提出了考虑时空结构和外部事件的复杂系统整体性建模的方法,给出了整体性建模与仿真的基本步骤;对湖南省科普系统做了整体性建模,具体给出了该系统中的环境模型、各种Agent模型和对策模型,并且在分析外部事件对整体性影响的基础上给出了外部事件建模方法;根据真实系统数据进行仿真初始化并运行,仿真结果表明了AdvacedJCass平台的可用性。更多还原

【Abstract】 With the arrival of the 21st century, problems about complex system and complexity science become increasingly noticeable. These problems involve the environment, resources, economy, population, health, disaster, peace, security and etc, which are concerned with the human survival and the sustainable development of the society. To solve these problems, people must rely on the interdisciplinary collaboration and integration and hold a wholeness perspective.Under the guide of the CAS theory, multi-agent modeling and simulation provides a new approach to study complex systems. It becomes one of the most popular methods in this domain. To satisfy the requirements of large scale complex system simulation, this thesis studies the architecture and key techniques of multi-agent platform for distributed simulation of complex systems.Firstly, according to the requirements of the CAS theory, the methodology of multi-agent complex system distributed simulation is described, and the way to implement multi-agent complex system distributed simulation is formalized. The base techniques of multi-agent platform for distributed simulation of complex systems are summarized in four aspects: techniques providing distributed computation support, techniques providing simulation support, techniques providing multi-agent modeling support and methods for observation and intervention of the simulation. The architecture of a multi-agent platform for complex system distributed simulation is then proposed.Secondly, this thesis studies the issues about the distributed modeling and partitioning of the environment. Several vague concepts about the environment are distinguished. After analyzed the important impacts of environment on multi-agent complex system simulation, the necessity of distributed simulation of the environment is presented. Then a distributed environment model is introduced. In this model, the whole environmental space is divided into grids and each grid is modeled separately. The method to determine the size of the grid is also presented. The issue to partition the environment is described in the form of partitioning the environment-model-load graph. This problem is proved to be NP-hard, and there is no polynomial time approximation algorithm with finite approximation factor unless P=NP. Based on the heuristic information, a pseudo greedy bisection partitioning algorithm is proposed. It can be used to bisection the environment approximately. To solve the problem of partitioning the environment generally, a k-way recursive pseudo bisection partitioning algorithm is given based on the divide-and-conquered technique. Experimental results indicate that these two algorithms can produce satisfactory partitions with relatively smaller cost of time than current methods.Thirdly, a hierarchical causal order time management algorithm is presented. After analyzing the necessity of time management in distributed simulation and introducing the special demands of multi-agent distributed simulation for complex systems, drawbacks of timestamp order time management algorithms are pointed out. Then the research and development of current causal order time management algorithms are surveyed and an improved algorithm based on effective immediate causal predecessor is proposed according to a causal order time management algorithm named MSES. The improved algorithm is extended hierarchically to fulfill the demands of large scale distributed simulations. Experimental results show the correctness and efficiency of our algorithm.Fourthly, a multi-agent platform for distributed simulation of complex system named Advanced JCass is implemented and the key issues in the implementation are conquered.Finally, to validate our works, a simulation application to forecast the trend of public scientific literacy and study the effect of science popularization in Hunan province is designed and implemented. This problem is considered as a typical complexity problem, and weaknesses of current methods are pointed out. Then an approach to model the wholeness of complex system is proposed, which considers both time-space structure and external events. The process to modeling and simulating the wholeness is also presented. With this approach, the wholeness of science popularization system in Hunan province is modeled, and several models for environment, agents and policy are explicitly constructed. Based on the analysis of the impact of external events on the wholeness of the system, methods to model external events are given. Initialized and executed with data from real system, execution results show that our platform can simulate complex systems correctly.更多还原