QQ客服 官方微博 反馈留言

	最优联盟结构生成的研究:以层为单位搜索或计算
	胡山立 ; 石纯一 ; HU Shan-Li ; SHI Chun-Yi
	2010-07-15 ; 2010-07-15
会议名称	第一届建立和谐人机环境联合学术会议（HHME2005）论文集 ; 第一届建立和谐人机环境联合学术会议（HHME2005） ; 中国昆明 ; CNKI ; 中国计算机学会、中国图象图形学学会、ACM SIGCHI中国分会、清华大学计算机科学与技术系
关键词	联盟 联盟结构 算法 多Agent系统 coalition, coalition structure, algorithm, multi-agent system TP18
其他题名	Research on Optimal Coalition Structure Generation:the Search Taking Level as Unit or Computation
中文摘要	联盟形成已成为多Agent系统中一个非常活跃的研究领域。大部分研究集中在Agent如何通过协商来形成联盟和分配联盟的收益。另一种研究方法研究agents的最优划分,把Agents划分为若干个联盟(两两互不相交的子集),使各个联盟收益的总和最大。这就是最优联盟结构生成问题。这可以通过在联盟结构图上搜索或直接计算。文章讨论了在“一个联盟的收益与非该联盟成员的活动无关”的一般假设下,最优联盟结构生成的这两种方法。联盟形成已成为多Agent系统中一个非常活跃的研究领域。大部分研究集中在Agent如何通过协商来形成联盟和分配联盟的收益。另一种研究方法研究agents的最优划分,把Agents划分为若干个联盟(两两互不相交的子集),使各个联盟收益的总和最大。这就是最优联盟结构生成问题。这可以通过在联盟结构图上搜索或直接计算。文章讨论了在“一个联盟的收益与非该联盟成员的活动无关”的一般假设下,最优联盟结构生成的这两种方法。; Coalition formation has been a very active research area in multi-agent systems. Most of these researches concentrate on how to form a coalition and assign the revenues of the coalition through negotiation. Another researching branch is to study the optimal division of agents into coalitions (the pairwise disjoint subsets) so that the sum of the revenues of all coalitions is maximal. This is the optimal coalition structure generation problem. This problem can be solved through searching in the coalition structure graph or computing directly. This paper discusses the two approaches of generating the optimal coalition structure under the general assumption that each coalition’s revenue is independent of nonmembers’ actions. This paper introduces the coalition structure graph and character function, and then discusses some methods for searching the optimal coalition structure on the coalition structure graph based on the level as a unit. Firstly, we introduce algorithm 1: Coalition structure generation with worst case guarantees. Considering that the optimal coalition structure generation problem is NP complete, in practice, there is not any effective algorithm when it is larger than n. So algorithm 2 is proposed: An anytime coalition structure generation algorithm. This algorithm can be interrupted at anytime and the relatively optimal solution can be achieved under the worst case. Following this we discuss: if the requirement of a solution under the worst case, in other words bound, is given, how to do the searching. Then algorithm 3 is introduced: coalition structure generation with given required bound. In addition, we also discuss the problems of generating the optimal coalition structure through the method of direct computing. Using the result of optimal combination auction, algorithm 4 is proposed: the dynamic programming algorithm for optimal coalition structure generation. At last, the two methods, searching and computing, are compared. The methods and results in this paper can also be used in such problems as the optimal combination use of resource and the optimal combination auction of valuables.; 国家自然科学基金(Nos.60373079,60573076)资助
语种	中文 ; 中文
内容类型	会议论文
源URL	[http://hdl.handle.net/123456789/69955]
专题	清华大学
推荐引用方式 GB/T 7714	胡山立,石纯一,HU Shan-Li,等. 最优联盟结构生成的研究:以层为单位搜索或计算[C]. 见:第一届建立和谐人机环境联合学术会议（HHME2005）论文集, 第一届建立和谐人机环境联合学术会议（HHME2005）, 中国昆明, CNKI, 中国计算机学会、中国图象图形学学会、ACM SIGCHI中国分会、清华大学计算机科学与技术系.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。