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

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

向量的种子生成策略与 ProbSAT 相结合, 当然也可以与其他任何 SLS 求解器相结合. 另外, 第 5.5.1 节的实验结果
表明, 在多数情况下, 仅引入基于概率向量的种子生成策略即可显著提升测试效果. 因此, 在算法设计时, 本文以简
洁性和灵活性为重要原则, 仅关注基于概率向量种子生成策略, 而保持 ProbSAT 的内部随机搜索机理机制不变.
4.3 测试集的归档策略
算法 2 产生的多样化的测试用例将被加入测试集 TS. 为维护测试集的多样性, 本文采用了两种归档策略
GlobalArch (见算法 4) 和 LocalArch (见算法 5), 它们均是根据 NS 算法的思想设计的, 分别考虑了测试集的全局和
局部多样性. 我们从详细介绍全局归档策略开始. 如算法 4 的第 1 行所示, 合并新产生的测试用例{ tc }与测试集
TS 得到扩展测试集, 记作 TS . 接着计算个体 c ∈ TS 的新颖得分 (novelty score) [38] , 其定义如下:
′
′
1 k ∑
′
ρ(c,TS ) = d(c,tc ) (4)
′
i
k
i=1
′
′ TS 中与 第 c 的第 k 明确了参与新颖得分计算的邻居个
其中, tc 表示集合 c i 近的个体, 称为 i 个“邻居”. 超参数
i
′
′ tc 之间的距离. 本文采用公式 (5) 定义的 anti-Dice 距离. 研究表明 [33] , 对于软件产品线测
数. d(c,tc ) 表示个体 c 与 i
i
试问题, anti-Dice 是一种有效的距离测度. 注意公式 (5) 的测试用例采用集合形式的表示方法 (参考定义 2).
|c∩tc | ′
′ i
d(c,tc ) = 1− (5)
i ′ ′
2|c∪tc |−|c∩tc |
i i
新颖得分是 NS 算法中的核心概念, 它度量了个体所在区域的拥挤程度. 新颖得分越高, 说明个体所在区域越
稀疏, 反之则越密集. 通过不断搜索更新颖的个体 (即新颖得分更高的个体), 可逐步提高档案的整体多样性, 这正
好契合了基于相似性的软件产品线测试所追求的目标.
算法 4. TS ← GlobalArch(TS,tc) .
′
1. TS ← TS ∪{tc}
c ∈ TS do
′
2. for each
3. 根据公式 (4) 计算测试用例 c 的新颖得分 tc closest
ρ(tc,TS )
′
4. end for
5. 找出测试集 TS 中新颖得分最小 (最差) 的个体, 记为 tc worst
′
′
6. if ρ(tc,TS ) > ρ(tc worst ,TS )
tc 替换 TS
7. 用 中的 tc worst
8. 更新概率向量: p i ← p i +(tc i −tc worst,i )/N , 其中 i = 1,2,...,n
9. end if
10. return TS
算法 5. TS ← LocalArch(TS,tc) .
1. 找到 TS 中与 tc 距离最近的测试用例, 记为
2. 根据公式 (4) 计算测试用例 tc 的新颖得分 ρ(tc,TS \{tc closest })
3. 根据公式 (4) 计算测试用例 tc closest 的新颖得分 ρ(tc closest ,TS )
4. if ρ(tc,TS \{tc closest }) > ρ(tc closest ,TS )
tc 替换 TS
5. 用 中的 tc closest
6. 更新概率向量: p i ← p i +(tc i −tc closest,i )/N , 其中 i = 1,2,...,n
7. end if
8. return TS