Page 248 - 《软件学报》2025年第8期

李睿智 等: 局部搜索算法求解最小弱连通支配集问题 3671

(ALS) 之间进行比较时, APLS 算法在多个经典基准测试实例上均表现出更好的性能. 这表明扰动策略提高了算法
在寻找最小弱连通支配集问题上解的质量.

表 6 扰动策略有效性验证实验结果

ALS APLS
实例 |V| |E|
Best Avg Best Avg
ba_1k_30k 1 000 30 039 21 21.0 21 21.0
ba_1k_6k 1 000 5 964 80 80.0 80 80.0
c-fat200-1 200 1 534 18 18.0 18 18.0
DD_g140 560 2 710 118 118.6 118 118.9
DD_g142 288 1 290 64 64.0 64 64.0
DD_g143 414 2 088 84 84.7 83 84.7
DD_g144 288 1 514 56 56.1 56 56.5
DD_g145 404 2 320 70 70.9 71 71.1
DD_g146 327 1 506 70 70.0 69 69.9
delaunay_n11 2 048 6 127 334 337.3 333 337.1
delaunay_n12 4 096 12 264 690 693.6 683 687.2
delaunay_n13 8 192 24 547 1 403 1 407.3 1 376 1 381.8
DSJC500-5 500 125 248 5 5.0 5 5.0
er_graph_1k_6k 1 000 6 000 109 109.6 107 108.9
socfb-Haverford76 1 446 59 589 58 58.5 58 58.5
str_0 363 2 454 55 55.3 55 55.2
str_200 363 3 068 47 47.0 47 47.0
str_400 363 3 157 46 46.0 46 46.0
str_600 363 3 279 41 41.0 41 41.0
SW-1000-6-0d3-trial3 1 000 3 000 167 168.8 166 168.1
SW-100-6-0d3-trial3 100 300 16 16.0 16 16.0
t3dl_a 20 360 265 113 1 171 1 182.4 1 052 1 057.3
tube1 21 498 459 277 634 637.1 644 648.5
vibrobox 12 328 177 578 790 794.9 780 786.1
最小值 5 5.0 5 5.0
最大值 1 403 1 407.3 1 376 1 381.8
平均值 256.13 257.63 249.54 251.16
标准差 380.60 382.81 365.31 367.21
注: 加粗数值是对应算法找到的最优值

5.1.3 避免循环方法的有效性
为了验证基于年龄属性, 双层格局检测策略与禁忌策略的避免循环方法的有效性, 对 ALS 算法进行了改写,
2
得到了算法 LS_Tabu 和 CC LS_Tabu. LS_Tabu 算法和 ALS 算法的区别在于 LS_Tabu 算法仅使用基于禁忌策略
2
的方法来避免循环问题, CC LS_Tabu 算法使用基于禁忌策略和双层格局检测策略的方法来避免循环问题, 而在
ALS 算法中则结合了年龄属性, 双层格局检测策略与禁忌策略一起来减少循环问题. 具体而言, 在 ALS 算法中, 刚
加入解的顶点被放置在禁忌列表中, 以防止其被移出解, 从而避免循环问题的发生. 同时, 每个顶点都具有一个格
局值和年龄值, 在选择要加入解的顶点时, 考虑了这两个值, 若顶点的格局值为 1, 则允许将其加入解中, 否则不允
许. 在选择加入或移出解的顶点时, ALS 算法会选择具有最大 Dscore 值或最小 Nscore 值的顶点, 若存在多个满足
2
条件的顶点, 则选择年龄值最大的顶点. 通过对比 ALS、CC LS_Tabu 和 LS_Tabu 算法的求解效果, 可以评估年龄
属性和双层格局检测策略结合禁忌策略对算法性能的影响.
2
LS_Tabu、CC LS_Tabu 和 ALS 算法的实验结果如表 7 所示. 在此表中, 每列和每行的含义与表 2 中的含义
相同. 从表 7 中可以看出, 在实例“ba_1k_30k”“c-fat200-1”“DSJC500_5”和“SW-100-6-0d3-trial3”上, LS_Tabu、
2
CC LS_Tabu 和 ALS 算法可以找到相同的最小解. 在其他 18 个实例上, ALS 算法能够找到优于其他两种算法的