基于局部最优的联盟结构生成算法

摘要

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