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

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

实验结果显示 Tang 等人改进的人工蜂群算法在求解 MLCP 问题上有着良好的表现. Ye 等人 [10] 针对 MLCP 问题
设计了一个高效的局部搜索算法, 实验结果显示该算法远远超过当时其他求解 MLCP 问题的启发式算法. Zhang
等人 [11] 结合局部搜索和进化算法设计了一个高效的文化基因算法, 实验结果显示该算法在部分标准测试数据上
提高了已知的最优解. 近几年, Sun 等人 [1] 和 Herrán 等人 [12] 分别设计了两个不同版本的局部搜索算法, 是当前求
解 MLCP 问题表现最好的启发式算法. Sun 等人设计的局部搜索算法在搜索过程中利用强化学习机制生成新的初
始解来为局部搜索算法开辟新搜索区域. Alberto 等人设计了多个不同的邻域空间来帮助局部搜索算法在不同的
区域搜索最优解, 这大大提高了算法的搜索表现.
虽然当前存在多种求解 MLCP 问题表现良好的启发式算法, 但现有的启发式算法多是针对较小规模的测试
用例设计的, 所求解测试用例的顶点数目只有几百个. 随着科技的进步, 各种通信网络的规模越来越大, 所对应测
试用例的规模也越来越大. 现有的启发式算法在面对大规模顶点数目所造成的巨大搜索空间时表现乏力, 因此, 设
计高效的启发式算法去解决 MLCP 问题中的大规模图测试用例是亟待解决的一个问题. 本文在当前表现最好的
一个启发式算法, 即 Sun 等人设计的高效的局部搜索算法 RLTS (reinforcement learning based tabu search) 的基础

上, 提出了两点针对大规模测试用例的优化策略, 具体如下:
(1) 当前的启发式算法处理大规模图测试用例所面临的一个挑战在于随图顶点数目呈指数增长的解空间. 为
此我们提出一度顶点规则对图测试用例进行约简. 一度顶点规则旨在通过约简大规模图测试用例的顶点数目来达
到缩减解空间规模的目的, 它有效地减少了图测试用例的顶点数目, 从而为算法后期的搜索提供一个较小的搜索
空间. 在第 3.1 节中将详细介绍一度顶点规则, 并对该规则的有效性进行理论性分析.
(2) 局部搜索算法通过不断迭代地从当前解移动到邻居解的方式来搜索最优解, 当前表现最优的局部搜索算
法 RLTS 在搜索合适的邻居解时存在着过于耗时的缺陷, 在面对有较多顶点数的图测试用例所形成的大规模领域
空间时, 这一缺陷尤为明显. 为此我们提出了两阶段多重选择策略 (two-stage multiple selection strategy, TSBMS) 来
进一步优化当前最优的局部搜索算法 RLTS. TSBMS 策略改进于 Cai [13] 提出的多重选择策略 (multiple selection
strategy, BMS), BMS 策略被广泛用于解决各类大规模图测试用例的组合优化问题 [14−16] , 但是它存在着处理小规模
图测试用例表现不佳的缺陷. 为此我们进一步优化 BMS 策略得到了 TSBMS 策略. TSBMS 策略可以高效地帮助
RLTS 算法选择合适的邻居解, 提高 RLTS 算法的适用性, 使其在面对不同规模的图测试用例时都有优秀的表现.
我们将优化后的 RLTS 算法命名为 IRLTS (improved reinforcement learning based tabu search). 在实验部分, 我
们采用 74 个不同规模的经典测试用例来验证 IRLTS 算法的有效性. 实验结果表明, 无论最优解还是平均解,
IRLTS 算法在大多数测试用例上都明显超过了当前最优的 3 个启发式算法.
本文第 1 节介绍 MLCP 问题的具体定义. 第 2 节介绍当前表现最优的 RLTS 算法. 第 3 节介绍我们提出的一
度顶点规则和 TSBMS 策略, 以及优化 RLTS 算法后所形成的 IRLTS 算法. 在第 4 节, 我们通过对比实验来验证
IRLTS 算法和所提策略的有效性, 以及分析关键参数对 IRLTS 算法的影响. 第 5 节总结全文.

1 MLCP 问题定义

现有文献中存在多种对 MLCP 问题的具体定义. 在本文的研究中, 我们采用文献 [1] 中关于 MLCP 问题的定
n 个顶点构成的集合 ( ), m 条边构成的集
义. 给定一个无向图 G = (V,E), 其中 V 表示由 V = {v 1 ,v 2 ,v 3 ,...,v n } E 表示由
合 ( E = {e 1 ,e 2 ,e 3 ,...,e m }). 边是由两个顶点构成的无序二元组, 一般表示为 e = {u,v}, 简写为 e uv , 其中 u 和 表示边 e
v
的两个端点. 最小负载着色问题旨在将集合 V 中的顶点划分为两个不相交的子集 V r 和 V b , 同时寻求两个子集合的
|E(V r )| 和 |E(V b )| 中较小的值最大, 其中 E(V r ) 表示两端顶点都属于集合 V r 的边的集合, |E(V r )| 表示两端顶点都属
于集合 V r 的边的数目. 同理, E(V b ) 表示两端顶点都属于集合 V b 的边的集合, |E(V b )| 表示两端顶点都属于集合 V b
的边的数目. 划分完成后, 集合 V r 中的顶点被标记为红色, 集合 V b 中的顶点被标记为蓝色.
我们用 e ij = 1 表示顶点 v i 和 v j 之间存在边连接, e i j = 0 表示顶点 v i 和 v j 之间不存在边连接. x i = 1 表示顶点 v i
.
,
属于集合 V r x i = 0 表示顶点 v i 属于集合 V b r ij = 1 表示顶点 v i 和 v j 同时属于集合 V r , 如果顶点 v i 和 v j 不同时属于