论文部分内容阅读
联盟形成一直是多agent系统(multi-agent systems,MAS)和人工智能中的一个热点课题。其中,资源结盟博弈(coalitional resource games,CRGs)同时考虑资源受限、消耗和竞争,提供了一种最自然的通用协作机制实现agent共享稀缺资源完成相互满意的目标。然而,传统的CRGs研究均假设每个agent可以响应所有目标,即使有目标不在其感兴趣的子目标集内,这种目标毫无约束下的联盟形成往往偏离应用实际,并带来巨大的计算开销。因此,本文提出一种考虑agent偏好的CRGs,每个agent只愿意把自己的有限资源贡献给自己的兴趣集中的目标。本文主要工作如下:(1)通过对国内外联盟形成问题的研究现状进行调研、分析、总结,指出目前联盟形成问题研究中存在的问题。(2)对考虑agent偏好的CRGs进行数学建模。通过对模型中agent、目标(goal)和联盟(coalition)三者之间的联系进行分析,提出了“实际贡献量”和“剩余资源量”等概念,重新定义了agent偏好下的成功联盟问题,并推演了其计算复杂性。(3)提出了一种基于“至少承担量”和二维二进制粒子群优化的最大成功联盟生成算法。将二进制粒子群优化扩充到二维编码,每个agent响应目标与否,由其在联盟中的至少承担量来决定,并提出一种编码修正启发式算法以解决多个目标竞争同一agent资源可能引起的资源冲突。与已有相关算法的对比实验分析验证了所提方法的有效性。(4)提出了一种基于“贡献量均摊”的改进的最大成功联盟生成算法。针对“至少承担量”在一定程度上降低了agent参与联盟的几率,不利于最大成功联盟的搜索,把贡献量均摊在每个成员上,保证每个有可用资源的agent都能参与联盟,并在此基础上提出了一种更为简单有效的编码修正算法。对比实验结果表明,所提方法在面向大规模样本时格外有效。