基于溢出性原理的联盟结构生成算法

Algorithm of Coalition Structure Generation Based on Externalities

联盟结构的生成问题中由于搜索空间的联盟结构数目太大,因而搜索联盟结构的最底两层建立一个最坏情况下的边界值是必要的,边界值将最优的联盟结构限制在某个限界内,通过进一步的搜索可以在任意时间内得到一个较优值。根据联盟的溢出性质,文中提出了一种新的建立边界值的方法,即对任意不相交的联盟集合计算其上下边界的值,通过搜索特定的联盟结构集合建立最坏情况下的边界值。联盟的边界值建立以后,可以在任意时间内得到一个较优值,通过搜索剩余的联盟结构集合,可以对边界值和返回的联盟结构进一步优化。在此基础上文中提出了基于溢出性质的任意时间算法。实验结果表明,采用新的方法建立边界值,使得算法的收敛速度更快,效率更高。

The search space of coalition structure graph is so big in characteristic function games that it is necessary to build a worst -case bound to bound the best coalition structure by searching the last two levels of coalition structure graph, and it can finally get a better coalition structure from it. In partition function games, one coalition may be affected by the formation of other distinct coalitions, so a new method of building the worst-case bound is proposed. Build the worst-case bound by computing the upper and lower bounds on the values of any set of coalitions and searching the set of the coalition structure. So anytime algorithm based on externalities is proposed. It is able to get a good result after building the worst-case bound, and the result could be optimized through further search. The efficiency of algorithm is improved and a satisfactory value is able to be gained at any time.