【作者】 杜晓东；

【导师】 张国富；

【作者基本信息】 合肥工业大学 ， 信号与信息处理， 2017， 硕士

【摘要】 联盟形成一直是多agent系统(multi-agent systems,MAS)和人工智能中的一个热点课题。其中,资源结盟博弈(coalitional resource games,CRGs)同时考虑资源受限、消耗和竞争,提供了一种最自然的通用协作机制实现agent共享稀缺资源完成相互满意的目标。然而,传统的CRGs研究均假设每个agent可以响应所有目标,即使有目标不在其感兴趣的子目标集内,这种目标毫无约束下的联盟形成往往偏离应用实际,并带来巨大的计算开销。因此,本文提出一种考虑agent偏好的CRGs,每个agent只愿意把自己的有限资源贡献给自己的兴趣集中的目标。本文主要工作如下:(1)通过对国内外联盟形成问题的研究现状进行调研、分析、总结,指出目前联盟形成问题研究中存在的问题。(2)对考虑agent偏好的CRGs进行数学建模。通过对模型中agent、目标(goal)和联盟(coalition)三者之间的联系进行分析,提出了“实际贡献量”和“剩余资源量”等概念,重新定义了agent偏好下的成功联盟问题,并推演了其计算复杂性。(3)提出了一种基于“至少承担量”和二维二进制粒子群优化的最大成功联盟生成算法。将二进制粒子群优化扩充到二维编码,每个agent响应目标与否,由其在联盟中的至少承担量来决定,并提出一种编码修正启发式算法以解决多个目标竞争同一agent资源可能引起的资源冲突。与已有相关算法的对比实验分析验证了所提方法的有效性。(4)提出了一种基于“贡献量均摊”的改进的最大成功联盟生成算法。针对“至少承担量”在一定程度上降低了agent参与联盟的几率,不利于最大成功联盟的搜索,把贡献量均摊在每个成员上,保证每个有可用资源的agent都能参与联盟,并在此基础上提出了一种更为简单有效的编码修正算法。对比实验结果表明,所提方法在面向大规模样本时格外有效。更多还原

【Abstract】 Coalition formation(CF)has been a hot topic in multi-agent systems(MAS)and artificial intelligence.In CF,coalitional resource games(CRGs)take into account resource constraint,consumption,and competition altogether,and provide a natural collaboration mechanism to make agents share scarce resources to achieve mutual satisfactory goals.However,the traditional CRGs assume that each agent can respond to all the goals,even if the agent is not interested in the goal at all,which makes CF deviate from the practical applications and brings a huge computational cost.Therefore,this dissertation considers the CRGs under the agent preferences over goals.In such case,each agent is only willing to contribute its own limited resources to the goals in its own interest set.The main work of this dissertation is as follows:(1)The existing work on CF is analyzed and summarized,based on which the drawbacks of existing research are discussed.(2)The mathematical modeling of CRGs with agent preferences over goals is proposed.Based on the analysis of the link between agent,goal,and coalition in the model,the concepts of "actual contribution amount" and "residual resource quantity" are put forward.In addition,the successful coalition problem with the agent preferences is redefined.Moreover,the computational complexity of the new successful coalition problem is deduced.(3)A maximal successful coalition generation algorithm is presented based on "least workload" and two-dimensional binary particle swarm optimization.First,the binary particle swarm optimization is extended to two-dimensional encoding.Next,whether each agent responses to a goal is determined by the least workload that the agent should contribute to the goal.Besides,a heuristic is developed to resolve the potential resource conflicts over the scarce resources.Finally,the experimental results demonstrate the effectiveness of the proposed approaches.(4)An improved maximal successful coalition generation algorithm is presented based on "contribution sharing".Since the "least workload" reduces the chance of agents to join the coalition,which is not conducive to the search of the maximal successful coalition,the resource contribution is spread on each member in a coalition to ensure that each available agent can participate in the coalition.After that,a more simple and effective encoding repair algorithm is proposed.The comparative results show that the proposed algorithm is particularly effective in large-scale settings.更多还原