·420· 智能系统学报 第14卷 ③更新上边界：进行搜索的CS·是可以计算 Agent集，称为枢纽Agent。规定任意一个可行联 本身的数值或者将其自身分裂后形成联盟的最大 盟结构中不允许存在两个及其以上的枢纽Agent。 值。例如，在搜索配置为G={1,1,1,1,2,3,4}的 a,B:SHR是两个评估函数，而x,y∈R是两个实 元素时，最大值可能的组合是{1,1,3}。当求配 数，则=<D,S,a,B,x,y>是<N,v>的评估结构。 置G={1,1,1,3,3,4;的上边界时，在配置G={1,1,3} 例4给定一个联盟博弈T=<N,v>,其中N= 的上边界的基础上加上max,+max+max。以 {a1,a2,…,a}。评估结构为c=(D,{a1,a2,,B,x,y), 该方式对配置进行拆分处理，能更好地更新上 其中图D如图4所示。 边界。 3)搜索元素 搜索过程的关键在于构建联盟结构。在该算 0 法中，构建联盟结构的主要问题是，在执行时会 进行重复操作，从而形成冗余和无效的联盟结构。 ①避免重叠的联盟结构：重叠的联盟结构 是{a1,a2{a2,as》这样。使用快速索引技术进行 图47个Agent交互图 解决。 Fig.4 The interactive graph of 7 Agents ②避免冗余的联盟结构：冗余的联盟结构是 图4中C1={a1,al,C2={a4,a5,a6}是2个可行 {a1,l,{a3,a》和{Ha,aa,{a1,a2》这样。在进行组 联盟，而{a1,2}和{as,a}是2个不可行联盟，前者 合的过程中以升序排列，并且使用联盟中最小的 是因为联盟中2个Agent都是枢纽Agent,,后者则 元素C作为关键点，以确定已经存在的联盟。 是因为联盟不是图4的子图。 ③正确性证明：通过上述步骤可以生成唯一 如果C是可行联盟结构，将函数α、B和实数 的和有效的解决方案。 x、y通过式(2)定义成评估函数v的映射val,。 6约束条件下联盟生成求最优解 vale(v,C)= a(a)xv(C)+B(ai),(ai)=cns xxv(C)+y,cns=0 (2) Frankovi等B将关注点从所有Agent之间的 例5假设图4中，估值函数为”，C是一个 联系转移到只关注给定Agent之间建立最优的联 可行联盟，则v(C)被定义为由C所覆盖的边的权 盟。Greco等1经过进一步研究，提出了一种新的 值的总和，即 联盟结构生成方式一约束联盟结构，即在生成 C)=∑eeE,eeCw 联盟的过程对联盟添加约束。 C1={a,as1,C2={as,a6,a}的估值为 6.1约束联盟的基础 v(C1)=w(a1,a3)=1 在进行约束联盟结构形成的过程中，主要是 vC2)=w(a,a6,a)=w(as,a6)+w(a6,)=1+1=2 定义在一对<N,v>上的，<N,v>称为联盟博弈，其 假设函数、B分别为a:{a1,a2}→{1，B:{a1, 中N=(a,a2,,an)是Agent集，v是评估函数。 a2}→{0，而实数=0，=-12，则val(C)=1×v(C)+ 例3假设一个联盟博弈为<N,v>,其中 0=1,val(C2)=0×vC2)-12=-12。 N=(a1,a2,a),评估函数为 63边际贡献网上联盟生成 ({a3》=0 边际贡献网在过去的几年里收到了相当大 v({a1)=v({a2l》=v({a1,a3l)=v(《a2,a3》=1 v({a1,a2l)=v({a1,a2,a3l》=3 的关注。边际贡献网(marginal contribution net- 易知，最优联盟结构是{a,a2,a}和{a,a2,{a3, work,MC-net)是包含一系列代表Agent的布尔变 这是因为v({a1,a2》+v({al》=({a1,a2,a3)=3。 量的规则，每个规则的形式为pattern)→value,其 假设在联盟博弈<N,v>中，Agent集上定义 中pattern可以包含正面的连接或负面的连接， 一个无向图G,G称为交互图。联盟C是可行的， value是与此pattern相关的附加贡献。 当且仅当C在G的子图上是连通的。 例6给定一个联盟博弈T=<N,v>,其中 6.2约束联盟结构生成 N={a1,a2,,as},v({a1,a2l)=v({a2,a3)=v({a1,a)=2; 令T=<N,v>是联盟博弈，D=(W,E)是联盟 3ie(1,2,,5l,v({al)=0w({a1,a2,a3)=5:3Cc{a1,a2, 博弈上的一个交互图，其中图中的交点是N中的 a},vCU{a4》=vC{a)=v(C)=(CU{a,as);根 Agent,,边是节点集，设S∈W是一个可能为空的 据边际贡献网，给定规则为CS ∗ max1 +max3+max4 ③更新上边界：进行搜索的 是可以计算 本身的数值或者将其自身分裂后形成联盟的最大 值。例如，在搜索配置为 G={1, 1, 1, 1, 2, 3, 4}的 元素时，最大值可能的组合是{1, 1, 3}。当求配 置 G={1, 1, 1, 3, 3, 4}的上边界时，在配置 G={1, 1, 3} 的上边界的基础上加上 。 以 该方式对配置进行拆分处理，能更好地更新上 边界。 3) 搜索元素 搜索过程的关键在于构建联盟结构。在该算 法中，构建联盟结构的主要问题是，在执行时会 进行重复操作，从而形成冗余和无效的联盟结构。 {{a1,a2}{a2,a3}} ①避免重叠的联盟结构：重叠的联盟结构 是 这样。使用快速索引技术[36]进行 解决。 {{a1,a2},{a3,a4}} {{a3,a4},{a1,a2}} C 1 k ②避免冗余的联盟结构：冗余的联盟结构是 和 这样。在进行组 合的过程中以升序排列，并且使用联盟中最小的 元素 作为关键点，以确定已经存在的联盟。 ③正确性证明：通过上述步骤可以生成唯一 的和有效的解决方案。 6 约束条件下联盟生成求最优解 Frankovi 等 [37]将关注点从所有 Agent 之间的 联系转移到只关注给定 Agent 之间建立最优的联 盟。Greco 等 [18]经过进一步研究，提出了一种新的 联盟结构生成方式——约束联盟结构，即在生成 联盟的过程对联盟添加约束。 6.1 约束联盟的基础 < N, v > < N, v > (a1,a2,· · ·,an) 在进行约束联盟结构形成的过程中，主要是 定义在一对 上的， 称为联盟博弈，其 中 N = 是 Agent 集，v 是评估函数。 < N, v > N = (a1,a2,a3) 例 3 假设一个联盟博弈为 ，其中 ，评估函数为 v({a3}) = 0 v({a1}) = v({a2}) = v({a1,a3}) = v({a2,a3}) = 1 v({a1,a2}) = v({a1,a2,a3}) = 3 {a1,a2,a3} {{a1,a2},{a3}} v({a1,a2})+v({a3}) = v({a1,a2,a3}) = 3 易知，最优联盟结构是 和 ， 这是因为 。 假设在联盟博弈 < N, v > 中，Agent 集上定义 一个无向图 G，G 称为交互图。联盟 C 是可行的， 当且仅当 C 在 G 的子图上是连通的。 6.2 约束联盟结构生成 Γ= < N, v > D = (N,E) S ∈ N 令 是联盟博弈， 是联盟 博弈上的一个交互图，其中图中的交点是 N 中的 Agent，边是节点集，设 是一个可能为空的 α, β : S 7→ R x, y ∈ R σ= < D,S,α, β, x, y > < N, v > Agent 集，称为枢纽 Agent。规定任意一个可行联 盟结构中不允许存在两个及其以上的枢纽 Agent。 是两个评估函数，而 是两个实 数，则 是 的评估结构。 Γ= < N, v > {a1,a2,··· ,a7} σ = (D,{a1,a2},α, β, x, y) 例 4 给定一个联盟博弈 ，其中 N = 。评估结构为 ， 其中图 D 如图 4 所示。 C1 = {a1,a3} C2 ={a4,a5,a6} {a1,a2} {a5,a7} 图 4 中 ， 是 2 个可行 联盟，而 和 是 2 个不可行联盟，前者 是因为联盟中 2 个 Agent都是枢纽 Agent，后者则 是因为联盟不是图 4 的子图。 valσ 如果 C 是可行联盟结构，将函数 α、β 和实数 x、y 通过式 (2) 定义成评估函数 v 的映射 。 valσ(v,C) = { α(ai)×v(C)+β(ai), {ai} = C ∩S x×v(C)+y, C ∩S = Ø (2) v(C) 例 5 假设图 4 中，估值函数为 v，C 是一个 可行联盟，则 被定义为由 C 所覆盖的边的权 值的总和，即 v(C) = ∑ e ∈ E, e ∈ Cwe C1 = {a1,a3},C2 = {a5,a6,a7} 的估值为 v(C1) = w(a1,a3) = 1 v(C2) = w(a5,a6,a7) = w(a5,a6)+w(a6,a7) = 1+1 = 2 α、β α : {a1,a2} → {1} β : {a1, a2} → {0} valσ(C1) = 1×v(C1) 0 = 1,valσ(C2) = 0×v(C2)−12 = −12 假设函数 分别为 ， ，而实数 x=0，y=−12，则 + 。 6.3 边际贡献网上联盟生成 {pattern} → value 边际贡献网[38]在过去的几年里收到了相当大 的关注。边际贡献网 (marginal contribution net￾work, MC-net) 是包含一系列代表 Agent 的布尔变 量的规则，每个规则的形式为 ，其 中 pattern 可以包含正面的连接或负面的连接， value 是与此 pattern 相关的附加贡献。 Γ =< N, v > N = {a1,a2,· · ·,a5} v({a1,a2})=v({a2,a3}) = v({a1,a3})=2 ∃i ∈ {1,2,· · ·,5}, v({ai}) = 0；v({a1,a2,a3}) = 5；∃C ⊆ {a1,a2 a3} v(C ∪ {a4}) = v(C ∪ {a5}) = v(C) = v(C ∪ {a4,a5}) 例 6 给定一个联盟博弈 ，其中 ， ； , ， ； 根 据边际贡献网，给定规则为 a1 a2 a3 a4 a6 a5 a7 1 2 1 2 2 1 1 1 图 4 7 个 Agent 交互图 Fig. 4 The interactive graph of 7 Agents ·420· 智 能 系 统 学 报 第 14 卷