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

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

此, 需要提出更加有效的启发式策略来求解最小弱连通支配集问题. 为此, 本文设计了一种更有效的启发式算法
FPLS (local search algorithm based on the feedback mechanism and the perturbation strategy) 来寻找最小弱连通支配
集问题的次优解或最优解. 在该算法框架中, 提出了基于锁定顶点和候选解中顶点反馈信息的初始解构造过程, 并
提出了带有年龄属性、双层格局检测策略、禁忌策略和扰动策略的局部搜索过程.
首先, 本文提出了图中锁定顶点的定义. 锁定顶点可被证明是最优解的一部分, 通过在算法初期就明确锁定这
些必选顶点, 可以直接缩小后续搜索的顶点集合, 使得算法能更集中资源在剩余顶点的优化选择上, 从而提高搜索
效率. 因此, 将锁定顶点添加到候选解中可以有效地减少搜索空间, 并且在拥有锁定顶点的基础上, 其他策略如反
馈机制、年龄属性、双层格局检测策略和禁忌策略等可以更专注于优化剩余顶点的选择, 无需再考虑这些已锁定
顶点, 简化了策略的复杂度. 在贪心构造初始解过程中, 优先将锁定顶点的加入解中, 然后根据顶点的分数和局部
搜索过程中所反馈的信息, 优先考虑那些历史上频繁出现在最优解中的顶点, 这直接提升了初始解的质量, 为后续
的局部搜索打下坚实基础.
其次, 循环问题是局部搜索算法固有的问题. 为了提高算法效率, 本文提出了一种基于年龄属性、双层格局检
测策略和禁忌策略的方法来避免循环问题. 同时, 本文提出了一个扰动策略, 当算法陷入局部最优时, 该策略可以
帮助算法有效地跳出.
最后, 本文综合运用反馈机制、年龄属性、双层格局检测策略、禁忌策略、扰动策略以及两个评分函数
Dscore 和 Nscore, 提出了一种有效的顶点选择方法和局部搜索算法. 实验结果表明, 与著名的 CPLEX 求解器、
MWCDS、MA、GRASP 和 GRASP_impLS 算法相比, 本文提出的局部搜索算法获得了更优的结果.
本文第 2 节介绍了相关概念. 第 3 节详细描述了算法的框架和相关策略的细节. 第 4 节对本文提出的算法与
其他算法在 4 组实例上的实验结果进行了对比分析. 第 5 节对实验部分进行了讨论分析. 最后, 第 6 节是本文的结论.

2 相关概念

对于一个无向连通图 G(V, E), 其中 V = {v 1 , v 2 , v 3 ,…, v n }表示图 G 的顶点集, E = {e 1 , e 2 , e 3 ,…, e m }表示图 G 的
边集. N(v) 表示顶点 v 的邻居集合但不包括顶点 v, 记为 N(v) = {u ∈ V | {u, v} ∈ E}. d(v) = |N (v)|表示 v 的度. N[v]
表示顶点 v 的邻居集合并且包含顶点 v, 记为 N[v] = N(v) ∪ {v}. N[D] 表示 D 的邻居集合并且包含集合 D, 记为
∪
= v∈D N [v]. 假设 u 和 v 是图中的两个顶点, 他们之间的最短路径记为 hop(u, v). 顶点 v 的 i 跳邻居记为 N i (v)
N[D]
= {u | 1 ⩽ hop(u, v) ⩽ i}, 并且 N i [v] = N i (v) ∪ {v}. 当 i = 1 时, N i (v) = N(v), N i [v] = N[v]. 下面, 给出本文中将会提到
的一些基本定义.
定义 1 (支配集). 给定一个无向图 G(V, E), 若顶点子集 D ⊆ V 使得 V \ D 中的每一个顶点都至少与 D 中的一
个顶点相邻, 则 D 是一个支配集.
定义 2 (连通支配集). 给定一个无向连通图 G(V, E), 若顶点子集 D ⊆ V 是一个支配集, 并且 D 中的任意两个
顶点之间存在一条路径, 且该路径上的顶点都在 D 中, 则集合 D 是一个连通支配集.
定义 3 (弱诱导子图). 给定一个无向连通图 G(V, E) 和一个顶点子集 D ⊆ V, 子图 WIS G (D) = (N[D], E ∩ (D ×
N[D])) 被称为基于 D 的弱诱导子图, 其中 N[D] 包含集合 D 及 D 中顶点的邻居顶点, 即 N[D] = ∪ v∈D N [v].
定义 4 (弱连通支配集). 给定一个无向连通图 G(V, E), 若顶点子集 D ⊆ V 是一个支配集, 并且弱诱导子图
WIS G (D) 是连通的, 则集合 D 是一个弱连通支配集.
定义 5 (最小弱连通支配集问题). 给定一个无向连通图 G(V, E), 图 G 的最小弱连通支配集问题是找出一个具
有最小基数的弱连通支配集.
定义 6 (锁定顶点, locked vertex). 给定一个无向连通图 G(V, E), 如果图 G 中存在一个顶点 v, 且该顶点的度
为 1, 即 d(v) = 1, 那么顶点 v 的邻居顶点 u 被定义为锁定顶点.
本文采用了两个评分函数来引导局部搜索, 这两个评分函数分别是 Dscore 和 Nscore. 对于顶点 v, Dscore(v)
表示当顶点 v 加入或移出当前候选解时, 该顶点的邻居从非支配变成支配或者从支配变成非支配的顶点数量, 如
公式 (1) 所示: