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

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

v i 的度数为 v i 和
如果顶点 1, 则顶点 v i 与其邻接顶点 v j 之间只存在一条边 e i j . 对于当前解 S = {V r ,V b }, 若顶点
v j 所属的集合不同, 则只会出现两种情况: v j ∈ V r 且 v i ∈ V b 或者 v j ∈ V b 且 v i ∈ V r . 当 v j ∈ V r 且 v i ∈ V b 时, 边 e i j <
′ ′ ′ ′ ′
E(V r ) 且 e i j < E(V b ). 若在此基础上将顶点 v i 移动至集合 V r 形成一个新的解 S = {V ,V }, 即 v j ∈ V 且 v i ∈ V , 则 e i j ∈
r
r
r
b
,
′ ′ ′
,
E(V ) |E(V )| = |E(V r )|+1 |E(V )| = |E(V b )|. 因为适应度值 f(S ) = min{|E(V r )|,|E(V b )|}, 因此, 如果 |E(V r )| < |E(V b )|,
r r b
′ ′ v i ∈ V r 时
则 F(S ) = F(S )+1, 适应度值被提高. 如果 |E(V r )| ⩾ |E(V b )|, 则 F(S ) = F(S ), 适应度值不变. 当 v j ∈ V b 且
与此相同, 我们不再另作分析.
基于上述分析过程, 我们给出一度顶点规则的定义, 即度为 1 的顶点只有在与其邻接顶点所属集合相同时才
有可能提高解的适应度值, 故在数据预处理阶段可首先对度为 1 的顶点及其邻接边进行约简, 从而减少测试用例
的顶点数目.
由一度顶点规则可知, 度为 1 的顶点只有在与其邻接顶点所属集合相同时才有可能提高解的适应度值. 借助
此规则, 我们可以在数据预处理阶段对数据进行约简, 减少测试用例的顶点数目. 具体操作如下: 首先, 我们将测试
用例中度为 1 的顶点及其邻接边在测试用例中移除. 其次, 将约简后的测试用例作为 IRLTS 算法的输入用例来获
取最优解. 再次, 根据获取的最优解中顶点的划分结果来确定所移除的度为 1 顶点的所属集合, 移除顶点应与其邻
接顶点所属集合相同. 最后, 根据补充完整后的测试用例调整适应度值. 在第 4.2 节, 我们通过实验结果来验证一
度顶点规则的约简效果.

3.2 TSBMS 策略
局部搜索算法通过不断迭代地从当前解移动到另一个质量更优邻居解的方式来寻找最优解. 如算法 3 所示,
RLTS 算法依据概率 p 随机地从解空间 N 1 或者解空间 N 2 中选择一个质量最优的邻居解作为新的当前解. 显然, 在
解空间 N 1 中选择一个最优邻居解的时间复杂度是 O(n), 在解空间 N 2 中选择一个最优邻居解的时间复杂度是
2 算法可以快速地在两个邻域空间中遍历选择出质量
O(n ), 其中 n 表示测试用例中顶点的数目. 当 n 较小时, RLTS
最优的邻居解. 但是随着数据规模的逐渐增大, n 越来越大时, RLTS 在两个空间中通过遍历选择最优邻居解的方
式会耗费大量的时间, 对于解空间 N 2 , 该缺陷尤为明显.
为解决局部搜索算法面对大规模测试用例时选择最优邻居解过于耗时的缺点, Cai [13] 提出 BMS 策略, 该策略
通过采样择优替代遍历搜索的方式在邻域空间中寻找最优邻居解, 被广泛用于多种大规模组合优化问题的局部搜
索算法设计中, 并且有着优秀的表现 [14−16] .
BMS 策略通过采样择优的方式寻找最优邻居解, 具体的操作步骤如下: 当算法面对一个较大规模的解空间
时, BMS 策略被触发采用. BMS 策略并不采用遍历解空间中所有候选解后选择质量最优解的方式, 因为这种方
式显然会耗费大量的时间, 从而使得算法单次迭代的时间较长, 在限定时间内, 算法无法完成多次迭代搜索. 面
对大规模解空间, BMS 策略首先从解空间中随机选择 bmsLen 个解 (bmsLen 的值通常根据具体问题来设定), 然
后再从 bmsLen 个解中选择出质量最优的一个解来作为该次迭代发现的最优解. 因为 bmsLen 的值通常远小于解
空间的大小, 因此 BMS 策略所耗费的时间也远小于遍历搜索方式耗费的时间. BMS 策略取得邻居解的质量虽
然不如遍历搜索得到的邻居解的质量, 但是该策略在面对大规模数据造成的巨大解空间时可以降低单次迭代耗
费的时间, 从而增加局部搜索算法的迭代次数, 进而找到最优解. 文献 [13] 提供了 BMS 策略的有效性分析, 本
文不再赘述.
当 BMS 策略面对较小规模的数据时, 采样择优方式所带来的降低单次迭代运行时间的优势不再明显, 而采样
择优所找到的邻居解质量较差的劣势被进一步放大, 此时 BMS 策略不能很好地帮助局部搜索算法搜索最优解. 为
了解决 BMS 策略存在的缺陷, 本文提出了优化版本的 BMS 策略, 即两阶段多重选择策略. TSBMS 策略不同于
BMS 策略, 它的搜索过程分为两个阶段: 当局部搜索算法面对的解空间较小时, TSBMS 策略利用遍历搜索的方式
来寻找最优邻居解. 因为解空间较小, 遍历搜索可以快速地找到最优解, 不耗费时间且能保证所找到邻居解的质
量. 当局部搜索面对的解空间较大时, TSBMS 策略则选择利用 BMS 策略以采样择优的方式选择一个较优的邻居
解. 具体的步骤如算法 4 所示.