给定限界的势结构分组与联盟结构生成

联盟形成是多Agent系统中的一个关键问题,寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.当实际应用提出最坏情况下的具体限界要求时,如何通过进一步的最小搜索找到一个能保证在最坏情况下其联盟结构值与最优的联盟结构值相距在一个给定的限界内的联盟结构,是个长期以来值得研究而又尚未解决的问题.文中深刻分析了不同的分组方法对需要搜索的势结构数的影响,针对给定限界,在最坏情况下提出一种新的分组方法和一个新的联盟结构生成算法,使需要搜索的势结构数和联盟结构数比已有的算法都大大减少.

基于势结构的给定限界的联盟结构生成算法

联盟结构生成是多agent系统中的一个关键问题。Sandholm等人证明了要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的,如何进一步搜索是一个长期以来未能解决的问题。当实际应用提出最坏情况的具体限界要求时,如何通过部分的搜索达到这个限界?胡山立和石纯一给出了一种以层为单位的最优搜索算法,Dang等人和苏射雄等人给出了以势结构为单位的联盟结构生成算法。新算法MCCS提出在搜索最底两层及顶层后,搜索势结构集合MCCS(n,k)对应的联盟结构,以更少的势结构达到给定限界k。实验表明,在已有的算法中其所搜索的势结构最少,具有一定的理论和实践意义。

给定限界势结构生成算法的改进

寻求最优联盟结构是NP-完全的,建立限界k=n/2的最小搜索是搜索联盟结构图的最底二层及顶层,在最小搜索之后,不同算法采用不同的搜索单位和路径进行有选择地部分搜索,以尽快达到给定限界值。在实际应用中,充分利用同势的两个联盟同值或值相差不大的特征,研究最优势结构生改进算法效率。文中通过分析势结构间的关系,指出了给定限界的势结构生成算法中一些可以去除的冗余搜索集合,从两个方面改进了算法,并进行了相关结果的证明。

基于联盟组合的给定限界联盟结构生成算法

通过分析联盟之间的关系,提出了基于联盟组合的给定限界联盟结构生成算法.根据给定的限界k(n)≥2,在搜索最底两层及顶层后,只要再搜索联盟组合势结构CCCS(n,k)对应的联盟结构就能达到给定的限界,并给出构造对应联盟结构的方法.