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

3672 软件学报 2025 年第 36 卷第 8 期

最小解, 在实例“DD_g140”“DD_g143”“DD_g144”“DD_g145”“delaunay_n13”“SW-1000-6-0d3-trial3”和“tube1”上,
2
2
CC LS_Tabu 算法能够找到优于 LS_Tabu 算法的最小解. 在平均解方面, ALS 算法也明显优于 LS 和 CC LS_Tabu
2
算法, CC LS_Tabu 算法也优于 LS_Tabu 算法. 因此可以得出结论, 年龄属性作为节点选择策略的一个关键组成部
分, 在解决该问题时对于提高算法收敛速度和避免循环具有积极影响. 年龄属性通过给每个顶点分配一个年龄值
来记录它在解中或不在解中的持续时间, 并据此优先选择年龄较大的顶点进行状态改变 (添加或删除). 这种策略
有助于打破搜索过程中的循环现象, 即防止算法反复尝试相同的顶点操作, 从而提高了搜索效率, 使得算法能够更
快地遍历不同的解空间区域.

表 7 避免循环策略有效性验证实验结果

2
LS_Tabu CC LS_Tabu ALS
实例 |V| |E|
Best Avg Best Avg Best Avg
ba_1k_30k 1 000 30 039 21 21.0 21 21.0 21 21.0
ba_1k_6k 1 000 5 964 81 81.9 81 81.9 80 80.0
c-fat200-1 200 1 534 18 18.0 18 18.0 18 18.0
DD_g140 560 2 710 126 126.0 121 121.9 118 118.6
DD_g142 288 1 290 66 66.9 66 66.8 64 64.0
DD_g143 414 2 088 85 86.3 84 84.8 84 84.7
DD_g144 288 1 514 57 57.1 56 56.9 56 56.1
DD_g145 404 2 320 73 73.8 71 72.0 70 70.9
DD_g146 327 1 506 73 73.7 73 73.9 70 70.0
delaunay_n11 2 048 6 127 357 358.5 357 357.5 334 337.3
delaunay_n12 4 096 12 264 747 748.9 750 750.6 690 693.6
delaunay_n13 8 192 24 547 1 484 1 485.8 1 464 1 466.1 1 403 1 407.3
DSJC500-5 500 125 248 5 5.0 5 5.0 5 5.0
er_graph_1k_6k 1 000 6 000 112 113.1 112 113.0 109 109.6
socfb-Haverford76 1 446 59 589 60 60.8 60 60.6 58 58.5
str_0 363 2 454 56 56.8 57 57.0 55 55.3
str_200 363 3 068 49 49.0 49 49.0 47 47.0
str_400 363 3 157 47 47.4 47 47.4 46 46.0
str_600 363 3 279 42 42.0 42 42.0 41 41.0
SW-1000-6-0d3-trial3 1 000 3 000 176 178.6 175 178.2 167 168.8
SW-100-6-0d3-trial3 100 300 16 16.0 16 16.0 16 16.0
t3dl_a 20 360 265 113 1 258 1 271.4 1 258 1 264.1 1 171 1 182.4
tube1 21 498 459 277 674 680.6 667 678.8 634 637.1
vibrobox 12 328 177 578 832 837.8 835 837.7 790 794.9
最小值 5 5 5 5.0 5 5.0
最大值 1 457 1 468.4 1 464 1 466.1 1 403 1 407.3
平均值 271.46 273.18 270.21 271.68 256.13 257.63
标准差 405.89 408.00 403.59 404.96 380.60 382.81
注: 加粗数值是对应算法找到的最优值

年龄得分置换节点的策略鼓励了搜索过程中更多样化的决策, 增加了跳出局部最优解的可能性, 因为较老的
顶点如果被改变, 则更可能引入新的结构信息, 引导算法向全局最优解或者更好的次优解靠近. 因此, 该策略对算
法收敛速度有正面促进作用, 尤其是在大规模、复杂网络结构的问题实例上, 能有效缩短达到满意解所需的时间,
并且提高最终找到解的质量. 实验结果显示, 结合年龄属性、禁忌策略和双层格局检测策略的局部搜索算法, 相对

于未使用这些策略的版本, 在多个基准测试实例上均表现出更快的收敛速度和更好的解质量.

5.2 对解质量的分析
根据第 4.3–4.6 节的实验结果, 在 4 组经典基准测试实例上, 本文提出的 FPLS 算法能够找到与比较算法相同