Page 250 - 《软件学报》2024年第6期
P. 250
2826 软件学报 2024 年第 35 卷第 6 期
法 1 遵循了 NS 算法的基本框架, 其主要特色在于运用领域知识生成新解 (即新测试用例) 和采用两种归档策略.
接下来, 本文将详细介绍该算法的一些关键细节.
算法 1. dSATNS 算法.
输入: 测试集规模 N;
输出: 测试集 TS.
1. 采用 rSAT4J 随机地产生初始测试集 TS = [tc 1 ,tc 2 ,...,tc N ] // N 为测试集规模
2. 根据 TS 中的个体初始化概率向量 p = [p 1 , p 2 ,..., p n ] n 为特征数
//
3. while 终止条件未满足 do
4. c ← DiverseSATSolving(p)
5. if rand(0,1) < 0.5
6. GlobalArch(TS, c)
7. else
[40]
8. LocalArch(TS, c)
9. end if
10. end while
11. return TS
4.1 概率向量及其初始化
本文采用了分布估计算法中概率向量 [41,42] 的概念. 概率向量 p = [p 1 , p 2 ,..., p n ] 的第 j 个分量 p j 的含义为第 j
个变量取值为 1 (或 true) 的概率. 显然, 该概率事先未知, 但可用当前种群 (即测试集) 的分布进行估计. 具体地, 令
tc ij 表示第 i 个测试用例第 j 个变量的取值, 则可根据公式 (3) 初始化 p j :
N ∑
tc ij
i=1
p j = (3)
N
也就是说, p j 被初始化为当前测试集 TS 中第 j 个变量取值为 1 的所有测试用例所占的比例. 概率向量主要用
于生成多样化的 (候选) 测试用例. 在算法的迭代过程中, 概率向量会根据当前测试集动态地更新 (第 4.3 节将予以
详细介绍).
4.2 多样性 SAT 求解器
如第 1 节所述, dSATNS 采用了两类多样性求解器, 它们的结合方式如算法 2 所示. DiverseSATSolving 以概
率 1− P r 调用 rSAT4J, 而以概率 P r 调用多样化版本的 ProbSAT, 即 tc (见算法 3). 如前所述, 作为一种 CDCL 求解
器, rSAT4J [20,35] 是随机化版本的 SAT4J, 旨在产生尽可能不相似的 SAT 解; 而 dProbSAT 则是本文提出的
ProbSAT [37] 求解器的一种改进版本. 值得说明的是, 算法 2 同时采用了两种类型的 SAT 求解器, 其原因在于: 既往
研究工作已表明, 无论是针对软件产品线配置问题 和还是测试问题 [33] , 这都是一种生成新解/个体的有效策略.
此外, 与文献 [33] 一样, 调用 CDCL 和 SLS 求解器的概率分别设置为 1− P r 和 P r . 但与文献 [33] 直接采用原始的
ProbSAT 求解器不同的是, 算法 2 中的 SLS 类型求解器 (即 dProbSAT) 也是一种多样性求解器. 它的基本思想是:
借助概率向量产生一个多样化的初始解 (称为“种子”); 若该初始解不可行, 则调用原始的 ProbSAT 予以修复.
算法 2. c ← DiverseSATSolving(p).
r ← rand (0, 1) // 是位于 [0, 1] 区间的随机数
1. r
P r 为控制参数
2. if r < 1− P r do //
c ← rSAT4J() //随机化的 SAT4J 求解器 (CDCL 类型)
3.
