基于群智能的复杂联盟机制研究

论文摘要

基于多agent系统（Multi-agent systems,MAS）的分布式智能控制正在蓬勃兴起,以适应计算机支持的协同工作等应用需求,因而使得对MAS中的联盟研究也变得越来越重要。如何形成一个稳定均衡的联盟,使联盟朝着稳定的方向发展,是控制理论的前沿课题,已经成为迫切需要解决的关键问题。传统的研究方法仅考虑一个agent只能加入一个联盟,势必造成agent能力和资源的极大浪费,而且在很多应用场合不能满足实际系统的需要。基于上述背景,本文提出“复杂联盟”的概念,并引入群智能技术,力图在多任务环境中实现真正意义上的一个agent可以同时加入多个联盟和一个联盟可以同时承担多个任务,从而能在一定程度上提高系统的任务求解效率和资源利用率,为解决复杂控制问题提供理论指导和方法依据。本文的主要内容及创新之处如下:（1）提出一种基于多粒子群协同优化的复杂联盟串行生成算法。基于图论的思想,给出了“虚拟agent”的概念,旨在转移父联盟的剩余能力,由“虚拟agent”代表其父联盟参与后续任务的竞争,在一定程度上解决了agent资源和能力的浪费问题。实验结果表明,本算法对于任务较多且较简单的情形特别有效。（2）将离散粒子群算法扩充到二维二进制编码,实现复杂联盟的并行生成。算法中设计的编码有效性检查、冲突消解策略克服了求解过程中因多个任务求解联盟同时竞争某个能力有限的agent而导致的资源冲突和联盟死锁,而且实现了真正意义上的一个agent可以参加多个联盟,在一定程度上可以提高系统的资源利用率。（3）提出一种基于按劳分配和效用非减的效用分配策略。针对已有工作无法摆脱搭便车问题,导致联盟潜在的不稳定,采用拍卖机制对任务进行快速和有效分解,基于合同机制对联盟效用以及额外效用进行合理分配,并依据联盟机制的数学模型推导出了局部效用非减和全局效用非减应满足的条件。该策略既严格遵循按劳分配又完全符合效用非减,在具有超加性的面向任务的领域中可以形成全局最优联盟,并具有Nash均衡意义下的稳定性。（4）基于Markov过程和鞅理论推演了蚁群算法的几乎处处强收敛性,并提出一种基于蚁群正反馈的动态联盟形成策略。利用蚁群中的信息素浓度表示熟人之间的熟悉度,以信息素更新规则作为熟悉度调整规则。仿真实验的测试及分析说明了该策略能在一定程度上降低整个系统的通信代价和资源开销,提高了系统的可靠程度。

论文目录

• 摘要
• ABSTRACT
• 致谢
• 第一章 绪论
• 1.1 联盟形成（Coalition Formation）
• 1.1.1 智能agent
• 1.1.2 多agent系统（MAS）
• 1.1.3 联盟（Coalition）
• 1.2 群智能（Swarm Intelligence）
• 1.2.1 粒子群算法（Particle Swarm Optimization）
• 1.2.2 蚁群算法（Ant Colony Optimization）
• 1.3 目前存在的问题
• 1.4 课题来源、目的与意义
• 1.5 研究内容、技术路线及论文组织
• 1.5.1 研究内容
• 1.5.2 技术路线
• 1.5.3 论文组织
• 第二章 复杂联盟的串行生成
• 2.1 相关工作分析
• 2.2 复杂联盟（Complicated Coalition）
• 2.3 问题描述
• 2.4 虚拟agent（Virtual Agent）
• 2.5 基于离散粒子群的复杂联盟串行生成算法
• 2.5.1 离散粒子群算法
• 2.5.2 粒子编码方案
• 2.5.3 基于信息正反馈的孤岛模型
• 2.5.4 复杂联盟串行生成算法
• 2.5.5 仿真结果及分析
• 2.6 小结
• 第三章 复杂联盟的并行生成
• 3.1 相关工作分析
• 3.2 问题描述
• 3.3 Yang和Luo的算法
• 3.3.1 二维二进制染色体编码
• 3.3.2 编码初始化
• 3.3.3 交叉算子
• 3.3.4 变异算子
• 3.3.5 GA算法求解联盟结构
• 3.4 离散粒子群算法（DPSO）
• 3.5 基于离散粒子群的复杂联盟并行生成算法
• 3.5.1 编码初始化
• 3.5.2 编码有效性检查（Checking on Encoding Validity）
• 3.5.3 冲突消解策略（Strategies for Conflict Resolution）
• 3.5.4 复杂联盟并行生成算法
• 3.5.5 仿真结果及分析
• 3.6 小结
• 第四章 联盟效用分配策略
• 4.1 问题描述
• 4.2 相关工作分析
• 4.3 基于按劳分配的效用分配策略
• 4.3.1 公平分配原则
• 4.3.2 无妒忌原则
• 4.3.3 基于拍卖的任务分解（Task Allocation via Auction）
• 4.3.4 基于合同的效用分配（Utility Distribution via Bargain）
• 4.3.5 实例分析
• 4.4 基于按劳分配和效用非减的效用分配策略
• 4.4.1 局部效用非减（Local Non-reducing Utility）
• 4.4.2 全局效用非减（Global Non-reducing Utility）
• 4.4.3 实例分析
• 4.4.4 性能分析
• 4.4.5 仿真结果及分析
• 4.5 小结
• 第五章 基于蚁群正反馈的动态联盟形成
• 5.1 相关工作分析
• 5.2 蚁群的正反馈思想
• 5.3 蚁群算法的几乎处处强收敛性分析
• 5.3.1 算法模型
• 5.3.2 收敛性分析
• 5.3.3 讨论
• 5.4 基于蚁群正反馈的动态联盟形成
• 5.4.1 任务分配
• 5.4.2 动态联盟形成过程
• 5.4.3 仿真结果及分析
• 5.5 小结
• 第六章 总结与展望
• 6.1 本文的主要创新之处
• 6.2 进一步的研究工作
• 参考文献
• 攻读博士学位期间发表的论文
• 攻读博士学位期间参加科研项目及获奖情况