第14卷第3期 智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201804054 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180619.1422.002.html 约束条件下联盟生成研究进展 任子仪，童向荣 (姻台大学计算机与控制工程学院，山东烟台264005)】 摘要：联盟生成是在多Agent系统的研究中最为重要的挑战之一。如何对Agent进行划分使所得社会福利最 大化是当前面临的主要问题。假设每个Agt都具有理性和自利性的特性，为了追求自身的利益最大化而选 择和其他的Agεt进行联合，进而使整个系统实现利益的最大化。目前，联盟生成问题有很大的计算挑战，即 使在进行联盟的时候添加了约束条件，也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下 的联盟生成的研究进行综述，主要包括4部分：最坏情况有限界联盟生成、动态规划联盟生成求精确最优解 联盟生成求近似最优解和约束条件下联盟生成求最优解。 关键词：联盟结构；社会福利；联盟生成；约束条件；特征函数；联盟结构图：联盟博弈；动态规划 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)03-0413-10 中文引用格式：任子仪，童向荣.约束条件下联盟生成研究进展机.智能系统学报，2019,14(3)：413-422 英文引用格式：REN Ziyi,TONG Xiangrong.Research progress of constrained coalition formation.CAAI transactions on intelli- gent systems,2019,14(3:413-422. Research progress of constrained coalition formation REN Ziyi,TONG Xiangrong (School of Computer and Control Engineering,Yantai University,Yantai 264005,China) Abstract:Coalition formation is one of the most important challenges in the research of multiagent systems.Currently, our main problem is how to divide Agent to maximize the social welfare.We assume that each Agent possesses the characteristics of rationality and self-interest to maximize its own interests.An Agent integrates with another Agent, which also maximizes the interest of the whole system.At present,the coalition formation problem presents notable computational challenges.If constraints are added during the coalition process,new algorithms are needed to solve the problem more rapidly and effectively.This paper mainly summarizes the study of coalition structure generation under constraint conditions.This paper comprises four parts:the coalition structure generation with the worst case guaranteed, the use of the dynamic programming to find the exact optimal solution,the near-optimal solution after formation of the coalition structure,and the optimal solution to the constrained coalition formation. Keywords:coalition structure;social welfare;coalition formation;constraint;characteristic function;coalition structure graph;coalition game;dynamic programming 联盟生成是多Agent系统(multi--agent system, 中的其他Agent合作，共同合作活动的目的是达 MAS)研究基本问题之一a,主要将Agent进行合 到最佳的标准。当Agent通过组建联盟共同工作 作或协商，使其效用增加。Agent联盟基本上被 时，联盟结构生成就会发生。目标就是求一种 认为在MAS的框架内的一组Agent,.愿意与这组 最优的联盟结构，使得所求的社会福利最大，并 返回其值4。 收稿日期：2018-04-26.网络出版日期：2018-06-20 Agent在联盟生成时达到最优方案不一定是 基金项目：国家自然科学基金项目(61572418)：山东省科技发 展计划项目(2016GGX109004) 全局最优解，但是应该是Nash最优解6-或者次优 通信作者：童向荣.E-mail:twr@ytu.edu.cn 解，因此联盟生成主要包括以下活动：DOI: 10.11992/tis.201804054 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180619.1422.002.html 约束条件下联盟生成研究进展 任子仪，童向荣 （烟台大学 计算机与控制工程学院，山东 烟台 264005） 摘 要：联盟生成是在多 Agent 系统的研究中最为重要的挑战之一。如何对 Agent 进行划分使所得社会福利最 大化是当前面临的主要问题。假设每个 Agent 都具有理性和自利性的特性，为了追求自身的利益最大化而选 择和其他的 Agent 进行联合，进而使整个系统实现利益的最大化。目前，联盟生成问题有很大的计算挑战，即 使在进行联盟的时候添加了约束条件，也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下 的联盟生成的研究进行综述，主要包括 4 部分：最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、 联盟生成求近似最优解和约束条件下联盟生成求最优解。 关键词：联盟结构；社会福利；联盟生成；约束条件；特征函数；联盟结构图；联盟博弈；动态规划 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)03−0413−10 中文引用格式：任子仪, 童向荣. 约束条件下联盟生成研究进展[J]. 智能系统学报, 2019, 14(3): 413–422. 英文引用格式：REN Ziyi, TONG Xiangrong. Research progress of constrained coalition formation[J]. CAAI transactions on intelli￾gent systems, 2019, 14(3): 413–422. Research progress of constrained coalition formation REN Ziyi，TONG Xiangrong (School of Computer and Control Engineering, Yantai University, Yantai 264005, China) Abstract: Coalition formation is one of the most important challenges in the research of multiagent systems. Currently, our main problem is how to divide Agent to maximize the social welfare. We assume that each Agent possesses the characteristics of rationality and self-interest to maximize its own interests. An Agent integrates with another Agent, which also maximizes the interest of the whole system. At present, the coalition formation problem presents notable computational challenges. If constraints are added during the coalition process, new algorithms are needed to solve the problem more rapidly and effectively. This paper mainly summarizes the study of coalition structure generation under constraint conditions. This paper comprises four parts: the coalition structure generation with the worst case guaranteed, the use of the dynamic programming to find the exact optimal solution, the near-optimal solution after formation of the coalition structure, and the optimal solution to the constrained coalition formation. Keywords: coalition structure; social welfare; coalition formation; constraint; characteristic function; coalition structure graph; coalition game; dynamic programming 联盟生成是多 Agent 系统 (multi-agent system， MAS) 研究基本问题之一[1-2] ，主要将 Agent 进行合 作或协商，使其效用增加。Agent 联盟基本上被 认为在 MAS 的框架内的一组 Agent，愿意与这组 中的其他 Agent 合作，共同合作活动的目的是达 到最佳的标准。当 Agent 通过组建联盟共同工作 时，联盟结构生成就会发生[3]。目标就是求一种 最优的联盟结构，使得所求的社会福利最大，并 返回其值[4-5]。 Agent 在联盟生成时达到最优方案不一定是 全局最优解，但是应该是 Nash 最优解[6-7]或者次优 解，因此联盟生成主要包括以下活动： 收稿日期：2018−04−26. 网络出版日期：2018−06−20. 基金项目：国家自然科学基金项目 (61572418)；山东省科技发 展计划项目 (2016GGX109004). 通信作者：童向荣. E-mail：txr@ytu.edu.cn. 第 14 卷第 3 期 智 能 系 统 学 报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019