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

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

5. while Iter < T r do
6. if 小于概率值 p then
7. 构造当前解 S 的邻域空间 N 1
8. 在 N 1 中选择未被 tabu 禁止的最优解 S ′
′
9. S ← S
10. else
11. 构造当前解 S 的邻域空间 N 2
12. 在 N 中选择未被 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
20. if Noimprove > T p then
21. Noimprove ← 0
22. S ← Perturb(S)
23. return S best
S
无向图 G = (V,E) 的顶点集合 V 被划分成任意两个不相交的子集 V r 和 V b 后会产生一个可行解 . 搜索空间 Ω
Ω = {{V r : V b } : V r ∩V b = ∅,V r ∪V b = V}. 显然, 搜索空间的大小为 n n 为顶点数
由所有的可行解构成, 也就是 2 , 其中
目. 对于一个可行解 S = {V r ,V b }, 该可行解的适应度值为 f(S ) = min{|E(V r ),|E(V b )|}.

2.2.1 解空间 N 1
v
对于当前解 S = {V r ,V b }, 从子集合 V r 或 V b 中任意选择一个顶点 移动到另一个子集合, 该行为产生的所有可
′ ′ ′ V ′
行解构成解空间 N 1 . 为了快速地计算移动一个顶点后所生成候选解 S = {V ,V } 的适应度值, 也就两个子集合
r b r
′ ′ ′ v i 所
和 V 的内部边的数目 |E(V )| 和 |E(V )|, RLTS 算法用数组 ( v i 存在连接且与顶点
δ i i ∈ {1,...,n}) 来保存与顶点
b r b
属子集合相同的顶点数目. 此外, RLTS 算法用数组 D 来保存顶点的度, D i 存储顶点 v i 的度. 在此基础上, 我们可以
,
′ ′ ′
根据下述公式快速地计算出候选解 S 的适应度值: 如果 v i ∈ V r , 则 |E(V )| = |E(V r )|−δ i |E(V )| = |E(V b )|+ D i −δ i .
r
b
′ , ′ v i ∈ V 后, RLTS 算法可以依照下面公
如果 v i ∈ V b , 则 |E(V )| = |E(V r )|+ D i −δ i |E(V )| = |E(V b )|−δ i . 在移动一个顶点
r b
式在 O(n) 内更新数组 δ:
对于顶点 , v i 相连接的顶点 ,
v i δ i = D i −δ i . 对于除顶点 v i 外的其他与顶点 v u
{
δ u −1, 如果v u 属于v i 移动前的集合
δ u = (3)
δ u +1, 如果v u 不属于v i 移动前的集合

2.2.2 解空间 N 2
v i 和 , 交换两个顶点所属的子集合, 该
对于当前解 S = {V r ,V b }, 从子集合 V r 和 V b 中各自随机选择一个顶点 v j
行为产生的所有可行解构成解空间 N 2 . 与计算单个顶点 v 移动后所产生候选解适应度值的方式相同, 借助数组 δ, 在
,
′
′
完成交换操作后所产生候选解的适应度值也可以在 O(1) 内完成: |E(V )| = |E(V r )|+ D i −δ i −δ j − E i j |E(V )| = |E(V b )|+
r b
D i −δ i −δ j − E ij . 交换操作可以看作是两个顶点移动操作的组合, 数组 δ 在交换操作中的单个顶点移动操作完成后
被更新, 更新公式与公式 (3) 相同.

2.2.3 禁忌管理
在局部搜索过程中, 当顶点 v 被从当前的子集合移动到另一个子集合后, 它会很容易被再次选择移动回原有