最优联盟结构生成算法中的分支限界技术

Branch-and-Bound Technique for Generation Algorithm of Optimal Coalition Structure

讨论多Agent系统中的最优联盟结构生成问题.对于联盟值以特征函数表示的情况下,提出了一种分支限界技术.该技术用联盟大小所代表的整数多个二部拆分作为当前搜索空间的多个分支,以已经求得的局部联盟值的下界和当前所得到的最优值所构造出的剪枝函数来限界.这样,若当前要搜索的一个分支——二部拆分的上界小于所构造的剪枝函数时,该二部拆分分支所对应的大量二部划分就不需进行分解,从而减少了搜索时间.该分支限界技术可整合到当前所出现的各种联盟结构生成算法中.为了测试该技术的有效性,本文将该技术应用到了Rothkopf所提出的DP算法和Rahwan等人所提出的IDP算法中.在具有21个Agent系统中,带有分支限界的BBDP(Branch Bound Dynamitic Programming)算法比不带有分支限界的DP算法可节省时间58.2%;带有分支限界的比不带有分支限界的IDP算法可节省时间17.8%.

Concerned with optimal coalition structure generation in multi-agent systems. For characteristic function game representations, we propose a branch-and bound technique, presented in the form of possible bipartite partition and bound of coalition structure value, that reduces the intractability of the coalition structure generation problem by pruning coalition structures which cannot belong to any optimal structure. It is because that the upper value of searching coalition structures which have the same size of coalition is lower than prune function. These techniques can be incorporated into many potential coalition structure generation algorithms. In order to test the approach effectiveness, we only compare the sequential application of DP （Dynamic Programming） algorithm of Rothkopf and IDP（Improved Dynamic Programming） algorithm of Rahwan both with and without the branch-and-bound technique. Following the MAS literature, we show that the proposed branch-and bound technique reduces the number of bipartite partition evaluated by a considerable amount. For example, in a system of 21 agents, in DP algorithm, fewer than 58.2% of bipartite partitions need not be evaluated when the branch-and bound technique is employed. In IDP algorithm, fewer than 17.8% of bipartite partitions need not be evaluated.