学位论文 > 优秀研究生学位论文题录展示

面向多Agent系统的博弈联盟形成与分配问题研究

作　者: 李天文
导　师: 刘惟一
学　校: 云南大学
专　业: 通信与信息系统
关键词: 多Agent系统联盟形成效用分配合作博弈 Shapley值谈判集多选择合作博弈
分类号: TP18
类　型: 博士论文
年　份: 2013年
下　载: 54次
引　用: 0次
阅　读: 论文下载

内容摘要

多Agent系统是分布式人工智能领域的两个重要研究分支之一,其研究已经为智能机器人系统、云计算、搜索引擎、交通控制、网络通信等诸多应用领域核心问题的解决开辟了新的思路,并推动了相关应用领域中实际复杂系统的形成与发展。在多Agent系统研究领域,多个Agent如何进行有效合作和效用分配的问题是该领域的核心问题之一。基于合作博弈理论进行多Agent系统的联盟形成与效用分配问题的研究已经取得了诸多成果,其基于合作博弈理论的研究方法也得到了普遍的认可。然而,由于多Agent系统本身的复杂性和合作博弈理论到具体应用的难点,使得基于合作博弈理论对多Agent系统的联盟形成和效用分配问题的研究仍然存在许多待解决的问题。针对现有研究仍待解决的问题,论文基于合作博弈理论对多Agent系统的联盟形成与分配问题进行了深入的研究,其研究工作具有一定的理论意义。论文具体的研究工作如下：(1)以公平分配为原则基于合作博弈理论中Shapley值的公平分配特性针对多Agent系统的动态联盟形成和分配问题进行了研究。首先,论文提出了一种快速的静态初始化联盟形成算法。其次,针对Agent个体的参与能力和任务发生动态变化的情况,论文提出了一种联盟形成的快速动态更新算法；针对Shapley值求解效率差的问题,论文提出一种快速求解联盟中各个Agent近似Shapley值分配的算法。实验结果表明所提算法不仅获得了预期联盟形成结果和合理分配,而且具有较低的算法复杂度。(2)以稳定分配为原则基于合作博弈理论中谈判集的稳定分配特性对多Agent系统的联盟形成与分配问题进行了研究。针对求解谈判集的复杂博弈问题,借助删除谈判劣势联盟后获得的精简联盟集合,提出了一种基于遗传算法的稳定分配向量的求解算法,并给出了基于精简联盟集合获得的谈判集与经典谈判集相等的证明。论文进一步提出了一种基于字典序比较寻找联盟结构集合中最稳定联盟结构及稳定分配向量的算法。实验结果表明所提出算法不仅保证了求解的成功率,而且具有较低的算法复杂度。(3)针对多选择合作博弈关于稳定分配解理论的不足,论文将经典合作博弈中谈判集、内核和核仁等与稳定分配相关的概念拓展到多选择合作博弈中,并证明了谈判集的存在性、核仁的存在且唯一性、以及内核、核仁和谈判集三者之间的关系。借助拓展的稳定分配解,论文提出了基于多选择合作博弈求解复杂多Agent系统稳定分配向量的方法,并给出了一种基于遗传算法求解多个Agent在不同级别上稳定分配向量的算法。

全文目录

摘要  3-5
Abstract  5-7
目录  7-10
第一章绪论  10-20
  1.1 研究背景  10-12
  1.2 国内外研究现状  12-17
    1.2.1 基于联盟结构搜索的方法  13-14
    1.2.2 基于合作博弈的方法  14-16
    1.2.3 待研究的问题  16-17
  1.3 论文的主要工作  17-18
  1.4 论文的组织结构  18-20
第二章相关的基础理论知识  20-34
  2.1 Agent和多Agent系统  20-24
    2.1.1 智能Agent  20-21
    2.1.2 多Agent系统  21-22
    2.1.3 Agent联盟  22-23
    2.1.4 效用分配  23
    2.1.5 任务分配  23-24
  2.2 合作博弈及其分配解  24-33
    2.2.1 合作博弈  25-27
    2.2.2 核心  27-28
    2.2.3 Shapley值  28-29
    2.2.4 谈判集  29-30
    2.2.5 内核  30-32
    2.2.6 核仁  32-33
  2.3 本章小结  33-34
第三章基于公平分配原则的联盟形成与分配方法  34-54
  3.1 问题描述  34-37
  3.2 Shapley值优势联盟的思想  37-38
  3.3 基于Shapley值的联盟形成与分配方法  38-48
    3.3.1 静态初始化联盟的形成方法  38-42
    3.3.2 动态更新联盟状态的方法  42-46
    3.3.3 求解Agent效用分配的方法  46-48
  3.4 实验结果及分析  48-53
    3.4.1 效率对比分析  48-50
    3.4.2 效果对比分析  50-53
  3.5 本章小结  53-54
第四章基于稳定分配原则的联盟形成与分配方法  54-78
  4.1 问题描述  54-57
  4.2 谈判劣势联盟和精简联盟谈判集  57-63
    4.2.1 谈判劣势联盟  57-61
    4.2.2 精简联盟谈判集  61-63
  4.3 基于谈判集的联盟形成与分配方法  63-72
    4.3.1 精简联盟集合和联盟结构集合的求解方法  63-67
    4.3.2 稳定分配向量的求解方法  67-70
    4.3.3 最稳定联盟结构的求解方法  70-72
  4.4 实验结果及分析  72-77
    4.4.1 精简联盟集合求解算法的实验与分析  72-75
    4.4.2 稳定分配向量求解算法的实验与分析  75-77
  4.5 本章小结  77-78
第五章复杂多Agent系统的分配问题研究  78-98
  5.1 复杂多Agent系统  78-81
    5.1.1 多级别Agent  78-79
    5.1.2 复杂多Agent系统  79-81
  5.2 多选择合作博弈  81-83
  5.3 拓展的多选择合作博弈的稳定分配解  83-89
    5.3.1 谈判集  83-85
    5.3.2 内核  85-87
    5.3.3 核仁  87-88
    5.3.4 举例  88-89
  5.4 复杂多Agent系统的稳定分配求解方法  89-97
    5.4.1 基于谈判集、内核和核仁的稳定分配求解方法  89-94
    5.4.2 基于谈判集的稳定分配求解算法  94-97
  5.5 本章小结  97-98
第六章总结与展望  98-102
附录拓展稳定分配解的相关证明  102-112
参考文献  112-120
致谢  120-122
在读期间科研成果清单  122

面向多Agent系统的博弈联盟形成与分配问题研究

内容摘要

全文目录

相似论文