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

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

例共有 41 个, 实例的顶点数取值范围为 80–400, 规模相对较大.
NDR 实例: 该组基准实例是由在线网络数据存储库 (network data repository, NDR) 中具有 100–21 498 个顶点
的无权连通图转换而来的, 该组基准实例共有 24 个, 规模分布较广.

4.2 比较算法
CPLEX 是一种通用的混合整数规划求解器, 被广泛用于求解组合优化问题. 若给予足够的求解时间和空间,
则 CPLEX 最终一定能找到精确解. 在本文的实验中, CPLEX 的结果是由 CPLEX v12.9 [16] 求解得到.
MWCDS 是由 Ding 等人 [13] 提出的一种线性时间自稳定算法, 而 MWCDS 是一种线性时间复杂度算法.
MWCDS 对具有 n 个顶点的任意连通图使用同步守护进程在 O(n) 步骤中终止.
MA [15] 是一种求解最小弱连通支配集问题的模因算法, 它首先初始化种群, 然后通过选择、交叉、变异等操
作产生一个不可行解, 再通过 MWCDS 算法将该不可行解变成可行解, 随后通过一个简单的局部搜索过程来优化
该可行解.
GRASP [16] 是一种求解最小弱连通支配集问题的贪婪随机自适应搜索算法, 它利用平衡随机和贪婪策略构造
初始解, 然后利用简单的局部搜索对初始解进行优化.
GRASP_impLS [16] 是对 GRASP 算法的改进, 改进部分主要在局部搜索阶段, 它引用了概率参数来增加删除顶
点的多样性, 同时如果当前解从不可行到可行时, 首先从当前候选解的 2 层邻居内选择顶点使当前候选解变为支
配集, 然后从集合 SWCE 中选择顶点使当前的候选解变成一个弱连通支配集.

4.3 实验环境与参数
本文提出的 FPLS 算法用 C++编程语言实现的, 并由 GNU g++使用-O 选项进行编译. 本文的算法实验是在
一台具有 Intel(R) Core(TM) i5-11400H@2.70 GHz 和 8 GB 内存的计算机上进行的. CPLEX、MWCDS、MA、
GRASP 和 GRASP_impLS 的实验结果见文献 [16]. 对于 CPLEX 求解器, 设置了 3 600 s 的时间限制. 本文提出的
算法和其他 4 个对比算法在每个实例上都运行了 10 次, 并记录找到的最小解和平均解, 并将求解每个实例的截
止时间设置为 300 s. 为了获得更多高质量的候选解, 针对所提出的算法, 进行了多次实验, 最终确定了其中涉及
的参数. 其中, 外层迭代次数和内层迭代次数均设置为 1 000, 概率参数 wp 设置为 0.35, 扰动顶点个数设置为
0.01×|V|.

4.4 在随机 UDG 实例上的实验结果
表 1 呈现出了 CPLEX 求解器和其他算法在随机 UDG 实例上的实验结果. “Nodes”列表示 Area(N×N) 领域范
围内的顶点数量. R 和|E|列分别表示文献 [25] 中提到的半径值和实例的边数. CPLEX 求解器求解出来的结果中,
“Solu”列表示在指定的时间内求解出来的最好的解, 当求解时间超过了 3 600 s 依然没有找到一个可行解, 那么将
这个解记录为“N/A”, “Stat”列表示找到最优解的时间, 当运行时间达到 3 600 s, CPLEX 停止运行, 此种情况无法保
证找到解的最优性, 此时会被记录为“Feasible”, 这些符号定义用于表 1−表 4. 对于 MWCDS、MA、GRASP、
GRASP_impLS 和 FPLS 算法, “Best”列表示对应算法找到的最小解, “Avg”列表示 10 次运行所得到的平均解. 在
MWCDS 中, “time”列表示找到最小解所需的时间. 每个表的底部还求出了每个算法在每组实例上的“最小值”“最
大值”“平均值”和“标准差”.
从表 1 中可以看出, 对于该组的 24 个实例, CPLEX 求解器在 14 个实例上得到了最优解, 在 7 个实例上给出
了可行解, 但并未能证明其最优性, 在其余的 3 个实例上, 无法在给定的时间内找到一个可行解. 对比 5 个启发式
算法可发现, MA、GRASP_impLS 和 FPLS 能够在所有 24 个随机 UDG 实例上找到最小解. 而 MWCDS 和
GRASP 分别可以找到 13 个和 18 个最小解. 平均解方面, 本文提出的算法 FPLS 能找到更优的平均解, 除了在实
例 (100_25_25_45) 上, 在其他 23 个实例上 MA、GRASP_impLS 和 FPLS 得到的平均解相等. 而 MWCDS 和
GRASP 分别在 5 个和 18 个实例上能得到与 FPLS 相等的平均解. 总的来说, MA、GRASP_impLS 和 FPLS 在随
机 UDG 实例上的最小解和平均解均优于 MWCDS 和 GRASP 算法. 此外, MA、GRASP_impLS 和 FPLS 算法在
这组实例上的“最小值”“最大值”“平均值”和“标准差”均相等, 并且优于 MWCDS 和 GRASP 算法.