软件学报

作者：田新亮，欧阳丹彤，周慧思，蒋璐宇，太然，张立明

单位：田新亮，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001211,欧阳丹彤，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001202,周慧思，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001203,蒋璐宇，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001204,太然，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001205,张立明，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001206

关键词：最小负载着色问题;启发式算法;局部搜索算法

基金：国家自然科学基金(62076108, 61872159)

最小负载着色问题(minimum load coloring problem, MLCP) 源于构建光通信网络的波分复用(wavelength division multiplexing, WDM)技术, 是一个被证明的NP完全问题. 由于NP完全问题有着随问题规模呈指数增长的解空间, 因此启发式算法常被用来解决这类问题. 在对国内外相关工作的深入分析基础上得知, 现有的多类求解MLCP问题的启发式算法中局部搜索算法表现是最好的. 研究针对当前求解MLCP问题的局部搜索算法在数据预处理和邻域空间搜索上的不足, 提出了两点相应的优化策略: 一是在数据的预处理阶段, 提出一度顶点规则来约简数据的规模, 进而减小MLCP问题的搜索空间; 二是在算法的邻域空间搜索阶段, 提出两阶段多重选择策略(two-stage best from multiple selections, TSBMS)来帮助局部搜索算法在面对不同规模的邻域空间时可以高效地选择一个高质量的邻居解, 它有效地提高了局部搜索算法在处理不同规模数据时的求解表现. 将这个优化后的局部搜索算法命名为IRLTS. 采用74个经典的测试用例来验证IRLTS算法的有效性. 实验结果表明, 无论最优解还是平均解, IRLTS算法在大多数测试用例上都明显优于当前表现最好的3个局部搜索算法. 此外, 还通过实验验证了所提策略的有效性以及分析了关键参数对算法的影响.

来源：2025年第8期

《软件学报》期刊编辑部

查看软件学报杂志2025年第8期