第3期 任子仪，等：约束条件下联盟生成研究进展 ·419· 表34个Agent配置表及具体联盟表示 Table 3 The configuration table and specific coalition representation of 4 Agents 联盟数量 配置表及具体联盟表示 1 G={4,F(G={a1,a2,a3,a4} {a1,a2h,{a3,a4H {Ha1,{a2,a3,a4} 2 G=2,21,F(G)= {a1,a3,{a2,a4} G={1,3,F(G)= {a2h,{a1,a3,a4}》 {a1,a4,{a2,a3} {a3,{a1,a2,a4》 {a4,{a1,a2,a3} {a3h,{a4,{a1,a2} {a2,{a4,{a1,a3} G=1,1,2,F(G= {a2,{a3,{a1,a4} {a1,{a4,{a2,a3} {a1,{a3,{a2,a4} {a1,{a2,{a3,a4} G={1,1,1,1,F(G={Ha1,{a2,{a3h,{a4} 5.2具体实现 中的联盟组成的不相交的联盟结构的值。 算法实现分为3个部分：1)预处理操作：2)构 ②泡含配置为1,2，…，的联盟：计算G={1,2,…,i 造和选择合适的配置：3)搜索元素。 配置的联盟结构的值。 1)预处理操作 经过上述两个操作搜索联盟结构，可以搜索 预处理的主要目的是计算CL,的最大值max, 空间的一部分（随着n的增加而减小）。表4表示 和平均值avg,并返回计算值，同时将当前搜索社 的是8个Agent搜索结果，其中配置G={8, 会福利最大的联盟结构返回记为CS。此过程 G={4,4},G=3,5,G=2,6,G={1,71,G={1,1,6, 中，主要进行2种操作，分别是评估互补大小和包 G=1,1,1,5},G=1,1,1,1,1,3},G={1,1,1,1,1,3}, 含配置为{1,2，…，计的联盟。 G=1,1,1,1,1,1,2,G=1,1,1,1,1,1,1,1)是在预处 ①评估互补大小：将CL,和CL,称为互补 理操作中需要将被搜索的配置。 的，如CL和CL1。在此过程中需要计算由互补 2)构造和选择合适的配置 表48个Agent配置表 Table 4 The configuration table of 8 Agents 层数 配置表 1=1 G={8) 1=2 G=4,4}G=3,5}G=2,61G={1,7} 1=3 G=2,3,3}G={2,2,4G=1,3,41G={1,2,5}G={1,1,6 1=4 G=2,2,2,2}G={1,2,2,3}G={1,1,3,3}G={1,1,2,4}G={1.1,1,5 1=5 G={1,1,2,2,2G={1,1,1,2,3}G={1,1,1,1,1,3引 1=6 G={1,1,1,1,2,2}G={1,1,1,1,1,3} 1=7 G={1,1,1,1,1,1,2} 1=8 G={1,1,1,1.1,1,1.1} 在搜索过程中，进行剪枝操作主要目的是减 1}和{1,1,1,1,1}。计算每个配置G对应于 少搜索空间。G为搜索完后找到可能存在最优联 F(G)的上界UBc和平均值Avgc。将V(CS)和 盟结构的配置。 UBcB进行比较，如果G中所有的配置都满足前 ①构造独一无二的配置：保证所有的配置的 者大于后者，那么该解即为最优解。否则，进行 集合等于所有Agent可能产生的整数分区。例 ②操作。 如，有5个Agent,.可能存在的整数分区的配置 ②选择合适的配置：搜索过程中满足AYC> 0BE≥K G为{5}，{4,1}，{3,2}，{3,1,1，{2,2,1}，{2,1,1， 则选择元素中最小的一个，否则继续进行剪枝工作。5.2 具体实现 算法实现分为 3 个部分：1) 预处理操作；2) 构 造和选择合适的配置；3) 搜索元素。 1) 预处理操作 CLs maxs avgs CS′ {1,2,· · ·,i} 预处理的主要目的是计算 的最大值 和平均值 并返回计算值，同时将当前搜索社 会福利最大的联盟结构返回记为 。此过程 中，主要进行 2 种操作，分别是评估互补大小和包 含配置为 的联盟。 CLs CLn−s CL3 CL1 ①评估互补大小：将 和 称为互补 的，如 和 。在此过程中需要计算由互补 中的联盟组成的不相交的联盟结构的值。 ②包含配置为 {1,2,··· ,i} 的联盟：计算 G = {1,2,··· ,i} 配置的联盟结构的值。 G = {8} G = {4,4} G = {3,5} G = {2,6} G = {1,7} G = {1,1,6} G = {1,1,1,5} G = {1,1,1,1,1,3} G = {1,1,1,1,1,3} G = {1,1,1,1,1,1,2} G = {1,1,1,1,1,1,1,1} 经过上述两个操作搜索联盟结构，可以搜索 空间的一部分 (随着 n 的增加而减小)。表 4 表示 的 是 8 个 Agen t 搜索结果，其中配置 ， ， ， ， ， ， ， ， ， ， 是在预处 理操作中需要将被搜索的配置。 2) 构造和选择合适的配置 G ′ 在搜索过程中，进行剪枝操作主要目的是减 少搜索空间。 为搜索完后找到可能存在最优联 盟结构的配置。 ①构造独一无二的配置：保证所有的配置的 集合等于所有 Agent 可能产生的整数分区。例 如 ，有 5 个 Agent，可能存在的整数分区的配置 G 为{5}，{4, 1}，{3, 2}，{3, 1, 1}，{2, 2, 1}，{2, 1, 1, UBG AvgG V(CS′ ) UBG′β G ′ 1}和{1, 1, 1, 1, 1}。计算每个配置 G 对应于 F(G) 的上界 和平均值 。将 和 进行比较，如果 中所有的配置都满足前 者大于后者，那么该解即为最优解。否则，进行 ②操作。 AVG UB∗ G ②选择合适的配置：搜索过程中满足 ⩾ k， 则选择元素中最小的一个，否则继续进行剪枝工作。 表 3 4 个 Agent 配置表及具体联盟表示 Table 3 The configuration table and specific coalition representation of 4 Agents 联盟数量 配置表及具体联盟表示 1 G = {4},F(G) = {{a1,a2,a3,a4}} 2 G = {2,2},F(G) =    {{a1,a2},{a3,a4}} {{a1,a3},{a2,a4}} {{a1,a4},{a2,a3}} G = {1,3},F(G) =    {{a1},{a2,a3,a4}} {{a2},{a1,a3,a4}} {{a3},{a1,a2,a4}} {{a4},{a1,a2,a3}} 3 G = {1,1,2},F(G) =    {{a3},{a4},{a1,a2}} {{a2},{a4},{a1,a3}} {{a2},{a3},{a1,a4}} {{a1},{a4},{a2,a3}} {{a1},{a3},{a2,a4}} {{a1},{a2},{a3,a4}} 4 G = {1,1,1,1},F(G) = {{a1},{a2},{a3},{a4}} 表 4 8 个 Agent 配置表 Table 4 The configuration table of 8 Agents 层数 配置表 l = 1 G = {8} l = 2 G = {4,4} G = {3,5} G = {2,6} G = {1,7} l = 3 G = {2,3,3} G = {2,2,4} G = {1,3,4} G = {1,2,5} G = {1,1,6} l = 4 G = {2,2,2,2} G = {1,2,2,3} G = {1,1,3,3} G = {1,1,2,4} G = {1,1,1,5} l = 5 G = {1,1,2,2,2} G = {1,1,1,2,3} G = {1,1,1,1,1,3} l = 6 G = {1,1,1,1,2,2} G = {1,1,1,1,1,3} l = 7 G = {1,1,1,1,1,1,2} l = 8 G = {1,1,1,1,1,1,1,1} 第 3 期 任子仪，等：约束条件下联盟生成研究进展 ·419·