一种基于差分进化和编码修正的重叠联盟结构生成算法

An algorithm for overlapping coalition structure generation based on differential evolution and encoding repairs

中文关键词  多智能体系统  重叠联盟  资源冲突  差分进化  编码修正

英文关键词  multi-agent systems  overlapping coalitions  resource conflicts  differential evolution  encoding repairs

中文摘要

      重叠联盟结构生成是人工智能和多智能体系统领域中的一个难点问题. 在重叠联盟中, 一个智能体可以同 时参与多个不同的任务求解联盟. 然而, 由于每个智能体拥有的资源有限, 不同任务求解联盟之间的资源竞争会带 来潜在的资源冲突. 针对这一问题, 本文将传统的差分进化扩充到三维整数编码, 编码中的每一个元素代表某智能 体在某种资源上对某任务的实际贡献量. 此外, 设计了相应的编码修正策略以评估和解决编码中可能存在的资源 冲突. 最后, 与相关已有方法进行了对比实验分析. 实验结果表明, 本文所提算法可以在较短的编码修正时间内获 得更好的联盟结构值

英文摘要

      Overlapping coalition structure generation (OCSG) is a hard topic in the fields of artificial intelligence and multi-agent systems. In overlapping coalitions, an agent may join in different task-oriented coalitions at the same time. Unfortunately, each agent’s resources are limited, and thus there may exist potential resource conflicts over the scare resources among different cooperative coalitions. To tackle such situations, first of all, this paper improves the traditional differential evolution with 3D integer encoding, in which each element represents the actual contribution amount of one type of resource of an agent to a task. Next, the corresponding encoding-repair strategy is presented to check and resolve the possible resource conflicts in each encoding. Finally, we compare the proposed algorithm with the existing approaches to OCSG. The empirical results show that the proposed algorithm can obtain a better coalition structure value within a shorter repair time.