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

Distributed coalition structure generating algorithm based on local information

作　　者：汲长飞[1] 张伟[1] 童向荣[1] 刘惊雷[1] 刘其成[1] 

机构地区：[1]烟台大学计算机科学与技术学院智能信息处理实验室,山东烟台264005

出　　处：《计算机工程与应用》2012年第29期59-63,共5页Computer Engineering and Applications

基　　金：国家重点基础研究发展规划(973)(No.2007CB307100);山东省高等学校科技计划项目(No.J11LG35;No.J10LG27)

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

关 键 词：AGENT联盟 局部信息 分布式 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]