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

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

V b 的概率是相等的. 在迭代过程 (第 4–10 行) 中, RLTS 算法
1/2, 也就是在初始阶段每个顶点被分配到集合 V r 和
首先根据概率矩阵生成一个初始解 S initial (第 5 行), 然后利用局部搜索过程在该初始解的邻域空间进行搜索, 直至
找到一个局部最优解 S target (第 6 行). 为了解决可能存在的对称解问题 (solution symmetry), 子集匹配函数被设计
来发现初始解 S initia 和局部最优解 S targe 之间的子集对应关系 (第 9 行). 之后, 通过比较初始解 S initia 和局部最优
l
l
t
解 S targe 之间的差异, 概率矩阵 P 被更新 (第 10 行). 至此, RLTS 算法的一次迭代过程执行完成. 在运行时间达到
t
最大时间限制时, RLTS 算法结束迭代并返回发现的最优解.

2.1 子集分配
本节将详细概述 RLTS 算法的子集分配过程 (算法 1 第 5 行). 概率矩阵 P 中存储了每个顶点 v i 被分配到集合
V r 和 V b 的概率 p ir 和 p ib . RLTS 算法依据轮盘选择策略 [17] 来计算分配顶点到集合 V r 或 V b 的概率值, 由轮盘选择
策略计算可知顶点 v i 被分配到集合 V r 的概率值是 p ir /(p ir + p ib ), 顶点 v i 被分配到集合 V b 的概率值是 p ib /(p ir + p ib ).
具体的子集分配过程如算法 2 所示.
算法 2. 子集分配过程.

输入: 无向图 G=(V, E), 概率矩阵 P;
输出: 初始解 S initial .
1. 初始化概率矩阵 P
2. for i=1, …, n do
3. l = p ir /(p ir +p ib )
4. if random(0, 1) < l then
5. 将顶点 v i 分配至集合 V r
6. else
7. 将顶点 v i 分配至集合 V b
8. return S initial ;

2.2 局部搜索
RLTS 算法通过局部搜索过程来提高输入初始解的质量, 它主要由两部分构成: 一是对当前解邻域空间的搜
索过程, 二是算法陷入局部最优后的扰动机制. 算法 3 是 RLTS 算法局部搜索过程的伪代码, 局部搜索在每次的迭
代过程中通过概率的方式 [18] 选择一个邻域空间来搜索最优解 (第 6–13 行). 如果在该领域空间内所发现的新的最
优解优于搜索历史中记录的最优解, 则历史最优解被更新, 否则搜索失败的次数加 1 (第 14–18 行). 当失败的次数
超过 T p 时, 局部搜索的扰动机制被触发 (第 20–22 行). 扰动结束后所产生的新的初始解被局部搜索过程重新搜索
T r 时, 局部搜索过程结束 (第 3、5 行). 算法中的扰动机制是通过在
其邻域空间. 当局部搜索算法的迭代次数超过
k
集合 V r 和 V b 中随机地选择 k ×|V| 对顶点交换来实现的, 其中 是一个通过实验来确定的参数. 下面我们将详细地
介绍局部搜索过程的主要组成部分: 领域空间 N 1 和 N 2 , tabu 禁忌机制.
算法 3. 局部搜索过程.
输入: 初始解 S initial , 局部搜索最大迭代次数 T r , 触发扰动的迭代次数 T p ;
输出: 发现的最优解 S best .

1. S best ← S initial
2. S ← S initial
3. Iter ← 0
4. Noimprove ← 0