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

田新亮 等: 一种高效的求解最小负载着色问题的局部搜索算法 3687

于每一个算法, 本文展示该算法在相应测试用例上获取的最优值 (best), 平均值 (avg), 获取最优值所用的平均时间
(time (s)). 粗体字表示 4 个算法的结果在对比中占优势的数值. 为更清晰地获取 IRLTS 算法与其他 3 个对比算法
的对比结果, 表 2 总结了 IRLTS 算法与 3 个对比算法的对比结果. 第 1 列表示 IRLTS 算法与 3 个对比算法, 第 2
列表示总共 74 组测试用例, 第 3 列表示最优值和平均值两个对比指标, 第 4–6 列表示 IRLTS 算法与对比算法在
对比中占优的测试用例个数, 持平的测试用例个数和占劣势的测试用例个数.

表 1 4 个算法的参数值

分组 参数 参数值
α 0.2
β 0.2
γ 0.2
RLTS算法 T r 50 000
500
T p
k 0.1
tt 15
β×n/2
k max
GVNS算法 α 0.5
β 0.2
β×n/2
k max
MS-GVNS算法 α 0.5
β 0.2
α 0.2
β 0.2
γ 0.2
50 000
T r
IRLTS算法 T p 500
k 0.1
tt 15
maxT 1 000 000
m 10 000

表 2 IRLTS 算法与其他算法的对比结果总结

对比算法 测试用例总个数 对比指标 胜 平 负
best 37 28 9
IRLTS vs. GVNS 74
avg 33 25 16
best 38 28 10
IRLTS vs. MS-GVNS 74
avg 32 24 18
best 45 28 1
IRLTS vs. RLTS 74
avg 58 13 3

从表 2 可以发现, 相较于 GVNS 算法, IRLTS 算法在 37 组测试用例的最优值对比中取得优势, 28 组测试用例
的最优值对比中持平, 9 组测试用例的最优值对比中相较 GVNS 算法占劣势. 在平均值指标上, IRLTS 算法占优势、
持平、占劣势的测试用例个数分别为 33、25、16. 与 MS-GVNS 算法相比, 在最优值指标上, IRLTS 算法在 38 组
测试用例上占优势, 在 28 组测试用例上持平, 在 10 组测试用例上占劣势, 在平均值指标上, IRLTS 算法占优势、
持平、占劣势的测试用例个数分别为 32、24 和 18. 与 RLTS 算法相比, 在最优值指标上, IRLTS 算法占优势、持
平、占劣势的测试用例个数分别为 45、28 和 1, 在平均值指标上, IRLTS 算法占优势、持平、占劣势的测试用例
个数分别为 58、13 和 3. 实验结果表明, 无论最优解还是平均解, 改进后的 IRLTS 算法在大多数测试用例上明显
超过当前最优的 3 个算法. 如前文所述, 得益于一度顶点规则和 TSBMS 策略, IRLTS 算法的解空间被减小, 搜索