基于Tent混沌的测试用例优先级排序

张 娜,滕赛娜,吴 彪2,包晓安

(1.浙江理工大学 信息学院, 杭州 310018； 2.山口大学 东亚研究科,日本 山口 753-8514)

0 引言

回归测试是指对修改后的代码进行重复测试，确认未产生新的缺陷。在软件开发过程中，频繁使用回归测试可以确保软件的质量，所以降低回归测试的成本是重中之重，而生成后的测试用例集进行排序或优化[1]是一种非常有效的方法。近年来，智能搜索算法也开始被应用于解决测试用例排序问题，如粒子群算法[2]、蜂群算法等。

目前，在已有的研究中，Yu等人[3]将软件转换为类级有向网络模型，通过杠铃模型的风险值作为排序依据，从而提高错误检出率。Zhang等人[4]通过关注三个影响因子(需求覆盖率、测试用例失效率、测试用例重要度)，动态调整测试同理优先级。Chang等人[5]基于历史信息和动态调整策略，改进测试用例优先级技术以尽早地发现缺陷。Meng等人[6]将混沌融入粒子群中，当最优粒子与普通粒子的距离小于某值时，进行混沌搜索。Zhang等人[7]将OTT策略和粒子群相结合，在测试用例重要度和失效率上具有一定优势。Zhu[8]在测试用例优先级排序中引入了缺陷影响因素，通过实验证明其可以有效保证软件产品的质量。Xu等人[9]提出粒子可以通过在混沌与稳定之间的交替运动,从而得到最优解，以跳出局部最优。Wang等人[10]通过定义失效覆盖等价划分优化选择准则来提高错误定位的有效性，不同的测试同理赋予不同优先级。Zheng等人[11]根据函数调用关系图进行关联性分析并对测试用例排序，大大减少了回归测试的成本。

结合上述研究，本文对PSO进行改进，结合了混沌算法的思想，提出了基于Tent混沌的粒子群优化算法(Tent-Chaos Particle Swarm Optimization，TCPSO)。对Tent映射引入参数，防止粒子落入小周期内，并引入带有权重函数的学习因子，两者相结合进行非线性递减变化，平衡TCPSO算法全局与局部能力，其次，对陷入局部最优的粒子及部分最差粒子进行混沌搜索优化，保证种群多样性，同时跳出局部最优，最后，以测试用例缺陷检测率作为排序的评判标准进行实验，并验证算法具有较好的寻优能力。

1 粒子群算法优化

1.1 初始化优化

在标准粒子群的初始化中，解的质量对最终结果有着重要影响，种群的速度和位置信息一般随机产生，它可以使得初始种群均匀分布，由于部分粒子可能会远离最优解，所以粒子的质量不能完全保证，从而影响算法收敛速度和最终结果。

利用混沌序列本身具有的规律性，随机性及遍历性三大特性对粒子进行初始化优化，既能保持种群多样性，同时利于跳出局部最优，改善PSO算法的全局搜索能力。映射算法一般有四种，被引用最多的为Logistic和Tent[12]两种，Dan等人[13]指出在[0，1]区间内，Tent映射产生的混沌序列与Logistic映射产生的混沌序列相比分布更均匀，所以本文在种群初始化中引入Tent混沌映射算法，并对Tent方程进行改进，以提高初始解质量。

改进后Tent映射的迭代公式如下：

(1)

其中：xk为粒子的位置信息，K为粒子的迭代次数，α，β为调度参数，取值范围[-0.1，0.1]，其作用是避免粒子落入小周期内。

Tent映射经贝努利移位变换后的公式如下所示：

xk+1=2(xk)mod

(2)

1.2 位置和速度更新

(3)

(4)

将学习因子与惯性权重相结合,两者进行相关联的非线性递减变化，公式如下所示：

(5)

其中:A，B，C为常系数。

同时惯性权重ω采用常用的指数函数递减法，用以匹配算法过程中的非线性变化特点：

ω=ωmin+(ωmax-ωmin)×exp[-20(t/T)6]

(6)

在本文提出的TCPSO中，随着每一维位置与速度信息的更新，均计算个体历史最优pid和种群全局最优pgd，而非所有维度的位置和速度信息更新完毕后，再计算pid和pgd。

1.3 混沌优化算法

混沌运动有三大特点：1)随机性，混沌类似于随机，因而具有随机性；2)遍历性，在一定范围之内，混沌能够使粒子不重复经历任何一种状态；3)规律性，虽然混沌类似于随机，但是混沌本身也有一定的规律。因此，通过混沌运动，种群在跳出局部最优的同时也能寻找全局最优。

当粒子经过几次迭代后，少数优秀粒子被保存下来，此时，粒子容易陷入局部最优，所以为了跳出局部最优，保证种群多样性，本文引入了混沌搜索进行优化。首先分别以当前粒子的最优解pid和最差的百分之20的粒子piw为基础，进行混沌搜索，产生与之对应的混沌序列，然后，以pid为基础产生的混沌序列中的最优解代替原粒子的最优解pid，以piw为基础产生的混沌序列中的粒子代替原粒子中最差的百分之20。

最优解取代的具体步骤如下所示：

步骤1：利用以下公式将最优解pid的变量取值范围[a,b]映射到混沌算法的区间[0,1]

(7)

步骤3：将m个混沌变量通过逆转换，从区间[0,1]映射到粒子群算法的取值区间[a,b]

公式如下所示：

(8)

步骤4：将混沌序列中的最优解取代原粒子群算法得到最优解pid。

