多Agent复杂系统分布仿真平台中的关键技术研究

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 复杂性问题的提出
• 1.1.2 基本概念与研究思路
• 1.1.3 复杂系统仿真方法的重要意义
• 1.2 相关研究现状
• 1.2.1 复杂系统建模的理论基础研究
• 1.2.2 复杂系统演化算法的研究
• 1.2.3 复杂系统演化模型的研究
• 1.2.4 复杂系统建模与仿真方法的研究
• 1.2.5 复杂系统仿真应用开发的研究
• 1.2.6 复杂系统仿真支持软件的研究
• 1.2.7 研究现状存在的不足
• 1.3 本文的研究内容与主要贡献
• 1.4 论文的结构
• 第二章 多AGENT复杂系统仿真平台的体系结构研究
• 2.1 研究的必要性
• 2.2 仿真平台的方法学基础
• 2.2.1 理论基础
• 2.2.2 多Agent建模与仿真
• 2.2.3 仿真步骤与实现途径
• 2.3 仿真平台的形式化基础
• 2.3.1 微观行为模型
• 2.3.2 系统演化模型
• 2.3.3 分布仿真运行模型
• 2.3.4 实现途径的形式化描述
• 2.4 仿真平台的支撑技术
• 2.4.1 分布计算支撑技术
• 2.4.2 仿真支撑技术
• 2.4.3 多Agent建模支持
• 2.4.4 仿真过程观察与干预手段
• 2.4.5 相关平台的比较分析
• 2.5 层次式的仿真平台体系结构
• 2.6 本章小结
• 第三章 环境的分布建模与划分问题研究
• 3.1 环境分布仿真的必要性
• 3.1.1 环境的定义
• 3.1.2 集中式环境模型存在的不足
• 3.2 相关工作
• 3.2.1 Agent的分布式环境建模方法
• 3.2.2 分布式系统中的任务分配问题
• 3.3 分布式环境模型
• 3.4 环境划分模型
• 3.4.1 环境划分问题描述
• 3.4.2 问题的NP难证明
• 3.4.3 近似算法的有效性分析
• 3.5 对分近似算法
• 3.5.1 穷举法
• 3.5.2 贪心对分法
• 3.5.3 最大流归并法
• 3.5.4 最大可能收益归并法
• 3.5.5 准贪心对分法
• 3.6 性能评测
• 3.6.1 典型场景下的小规模环境对分测试
• 3.6.2 大规模环境对分测试
• 3.7 K路递归对分近似算法
• 3.7.1 算法描述
• 3.7.2 性能评测
• 3.8 本章小结
• 第四章 层次式的因果序时间管理算法研究
• 4.1 问题描述
• 4.1.1 时间管理的必要性
• 4.1.2 复杂系统分布仿真带来的挑战
• 4.2 相关工作
• 4.2.1 逻辑时钟
• 4.2.2 时间管理算法
• 4.3 系统假设与基本概念
• 4.3.1 系统假设
• 4.3.2 基本概念
• 4.4 基于有效直接因果前驱的因果序时间管理算法
• 4.4.1 MSES算法介绍
• 4.4.2 MSES算法的改进
• 4.4.3 因果序时间管理算法描述
• 4.5 时间管理算法的层次式扩展
• 4.5.1 层次模型的构造算法
• 4.5.2 层次模型中消息的传递路由
• 4.5.3 层次模型中的时间管理
• 4.5.4 层次式扩展的正确性验证
• 4.6 性能评测与适用范围
• 4.6.1 改进算法与MSES算法的比较
• 4.6.2 层次式扩展算法与单步步进算法的比较
• 4.6.3 算法的适用范围
• 4.7 本章小结
• 第五章 复杂系统分布仿真平台ADVANCED JCASS的实现
• 5.1 JCass平台概述
• 5.1.1 JCass平台的特点
• 5.1.2 JCass平台存在的不足
• 5.2 Advanced JCass平台设计
• 5.2.1 设计原则
• 5.2.2 平台的结构
• 5.3 通讯系统的实现
• 5.3.1 通讯系统的结构
• 5.3.2 通讯的过程
• 5.4 时间管理的实现
• 5.4.1 接收序时间管理的实现
• 5.4.2 时戳序时间管理的实现
• 5.4.3 因果序时间管理的实现
• 5.5 分布式环境模型框架的实现
• 5.5.1 对环境分布建模提供支持的类、接口及其关系
• 5.5.2 分布环境的建模及实现过程
• 5.5.3 分布环境中共享状态的获取和修改过程
• 5.6 Agent规则库
• 5.6.1 Agent的抽象结构及其行为模式
• 5.6.2 Agent的规则库
• 5.7 群组模型库的实现
• 5.8 遗传算法支持库
• 5.8.1 对遗传算法提供支持的类、接口及其关系
• 5.8.2 实现中的关键技术
• 5.9 观察与干预系统的实现
• 5.10 仿真平台的适用范围
• 5.11 本章小结
• 第六章 应用实例—湖南省公众科学素养趋势预测与对策研究
• 6.1 问题描述
• 6.2 系统的整体方法与仿真步骤
• 6.2.1 科普系统仿真中的整体性问题
• 6.2.2 考虑时空结构和外部事件的整体性建模方法
• 6.2.3 整体性建模与仿真的基本步骤
• 6.3 湖南省科普系统的整体性模型
• 6.3.1 科普系统的整体性演化模型
• 6.3.2 环境模型
• 6.3.3 各种Agent
• 6.3.4 对策模型与外部事件
• 6.4 仿真结果及分析
• 6.4.1 系统初始化
• 6.4.2 发展趋势预测仿真的结果
• 6.4.3 结果分析
• 6.5 本章小结
• 第七章 结束语
• 7.1 论文工作总结
• 7.2 未来的工作
• 致谢
• 攻读博士期间论文发表与科研工作情况
• （一） 论文发表情况
• （二） 获得的科研成果
• 参考文献