Page 78 - 《软件学报》2021年第9期

2702 Journal of Software 软件学报 Vol.32, No.9, September 2021

分支距离法 [28] 和层接近度法 [24] 是两个设置个体适应度的经典方法.为了便于与主要参考文献作比较,实验
选用了相同的函数(即分支距离法)设置个体的适应度.在程序的每个分支节点都插桩分支函数 f i (插桩方式见图
10),记录当前的测试用例与该分支的距离.当某分支被覆盖时,则将 f i 设为 0,若该目标路径共含有 m 个分支节点,
其总的适应度函数值 FT 的计算见公式(7):
m− 1 1
∑
i
FT = i= 0 f + 1 × 100% (7)
m
由适应函数的计算公式可以推算出,测试用例的适应度跟分支节点覆盖率成正比例关系.特别地,当程序的
每个分支节点均被覆盖时,该测试用例的适应度为 1.
例如,对于数组 int a[⋅]={3,4,2}的测试用例测试冒泡排序,参考图 10 冒泡排序插桩后的伪代码.由于 a[0]<
a[1],则第 6 行的条件语句不满足,执行第 10 行的表达式,得 f 2 =|(3−4)|=1.又由于 a[1]>a[2],该条件语句满足,此时
f 4 =0.则该测试用例与各个分支的距离为{0,0,1,0,0,0,0},此用例下分支节点个数 m=7,将数据带入适应度函数计
算公式得 FT≈0.87.

1 void bubbleSort (int i; int j; int length; int a[⋅]; int count ){
2 for (i=0; i<length; i++ ){
3 count++; fcoun t−1=0;

4 for (j=0; j<length−1−i; j++){

5 count++; fcoun t−1=0;
6 if (a[j]>a[j+1]) {

7 count++; fcoun t−1=0;
8 a[j]=a[j+1]

9 }

10 count++; fcoun t−1=Math.abs(a[j]−a[j+1])
11 } } }

Fig.10 Pseudo-code of bubble sorting program after being instrumented
图 10 冒泡排序插桩后的伪代码
3.2 测试用例生成算法
测试用例生成算法采用 Java 语言编写,并在 MyEclipse 2010 中运行.计算机配置为 Windows(Intel(R) Core
(TM) CPU i5-6500,3.20GHz,8.00GB RAM,64 位操作系统.算法的具体流程见算法 2(传统方法).
算法 2(传统方法).
输入:种群大小 pop_size,个体 individual,染色体长度 chro_size,进化代数 gen_size,交叉概率 pc,变异概率 pm;
输出:新种群.
begin
1 initialize(pop_size,chro_size); //初始化种群
2 for i←:gen_size
3 individualSign_list←quicksort(pop_size,individual);
4 fitness_list←finess(pop_size,individual,individualSign_list);
//第 3 步和第 4 步这两步种群个体测试冒泡排序,生成能表示节点距离的序列,计算个体适应度
5 individual_list←select¬(pop_size,individual,fitness_list,elitism);
//轮盘赌法选择个体
6 pop1_list←crossover1(pop_size,chro_size,individual_list,pc); //交叉产生新个体
7 mutate1(pop_size,chro_size,pop1_list,pm); //变异过程
end for
end
算法 2 是利用传统方法生成测试用例的遗传算法,采用随机方式初始化种群,轮盘赌法选择个体,以一定概