基于整数二部拆分的最优联盟结构求解

Optimal Coalition Structure Solving Based on the Bipartite of Integer

联盟结构是对Agent集合的一个划分,通过联盟形成联盟结构,可以使Agent之间形成有效合作,完成单个Agent所不能完成的任务。本文提出了BIDP来求最优联盟结构,该算法利用整数二部拆分来生成二部划分,并利用二部拆分的界来对搜索空间进行限界。随后把该算法与DP算法做了理论和实验分析,理论上得出BIDP所需要的空间比DP减少33.3%。实验表明,当联盟值满足均匀分布和正态分布,BIDP在21个Agent的情况下,搜索空间比DP减少35%和92%。最后对求最优联盟结构的确定式算法作了总结,即时间复杂度的上界是O(3n),下界是Ω(2n),空间复杂度是Θ(2n)。

Coalition structure is a partition of the agent set, forming a coalition structure by coalition can make agents cooperate effectively and fulfill the tasks that a single agent can not. In this paper, we propose a BIDP （Bipartite of Integer Dynamic Programming） algorithm to solve the optimal coalition structure generation, which adopts the bipartite of integer to generate bipartite partitions, and takes the bound of integer bipartite as the bound of the search space. And a theoretical analysis proves that BIDP can save 33.3% memory in any case than DP （Dynamic Programming）. An experiment analysis shows that BIDP can save 35% and 920//00 searching numbers on 21 agents when the coalition values meet the uniform distri- bution and normal distribution. Finally, the paper gives a verdict that the time complexity of the determinant algorithm to solve OCS is between Ω（2n ） and O（3n ）, and the space complexity is θ（2n ）.