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

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

multiple selections (TSBMS) is proposed to help local search algorithms efficiently select a high-quality neighborhood solution for
neighborhood space with different sizes, which effectively improves the performance of local search algorithms for processing data of
different sizes. This optimized local search algorithm is named IRLTS. Seventy-four classic test instances are adopted to validate the
effectiveness of the IRLTS algorithm. Experimental results demonstrate that the IRLTS algorithm outperforms the three best local search
algorithms on most test instances in terms of both optimal and average solutions. Furthermore, the effectiveness of the proposed strategy is
validated through experiments, and the influence of key parameters on the IRLTS algorithm is analyzed.
Key words: minimum load coloring problem (MLCP); heuristic algorithm; local search algorithm

给定一个无向图 G = (V,E), 其中 V 表示由 n 个顶点构成的集合, E 表示由 m 条边构成的集合. 最小负载着色
问题 (minimum load coloring problem, MLCP) 旨在将集合 V 中的顶点划分为两个不相交的子集合 V r 和 V b , 同时寻
求两个子集合的内部边总数中较小的值最大. 在这里, 集合的内部边是指边的两个端点属于同一个集合的边. 划分
V b 中的顶点被标记为蓝色 [1] .
完成后, 集合 V r 中的顶点被标记为红色, 集合
最小负载着色问题源于波分复用 (wavelength division multiplexing, WDM) 技术, 它在构建复杂的通信网络和
大型的电网网络中有着广泛的应用 [2,3] . 下面我们通过一个简单的例子来解释 MLCP 问题在波分复用网络中的应
用. 图 1 是一个光广播波分复用网络, 它由双通道无源星形耦合器连接 5 个节点构成. 网络中的每个节点都配备了
一个可调发射机, 它可以利用两通道中的任何一个来传输消息. 此外, 每个节点还配备了一个固定调谐接收机, 它
只能接收在前缀信道中发送的消息. 波分复用网络是一个 2-匀齐超图 (two-uniform hypergraph), 网络中的节点需
要使用一个或两个通道向另外两个节点发送消息, 该消息可以被连接到该通道的所有节点接收. 怎样将信道分配
给这些节点的接收器而使得两个信道上的最大负载最小化, 这个问题可以转化为 MLCP 问题, 其中边对应于波分
i
e i 的两个端点对应于波分复用网络中节点 传输消息的两个节点. MLCP 问题寻求将图中
复用网络中的节点, 边
的顶点着色为两种颜色, 每种颜色对应于波分复用网络中的一个通道. MLCP 问题所寻求的将两个子集合内部边
总数中较小的值最大等同于将两个通道上的最大负载最小化. 关于 MLCP 问题在波分复用网络中的更多的应用
细节可以从文献 [4] 获知.

2 3
1
3 4 1 5 1 2
5 2
e 1
e 2
e 4
e 3
5 3
4 3 e 5
1 3 2 5
4
图 1 广播波分复用网络及其对应的图

鉴于 MLCP 问题的重要性和广泛应用性, 现有文献中存在很多关于 MLCP 问题的研究. 这些研究大致可以分
为两类: 一类是致力于寻求 MLCP 问题最优解的近似算法和多项式时间算法. 这类算法的优点是可以确保所找到
的解为最优解, 但是限于 MLCP 问题的复杂性, 在面对大规模的图测试用例时, 这类算法会耗费大量的运算时间.
因此现有的关于这类算法的研究多限于一些规模较小的图测试用例以及一些特殊的图测试用例, 比如树以及一些
不相连的团构成的图. Ahuja 等人 [2] 针对树形数据设计了一个复杂度为 O(n ) 的多项式时间算法, 并且证明了该类
3
数据的最优解不超过 1/2+(△/m)log n, 其中 △ 表示顶点度的最大值. Gutin 等人 [5] 证明了宽度为 t 的树的最优解可
2
O (2 ) 内被找到. Barbero 等人 [6] 针对 MLCP 的扩展版本问题最大 c 负载着色 (max c-load coloring) 问题
t
∗
以在时间
设计了相应的近似算法.
另一类求解 MLCP 问题的算法是启发式算法. 不同于近似算法和多项式算法, 启发式算法寻求在限定时间内
尽可能地去找到一个高质量的解. 在面对大规模的测试用例时, 启发式算法是常被采用的一类算法并且有着出色
的求解表现 [7,8] . Tang 等人 [9] 利用人工蜂群算法来求解最小负载着色问题, 并设计了模拟退火算法作为对比算法.