·416· 智能系统学报 第14卷 2联盟生成的复杂度 命题1表明，在联盟结构图上找到最优的联 盟结构是不可行的。所以，在进行联盟结构图的 2.1输入值的大小 搜索的时候设定一个限界。 对于具有n个Agent的数据集，会产生2n-1 对联盟结构的子集N进行搜索，目的在于寻 个非空的子集，生成2”-1个联盟，在进行运算时 找搜索中的最优联盟结构，即局部最优联盟结 需要输人2”-1个值。联盟结构生成算法的输入 构，记 值和Agent的个数之间呈指数关系。 理论上，在进行输入操作时即可排除一些不 CS=arg V(CS) 合理的联盟，或者在进行联盟结构生成的时候就 同时，为了保证设定的联盟结构在最佳范围 可以忽略一部分的输入。但是在接下来进行的操 内，即存在一个有限的但是尽可能小的值k,k被 作过程中无法保证存在单一的联盟与其他的联盟 称为搜索的解的界限，也是衡量局部最优解 进行合作之后的社会福利不是最佳社会福利，这 V(CSw)的标准。能够建立起界限的最小的k记为 V(CS) 是因为：被排除在外的联盟中可能存在比其他的 k=min),K≥vcS 联盟社会福利更大的联盟。 通常，如果没有对联盟结构进行完全搜索，设 2.2联盟结构的数量 定一个正确的界限是很难的。这是因为：在剪枝 随着联盟结构不断发展，Agent数量的增多， 的过程中虽然可以减少一些联盟结构的搜索，但 新问题也随之产生。联盟结构的个数表示为 是很难保证没有剪掉的比剪掉的具有更优性。在 立2 进行社会福利的定义的时候，令任意一个联盟C: 的值v(C)≥0，并且一个联盟结构的社会福利 其中：n代表数据集中的Agent个数；Zn,)表示具 V(CS)=∑v(C),这两点就保证了上述假设是不存 有i个联盟组成的联盟结构的个数；Zm,)满足第 2类Striling数的特征，即 在的，即在没有对联盟结构进行搜索的前提下设 Z(n,i)=iZ(n-1.)+Z(n-1,i-1) 置一个界限来缩小搜索联盟结构的数量。 式中：Zm,)=Zm,1)=1;Zn-1,)表示在现有存在 3.1建立界限 的联盟中增加一个新的Agent形成的联盟结构的 本节主要讨论如何尽可能地减少对图的搜索 个数；Zn-1,i-1)表示将一个新的Agent加入到 的前提下，建立一个界限k。 已有的联盟中，因为现在的联盟结构中只有 定理1对于界限k,可以只搜索联盟结构图 i-1个联盟被计算。有以下基本结果m2: 的最低的两级（图1中第7、5层）。在这个搜 命题1对于具有n个Agent的集合，具有 索中，界限=n,需要搜索的联盟结构节点的数量 2-1个联盟，O(n)和w2)个联盟结构（即联盟结 是2-1，这也是能够建立起界限的最小的搜索，即 构的个数的阶介于？n之间)。 nm=2-l。并且，没有其他的算法对于联盟结构 命题2寻找最优联盟结构是NP难问题。 的搜索的数量会比2-1少。 随着Agent数量的增加，联盟结构的数量也 最底层具有1个联盟结构，第二最底层中具 随之增加。经过实验的证明，当数据集中Agent 有2"-2个联盟(N中的所有子集，除掉全集和空 个数超过15时，使用穷举法列举出所有联盟结构 集)。在这一层中，每个联盟结构都有2个联盟， 是不可行的。 所以一共有2”-2)个联盟结构。只搜索最底下 3最坏情况有限界联盟结构生成 两层，一共搜索1+2-2)=2个联盟结果。 Dean和Boddy在时间依赖规划((time depend- 3.2算法描述 ent planning)的基础上提出了Anytime算法，其本 算法1最坏情况有保证联盟结构生成算法 质是一种反复求解使得结果更加精确的算法。在 1)搜索联盟结构图的最底二层； 算法的运行过程中，能够很快得到一个不精确的 2)从联盟结构图的顶层（第n层）开始，作宽 解，然后进行若干次的重复过程，经过重复后逐 度优先搜索，一直搜索到时间不允许为止或搜索 步提高解的质量，Anytime算法一个最显著的优 完整个联盟结构图； 点就是能够很好地权衡计算时间和解的质量。 3)返回迄今为止所得到的最优的联盟结构。 Sandholm等Is使用Anytime算法开创性地提出了 先前使用特征函数的方式2s2进行联盟结构 种最坏情况有限界联盟结构生成。 生成，算法1是一种任意时间算法，可以在任何时2 联盟生成的复杂度 2.1 输入值的大小 2 n −1 2 n −1 2 n −1 对于具有 n 个 Agent 的数据集，会产生 个非空的子集，生成 个联盟，在进行运算时 需要输入 个值。联盟结构生成算法的输入 值和 Agent 的个数之间呈指数关系。 理论上，在进行输入操作时即可排除一些不 合理的联盟，或者在进行联盟结构生成的时候就 可以忽略一部分的输入。但是在接下来进行的操 作过程中无法保证存在单一的联盟与其他的联盟 进行合作之后的社会福利不是最佳社会福利，这 是因为：被排除在外的联盟中可能存在比其他的 联盟社会福利更大的联盟。 2.2 联盟结构的数量 随着联盟结构不断发展，Agent 数量的增多， 新问题也随之产生。联盟结构的个数表示为 ∑N i=1 Z(n,i) Z(n,i) Z(n,i) 其中：n 代表数据集中的 Agent 个数； 表示具 有 i 个联盟组成的联盟结构的个数； 满足第 2 类 Striling 数的特征，即 Z(n,i) = iZ(n−1,i)+Z(n−1,i−1) Z(n,i) = Z(n,1) = 1 iZ(n−1,i) Z(n−1,i−1) 式中： ； 表示在现有存在 的联盟中增加一个新的 Agent 形成的联盟结构的 个数； 表示将一个新的 Agent 加入到 已有的联盟中，因为现在的联盟结构中只 有 i－1 个联盟被计算。有以下基本结果[22-24] ： 2 n−1 O(n n ) ω(n n/2 ) n 2 命题 1 对于具有 n 个 Agent 的集合，具有 个联盟， 和 个联盟结构 (即联盟结 构的个数的阶介于 ~n 之间)。 命题 2 寻找最优联盟结构是 NP 难问题。 随着 Agent 数量的增加，联盟结构的数量也 随之增加。经过实验的证明，当数据集中 Agent 个数超过 15 时，使用穷举法列举出所有联盟结构 是不可行的。 3 最坏情况有限界联盟结构生成 Dean 和 Boddy 在时间依赖规划 (time depend￾ent planning) 的基础上提出了 Anytime 算法，其本 质是一种反复求解使得结果更加精确的算法。在 算法的运行过程中，能够很快得到一个不精确的 解，然后进行若干次的重复过程，经过重复后逐 步提高解的质量，Anytime 算法一个最显著的优 点就是能够很好地权衡计算时间和解的质量。 Sandholm 等 [15]使用 Anytime 算法开创性地提出了 一种最坏情况有限界联盟结构生成。 命题 1 表明，在联盟结构图上找到最优的联 盟结构是不可行的。所以，在进行联盟结构图的 搜索的时候设定一个限界。 对联盟结构的子集 N 进行搜索，目的在于寻 找搜索中的最优联盟结构，即局部最优联盟结 构，记： CS ∗ N = argmax CS ∈N V(CS ) V(CS ∗ N ) 同时，为了保证设定的联盟结构在最佳范围 内，即存在一个有限的但是尽可能小的值 k，k 被 称为搜索的解的界限，也是衡量局部最优解 的标准。能够建立起界限的最小的 k 记为 k = min{κ}, κ ⩾ V(CS ∗ ) V(CS ∗ N ) Ci v(Ci) ⩾ 0 V(CS ) = ∑k i=1 v(Ci) 通常，如果没有对联盟结构进行完全搜索，设 定一个正确的界限是很难的。这是因为：在剪枝 的过程中虽然可以减少一些联盟结构的搜索，但 是很难保证没有剪掉的比剪掉的具有更优性。在 进行社会福利的定义的时候，令任意一个联盟 的 值 ，并且一个联盟结构的社会福利 ，这两点就保证了上述假设是不存 在的，即在没有对联盟结构进行搜索的前提下设 置一个界限来缩小搜索联盟结构的数量。 3.1 建立界限 本节主要讨论如何尽可能地减少对图的搜索 的前提下，建立一个界限 k。 Π C 1 、Π C 2 2 n−1 nmin = 2 n−1 2 n−1 定理 1 对于界限 k，可以只搜索联盟结构图 的最低的两级 (图 1 中第 层)。在这个搜 索中，界限 k=n，需要搜索的联盟结构节点的数量 是 ，这也是能够建立起界限的最小的搜索，即 。并且，没有其他的算法对于联盟结构 的搜索的数量会比 少。 2 n −2 1 2 (2n −2) 1+ 1 2 (2n −2) = 2 n−1 最底层具有 1 个联盟结构，第二最底层中具 有 个联盟 (N 中的所有子集，除掉全集和空 集)。在这一层中，每个联盟结构都有 2 个联盟， 所以一共有 个联盟结构。只搜索最底下 两层，一共搜索 个联盟结果。 3.2 算法描述 算法 1 最坏情况有保证联盟结构生成算法 1) 搜索联盟结构图的最底二层； 2) 从联盟结构图的顶层 (第 n 层) 开始，作宽 度优先搜索，一直搜索到时间不允许为止或搜索 完整个联盟结构图； 3) 返回迄今为止所得到的最优的联盟结构。 先前使用特征函数的方式[25-26]进行联盟结构 生成，算法 1 是一种任意时间算法，可以在任何时 ·416· 智 能 系 统 学 报 第 14 卷