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

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


 |N[D\{v}]|−|N[D]|,如果v ∈ D


Dscore(v) =  (1)

 |N[D∪{v}]|−|N[D]|,否则
其中, N[D] 包括了当前候选解 D 中的顶点和它的邻居顶点, 因此 N[D] 也可以表示当前候选解 D 所支配的顶点集.
同样, |N[D\{v}]|表示集合 D\{v}所支配的顶点个数, |N[D ∪ {v}]|表示集合 D ∪ {v}所支配的顶点个数. 根据公式 (1)
可知, 当顶点 v 被加入候选解中后, Dscore(v) 为非正数, 当顶点 v 从候选解中移出后, Dscore(v) 为非负数.
对于顶点 v, Nscore(v) 则表示顶点 v 的邻居顶点集合中有多少个顶点是在候选解中, 如公式 (2) 所示:

Nscore(v) = |N(v)∩ D| (2)
Nscore(v) 可以反映出当顶点 v 被移除时, 对当前候选解可行性的影响, 即当从解中移除顶点 v 时, 其邻居顶点
集合中的在解中的顶点数量将减少 1. 因此, 当某个顶点的 Nscore 值降低至 1, 并且该顶点被移除时, 当前候选解
将变得不可行.

3 最小弱连通支配集问题的求解

在本节中, 提出了一种高效的局部搜索算法求解最小弱连通支配集问题. 该算法框架中提出了基于年龄属性、
双层格局检测策略和禁忌策略相结合的避免循环搜索方法、扰动策略和反馈机制, 以优化局部搜索过程. 关于循
环问题的详细描述请参见第 3.1 节. 在第 3.2 节中介绍从当前候选解的弱连通元素中选择要添加的顶点的方法, 该
方法能够将多个弱诱导子图转变为连通状态. 扰动策略在第 3.3 节中进行介绍, 反馈机制在第 3.4 节中进行阐述.
顶点选择方法在第 3.5 节中进行说明, 算法框架在第 3.6 节中进行介绍.

3.1 循环问题
循环问题是局部搜索算法的固有问题, 即算法往往会重复访问最近已经访问过的顶点, 这会导致计算资源的
浪费并且影响了算法的性能. 目前尚无完全解决这一问题的方法. 为了有效避免循环问题, 本文提出了年龄属性,
双层格局检测策略和禁忌策略相结合的方法, 从而改善算法性能. 年龄属性用于判断是否将顶点加入候选解或从
当前候选解中移出; 禁忌策略用于防止刚刚加入解中的顶点被立即删除; 双层格局检测策略用于选择要添加到候
选解中的顶点. 下面, 将进一步介绍这 3 种方法.

3.1.1 年龄属性
在局部搜索过程中, 为了得到一个更优质的候选解, 经常需要添加或删除一些顶点以改变当前候选解的结构.
因此, 选择哪些顶点进行添加或删除变得非常重要. 然而, 在局部搜索的过程中, 往往会无意地重复删除或加入同
一个顶点, 从而导致出现循环问题. 为了有效解决这个问题, 本文提出了一种称为年龄属性的方法. 年龄属性通过
为每个顶点赋予一个“年龄值”, 年龄值表示了一个顶点在解中或者不在解中的状态下持续的时间, 这直接指导了
顶点的选择优先级. 在选择顶点时, 会优先考虑那些年龄值较大的顶点. 这是因为, 如果一个顶点在解中, 并且该点
的年龄值越大, 那么这意味着它在解中存在的时间更长; 反之, 如果一个顶点不在解中, 并且该点的年龄值越大, 就
说明它在不在解中的状态下持续的时间更长. 因此, 基于年龄值的优先级排序可以避免顶点的状态长时间不被改
变, 这减少了重复访问相同顶点导致的循环问题, 增加了搜索过程中的新鲜度, 鼓励算法探索未充分检验的解空间
区域. 一旦年龄大的顶点的状态被改变, 很可能带来结构上的新信息, 推动算法朝向全局或更优解迈进. 这种策略
鼓励算法在搜索中不断探索新的搜索空间, 加快了算法对新解的发现. 年龄属性的实现非常简单且计算复杂度较
低. 它通过使用 age 值来表示每个顶点的年龄. 具体而言, 其值的初始化和更新规则如下.
年龄更新规则 1: 在初始化阶段, 对于每个顶点 v ∈ V, age[v] 被设置为 0.
年龄更新规则 2: 在整个算法框架中, 当一个顶点 v 添加到解中时, 对于该顶点的 age[v] ← 1, 而对于顶点 u ∈ V\
{v}, age[u] 加 1.
年龄更新规则 3: 在局部搜索阶段, 当一个顶点 v 从当前解中移出时, 对于该顶点的 ← 1.
age[v]
3.1.2 禁忌策略
禁忌策略, 又被称为 tabu 策略, 最初由 Glover [21] 提出, 并被广泛应用于各种局部搜索算法中, 旨在解决循环问