Page 398 - 《软件学报》2024年第4期

1976 软件学报 2024 年第 35 卷第 4 期

表 1 MARCO 算法和 MARCO-ABC 算法在不同时间限制下枚举 MUS 个数比较 (续)

MARCO MARCO-ABC
Instances
0.5 h 1 h 2 h 0.5 h 1 h 2 h
fdmus_b22_662 23 47 81 20 38 75
#win 6 8 14 20 21 17

表 2 MARCO-MAM 算法和 MARCO-MAM-ABC 算法在不同时间限制下枚举 MUS 个数比较

MARCO-MAM MARCO-MAM-ABC
Instances
0.5 h 1 h 2 h 0.5 h 1 h 2 h
fdmus_b14_134 181 574 1 486 179 591 1 616
fdmus_b14_141 83 194 598 82 186 587
fdmus_b14_210 78 183 611 77 191 605
fdmus_b15_291 52 109 252 52 107 247
fdmus_b15_294 44 93 208 46 96 229
fdmus_b15_304 33 53 124 35 74 120
fdmus_b15_421 142 305 689 150 308 824
fdmus_b15_463 191 420 787 185 383 769
fdmus_b17_1037 539 1 082 2 362 537 1 079 2 412
fdmus_b17_1324 77 149 290 78 116 235
fdmus_b17_1456 178 383 746 178 374 749
fdmus_b17_420 154 323 664 157 332 674
fdmus_b20_141 17 35 70 18 33 70
fdmus_b20_171 19 35 74 21 39 74
fdmus_b20_238 48 92 219 48 96 236
fdmus_b20_341 190 600 1 496 188 615 1 528
fdmus_b20_349 31 68 157 31 69 154
fdmus_b20_381 32 71 170 33 66 165
fdmus_b20_492 40 89 375 42 93 385
fdmus_b20_498 65 176 510 62 179 513
fdmus_b21_111 13 29 57 15 29 57
fdmus_b21_112 13 26 52 15 27 51
fdmus_b21_167 31 63 151 32 67 152
fdmus_b21_481 28 63 152 28 58 161
fdmus_b21_96 118 309 710 115 305 726
fdmus_b22_102 36 67 135 36 69 131
fdmus_b22_113 12 23 47 13 23 45
fdmus_b22_133 40 98 223 45 93 216
fdmus_b22_172 22 41 89 22 39 90
fdmus_b22_241 27 60 136 29 60 138
fdmus_b22_356 14 27 58 14 30 61
fdmus_b22_488 47 106 390 48 102 408
fdmus_b22_600 14 34 62 16 34 65
fdmus_b22_662 23 44 76 23 47 77
#win 8 13 12 17 17 19

从表 1 和表 2 中均可以看出, 无论是 MARCO 算法还是 MARCO-MAM 算法, 在结合了本文提出的加强剪枝
策略 ABC 后, 在绝大多数标准测试用例上的结果都有较为明显的提升, 在 3 种时间限制下, 结合本文所提出的剪
枝策略 ABC 的算法#win 值均高于未结合 ABC 的算法. 并且在 0.5 h 的时间限制下的优化效果要优于时间限制
2 h 的结果, 这是由于极大化模型导致算法从哈斯图的顶部区域逐渐向下探索, 而由于关键 MSS 自身的集合基数
大导致其位于哈斯图的第 2 顶层, 从而会在算法的早期被尽可能多地搜索出来, 而通过性质 4 可知, 每找到一个关