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

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

一个例子上, FPLS 获得最小解的平均时间比 GRASP_impLS 和 GRASP 获得最小解的平均时间更短. 这可能是因
为在构造初始解的过程中简化了原始图且选择较大概率存在于最优解中的顶点, 使其搜索空间更小, 其次, 本文提
出的基于年龄属性, 两层格局检测策略与禁忌策略的避免循环方法、扰动策略、反馈机制, 使本文提出的算法效
率更高.

FPLS vs. GRASP_impLS X
1 000 100X
FPLS vs. GRASP
100
对比算法运行时间 (s) 10 1 X/100

0.1

0.01
0.01 0.1 1 10 100 1 000
FPLS 算法运行时间 (s)
图 3 在 4 组经典基准测试实例上的运行时间分布的比较

6 结 论

本文提出了名为 FPLS 的新型局部搜索算法, 用于求解最小弱连通支配集问题. 在初始解构造阶段, 提出了优
先选择锁定顶点的选择方法, 以简化无向连通图. 通过采用反馈机制、扰动策略、年龄属性、双层格局检测策略
及禁忌策略等综合手段有效避免了循环搜索和陷入局部最优. 这些方法能够确保算法在面对不同的实例输入时具
有较好的适应性和稳定性, 即使对于 NP 难问题也能寻找到高质量的解, 表明该算法具备良好的鲁棒性. 对于年龄
属性的设计使得算法倾向于选择长时间未改变状态的顶点进行操作, 增加了解空间探索的多样性和可能性. 同时,
扰动策略能有效地跳出局部最优解, 进一步促进了不同解的生成. 基于上述策略和特性, 设计了多重启元启发式局
部搜索算法 FPLS, 并将其与 CPLEX 求解器及其他 4 种先进的局部搜索算法进行了比较, 实验结果显示, 在多个
基准测试实例上, 提出的 FPLS 算法相比其他对比算法能找到更小的解或已知最小解, 显示出解的质量更高. 具体
而言, FPLS 算法能够找到随机 UDG 实例和 LPNMR’09 实例上已知的最小解, 在一般 UDG 实例上获得了 2 个最
小解的新上界以及 9 个平均解的新上界, 在 NDR 实例上获得了 20 个最小解的新上界和 20 个平均解的新上界. 在
求解时间方面, FPLS 算法在大部分基准测试实例上都能在较短的时间内 (平均不超过 200 s) 找到最小解, 尤其对
于规模较小的实例更是表现出高效快速的特点. 即使是对于较大规模的实例, 多数情况下也能在合理的时间内
(通常在 100 s 内) 完成求解任务. 相较于 GRASP_impLS 和 GRASP 等对比算法, FPLS 在平均运行时间上表现更
优, 说明该算法在时间效率方面有显著优势.
对于未来的研究工作, 本文提出的算法框架也能扩展到其他组合优化问题上, 例如最小加权连通支配集问
题 [26] , 广义顶点覆盖问题 [27] , 最小总支配集问题 [28] 和最小支配树问题 [29,30] . 同时, 相信在解决大规模图实例方面还
存在改进空间. 因此, 将继续探索其他策略, 以进一步改进 FPLS 算法, 并解决更多大规模图实例的问题.

References:
[1] Dunbar JE, Grossman JW, Hattingh JH, Hedetniemi ST, McRae AA. On weakly connected domination in graphs. Discrete Mathematics,
1997, 167–168: 261–269. [doi: 10.1016/S0012-365X(96)00233-6]
[2] Du HJ, Wu WL, Shan S, Kim D, Lee W. Constructing weakly connected dominating set for secure clustering in distributed sensor
network. Journal of Combinatorial Optimization, 2012, 23(2): 301–307. [doi: 10.1007/s10878-010-9358-y]
[3] Wang Y, Su R, Lv MS, Guan N. A multi-step estimation approach for optimal control strategies of interconnected systems with weakly
connected topology. Automatica, 2023, 148: 110791. [doi: 10.1016/j.automatica.2022.110791]