最差的百分之20的粒子piw的具体步骤如下所示：

步骤1：利用以下公式将最差的百分之20的粒子piw的变量取值范围[a,b]映射到混沌算法的区间[0,1]。

(9)

步骤3：将k个混沌变量通过逆转换，从区间[0,1]映射到粒子群算法的取值区间[a,b]，公式如下所示：

(10)

步骤4：将混沌序列中的粒子取代原粒子群算法得到的最差的百分之20的粒子piw。

2 基于混沌的测试用例优先级排序

2.1 实数编码

测试用例排序是指对测试用例集TS中的测试用例进行排序，通过判断最终找到一个最优的排列，降低测试成本，能更早发现程序中的错误。本文通过实数编码表示测试用例集中每个测试用例的序号。假设测试用例集TS中有M个测试用例，那么TS的任意一个序列可用粒子X=(xt1,xt2,…,xtm)表示，其中tm表示测试用例集 TS中第m个测试用例，xtm表示测试用例tm在测试用例集TS中的序号，且1≤xt≤M。

2.2 优先级评价标准

测试用例优先级技术(test case prioritization， TCP)是一个广泛的研究热点。该问题可以描述为满足下列公式:

(∀T″)(T″∈PT)(T″≠T′)[f(PT′)≥f(PT″)]

(12)

其中:T为测试用例集，PT为测试用例集中所有的可能的排列组合，f为目标函数。

适应度函数用以引导搜索算法的搜索方向，它决定了搜索算法能否快速有效地找到全局最优解，同时粒子的适应度值反应了该粒子是否为优质解，本文目的在于对测试用例进行优先级排序，减少回归测试成本，尽早发现缺陷，所以采用标准化的测试用例程序度量标准(normalized average of the percentage of faults detected，NAPFD)计算缺陷检测率，该标准用于衡量测试用例的优先级，公式如下所示：

(11)

其中:n表示测试用例集中参与测试的测试用例个数，m表示缺陷个数，p是n中缺陷个数与候选测试用例集T中缺陷个数的比率，TFi(1≤i≤m)表示检测出第i个缺陷需要运行的测试用例个数。通过公式可以得出，当NAPFD的值越大，则发现错误的速度越快。

3 实验仿真及结果分析

3.1 实验对象

实验使用 Matlab2012a实现，基本参数设置如下：最大迭代次数K=1 000，种群规模为K=30，c2,c1参考前文所写公式(5)，ω参考前文所写公式(6)，Ω∈[0.4,0.9]，为了避免随机性带来的影响，每组实验运行100次。本文采用了四种典型测试函数验证TCPSO算法的性能，并将结果与表粒子群算法进行对比，4种测试函数如表1所示。

表1 4种测试函数表

其中函数F1函数为Sphere，F2函数为Rosenbrock,F3函数为Rastrigrin，F4函数为Griewank。为验证本文提出的TCPSO算法在测试用例排序上的有效性，本文对6个不同类型的程序进行实验，并与标准粒子群算法进行结果对比，从缺陷检测率角度进行评价，程序相关信息如表2所示。

表2 6个被测程序

3.2 实验结果分析

针对4个测试函数，本文采用标准粒子群优化算法和TCPSO算法分别进行了实验，评判标准为平均适应度值的大小，如表3所示。

表3 各测试函数的平均适应度值

从表3中可以看出，本文提出的TCPSO算法得到的函数值明显优于标准粒子群算法，搜索精度提高了5倍以上，普遍在10倍左右，其中改进后的粒子群算法在f4函数上取得了最好的优化结果，将精度提高了近20倍。实验结果表明，TCPSO算法的适用范围广泛，全局和局部搜索能力得到提高。

本文对标准粒子群优化算法和TCPSO算法分别通过表1中的 6个被测程序进行了测试用例排序实验。对于程序Print_tokens和Schedule，由于两者的测试用例较多，所以均匀地从中随机选取了56和75个测试用例用于排序实验。通过计算6个被测程序排序后的最优排列的NAPFD，以上实验进行100次，由于实验次数较多，所以实验结果用箱形图形式展现，便于整体观察分析，箱形图如图1～2所示。

图1 PSO算法对应的NAPFD

图2 TCPSO算法对应的NAPFD

通过图1和2的箱形图对比可知，TCPSO算法在缺陷检测率上明显优于标准粒子群算法，其中对于Schedule程序而言，优化程度是最高的，NAPFD将近提高百分之二十五，但对于tokens程序而已，缺陷检测率提高并不明显，两种算法的NAPFD相近，其余算法的缺陷检测率提高程度近似；count程序在PSO算法的应用中，NAPFD数值波动较大，而在TCPSO算法的应用中，较为均衡。

通过两个实验结果表明，基于Tent混沌的粒子群算法在测试用例排序问题上效果显著，在粒子寻优能力与测试用例缺陷检测率两个指标上均有优势。

4 结束语

本文将粒子群算法与混沌算法相结合，应用于测试用例排序研究中。对Tent映射添加参数，使粒子避免落入小周期内，提高了初始种群质量；学习因子与惯性权重相结合，进行非线性递减变化，用以平衡算法；对陷入局部最优和部分最差粒子进行混沌搜索优化，以跳出局部最优同时保证种群多样性。在实验部分，通过4种典型测试函数和6个被测程序对优先级排序进行验证，结果表明在粒子寻优能力和测试用例缺陷检测率上有优势。本实验用到的程序并非大型程序，如何对大型的程序进行测试用例优先级排序是进一步的研究问题。