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

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

36. 根据格局更新规则 2 更新顶点 w 的二层邻居内所有顶点 v 的格局值 ConfChange;
37. add_frequency[w]++;
38. 将顶点 w 添加到 tabu 列表中;
39. it++;
40. RETURN W’;

在算法 3 的描述中, 第 1–3 行将局部最优解初始化为当前解, 算法迭代步数和当前候选解的质量没有改善的迭
代步数都初始化为 1. 外层循环从第 4–40 行. 在第 6–10 行中, 当当前候选解 W 为弱连通支配集时, 将 W 与局部最
优解 W'进行比较. 如果 W 优于 W', 则将 W'更新为 W, 并将最小解没有改善的迭代次数 Noimprovestep 值初始化为
1; 否则, 将 Noimprovestep 值加 1. 然后, 在第 11/12 行中, 算法逐个从候选解中删除顶点, 直到候选解变得不可行.
在这个阶段, 算法根据移出顶点规则 1 从候选解中选择顶点. 具体来说, 随机生成一个概率 p, 如果 p 小于 wp, 则从
候选解中选择一个具有最大 Dscore 值的顶点; 否则, 从候选者中选择一个具有最小 Nscore 值的顶点. 如果有多个
顶点满足该条件, 则选择一个年龄值 age 最大的顶点, 但不能是锁定顶点. 接下来, 根据格局更新规则 3, 更新每个
顶点 u 在 N 2 (w) 中的 ConfChange[u] 值 (第 13 行), 根据年龄更新规则 3 更新顶点 w 的年龄值 age[w] 为 1 (第
14 行). 在第 15/16 行中, 当 W 不是弱连通支配集时, 根据移出顶点规则 2 从候选解中删除一个顶点. 具体而言, 随
机生成一个概率 p, 如果 p 小于 wp, 则选择一个具有最大 Dscore 值的顶点; 否则, 选择一个具有最小 Nscore 值的顶
点. 如果有多个顶点满足该条件, 则选择一个年龄值 age 最大的顶点, 但该顶点不能是锁定顶点, 并且不能在禁忌列
表中. 然后根据格局更新规则 3, 更新每个顶点 u 在 N 2 (w) 中的 ConfChange[u] 值 (第 17 行), 根据年龄更新规则 3
更新顶点 w 的年龄值 age[w] 为 1 (第 18 行). 在第 19–22 行中, 当当前候选解的质量没有改善的迭代步数达到 50
步时, 根据移出顶点规则 2 从候选解中删除 0.01×|V|个顶点. 接着根据格局更新规则 3, 更新每个顶点 u 在 N 2 (w) 中
的 ConfChange[u] 值 (第 23 行), 根据年龄更新规则 3 更新顶点 w 的年龄值 age[w] 为 1 (第 24 行). 在第 25–27 行
中, 当存在没有被支配的顶点时, 根据添加顶点规则 2, 算法从顶点集合 N 2 (W) 中随机选择一个具有最大 Dscore 值
的顶点. 然后将该顶点添加到候选解中, 并根据年龄更新规则 2 和格局更新规则 2 (第 28/29 行), 更新每个顶点的年
龄值 age 以及每个顶点 u 在 N 2 (w) 中的 ConfChange[u] 值. 在第 30 行中, add_frequency[w] 值加 1. 接下来, 在第 32
行中, 更新集合 SWCE. 在第 31–38 行中, 当 W 不是弱连通支配集时, 算法将逐一添加一些顶点到候选解中, 直到候
选解成为一个可行的弱连通支配集. 在这个阶段, 算法根据添加顶点规则 3 从集合 SWCE 中选择顶点. 具体而言,
选择一个具有最大 Dscore 值的顶点. 如果有几个顶点具有相同的最大值, 并且其中有一个 ConfChange 值等于 1 的
顶点, 则选择一个年龄值 age 最大的顶点 (第 33 行). 然后根据年龄更新规则 2 和格局更新规则 2, 更新每个顶点的
年龄值 age 以及每个顶点 u 在 N 2 (w) 中的 ConfChange[u] 值 (第 35/36 行). 在第 37 行中, add_frequency[v] 值加 1.
然后将添加到解中的顶点添加到 tabu 列表中 (第 38 行). 最后, 在第 40 行中, 返回局部最优解 W'.

4 实验比较

本节进行多组实验来评估本文提出的算法 FPLS. 在随机 UDG 实例、LPNMR’09 实例、一般 UDG 实例和 NDR
实例上对算法进行测试. 4 组实例均由牛当当为本文提供. 将 FPLS 与 CPLEX 精确求解器和 MWCDS、MA、GRASP
及 GRASP_impLS 这 4 种最先进的算法进行比较. 接下来, 对 4 组实例、CPLEX 求解器及 4 种对比算法进行介绍.

4.1 实例介绍
随机 UDG 实例: 该组基准实例采用 Jovanovic 等人 [25] 提出的方法随机生成的, 该方法来自自组织网络聚类问
题. 该问题是最小弱连通支配集问题的重要应用场景. 该组基准实例共有 24 个, 实例的顶点数取值范围为 15–30,
规模相对较小.
LPNMR’09 实例: 该组基准实例源于第 10 届国际逻辑规划和非单调推理会议, 该组基准实例共有 9 个, 实例
的顶点数取值范围为 40–90, 规模相对较小.
一般 UDG 实例: 该组基准实例最初由 Jovanovic 等人 [25] 提出, 实例来源于自组织网络聚类问题. 该组基准实