计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (29): 59-63.

• 研究、探讨 • 上一篇    下一篇

局部信息的分布式联盟结构生成算法

汲长飞,张  伟,童向荣,刘惊雷,刘其成   

  1. 烟台大学 计算机科学与技术学院 智能信息处理实验室,山东 烟台 264005
  • 出版日期:2012-10-11 发布日期:2012-10-22

Distributed coalition structure generating algorithm based on local information

JI Changfei, ZHANG Wei, TONG Xiangrong, LIU Jinglei, LIU Qicheng   

  1. Laboratory of Intelligence Information Processing, Institute of Computer Science and Technology, Yantai University, Yantai, Shandong 264005, China
  • Online:2012-10-11 Published:2012-10-22

摘要: 已有的求解最优联盟结构方法大多假定Agent的全局信息已知,采用集中式求解思路,这种假设不适用于分布式环境,且没有充分利用Agent的自治性。在多Agent环境下,个体Agent往往只拥有部分联盟信息并且是自利的,如何在局部信息条件下寻找最优联盟结构是多Agent系统需要解决的关键问题。针对以上问题,基于个体Agent的局部信息及系统整体收益的考虑,通过局部Agent之间的优势信息传递,给出了最优联盟结构的分布式求解算法。该算法的特色是在局部最优假设下,通过局部信息的指导,n个Agent在深度方向上自顶向下对联盟结构图的并行搜索,从而达到缩短搜索时间,降低搜索复杂度的目的,该算法的时间复杂度为O(n2)。

关键词: Agent联盟, 局部信息, 分布式

Abstract: Most of the existing methods to generate optimal coalition structure are centralized which assumed the global information has been given. These ideas do not match the distributed environment and do not make full use of the Agent’s autonomy well. In MAS, the individuals are self-interested and usually hold the local information, so how to generate the optimal coalition structure under local information becomes an important problem. In view of the above question, it gives a distributed coalition structure generating algorithm based on individual agent local information and the systems global income. The algorithm follows the local optimum principle and the characteristic is n Agents’ top-down parallel search in the coalition structure graph, thus it can shorten the search time, and the time complexity can reach O(n2).

Key words: multi-agent coalition, local information, distributed