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

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

的子集合. RLTS 算法采用禁忌表 (tabu list) [19] 的方式来阻止这种短期循环 (short-term cycling) 现象的产生. 当顶点

v 被从当前的子集合移动到另一个子集合后, 它将被禁止在未来的 tt 次迭代内移动回最初的子集合. 只有当移动
该顶点所产生解的质量优于当前最优解的质量时, 该禁忌策略可以被违背. RLTS 算法中的禁忌表是通过一个
,
j j = 0 表示子集合
|V|×2 的二维数组 T 来实现的. 每次顶点 v 被从子集合 ( V r j = 1 表示子集合 V b ) 移除后, T[v][j]
Iter < T[v][ j] 时, 顶点 禁止被移回子集
v
被更新为 Iter +tt, 其中 Iter 是当前的迭代次数. 在算法的迭代过程中, 当
v
合 j. 当 Iter > T[v][ j] 时, 顶点 不受该规则限制.

2.3 子集匹配
MLCP 问题旨在将集合 V 中的顶点划分到两个不相交的子集 V r 和 V b . RLTS 算法用数组去表示一个可行解,
下标为 i 的元素置为 1 或 0 表示顶点 v i 被分配到集合 V r 或 V b . 在 RLTS 算法中, 强化学习机制是通过初始解
S initia 和局部最优解 S targe 各自分配到集合 V r 和 V b 中的顶点个数差异来学习的. 很显然, 这必然会导致一种解对
l
t
称 (solution symmetry) 问题 [20] . 例如, 无向图 G 有 6 个顶点 {v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 }, 存在两个解, 解 S 1 = {V r ,V b }, 其中
,
,
′
′
′
′
V r = {v 1 ,v 2 ,v 3 } V b = {v 4 ,v 5 ,v 6 }, 解 S 2 = {V ,V }, 其中 V = {v 4 ,v 5 ,v 6 } V = {v 1 ,v 2 ,v 3 }. 其实解 S 1 和 S 2 是相同的, 但是在
r
r
b
b
算法中去表示这两个解的数组 {0,0,0,1,1,1} 和 {1,1,1,0,0,0} 会被看作是不同的解. RLTS 算法设计子集匹配函数
(subset matching, 算法 1 第 9 行) 来解决该问题, 具体方法如下.
S target = {V ,V }. 算法通过下面的方式来处理对
′
′
对于初始解 S initial = {V r ,V b } 以及局部搜索提高后的局部最优解 r b
′ ′ ′ ′ S target 两个子集中的顶
称解问题: 如果 |V r ∩V |+|V b ∩V | < |V r ∩V |+|V b ∩V |, 子集匹配函数选择交换局部最优解
r b b r
点, 否则, 局部最优解 S target 的两个子集保持不变.

2.4 强化学习机制
RLTS 算法中的强化学习机制 [21] 是根据初始解 S initial 和经过局部搜索后得到的局部最优解 S target 之间各个顶
v
点 v 所属集合的差异来学习的, 它是通过增加或者减小概率矩阵 P 中顶点 分配到集合 V r 或者 V b 的概率值来实
现的, 具体步骤如下.
在经历局部搜索后, 如果顶点 v 依然被保留在原有的集合中, RLTS 算法就采用公式 (4) 来增加顶点 v 保留在
原有集合中的概率值, 以及减小移动到另一个集合的概率值. 我们用 u 来表示原有的集合, u ∈ {0,1}.


 α+(1−α)p ij , j = u


p ij =  (4)

 (1−α)p i j , j = 1−u
如果在经历局部搜索后, 顶点 v 从集合 V u 移动到集合 V 1−u , RLTS 算法则降低顶点 v 分配到集合 V u 的概率值,
增加 v 分配到集合 V 1−u 的概率值. 具体公式如下, 其中 β 是惩罚因子, γ 是补偿因子.


 (1−γ)(1−β)p ij , j = u


p ij =  (5)

 γ +(1−γ)β+(1−γ)(1−β)p i j , j = 1−u
最后, RLTS 算法为了防止顶点 v 被过于贪心地分配到某个集合内, 强化学习机制限制概率值的上限和下限区
间为 [0.2,0.8], 这为 RLTS 算法生成初始解增添了一些随机性.

3 IRLTS 算法
IRLTS 算法是我们在 RLTS 算法的基础上提出两点优化策略后得到的一个高效的启发式算法. 第 3.1 节和第
3.2 节将详细地介绍针对 RLTS 算法不足所提出的两点优化策略: 一度顶点规则和 TSBMS 策略. 经过这两个策略
优化后, 生成新的高效算法. 我们将其命名为 IRLTS 算法, 该算法将在第 3.3 节介绍.

3.1 一度顶点规则
MLCP 问题是一个经典的 NP 完全问题, 它的解空间随测试用例的顶点数呈指数增长. 为了约简测试用例的
顶点数, 进而降低 MLCP 问题的解空间规模, 我们提出一度顶点规则来约简测试用例的顶点数目. 下面给出该规
则的有效性分析以及具体定义.