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

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

集合 V r 则用 r i j = 0 表示. b i j = 1 表示顶点 v i 和 v j 同时属于集合 V b , 如果顶点 v i 和 v j 不同时属于集合 V b 则用 b i j = 0
表示. z 表示两端顶点都属于集合 V r 的边的数目和两端顶点都属于集合 V b 的边的数目中较小的数值.

max z (1)


 1 ⃝ 2×r ij < x i + x j ,∀i, j ∈ {1,...,n}




 2 ⃝ 2×b ij ⩽ 2− x i − x j ,∀i, j ∈ {1,...,n}




 ∑ ∑

 3 ⃝ z ⩽


 r i j ×e i j
 i∈V j∈V


 ∑ ∑

s.t.  4 ⃝ z ⩽ (2)
 b i j ×e i j
 i∈V j∈V





 5 ⃝ b ij ,r ij ∈ {0,1},∀i, j ∈ {1,...,n}






 6 ⃝ x i ∈ {0,1},∀i ∈ {1,...,n}




7 ⃝ z ∈ N

公式 (1) 表示 MLCP 问题寻求两端顶点都属于集合 V r 的边的数目和两端顶点都属于集合 V b 的边的数目中较
小的那个值最大. 约束①确保只有当顶点 v i 和 v j 同时属于集合 V r 时 r i j 的值为 1. 约束②确保只有当顶点 v i 和 v j
∑ ∑ ∑ ∑
b i j 的值为 1. V r 所构成的边的数目.
同时属于集合 V b 时 r ij × e ij 表示两个端点都属于集合 b ij
i∈V j∈V i∈V j∈V
z
× e i j 表示两个端点都属于集合 V b 所构成的边的数目, 约束③、④确保 的值小于等于集合 V r 和 V b 各自内部边总
数中较小的那个值. 约束⑤–⑦约束了变量的取值范围.

2 RLTS 算法
RLTS 算法是当前求解 MLCP 问题表现最好的启发式算法, 本文所提出的 IRLTS 算法正是以 RLTS 算法为基
础优化得到的, 本节将详细介绍 RLTS 算法. RLTS 算法主要由局部搜索过程和强化学习机制两部分构成. 局部搜
索过程在输入初始解的邻域空间内不断地寻找最优解, 直到算法陷入局部最优. 强化学习机制根据局部搜索过程
所获取的新的最优解来不断地更新概率矩阵, 概率矩阵则指导生成新的初始解提供给局部搜索过程. RLTS 算法
在生成新初始解的强化学习机制和搜索初始解邻域空间的局部搜索过程间不断切换来寻找最优解. RLTS 算法的
框架如算法 1 所示.
算法 1. RLTS 算法.
输入: 无向图 G=(V, E), 时间限制 t max ;
输出: 发现的最优解 S best .
1. 初始化概率矩阵 P
2. for i=1, …, n do
3. p i0 =p i1 =1/2
4. while time()<t max do
5. S initial ←Subset_Selection(P)
6. S target ←Local_Search(S initial )
7. if S target is better than S best then
8. S best ← S target
9. S target ← Subset_Matching(S initial , S target )
10. P ← Probability_Updating(S initial , S target , P)
11. return S best ;
RLTS 算法采用一个 n×2 的矩阵 P 来表示概率矩阵, 其中元素 p ir i ∈ {1,...,n}) 表示顶点 v i 分配给集合 V r 的概
(
率, 元素 p ib 表示顶点 v i 分配给集合 V b 的概率. 在 RLTS 算法的初始阶段, 概率矩阵 P 中的每个元素都被设置为