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

将联盟结构的空间抽象为联盟结构图,并在该图上定义2种运算并和交,从而联盟结构图中所有顶点关于并和交构成代数结构--联盟结构格.为了简化该格性质的研究,又引入整数拆分图,并在联盟结构图和整数拆分图之间建立映射关系F,且由映射关系,诱导一个等价关系E_F.这样在联盟结构图中搜索最优联盟结构时,可以利用某个联盟结构对E_F产生的等价类的上界和平均值作为剪枝函数,当某个等价类的上界低于剪枝函数时,该等价类中的大量联盟结构就被剪枝掉.最后设计一种动态规划算法.实验表明它的有效性.在20个Agent时,它比原动态规划算法减少43%的搜索次数.

Algebra Property and Application of Coalition Structure Graph

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 E_F based on F are constructed. Therefore, during searching optimal coalition structure in CSL, the current optimal value and average value axe 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.