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

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

20. if Noimprove > T p then
21. Noimprove ← 0
22. S ← Perturb(S)
23. return S best
IRLTS 算法搜索过程与第 2 节 RLTS 算法的搜索过程相同, 只是在选择邻居解时采用的搜索策略存在差异,
体现在算法 5 的第 8 行和第 12 行. RLTS 算法在解空间 N 1 和 N 2 中选择最优邻居解时是通过遍历搜索的方法, 在
面对大规模测试用例造成的巨大的解空间时, 该方法存在单次迭代过于耗费时间的缺陷. 为此在 IRLTS 的局部搜
索过程 (算法 5) 中, 我们利用 TSBMS 策略替代了遍历搜索的方法 (第 8 行和第 12 行). 由于 TSBMS 策略可以根
据解空间的大小采用不同的策略选择最优邻居解, 因此 TSBMS 策略不仅大大提高了 RLTS 算法在处理大规模数
据时的表现, 同时也保持了 RLTS 算法在面对小规模数据时的优秀表现.

3.4 局部搜索算法
对于启发式算法的分类, 学术界存在多种不同的分类标准. 从搜索的对象, 也就是解的数量这个角度来划分,
启发式算法通常可以被划分为基于种群的启发式算法和基于单一解的启发式算法. 遗传算法、粒子群算法等以多
个个体的集合为起点, 搜索过程作用在一个种群上的算法属于基于种群的启发式算法. 在搜索过程中, 算法始终只
作用在一个解上, 这种算法属于基于单一解的启发式算法, 本文提出的 IRLTS 局部搜索算法属于基于单一解的启
发式算法这一类别.
不同于基于种群的启发式算法具有固定的搜索范式, 如遗传算法的父代选择、交叉变异, 粒子群算法的演化
公式等, 局部搜索算法的设计具有较高的灵活性, 研究者通常针对问题特性来设计与问题契合度较高的特定局部
搜索算法. 此外, 局部搜索算法的实现也较为简单, 这也加速了算法的推广与使用. 在近几年的现实应用方面, 局部
搜索算法在处理一些大规模复杂问题上取得出色的求解表现, 例如支配集问题 [22] , 调度问题 [23] , 顶点覆盖问题 [24]
等. 迅速发展的局部搜索算法在运筹学、统计学等多个学科发挥着突出的作用.

4 实验分析

第 4.1 节, 采用 3 个当前表现最优的启发式算法作为 IRLTS 算法的对比算法, 74 组经典的图测试用例被用来
评估 IRLTS 算法的有效性. 第 4.2 节, 通过实验分析了一度顶点规则和 TSBMS 策略的有效性. 第 4.3 节, 分析了
TSBMS 策略中的关键参数对 IRLTS 算法的影响.

4.1 IRLTS 算法与当前最优启发式算法对比
当前求解 MLCP 问题表现最好的 3 个算法分别是 RLTS 算法 [1] , GVNS 算法 [12] , MS-GVNS 算法 [12] , 这 3 个算
法的源码链接都在相关论文中被提供, 本文不再赘述. 为了公平地比较 IRLTS 算法与这 3 个对比算法, 本文在同
一台主机上运行 4 个算法, 主机的实验环境为 Ubuntu 18.04 版本的操作系统, RAM 为 60 GB, 处理器型号为 Intel
Xeon E5-2690v4 2.6 GHz. 4 个算法的程序语言均为 C++. 本文采用的 74 组经典图测试用例 (测试用例下载链接:
http://lcs.ios.ac.cn/~caisw/graphs.html) 常被用于各类图着色问题 [15,25] 、最大割问题 [26] 、最大二分问题 [27] 、顶点平
分问题 [28] 等多种图组合优化问题, 是应用较为广泛的一类图测试用例, 其顶点数目从几千到几万不等. 4 个算法的
参数通过调参软件 F-race 在 15 组随机选取的测试用例上获取, 具体参数值如表 1 所示. 除上述 3 个表现最好的
[1]
启发式算法外, 本文同样实现了标准的粒子群算法和遗传算法这两种元启发式算法作为对比算法, 但现有研究中
缺少以两种算法为基础, 并针对 MLCP 问题优化的算法, 因此标准版的两个算法在对比中表现不佳. 限于篇幅, 本
文对两个算法的实验结果不再展示.
在 74 组测试用例上, 每一组测试用例都被每个算法运行 10 次, 单次运行的截止时间为 1 800 s, 这与文献 [1]
中的运行次数以及运行截止时间是一致的. 本文统计 10 次运行所发现的最优值, 平均值以及获取最优值的平均运
行时间, 具体数据如附录 A 表 A1 所示. 在表 A1 中, Graph 表示测试用例的名字, |V| 表示测试用例的顶点个数. 对