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

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

算法 4. TSBMS 策略.
输入: 邻域空间 N, 临界值 maxT, 采样个数 bmsLen;
输出: 选择的最优邻居解 S.

1. if |N| < maxT then
2. S ← 遍历的方式从 N 中选择质量最优的一个解
3. else
4. S ← 从 N 中随机选择 bmsLen 个解, 然后从 bmsLen 个解中选择质量最优的解
5. return S

如算法 4 所示, TSBMS 策略根据解空间的大小选择不同的方式寻找最优邻居解. 当解空间的规模小于
maxT 时, TSBMS 策略利用遍历搜索的方式来寻找最优邻居解. 由于解空间的规模较小, 遍历搜索的方式既可以找
到最高质量的邻居解, 也不会花费太多的时间. 当解空间的规模大于 maxT 时, TSBMS 策略采用 BMS 策略以采样
择优的方式选择质量较优的邻居解, 该策略可以避免遍历搜索导致的大量时间耗费, 快速地返回一个质量较优的
邻居解.

3.3 IRLTS 算法
在数据的预处理阶段, IRLTS 算法利用一度顶点规则来约简数据的规模, 进而达到减小解空间规模的目的. 此
外, TSBMS 策略被用来改进 RLTS 算法中的局部搜索过程, 改进后的局部搜索过程如算法 5 所示.

算法 5. IRLTS 算法的局部搜索过程.
输入: 初始解 S initial , 局部搜索最大迭代次数 T r , 触发扰动的迭代次数 T p ;
输出: 发现的最优解 S best .

1. S best ← S initial
2. S ← S initial
3. Iter ← 0
4. Noimprove ← 0
5. while Iter < T r do
6. if 小于概率值 p then
7. 构造当前解 S 的邻域空间 N 1
8. 在 N 1 中根据 TSBMS 策略选择未被 tabu 禁止的最优解 S ′
9. S ← S ′
10. else
11. 构造当前解 S 的邻域空间 N 2
12. 在 N 2 中根据 TSBMS 策略选择未被 tabu 禁止的最优解 S ′
13. S ← S ′
14. if f(S) > f(S best ) then
15. S best ← S
16. Noimprove ← 0
17. else
18. Noimprove ← Noimprove + 1
19. Iter ← Iter + 1