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

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

题. 该策略的主要作用是禁止对刚刚改变状态的顶点进行再次翻转. 禁忌策略有一个重要参数, 即禁忌长度, 用于
限制在一定步数内, 刚刚改变状态的顶点不会再次被翻转. 在本文提出的算法中, 禁忌长度被设置为 1. 在每轮循
环中, 将添加到解中的顶点加入禁忌列表, 然后在下一轮的循环中, 在选择移除候选解中的顶点时, 禁止移除禁忌
列表中的顶点.

3.1.3 双层格局检测策略
顶点的格局具有重要的物理意义, 它反映了一个图中特定顶点与其邻居顶点之间关系的当前状态. 在求解最
小顶点覆盖 (MVC) 问题时, 为了避免局部搜索算法陷入循环, 即重复访问相同的候选解, Cai 等人 [22] 提出了格局
检测 (configuration checking, CC) 策略. 该策略在向候选解中添加顶点时考虑顶点的格局, 即当一个顶点 v 的格局
自上次从候选解中删除以来没有改变时, 禁止将该顶点添加到当前候选解中. 该策略是一种思想, 易于实现, 并可
以根据问题和算法的不同提出不同的格局检测策略, 格局检测策略已经被广泛应用于组合优化问题的局部搜索算
法中, 例如最小加权顶点覆盖问题 [23] 和最小可满足性问题 [24] 等.
2
在本文提出的算法中采用双层格局检测策略 (two hop configuration checking, CC ). 与原始的格局检测策略不
2
同的是, CC 策略考虑了顶点的 2 层邻居的格局. 也就是说, 传统的格局检测只考虑顶点及其直接邻居的格局状
态, 而双层格局检测扩展到考虑顶点的 2 层邻居, 即顶点的邻居的邻居. 这种扩展不仅考虑了更宽泛的影响范围,
还提升了对网络结构敏感性的把握, 帮助算法识别那些在更大范围内能引起解结构变化的顶点变动, 从而避免了
仅在局部小范围内无效的尝试. 当顶点 v 加入候选解或从候选解中移出时, 该顶点的 1 层邻居和 2 层邻居的格局
2
都会被改变为允许被加入候选解的状态. 初步测试表明, 通过考虑两层邻居的动态, CC 策略在添加或移除顶点
时, 能更准确判断对整体结构的影响, 减少不必要的扰动. 同时, 它促进了搜索过程中解的多样性, 因为对更远距离
的考虑自然引入了更多的解空间探索路径, 避免了算法过早陷入局部最优解从而可以得到令人满意的结果.
与原始的格局检测策略相同, 如果一个顶点的格局自上次从解中删除以来没有改变, 则禁止该顶点加入候选
解. 在实现中, 本文使用 ConfChange 值来表示每个顶点的格局值. 当 ConfChange[v] = 1 时, 表明顶点 v 的格局已
经改变, 可以将该顶点添加到当前候选解中. 当顶点 v 的 ConfChange[v] = 0 时, 表示顶点 v 的格局自上次从候选解
中删除以来没有发生变化, 因此不能将其添加到当前候选解中. 具体而言, ConfChange 值将根据以下规则进行初
始化和更新.
格局更新规则 1: 在算法开始时, 对于每个顶点 v ∈ V, ConfChange[v] 设置为 1.
格局更新规则 2: 当顶点 v 添加到候选解中时, 对于顶点 u ∈ N 2 (v), ConfChange[u] 设置为 1.
格局更新规则 3: 当顶点 v 被移除时, ConfChange[v] 设置为 0; 对于顶点 ∈ N 2 (v), ConfChange[u] 设置为 1.
u
3.2 候选解的弱连通元素
在局部搜索过程中, 首先会移除一些顶点, 以破坏当前候选解的结构, 从而获得不同的候选解. 这些被移除的
顶点导致当前候选解变得不再连通, 形成了几个弱连通的分量. 因此, 在局部搜索过程中, 尝试找到一些顶点, 使得
这些弱连通分量之间能够相互连通.
为了实现这一目标, 本文引用了 Niu 等人 [16] 提出的 GRASP_impLS 算法中的集合 SWCE. 集合 SWCE 包含了
当前候选解的弱连通元素. 它由每个弱连通分量的两层邻居中出现次数最多的顶点组成. 假设该候选解 W = W 1 ∪
W 2 ∪...∪ W k , 其中 W 1 , W 2 ,..., W k 是 k 个弱连通分量, SWCE = {v | sum_A (v) = max{sum_A (n) = ∑ i=1,…,k A(n, i),
n ∈ V\W}, v ∈ V\W}, 其中如果 n 出现在 N 2 (W i ) 中, A(n, i) = 1, 否则, A(n, i) = 0.

3.3 扰动策略
在运用上述策略后, 通常可以得到一些高质量的解. 然而, 这些解仍然可能受限于局部最优的问题. 在本文的
算法中, 当连续迭代后最优解的质量未能提升时, 搜索进程可能会停滞, 无法进一步优化结果. 为了帮助局部搜索
摆脱这种陷入局部最优的情况, 本文提出了一种扰动策略来解决这个问题. 这个扰动策略通过翻转一些顶点来
进行.
扰动策略通过在算法陷入局部最优时随机改变解的状态, 引入了一定程度的不确定性, 从而主动增强了算法