Page 254 - 《软件学报》2024年第6期

2830 软件学报 2024 年第 35 卷第 6 期

rSAT4J [20] 进行比较. 其中, TSENS 是本文算法的直接基础, 它与 dSATNS 的区别在于: TSENS 未采用多样化的
SAT 求解器且仅使用了全局型档案. 值得注意的是, 在生成“种子”时, TSENS 随机地为每个变量赋值 0 或 1. 将这
种以随机方式生成种子的策略替换成遗传算子 (选择、交叉和变异) 即得到算法 TSEGA. 最后, rSAT4J 是一个被
广泛采用的基准算法 [20] .
RQ4 是为了探索参数 P r 对 dSATNS 算法性能的影响. P r 是本文所提算法的一个重要参数, 它控制了调用两

类求解器的比例. 将 P r 以一定间隔 (如 0.1) 从 0 增加到 1, 然后比较每个可能值对应的算法性能, 进而确定其最优
取值.
5.1 实验数据
在实验部分, 本文采用 50 个公开的软件产品线/特征模型 (见表 1 的第 1 列) 进行仿真实验. 在既往工作
中 [20,33,34,43] , 它们也被广泛遴选为测试问题. 除了 SPLOT-FM-5000 之外的所有 SPLs 均代表真实软件产品线或高
度可配置系统, 而 SPLOT-FM-5000 则是人为构造的一个软件产品线, 被 Henard 等人 [20] 用于基于相似性的软件产
品线测试的研究. 对所有特征模型, 特征个数 (即 n) 的最小值为 24, 最大值为 14 910; 约束个数最小值为 35, 最大
值为 343 944. 我们将这些软件产品线分为 3 类: 小规模软件产品线 ( n < 1000 ), 中等规模软件产品线 ( 1000 <
69.97 •
n ⩽ 5000 ) 和大规模软件产品线 ( n > 5000 ). 表 1 所展示的软件产品线已按 n 值升序排列, 其中前 23 个是小规模
的, 后 4 个是大规模的, 中间 23 个是中等规模的. 所有软件产品线对应的特征模型均采用 DIMACS 这种 SAT 求
解器的标准格式进行表示.
表 1 dSATNS 和 SATNS 两算法覆盖率的比较 (%)

N=4 N=6 N=10 N=50 N=100
FM
dSATNS SATNS dSATNS SATNS dSATNS SATNS dSATNS SATNS dSATNS SATNS
CounterStrikeSFM 87.52 87.52 ± 95.86 95.74 ± 99.52 99.52 ± 100.00 100.00 ± 100.00 100.00 ±
HiPAcc 73.31 74.27 ◦ 84.93 84.49 ± 92.84 92.76 ± 99.88 99.88 ± 100.00 100.00 •
SPLSSimuelESPnP 87.78 87.78 ± 96.69 96.27 ± 99.72 99.65 ± 100.00 100.00 ± 100.00 100.00 ±
JavaGC 72.16 72.16 ± 81.12 81.85 ± 89.91 89.83 ± 99.75 99.75 ± 100.00 100.00 ±
Polly 76.35 76.35 ± 84.47 84.39 ± 93.03 92.92 ± 99.92 99.92 ± 100.00 100.00 ±
DSSample 60.32 60.49 ± 68.25 68.25 ± 77.78 77.78 ± 96.82 96.87 ± 99.19 99.19 ±
VP9 75.70 75.94 ± 85.25 85.19 ± 92.73 92.62 ± 99.96 99.96 ± 100.00 100.00 ±
WebPortal 80.43 80.19 ± 90.54 89.88 • 97.00 96.87 ± 100.00 100.00 ± 100.00 100.00 ±
JHipster 76.55 76.25 ± 85.53 84.99 ± 93.30 93.34 ± 99.81 99.81 ± 99.94 99.95 ±
Drupal 83.04 82.38 • 92.99 92.38 • 98.64 98.51 ± 100.00 100.00 ± 100.00 100.00 ±
SmartHomev2.2 81.93 80.68 • 92.15 91.48 • 98.03 97.79 • 100.00 100.00 ± 100.00 100.00 ±
VideoPlayer 85.00 84.16 • 94.23 93.43 • 99.14 98.94 • 100.00 100.00 ± 100.00 100.00 ±
Amazon 53.68 53.67 ± 60.42 60.42 ± 67.58 67.38 ± 89.92 89.59 ± 94.73 94.81 ◦
ModelTransformation 77.37 76.72 • 87.57 86.83 • 95.29 95.06 • 99.99 99.99 ± 100.00 100.00 ±
CocheEcologico 78.22 78.18 ± 84.81 84.18 • 90.80 90.80 ± 99.29 99.31 ± 99.77 99.77 ±
Printers 75.73 74.73 • 82.67 82.01 • 88.67 88.43 • 97.54 97.58 ± 98.80 98.81 ±
fiasco_17_10 59.79 59.60 ± 64.98 64.70 ± 71.90 71.76 ± 82.72 82.81 ± 85.47 85.72 ±
uClibc-ng_1_0_29 63.46 62.70 • 70.46 76.42 76.37 ± 88.02 87.92 ± 91.57 91.69 ±
E-shop 77.35 75.26 • 88.17 86.18 • 95.71 95.58 • 99.96 99.96 ± 100.00 100.00 ±
toybox 95.04 94.65 • 97.92 97.74 • 99.48 99.44 ± 100.00 100.00 ± 100.00 100.00 ±
axTLS 91.15 91.19 ± 95.59 95.51 ± 98.56 98.45 • 100.00 100.00 ± 100.00 100.00 ±
financial 47.10 47.18 ± 49.76 49.76 ± 53.96 54.02 ± 66.38 66.28 ± 71.44 71.49 ±
busybox_1_2_8_0 73.81 69.64 • 85.90 84.03 • 94.86 94.04 • 99.72 99.83 ◦ 99.90 99.93 ◦
mpc50 75.31 75.02 • 84.51 84.24 ± 92.08 93.05 ◦ 99.55 99.54 ± 99.83 99.82 ±
ref4955 75.50 75.03 ± 84.54 84.34 ± 92.27 92.77 ± 99.54 99.53 ± 99.82 99.82 ±
Linux 74.77 74.79 ± 84.10 83.87 ± 91.67 91.90 ± 99.42 99.41 ± 99.79 99.78 ±
csb281 74.87 74.20 • 84.05 83.86 ± 91.60 91.62 ± 99.44 99.44 ± 99.78 99.79 ±
ecos-icse11 74.67 74.28 • 84.01 83.74 ± 91.87 91.54 ± 99.48 99.48 ± 99.81 99.80 ±