第3期 任子仪，等：约束条件下联盟生成研究进展 ·417· 间中断。如果将第1、2层搜索完成后，还存在剩 的答案。将动态规划算法应用于最优化的问题， 余时间，则可进一步地搜索缩小界限。 般分为4个步骤来完成： 定理2如果联盟结构图的第1、2层已经被 1)找出最优解的性质，并刻画其结构特征； 搜索完成并且第1层以及以上的层也被搜索完成 2)递归定义的最优值： 亿引当n=-nd且n三mad)时，k=[ 3)以自顶向下的方式计算出最优值； 是紧的，否则k=月是紧的，其中归= n-l 4)根据计算最优值所得到的信息，构造最优解。 +2 2 将动态规划算法应用于联盟中的想法是 在2-1个节点被搜索完之前，无法建立一个 Yeh在1986年首次提出的I;Rothkopf0及刘惊 界限。当搜索到2-1+1个节点时，可以建立界限 雷等B使用DP算法对求解最优联盟结构的算法 k=;搜索到2-l+1个节点的时候，界限变成 进行了改进，主要解决存在大量重复子问题计算 k=”。通过更多实验验证：当界限k变成” 的问题；Rahwan等2提出了IDP(improved dynam- 时，搜索的层数就会增加2层。当搜索的层数每 itic programming))算法；张新良等在2007年提出 增加2层，界限k前面的除数就会加1，若只多搜 了一种快速动态生成(search of coalition structure, 索一层时，没有明显效果。 SCS)算法，主要降低搜索次数。本文中，DP算法 总之，最坏情况有限界联盟结构生成算法中 主要基于定理3。 第2步具有很强的理性，即界限k能够迅速地下 定理3任意给定一个联盟C∈N,V(CS)是 降，同时该算法的收益递减，如图3所示。 最优联盟结构的社会福利，即V(CS)=maxV(CS), 则 (C),IC=1 V(CS*)= maxv(C),ma(vC)+v(C"),其他 ●， (1) 使用定理3进行动态规划，先计算只有一个 Agent的联盟，接着迭代具有2个Agent的联盟， 然后是具有3个Agent的联盟，一直迭代到具有 n个Agent的联盟。对于每个联盟C都需要使用 式(1)计算。从式(1)中易知：当1C≠1时，需要 ×104 2.5 50 7.5 10.0 搜索节点数 分别计算aC)+C和C)的值，然后将 两个值进行比较，得到具有较大社会福利的联 图3界限k作为10个Agent博奔中搜索的函数 盟。在此过程中，将所产生的暂存结果保存在变 Fig.3 Ratio bound k as a function of search in a 10-Agents 量t(C)中。 game 通过上述操作，计算出来的最大(C)就是我 界限k=n的建立与输入的Agct联盟的个 们最终要求的V(CS)。计算CS的迭代过程具体 数之间呈线性关系，这是因为输入2-1个数据，而 操作如例2所示。 当界限k=”时能够建立21个联盟结构，就是 例2令数据集N={a,a2,a3,aal,假设特征函 数为 所说的第1、2层和第n层上面的节点。 胡山立等22对算法1深入研究并进行改进， (a1)=30,v({a2)=40 v({a3)=25,v({a4)=45 给出了解决问题的一种任一时间联盟结构生成算 v{a1,a2})=50,v(《a1,a3)=60. 法和给定界限要求的联盟结构生成。Dang v{a1,aa)=80,v({a2,a3)=55 等提出不以层为单位最坏情况有限界的联盟结 v({a2,aa})=70,v({a3,aa})=80 构生成。 v({a1,a2,a3）=90,v({a1,a2,a4)=120 vla1,a3,a4l)=100,v({a2,a3,aul）=115 v({a1,a2,a3,a4)=140 4动态规划联盟生成求精确最优解 表1表示算法的具体运算过程。由表1知， 动态规划(dynamic programming,DP)算法和 tW=({a1,a2,{a3,au),能够将N分裂成{a1,2}和 分治法类似，其基本思想是将待求解的问题分解 {a,aa},而t({as,a4)={a3,a},这是因为{a1,a2}分 成若干个次级子问题，在求解的过程中，先求解 裂成{a{a2}后的社会福利比较大，{a,aa}不需 子问题，然后从子问题的解中得到要求解的问题 要进行分裂。所以CS={a,{a2,{a3,aa}o间中断。如果将第 1、2 层搜索完成后，还存在剩 余时间，则可进一步地搜索缩小界限。 l > 3 n ≡ h−l( mod h) n ≡ l( mod h) k = ⌈ n h ⌉ k = ⌊ n h ⌋ h = ⌊ n−l 2 ⌋ +2 定理 2 如果联盟结构图的第 1、2 层已经被 搜索完成并且第 1 层以及以上的层也被搜索完成 ( )，当 且 时， 是紧的，否则 是紧的，其中 。 2 n−1 2 n−1 +1 2 n−1 +1 k = 1 2 n 1 3 n 在 个节点被搜索完之前，无法建立一个 界限。当搜索到 个节点时，可以建立界限 k=n；搜索到 个节点的时候，界限变成 。通过更多实验验证：当界限 k 变成 时，搜索的层数就会增加 2 层。当搜索的层数每 增加 2 层，界限 k 前面的除数就会加 1，若只多搜 索一层时，没有明显效果。 总之，最坏情况有限界联盟结构生成算法中 第 2 步具有很强的理性，即界限 k 能够迅速地下 降，同时该算法的收益递减，如图 3 所示。 k = 1 2 n 2 n−1 k = 1 2 n 2 n−1 界限 的建立与输入的 Agent 联盟的个 数之间呈线性关系，这是因为输入 个数据，而 当界限 时能够建立 个联盟结构，就是 所说的第 1、2 层和第 n 层上面的节点。 胡山立等[27-28]对算法 1 深入研究并进行改进， 给出了解决问题的一种任一时间联盟结构生成算 法和给定界限要求的联盟结构生成。 Dang 等 [29]提出不以层为单位最坏情况有限界的联盟结 构生成。 4 动态规划联盟生成求精确最优解 动态规划 (dynamic programming，DP) 算法和 分治法类似，其基本思想是将待求解的问题分解 成若干个次级子问题，在求解的过程中，先求解 子问题，然后从子问题的解中得到要求解的问题 的答案。将动态规划算法应用于最优化的问题， 一般分为 4 个步骤来完成： 1) 找出最优解的性质，并刻画其结构特征； 2) 递归定义的最优值； 3) 以自顶向下的方式计算出最优值； 4) 根据计算最优值所得到的信息，构造最优解。 将动态规划算法应用于联盟中的想法 是 Yeh 在 1986 年首次提出的[16] ；Rothkopf[30]及刘惊 雷等[31]使用 DP 算法对求解最优联盟结构的算法 进行了改进，主要解决存在大量重复子问题计算 的问题；Rahwan 等 [32]提出了 IDP(improved dynam￾itic programming) 算法；张新良等[33]在 2007 年提出 了一种快速动态生成 (search of coalition structure, SCS) 算法，主要降低搜索次数。本文中，DP 算法 主要基于定理 3。 C ∈ N V(CS∗ ) V(CS∗ ) = max CS ∈Πn V(CS) 定理 3 任意给定一个联盟 ， 是 最优联盟结构的社会福利，即 ， 则 V(CS∗ ) =    v(C), |C| = 1 max{v(C), max {C′ ,C′′}∈ΠN (v(C ′ )+v(C ′′)}, 其他 (1) |C| , 1 max {C′ ,C′′}∈ΠN v(C ′ )+v(C ′′) v(C) t(C) 使用定理 3 进行动态规划，先计算只有一个 Agent 的联盟，接着迭代具有 2 个 Agent 的联盟， 然后是具有 3 个 Agent 的联盟，一直迭代到具有 n 个 Agent 的联盟。对于每个联盟 C 都需要使用 式 (1) 计算。从式 (1) 中易知：当 时，需要 分别计算 和 的值，然后将 两个值进行比较，得到具有较大社会福利的联 盟。在此过程中，将所产生的暂存结果保存在变 量 中。 v(C) V(CS∗ ) CS∗ 通过上述操作，计算出来的最大 就是我 们最终要求的 。计算 的迭代过程具体 操作如例 2 所示。 例 2 令数据集 N = {a1,a2,a3,a4} ，假设特征函 数为 v({a1}) = 30, v({a2}) = 40, v({a3}) = 25, v({a4}) = 45, v({a1 ,a2}) = 50, v({a1 ,a3}) = 60, v({a1 ,a4}) = 80, v({a2 ,a3}) = 55, v({a2,a4}) = 70, v({a3,a4}) = 80, v({a1,a2,a3}) = 90, v({a1,a2,a4}) = 120 v({a1,a3,a4}) = 100, v({a2,a3,a4}) = 115, v({a1,a2,a3,a4}) = 140 t(N) = ({a1,a2},{a3,a4}) {a1,a2} {a3,a4} t({a3,a4}) = {{a3,a4}} {a1,a2} {a1}、{a2} {a3,a4} CS∗ = {{a1},{a2},{a3,a4}} 表 1 表示算法的具体运算过程。由表 1 知， ，能够将 N 分裂成 和 ，而 ，这是因为 分 裂成 后的社会福利比较大， 不需 要进行分裂。所以 。 5.0 10.0 ×10 1 4 3 5 7 9 k 搜索节点数 2.5 7.5 图 3 界限 k 作为 10 个 Agent 博弈中搜索的函数 Fig. 3 Ratio bound k as a function of search in a 10-Agents game 第 3 期 任子仪，等：约束条件下联盟生成研究进展 ·417·