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

An algorithm for overlapping coalition structure generation based on differential evolution and 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 with3D 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.