给定限界的势结构分组与联盟结构生成  

Cardinality Structure Grouping and Coalition Structure Generation with Given Required Bound

作　　者：胡山立[1] 石纯一[2] 李少芳[3] 

机构地区：[1]福州大学计算机科学与技术系,福州350108 [2]清华大学计算机科学与技术系,北京100084 [3]莆田学院电子信息工程学系,福建莆田351100

出　　处：《计算机学报》2012年第12期2618-2624,共7页Chinese Journal of Computers

基　　金：国家自然科学基金(60573076)资助~~

摘　　要：联盟形成是多Agent系统中的一个关键问题,寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.当实际应用提出最坏情况下的具体限界要求时,如何通过进一步的最小搜索找到一个能保证在最坏情况下其联盟结构值与最优的联盟结构值相距在一个给定的限界内的联盟结构,是个长期以来值得研究而又尚未解决的问题.文中深刻分析了不同的分组方法对需要搜索的势结构数的影响,针对给定限界,在最坏情况下提出一种新的分组方法和一个新的联盟结构生成算法,使需要搜索的势结构数和联盟结构数比已有的算法都大大减少.Coalition formation is a key topic in multi-agents system, however, finding the opti- mal coalition structure is NP-complete. Sandholm and Larson et al. showed that it is necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound k. When practical applications can present required real bound in the worst case, how to do a further minimal search to find a coalition structure which value can be guaran- teed to be apart from optimal coalition structure value mutually in a given bound. It is a problem that deserves to study and hasn＇t been solved for a long time. This paper analyzes the different method of grouping influence on the number of cardinality structures, and presents a new group- ing method and a new algorithm of coalition structure generation for the given bound in the worse case, decreases greatly the demanded searching the number of cardinality structure or coalition structure.

关 键 词：多AGENT系统 联盟结构 势结构 给定限界 分组 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]