局部信息的分布式联盟结构生成算法-计算机工程与应用.PDF

Computer Engineering and Applications 计算机工程与应用 2012 ，48 （29 ） 59 局部信息的分布式联盟结构生成算法 汲长飞，张 伟，童向荣，刘惊雷，刘其成 JI Changfei, ZHANG Wei, TONG Xiangrong, LIU Jinglei, LIU Qicheng 烟台大学 计算机科学与技术学院 智能信息处理实验室，山东 烟台 264005 Laboratory of Intelligence Information Processing, Institute of Computer Science and Technology, Yantai University, Yantai, Shandong 264005, China JI Changfei, ZHANG Wei, TONG Xiangrong, et al. Distributed coalition structure generating algorithm based on local information. Computer Engineering and Applications, 2012, 48 （29 ）：59-63. 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 in- formation 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 2 time complexity can reach O（n ）. Key words ：multi-agent coalition; local information; distributed 摘 要：已有的求解最优联盟结构方法大多假定Agent 的全局信息已知，采用集中式求解思路，这种假设不适用于 分布式环境，且没有充分利用Agent 的自治性。在多Agent 环境下，个体Agent 往往只拥有部分联盟信息并且是自 利的，如何在局部信息条件下寻找最优联盟结构是多Agent 系统需要解决的关键问题。针对以上问题，基于个 体Agent 的局部信息及系统整体收益的考虑，通过局部Agent 之间的优势信息传递，给出了最优联盟结构的分 布式求解算法。该算法的特色是在局部最优假设下，通过局部信息的指导，n 个Agent 在深度方向上自顶向下 2 对联盟结构图的并行有哪些信誉好的足球投注网站，从而达到缩短有哪些信誉好的足球投注网站时间，降低有哪些信誉好的足球投注网站复杂度的目的，该算法的时间复杂度为O（n ）。 关键词：Agent 联盟；局部信息；分布式