苏射雄, 胡山立, 林超峰, 郑盛福. 基于局部最优的联盟结构生成算法[J]. 计算机研究与发展, 2007, 44(2): 277-281.
 引用本文: 苏射雄, 胡山立, 林超峰, 郑盛福. 基于局部最优的联盟结构生成算法[J]. 计算机研究与发展, 2007, 44(2): 277-281.
Su Shexiong, Hu Shanli, Lin Chaofeng, Zheng Shengfu. A Coalition Generation Algorithm Based on Local Optimum[J]. Journal of Computer Research and Development, 2007, 44(2): 277-281.
 Citation: Su Shexiong, Hu Shanli, Lin Chaofeng, Zheng Shengfu. A Coalition Generation Algorithm Based on Local Optimum[J]. Journal of Computer Research and Development, 2007, 44(2): 277-281.

## A Coalition Generation Algorithm Based on Local Optimum

• 摘要: 联盟形成是多Agent系统中的一个关键问题.针对多Agent联盟数量是Agent个数指数倍的问题，给出了基于局部最优Agent联盟结构生成算法——OCS算法.基于局部最优，将Agent联盟结构图化简，并利用划分所对应的一类联盟结构的上界对Agent联盟结构图进行剪枝，极大降低了搜索空间.接着证明了OCS算法的时间复杂性为O(3\+n)，但在实验上已经接近O(23n/2).最后通过对比数据分析，表明了OCS算法的效率. OCS算法是对Rothkopf和刘惊雷等人相关工作的改进.

Abstract: Coalition formation is a key topic in multi-agent systems. To solve the problem of the number of coalition structure increasing rapidly, OCS algorithm—formation of agent coalition structure based on local optimum is given. Based on local optimum, the graph of agent coalition structure can be shirt cut and the graph of agent coalition structure is pruned by using the upper bound of coalition structures referred to the partition, which decreases the searching space. Then it is proved that the time complexity of OCS is O(3\+n), but experimentally it is already close to O(23n/2). Finally, by contrasting the data, the efficiency of the OCS is indicated. This work can be seen as the improvement of Rothkopf and Liu Jinglei's related work.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