给定限界要求的联盟结构生成

• 作者: 石纯一 胡山立
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 联盟 联盟结构 算法 多Agent系统
• 年，卷（期）: 2001,（11）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1185-1190
• 页数: 6页
• 分类号: TP18
• 字数: 5764字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2001.11.009

摘要

联盟形成是多Agent系统中的一个关键问题,目的是通过寻找使联盟值的总和最大的联盟结构来使系统得到最大的效益.但通常可能的联盟结构的数目太大,不允许穷尽搜索来找出最优解.当实际问题提出最坏情况的具体限界要求时,如何以最小的搜索达到这个要求是需要解决的.文中给出的算法对给定的限界要求K*2以最少的搜索层数解决了这个问题. Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的,此时限界是n(系统的Agent数). 以此为基础,文中给出了算法,在搜索最底两层之后,只要搜索一层就能保证K(n)3;而在搜索最底两层之后,最多搜索两层就能保证K(n)2. 与Samdholm等人给出的算法相比,文中给出的算法达到指定限界的搜索量显著减少.要 联盟形成是多Agent系统中的一个关键问题,目的是通过寻找使联盟值的总和最大的联盟结构来使系统得到最大的效益.但通常可能的联盟结构的数目太大,不允许穷尽搜索来找出最优解.当实际问题提出最坏情况的具体限界要求时,如何以最小的搜索达到这个要求是需要解决的.文中给出的算法对给定的限界要求K*2以最少的搜索层数解决了这个问题. Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的,此时限界是n(系统的Agent数). 以此为基础,文中给出了算法,在搜索最底两层之后,只要搜索一层就能保证K(n)3;而在搜索最底两层之后,最多搜索两层就能保证K(n)2. 与Samdholm等人给出的算法相比,文中给出的算法达到指定限界的搜索量显著减少.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	石纯一	清华大学计算机科学与技术系	85	3189	30.0	55.0
2	胡山立	中国科学院软件研究所	21	205	8.0	14.0