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

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

法后续的执行过程中可以不用关注这些度为 1 的顶点, 锁定顶点及其邻居顶点. 这样的做法可以有效地减少局部
搜索阶段的搜索空间, 从而有利于算法更快地找到更优的解. 具体地, LF_InitConstruct 过程在算法 2 中得到了详
细描述.
算法 2. LF_InitConstruct 过程.

输入: 无向连通图 G(V, E);
输出: 初始的弱连通支配集 W.
1. 每个顶点 Dscore(v) 值初始化为|N[v]|;
2. 图中每个顶点的 ConfChange[v] 值初始化为 1;
3. 图中每个顶点的 age[v] 值初始化为 0;
4. W ← ∅;
5. 根据添加顶点规则 2 从所有顶点中挑选一个顶点 w;
6. W ← W ∪ {w};
7. 顶点 w 的年龄值 age[w] 初始化为 1, 其余顶点 v 的年龄值 age[v] 加 1;
8. WHILE 当前解 W 不是一个弱连通支配集 THEN
9. IF 当前解 W 的 2 层邻居内存在一个顶点 v 为锁定顶点 THEN
10. w ← v;
11. ELSE
12. 根据添加顶点规则 1 从当前解 W 的 2 层邻居中挑选一个顶点 w;
13. W ← W ∪ {w};
14. 根据年龄更新规则 2 更新顶点 w 的年龄值 age[w] 为 1, 其余顶点 v 的年龄值 age[v] 加 1;
15. RETURN W;
在算法 2 的第 1 行中, 将每个顶点的 Dscore(v) 值初始化为其度数加 1. 在第 2 行中, 每个顶点的 ConfChange
值初始化为 1, 表示每个顶点都可以被添加到候选解中. 第 3 行中, 每个顶点的 age 值被初始化为 0, 表示每个顶点
都没有被添加到候选解中. 在第 4 行中, 将当前的候选解 W 设置为空集. 然后, 在第 5 行中, 为了打破随机性, 根据
添加顶点规则 2, 从顶点集 V 中选择具有最大 Dscore 值的初始顶点. 接着, 在第 6/7 行中, 选定的顶点 w 被添加到
集合 W 中, 并使用年龄更新规则 2 对每个顶点的年龄值 age 进行更新. 接下来, 该算法逐个将顶点添加到候选解
中, 直到候选解成为一个可行解 (第 8–14 行). 在此阶段, 如果 N 2 (W) 中包含一个锁定顶点, 则选择该顶点 (第
9/10 行); 否则, 选择 N 2 (W) 中具有最大 Dscore 值的顶点. 如果存在多个顶点具有相等的 Dscore 值, 则选择 add_frequency
值最大的顶点 (第 12 行). 在第 13/14 行中, 将选定的顶点 w 添加到候选解 W 中, 并根据年龄更新规则 2 更新每个
顶点的年龄值 age. 最终, 在第 15 行中, 当当前解 W 成为弱连通支配集时, 跳出循环并返回初始解 W.

3.6.3 FPLS_Search 过程
根据算法 1, 在 LF_InitConstruct 过程中构造了初始解后, 需要局部搜索过程 FPLS_Search 中对该初始解进行
优化, 以得到一个规模更小的弱连通支配集. 为了避免循环问题, 本文结合了年龄属性、双层格局检测策略和禁忌
策略, 并使用扰动策略使得当前候选解跳出局部最优. 在 FPLS_Search 过程中, 若连续 Noimprovestep 次迭代候选
解的质量没有优化, 则认为当前解陷入到了局部最优, 执行扰动策略. 根据实验测得, Noimprovestep 值设为 50. 此
外, 本文还引入了反馈机制, 以便在重启算法的新一轮 LF_InitConstruct 过程中选择大概率在最优解中的顶点, 从
而获得质量更高的初始解.
在移除顶点的过程中, 如果只选择一个 Dscore 值最大的顶点, 就会增加 FPLS_Search 过程所面临的循环问题.
因此, 本文引入了 Nscore 函数, 它增加了所选顶点的多样性, 从而可以选择在前一个循环中未被选择为候选顶点
的顶点. 同时, 本文引入了一个概率参数“wp”, 用来判断是选择一个最大的 Dscore 值或最小的 Nscore 值的顶点.