联盟结构图的代数性质及应用  

Algebra Property and Application of Coalition Structure Graph

作　　者：刘惊雷[1] 张伟[1] 王玲玲[1] 

机构地区：[1]烟台大学计算机学院,烟台264005

出　　处：《模式识别与人工智能》2009年第6期841-847,共7页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.60496323);山东省教育厅科技计划项目(No.J07JYJ24)资助

摘　　要：将联盟结构的空间抽象为联盟结构图,并在该图上定义2种运算并和交,从而联盟结构图中所有顶点关于并和交构成代数结构——联盟结构格.为了简化该格性质的研究,又引入整数拆分图,并在联盟结构图和整数拆分图之间建立映射关系F,且由映射关系F诱导一个等价关系EF.这样在联盟结构图中搜索最优联盟结构时,可以利用某个联盟结构对EF产生的等价类的上界和平均值作为剪枝函数,当某个等价类的上界低于剪枝函数时,该等价类中的大量联盟结构就被剪枝掉.最后设计一种动态规划算法.实验表明它的有效性.在20个Agent时,它比原动态规划算法减少43%的搜索次数.The space of coalition structure is abstracted as a coalition structure graph, and two operators, union and intersection, are defined. Thus, all the coalition structures form an algebra structure, coalition structure lattice （CSL）. In order to simplify the study of CSL algebra property, the integer split graph is introduced, and a mapping relation F from coalition structures to integer splits and an equivalent relation EF based on F are constructed. Therefore, during searching optimal coalition structure in CSL, the current optimal value and average value are used as prune function. When the upper bound of some equivalent class is lower than the prune function, a large number of coalition structures in equivalent class are pruned. Finally, better dynamic programming （BDP） algorithm is given, and the validity of the proposed algorithm is proved by experimental analysis. Furthermore, the results indicate that BDP decreases 43% searching numbers than dynamic programming when there are 20 agents.

关 键 词：最优联盟结构 联盟结构图 整数拆分图(ISG) 联盟结构格(CSL) 等价关系 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]