第3期 任子仪，等：约束条件下联盟生成研究进展 ·415· CFGs是PFGs的子集，联盟C在CFGs中有 1)联盟结构图 一个精确值，但在PFGs中却存在很多值，这是因 Sandholm等提出的联盟结构图中，每个节点 为使用PFGs有不同的方法对N/C中的Agent进 代表一个联盟结构，并且将节点进行了划分，表示为 行分区。因此，在进行研究的过程中，使用 ,巧，…，，其中表示由i个联盟组成的所 C℉Gs更容易得到解决方案，提高算法的效率。 有的联盟结构的节点；边缘连接两个联盟结构， 1.3空间表示 当且仅当它们属于不同的划分，如和S:其中 在联盟结构生成问题中，通过联盟结构搜索 口中的联盟结构是由☑S,中的联盟分裂成两个联盟 得到最优联盟结构。 形成的。图1所示为具有4个Agent集联盟结构图。 {a},{a,{a,{a} a,aaa④a.a,atalalaata,ta.aaa.a,aa☑.ai.aa④ alaaa aalaa ☑a44④a4a4④aa44④a4,a4④@}a44④9 {a1,4,43a} 图14个Agent联盟结构 Fig.1 The coalition structure graph with 4 Agents 2)整数分区图 假设I∈P,定义巧∈是所有联盟结构组 在联盟结构图中，能直接看出具有ⅰ个联盟 成的子空间，其中联盟的大小受！部分的影响。例 所组成的联盟结构的情况。而Dean等2o提出的 如：份表示是由2个只有1个Agent联盟 整数分区图中，则是基于联盟结构中所包含的联 和1个有2个Agent组成的联盟形成的联盟结 盟的数量，将联盟结构中的空间划分成不相交的 构。对于这种表示一般用整数分区图来表示。整数 子空间，每个子空间是由n个整数分割表示的。 分区图也是一个无向图，其中每个节点代表一个 整数n的分区值可以通过递归的方法计算2四，用 子空间。两个节点I,∈P"是通过边连接的，当 Pm表示整数分区。例如：P=4,{1,3,{2,2,{1,1,2, 且仅当i,je1时，P=(八伍，)i+(三表示多重集 (1,1,1,1}。 的结合操作)。图2给出了有4个Agent整数分区图。 {1,1,1,1} u={{a1h,{a2,{a,{a}} {a},{az},{as,a},{az},{a},{a,a4} {1,12} {a1},{a3},aa}},{a2},a4},{a1,a3 {{a,{a,a2,a3}},{a3,{a4},{a1,a2}} , {a1,a2},{a1,a}》 a103a103 =2{2,2} {1,3} 3 {a1a4,{a1a2 4 Tr4={{a1,a2,a3,a4}} 图24个Agent整数分区图 Fig.2 The integer-partition graph representation of 4 AgentsN/C CFGs 是 PFGs 的子集，联盟 C 在 CFGs 中有 一个精确值，但在 PFGs 中却存在很多值，这是因 为使用 PFGs 有不同的方法对 中的 Agent 进 行分区。因此，在进行研究的过程中，使 用 CFGs 更容易得到解决方案，提高算法的效率。 1.3 空间表示 在联盟结构生成问题中，通过联盟结构搜索 得到最优联盟结构。 1) 联盟结构图 Π C 1 ,ΠC 2 ,· · ·,ΠC n Π C i Π C i Π C i−1 Π C i Π C i−1 Sandholm 等 [15]提出的联盟结构图中，每个节点 代表一个联盟结构，并且将节点进行了划分，表示为 ，其中 表示由 i 个联盟组成的所 有的联盟结构的节点；边缘连接两个联盟结构， 当且仅当它们属于不同的划分，如 和 ；其中 中的联盟结构是由 中的联盟分裂成两个联盟 形成的。图 1 所示为具有 4 个 Agent集联盟结构图。 2) 整数分区图 P n P 4 = {{4},{1,3},{2,2},{1,1,2}, {1,1,1,1}} 在联盟结构图中，能直接看出具有 i 个联盟 所组成的联盟结构的情况。而 Dean 等 [20]提出的 整数分区图中，则是基于联盟结构中所包含的联 盟的数量，将联盟结构中的空间划分成不相交的 子空间，每个子空间是由 n 个整数分割表示的。 整数 n 的分区值可以通过递归的方法计算[21] ，用 表示整数分区。例如： 。 I ∈ P Π C I ∈ Π C I Π {a1 ,a2 ,a3 ,a4 } {1,1,2} I,I ′ ∈ P n i, j ∈ I I ′ = (I\{i, j})Ξ{i+ j} Ξ 假设 ，定义 是所有联盟结构组 成的子空间，其中联盟的大小受 部分的影响。例 如： 表示是由 2 个只有 1 个 Agent 联盟 和 1 个有 2 个 Agent 组成的联盟形成的联盟结 构。对于这种表示一般用整数分区图来表示。整数 分区图也是一个无向图，其中每个节点代表一个 子空间。两个节点 是通过边连接的，当 且仅当 时， ( 表示多重集 的结合操作)。图 2 给出了有 4 个 Agent 整数分区图。 {a1},{a2 ,a3 ,a4} {a1 ,a2},{a3 ,a4} {a2},{a1 ,a3 ,a4} {a1 ,a3},{a2 ,a4} {a3},{a1 ,a2 ,a4} {a1 ,a4},{a2 ,a3} {a4},{a1 ,a2 ,a3} {a1},{a2},{a3 ,a4} {a1 ,a2},{a3},{a4} {a1},{a3},{a2 ,a4} {a2},{a4},{a1 ,a3} {a1},{a4},{a2 ,a3} {a2},{a3},{a1 ,a4} {a1},{a2},{a3},{a4} {a1 ,a2 ,a3 ,a4} Πc 4 Πc 3 Πc 2 Πc 1 图 1 4 个 Agent 联盟结构 Fig. 1 The coalition structure graph with 4 Agents {1,1,1,1} Πc {1,1,1,1}={{{a1},{a2},{a3},{a4}}} Πc {4}={{{a1 ,a2 ,a3 ,a4}}} {1,1,2} {2,2} {1,3} {4} { } {{a1},{a2},{a3 ,a4}},{{a2},{a3},{a1 ,a4}} {{a1},{a3},{a2 ,a4}},{{a2},{a4},{a1 ,a3}} {{a1},{a4},{a2 ,a3}},{{a3},{a4},{a1 ,a2}} =Πc {1,1,2} { } {{a1 ,a2},{a1 ,a4}}, {{a1 ,a3},{a1 ,a3}}, {{a1 ,a4},{a1 ,a2}} =Π{2,2} { } {{a1},{a2,a3 ,a4}} {{a2},{a1 ,a3 ,a4}} {{a3},{a1 ,a2 ,a4}} {{a4},{a1 ,a2 ,a3}} Πc {1,3}= 图 2 4 个 Agent 整数分区图 Fig. 2 The integer-partition graph representation of 4 Agents 第 3 期 任子仪，等：约束条件下联盟生成研究进展 ·415·