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

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

Dscore 值, 则选择一个 age 值最大的顶点.
移出顶点规则 1: 设置固定概率 wp, 随机产生一个概率 p, 若 p < wp, 选择一个 Dscore 值最大的顶点, 若 p ≥ wp,
选择一个 Nscore 值最小的顶点, 如果有多个满足条件, 则选择一个 age 值最大的顶点, 但该顶点不能是锁定顶点.
移出顶点规则 2: 此选择规则与移出顶点规则 1 相同, 但所选的顶点不是锁定顶点, 且不在禁忌列表中.

3.6 基于反馈机制和扰动策略的局部搜索算法

3.6.1 FPLS 算法框架
该算法是一种多启动元启发式算法, 它一共包括两个过程: 基于锁定顶点和反馈机制的初始候选解构建过程
(an initial construction procedure based on the locked vertex and the feedback mechanism, LF_InitConstruct) 和基于的
反馈机制和扰动策略的局部搜索过程 (a local search procedure based on the feedback mechanism and the perturbation
strategy, FPLS_Search), 共同求解最小弱连通支配集问题. 当 FPLS_Search 过程达到最大迭代次数时, 算法重新启
动并从一个新的初始候选解开始搜索, 直到达到算法终止条件, 算法停止. 在算法 1 中描述了 FPLS 算法的框架.
算法 1. FPLS 算法.

输入: 无向图 G(V, E), 算法最大的内外层迭代次数 ITER_NUM 和 OUTTER_STEP, 算法最长运行时间 cutoff;
输出: 全局最优的弱连通支配集 W*.
1. 图中每个顶点的 add_frequency[v] 值初始化为 0;
2. 外层循环次数 step 初始化为 0;
3. W* ← V;
4. WHILE step < OUTTER_STEP 且 elapsed time < cutoff DO
5. IF step%2 == 0 THEN
6. 图中每个顶点的 add_frequency[v] 值初始化为 0;
7. W ← LF_InitConstruct( ); /*构建初始解*/
8. W' ← FPLS_Search(W, ITER_NUM); /*优化初始解*/
9. IF |W'| < |W*| THEN
10. W* ← W'; /*更新最小解*/
11. step++;
12. RETURN W*;
如算法 1 所示, 第 1 行中, 每个顶点的 add_frequency 值初始化为 0, 表示每个顶点在局部搜索过程中还未被
添加到候选解中. 第 2 行中, 循环步数被初始化为 0. 主循环从第 4–11 行, 在满足运行时间小于截止时间或循环次
数小于最大迭代次数 OUTTER_STEP 的循环条件下执行伪代码. 在第 5/6 行中, 对每个顶点的 add_frequency
进行初始化, 表示每反馈一次顶点信息, add_frequency 就要被初始化一次. 第 7 行调用函数使用贪心策略构造初
始解, 第 8 行调用函数对初始解进行优化. 在第 9/10 行中, 当找到更好的解时, 当前解会被更新为最小解, 并且在
第 12 行返回所找到的最小解.
3.6.2 LF_InitConstruct 过程
初始解的质量直接影响到局部搜索算法改进的结果. 为得到较高质量的初始解, 本文提出了名为 LF_
InitConstruct 的初始构造过程, 它基于锁定顶点和顶点的反馈信息. 在该过程中, 采用贪心策略来构造初始解, 利用
顶点的 Dscore 值和上一轮迭代反馈的信息 (顶点加入候选解的频率) 来指导如何选择顶点. 在此过程中, 如果一个
顶点满足锁定顶点的属性, 则该点将被优先添加到候选解中. 原因在于, 如果图上的度为 1 的顶点的邻居 (锁定顶
点) 不添加到解中, 那么度为 1 的顶点及其第 2 层邻居必须在解中, 这样才能保证候选解的弱连通性, 但会导致候
选解中顶点过多. 但是如果度为 1 的顶点的邻居 (锁定顶点) 在解中, 那么度为 1 的顶点和它的第 2 层邻居就可以
不在候选解中, 这样候选解中的顶点数相对较少. 因此, 认为度为 1 的顶点的邻居 (锁定顶点) 加入候选解中, 在算