李少芳

(莆田学院　信息工程学院，福建莆田　351100)



与联盟值有关的联盟结构生成优化

李少芳

(莆田学院信息工程学院，福建莆田351100)

摘要：基于势结构与联盟值无关的联盟结构生成算法的研究成果,可以应用到与联盟值有关的联盟结构生成优化中。同时，在与联盟值有关的问题研究中，充分利用给定的联盟值信息进一步优化计算，提高效率。文中介绍了同势的联盟值信息提取方法，并给出应用实例，减少的搜索空间接近一半。

关键词：多Agent；联盟结构；势结构；算法优化；联盟值

联盟结构生成问题已经被证明是NP-完全的。对于n个Agent产生的搜寻空间以O(nn)和 ω(nn/2)指数增长[1-3]，通过遍历所有联盟结构来找到一个最优联盟结构是行不通的。通常在有限时间内只能有选择地搜索部分联盟结构，得到一个满足给定限界k的次优联盟结构。

与联盟值无关的联盟结构生成算法，以不同搜索单位、不同搜索路径加以区分，取得很大进展。Sandholm等的算法[1]采用对联盟结构图首先搜索L1、L2、Ln层(它们只占联盟结构图的极小部分)，可得到收益不低于最优收益1/[n/2]的联盟结构。然后再执行自上往下逐层搜索方法，任意时间停止，可以得到一个满足一定限界要求的解，但是要得到全局最优解，必须搜索完所有可能的Agent联盟结构。胡山立等的算法[4]在搜索L1、L2、Ln层后，采用隔层搜索的方法，以最少的搜索层改进Sandholm等的算法。Dang等人[5]首次提出不是以层为搜索单位的算法。搜索所有最大联盟的势不大于[n(q-1)/q]的联盟结构，可得到收益不小于最大收益1/(2q-1)的联盟结构。……