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

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

或更小的解. 对于小规模图而言, 所比较的算法也能够找到很好的解, 本文的算法在小图上的优势并不十分明显.
但在大规模图上, 本文的算法展现出了更加显著的优势.
为了更好地展示统计实验结果, 本文针对 4 种启发式算法 (MA、MWCDS、GRASP、GRASP_impLS) 与
FPLS 算法在同一例子上获得的最小解进行了比较. 在图 1 中, 纵轴表示对比算法找到的最小解与 FPLS 算法找到
的最小解之间的比值, 记作 BEST (对比算法)/BEST (FPLS), 横轴表示实例序号. 其中, BEST (对比算法) 表示某个比
较算法在某个实例上的最小值. 当纵轴的值大于 1 时, 表示 FPLS 算法得到的最小解更优. 当纵轴的值为 1 时, 表
示 FPLS 算法与比较算法得到的最小解相同. 否则, 对比算法效果更好.

6
FPLS vs. GRASP_impLS
FPLS vs. GRASP
对比算法与 FPLS 算法在找到 2 最小解上的比值 4 3
FPLS vs. MA
5
FPLS vs. MWCDS

1
0 20 40 60 80 100
实例序号
图 1 在 4 组经典基准测试实例上获得的最小值的比较

从图 1 中可以观察到, FPLS 算法在整体上表现出更好的性能, 该算法得到的最小解均优于其他比较算法得到
的最小解. 这主要归因于在构造初始解阶段采用了锁定顶点的方法和反馈机制, 同时, 在局部搜索阶段通过扰动策
略和一系列避免循环问题的策略来处理循环问题. 因此, 本文提出的算法在最小解的质量方面具备显著的优势.

5.3 对运行时间的分析
图 2 显示了 FPLS 在 4 组经典基准测试实例上的运行时间. 在每个实例上运行 10 次, 并计算在每个实例上获
得最小解的平均时间. 很明显在 96 个实例上获得最小解的平均时间不超过 200 s. 对于前 60 个相对较小的实例,
算法 FPLS 可以非常快速地找到最小解. 对于规模较大的 38 个实例, FPLS 算法在大多数实例上能够在 100 s 内找
到最小解, 少数实例所需的时间大于 100 s.

300
250
算法运行时间 (s) 150
200

100
50

0
0 20 40 60 80 100
实例序号
图 2 FPLS 算法在 4 组经典基准测试实例上的运行时间

图 3 显示了 FPLS 算法与对比算法在 4 组经典基准测试实例上的运行时间分布的比较. 由于算法 MWCDS
和 MA 都没有可执行代码, 本文只比较 FPLS 与 GRASP_impLS 和 GRASP 得到最小解的运行时间. 在图 3 中, 横
轴和纵轴分别表示 FPLS 和对比算法得到最小解的平均时间. 可以看出, 大多数的图例分布在 X 的上方, 表明在同