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

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

邻居解的效率更高, 在两个策略的共同作用下, IRLTS 算法在测试用例上取得更好的求解表现.

4.2 所提策略有效性分析
本文提出了两个策略来优化 RLTS 算法, 分别是一度顶点规则和 TSBMS 策略. 本节将通过实验来分析这两
条策略的有效性.
一度顶点规则主要是通过约简测试用例中度为 1 的顶点来达到缩减数据规模的目的. 在 74 组测试用例中, 应
用一度顶点规则后顶点数目减少的测试用例有 70 组. 被约简的顶点数目与测试用例原有顶点数目的比率被用来
表示约简的效果, 比值越大说明测试用例被约简的顶点数越多. 本文统计了 70 组测试用例被约简的比率范围, 具
体结果如图 2 所示. 从图 2 可以发现, 有 48 组测试用例被约简的比率小于 0.1, 约简比率处于区间 (0.1, 0.3] 中的
测试用例个数为 10, 约简比率处于区间 (0.3, 0.5] 中的测试用例个数为 7, 约简比率大于 0.5 的测试用例有 5 个.
为验证 TSBMS 策略的有效性, 本文随机选择 10 个测试用例来完成 IRLTS 算法的消融实验. IRLTS 算法在移
除 TSBMS 策略后就是 RLTS 算法. 因此, 本文在随机选择的 10 个测试用例上运行 IRLTS 算法和 RLTS 算法, 通
过对比两个算法的实验结果来验证 TSBMS 策略的有效性. 在表 3 中可以发现, 相较于移除 TSBMS 策略的 RLTS
算法, 使用 TSBMS 策略的 IRLTS 算法在 7 组测试用例的最优值对比中取得优势, 8 组测试用例的平均值对比中
取得优势, 3 组测试用例的最优值对比中处于持平, 2 组测试用例的平均值对比中处于持平. 实验结果显示 IRLTS
算法在移除 TSBMS 策略后求解表现明显下降, 这说明 TSBMS 策略可以有效地提升 IRLTS 算法的搜索表现.

表 3 TSBMS 策略的有效性分析实验结果

RLTS IRLTS
测试用例
best avg best avg
scc_fb-messages 156 317 156 116 156 435 156 159
scc_rt_assad 30 30 30 30
50 48 scc_rt_obama 2 2 2 2
测试用例个数 30 10 scc_rt_mittromney 48 47.9 49 48.8
40
scc_rt_bahrain
scc_rt_saudi
29.2
30
30
30
20
48
47.9
43
42.7
10
0 7 5 scc_rt_gmanews 372 367.5 372 372
(0,0.1] (0.1,0.3] (0.3,0.5] (0.5,1] scc_rt_lolgop 1 668 1 658.5 1 670 1 666
约简比率区间 scc_retweet 23 238 23 011.6 23 509 23 429.3
图 2 一度顶点规则的约简效果统计 sc-nasasrb 330 305 329 221 642 004 633 975
4.3 参数影响分析
本文提出的 IRLTS 算法主要是在 RLTS 算法的基础上添加 TSBMS 策略得到的, TSBMS 策略中的两个关键
的参数分别是临界值 maxT 和采样个数 bmsLen. 本节利用随机选取的 10 组测试用例来分析两个关键参数对
IRLTS 算法的影响. 在每组测试用例上, 不同参数值的 IRLTS 算法被运行 10 次, 运行的截止时间是 1 800 s, 算法
10 次运行所产生的最优值和平均值被计算. 本文统计不同参数值的 IRLTS 算法在 10 组测试用例的最优值和平均
值对比中占优势的测试用例个数, 以此来衡量参数值对 IRLTS 算法的影响.
图 3 展示了参数值 maxT 对 IRLTS 算法的影响. 图中的 x 轴表示参数 maxT 的不同取值, y 轴表示取不同
maxT 值的 IRLTS 算法在 10 组测试用例的最优值和平均值对比中占优势的测试用例个数. 如图 3 所示, 当 maxT
的值为 1 000 000 时, IRLTS 算法在 3 组测试用例的最优值对比中取得优势, 在 5 组测试用例的平均值对比中取得
优势. 当 maxT 等于 2 000 000 和 5 000 000 时, 虽然 IRLTS 算法也在 3 组测试用例的最优值对比中取得优势, 但是
这时 IRLTS 算法在平均值上的表现不如 maxT 等于 1 000 000 时, 因此, 在本研究中, maxT 的默认参数值为 1 000 000.
图 4 展示了参数值 bmsLen 对 IRLTS 算法的影响. 图中的 x 轴表示参数 bmsLen 的不同取值, y 轴表示 bmsLen
取不同值的 IRLTS 算法在 10 组测试用例的最优值和平均值对比中取得优势的测试用例个数. 由图 4 可知, 当
bmsLen 的值等于 10 000 时, IRLTS 算法在 4 组测试用例的最优值对比中取得优势, 以及 3 组测试用例的平均值对