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

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

比中取得了优势. 当 bmsLen 取其他值时, IRLTS 算法的表现比 bmsLen 等于 10 000 时 IRLTS 算法的表现差, 因此
IRLTS 算法中 bmsLen 参数的默认值为 10 000.

5
best
5
5 best 4 average
average 4 3 3 3 3
4
测试用例个数 3 2 3 2 3 3 3 测试用例个数 2 1 1 2 2 2 2
1
1
1
0 0 1
0 0
100 000 500 000 1 000 000 2 000 000 5 000 000 1 000 5 000 10 000 20 000 50 000
maxT 的不同取值 bmsLen 的不同取值
图 3 临界值 maxT 对 IRLTS 算法的影响 图 4 采样个数 bmsLen 对 IRLTS 算法的影响
5 总 结

本文针对当前求解 MLCP 问题表现最好的启发式算法存在的缺陷, 提出了两点优化策略, 一是一度顶点规则,
该规则通过约简测试用例中度为 1 的顶点来减少测试用例的顶点数, 进而降低测试用例的解空间规模, 从而有利
于算法在相对较小的搜索空间内寻找最优解. 第 2 个优化策略是 TSBMS 策略. 该策略可以根据解空间规模的大
小采用不同的方式在邻域空间中选择最优邻居解, 它有效地提高了算法在处理不同规模测试用例时的求解表现.
本文将两个策略优化后的 RLTS 算法命名为 IRLTS 算法. 74 组经典的测试用例和 3 个当前表现最好的启发式算
法被用来验证 IRLTS 算法的有效性. 实验结果表明, 无论最优解还是平均解, IRLTS 算法在大多数测试用例上都
超过了 3 个当前最优的启发式算法. 此外, 本文还组织实验验证了所提策略的有效性, 以及分析了关键参数对算法
的影响. 在未来的研究中, 我们将在两个方面继续完善我们的工作, 一是对 IRLTS 算法的结构进行优化, 进一步提
高 IRLTS 算法的求解表现; 二是针对更大规模的测试用例设计高效的优化策略, 为 MLCP 问题的解决提供更高效
的求解算法.

References:
[1] Sun Z, Benlic U, Li MJ, Wu QH. Reinforcement learning based tabu search for the minimum load coloring problem. Computers &
Operations Research, 2022, 143: 105745. [doi: 10.1016/j.cor.2022.105745]
[2] Ahuja N, Baltz A, Doerr B, Přívětivý A, Srivastav A. On the minimum load coloring problem. Journal of Discrete Algorithms, 2007, 5(3):
533–545. [doi: 10.1016/j.jda.2006.09.001]
[3] Baldine I, Rouskas GN. Reconfiguration and dynamic load balancing in broadcast WDM networks. Photonic Network Communications,
1999, 1(1): 49–64. [doi: 10.1023/A:1010029100403]
[4] Thaker D, Rouskas GN. Multi-destination communication in broadcast WDM networks: A survey. Optical Networks Magazine, 2002,
3(1): 34–44.
[5] Gutin G, Jones M. Parameterized algorithms for load coloring problem. Information Processing Letters, 2014, 114(8): 446–449. [doi: 10.
1016/j.ipl.2014.03.008]
[6] Barbero F, Gutin G, Jones M, Sheng B. Parameterized and approximation algorithms for the load coloring problem. Algorithmica, 2017,
79(1): 211–229. [doi: 10.1007/s00453-016-0259-z]
[7] Yi JH, Xing LN, Wang GG, Dong JY, Vasilakos AV, Alavi AH, Wang L. Behavior of crossover operators in NSGA-III for large-scale
optimization problems. Information Sciences, 2020, 509: 470–487. [doi: 10.1016/j.ins.2018.10.005]
[8] Li W, Wang GG, Alavi AH. Learning-based elephant herding optimization algorithm for solving numerical optimization problems.
Knowledge-based Systems, 2020, 195: 105675. [doi: 10.1016/j.knosys.2020.105675]
[9] Fei T, Bo W, Jin W, Liu DC. Artificial bee colony algorithm for the minimum load coloring problem. Journal of Computational and
Theoretical Nanoscience, 2013, 10(9): 1968–1971. [doi: 10.1166/jctn.2013.3156]
[10] Ye AS, Zhang ZQ, Zhou XQ, Miao F. Tabu assisted local search for the minimum load coloring problem. Journal of Computational and