基于遗传算法的MOTCP方法

晏慧，康茜，雷建云

(中南民族大学 计算机科学学院，武汉 430074)

软件测试是保障软件质量的重要手段,是构建高可信软件的关键环节.软件测试占软件开发总成本的比例一般达到50% 以上[1].为了修复软件中未发现的问题或者满足客户提出的新的需求，常常需要对软件不断地修改，软件迭代过程中容易引入新的缺陷，导致软件质量受到影响.回归测试可有效解决此类问题，避免软件演化带来的副面影响.最简单的办法是将所有测试用例重新执行一遍，但存在如下问题：

(1)如果项目复杂，测试用例集庞大，执行所有代码代价较大，会导致超出项目预算或者延长软件开发周期.例如ROTHERMEL等人在某一合作企业内，在测试一个包含约20000行代码的软件产品时发现，运行所有测试用例所需时间长达49 d[2].

(2)对部分代码修改会影响到被测模块的原有外部接口或内在语义，并导致部分测试用例失效[1].

这使得研究如何提升回归测试的效率变得有意义.常见的测试用例维护技术有：失效测试用例的识别和修复、测试用例选择、测试用例优先排序(test case prioritization, TCP)、测试用例缩减和测试用例扩充[3].

测试用例优先排序策略是将所有测试用例按照一定约束进行处理并排序，从而在进行回归测试时，能使用较少的测试用例检测出较多软件缺陷的算法.李征等人通过将TCP问题多项式时间规约为背包问题, 证实该问题是一个NP难问题[4].同时他引入元启发式算法(如蚁群算法、遗传算法等)求解TCP问题.但遗传算法在求解TCP问题时容易出现收敛过慢，过早陷入局部最优而导致系统停滞[5].

排序目标的选择上通常认为覆盖越多代码模块的测试用例越有可能发现更多的软件缺陷，运行时间越短的测试用例运行效率越高.传统的测试用例排序技术的排序影响因子是代码覆盖率或有效运行时间.目前绝大部分的研究都是基于单目标解决TCP问题，但依旧存在这样的困惑：覆盖率高或者运行时间短的测试用例并不能检测出缺陷.

本文针对上述问题，将具有良好群体搜索特征的遗传算法引入多目标测试用例优先级排序技术[6](multi-objective test case prioritization,MOTCP)中，并采用多个约束目标指导其排序生成.该方法在执行前对所有测试用例运用聚类判定进行分类，首先进行一次约简，缩短算法执行时盲目收缩的时间，然后选取平均缺陷检测率和单个测试用例平均运行时间为评价指标，采用轮盘赌选择算子，选择适应度较高的种群.为避免这种随机采样算法遗失优秀种群个体，采用精英保留策略保留每次种群中最优秀的10%直接复制到下一代.

1 测试用例集约简

算法开始时对所有的测试用例进行简单的约简工作，这样可以有效提高算法运行效率，减少迭代次数，避免盲目搜索而导致的收敛速度慢问题.基于同一聚类测试用例可能是冗余的测试用例[7]的判定，本文将可以覆盖同一测试需求的测试用例划分为同一聚类，因为覆盖相同需求的测试用例较大可能检测出相同的缺陷.基于此，同一聚类的测试用例只保留一份用以代表此聚类.比如存在3个测试用例集R、M、K和一个测试需求集Q，表示为R={R1,R2,…,Rn}、M={M1,M2,…,Mm}、K={K1,K2,…,Kk}、Q={Q1,Q2,…,Qq}.n、m、k分别表示其对应的测试用例集的个数，q表示测试需求的个数，则存在以下3种情况：

(1)当R中的测试用例能完全覆盖Q中的测试需求，K中的测试用例也能覆盖Q中全部测试需求时，则将R和K视为同一聚类，删除任意一个测试用例集；

(2)当R中的测试用例能完全覆盖Q中的测试需求，K中的测试用例只能覆盖Q中部分测试需求时，则将R和K视为同一聚类，删除K测试用例集；

(3)当R和M两个测试用例集能完全覆盖Q中的测试需求，K中的测试用例只能覆盖部分Q中的测试需求时,则将K与R和M视为同一聚类，删除K测试用例集.

2 多目标评价指标

本文采用平均缺陷检测率和有效执行时间为测试用例个体适应度评价函数，当平均缺陷检测率越大、有效执行时间越小时，算法结果最优.

平均缺陷检测率(average percentage of failure detection, APFD)的公式[8]如下：

其中：测试用例集为T，n代表测试用例总数，m为缺陷个数，TFi代表首个可以检查到缺陷i的测试用例在这次测试用例集中的位置.

3 基于遗传算法的MOTCP方法

MOTCP是在TCP基础上出现的一种新的排序方式，相对于传统TCP技术主要区别体现在以下两个方面：一是在优化目标的个数选取上采用两个及两个以上的目标，二是在排序算法上采用加权法或者帕累托最优[9].相比于传统的基于单目标的遗传算法，它很好地解决了结果片面性这个问题.MOTCP问题[10]描述如下：

遗传算法是仿生物学算法，属于进化算法.它模仿自然生物进化过程，通过多次迭代来寻找最优解.一般的迭代算法很容易陷入局部最优解，遗传算法通过交叉运算和变异运算能较好地避免早熟.

基于遗传算法在MOTCP问题上的应用，其步骤如下：

(1)约简：对原始测试用例集进行约简，删除冗余测试用例，产生新的测试用例集；

(2)随机产生初始群体F(0)，产生候选最优非劣解P(F(0))；

(3)判断算法是否满足测试目标条件.若满足测试目标条件，则执行步骤(9)，若不满足，则执行步骤(4)；

(4)判断算法是否达到最大迭代次数.若达到最大迭代次数，则执行步骤(9)，若没有达到，则执行步骤(5)；

(5)计算种群个体适应度函数值；

(6)根据适应度选择产生子代种群；

(7)对子代种群进行单点交叉/基本位变异运算，从而产生新的种群F(t)和新的最优非劣解P(F(t))；

(8)将P(F(0))与P(F(t))进行支配关系比较，若P(F(t))完全支配P(F(0))中的个体，则将P(F(t))替换P(F(0))，否则不更新P(F(0)).然后执行步骤(3)；

(9)算法结束，输出最后结果.

3.1 选择算子

遗传算法中的选择操作就是通过某种方式从父代中选择出个体并遗传下来.常用的选择算子有轮盘赌选择、随机竞争选择、最佳保留选择、无回访随机选择等.本文采用最佳保留选择算子，首先采用轮盘赌的方式，即每个个体进入下一代的概率等于它的适应度值和整个种群中的个体适应度值之和的比例，然后将当前适应度最高的个体结构完整地复制到下一代群体中，本文选择将前10%的优秀个体复制到下一代.

3.2 交叉变异运算设计

遗传算法中包含多种交叉运算，比如单点交叉运算、多点交叉运算和循环交叉运算等，交叉概率取值一般在0.4-0.9[11-12].同样变异运算包含基本位变异、均匀变异和边界变异等，变异概率取值一般在0.001-0.1[11].本文采用单点交叉运算和均匀变异进行种群更新操作.

单点交叉运算首先设置交叉概率，如果rand(1)产生的随机数小于设置的交叉概率，则进行交叉运算，否则不进行交叉运算.假设存在父母个体Q1和Q2需要进行单点交叉运算，首先随机产生交叉点m，将Q1与Q2中m点位前的基因(不变)保留下来，m点位后的基因进行一一对应的交换.

均匀变异运算首先设置变异概率，对每个种群的每个个体按变异概率进行变异，若个体随机概率小于变异概率，则随机产生新的有效个体替换该个体.

3.3 更新最优非劣解

求两个目标函数的最优解，采用Pareto直接法[13-14]对其进行更新，将候选最优非劣解与新产生的解进行支配关系比较，若候选最优非劣解被新的解所支配，则采用新的解作为候选最优解[15].为更直观地表示，考虑存在5个测试用例以及8个缺陷，其覆盖缺陷数以及执行时间如表1和表2所示.

表1 覆盖的缺陷数

表2 测试用例执行时间

假设A-B-C-D为其候选最优非劣解T1，则当测试用例按照A-B-C-D的顺序依次运行时，其APFD取值为50%，其EET的取值为0.026 s.此时生成新的测试用例集F-B-C-D称为T2，依次执行，其APFD取值为59%，其EET取值为0.022 s，通过T1与T2的两个目标值进行支配关系比较，显然T1被T2支配，于是用T2替换掉T1.

4 仿真实验以及结果分析

实验从以下两个方向验证本文提出方法的有效性：(1)本文提出的算法是否可以缩短测试执行时间;(2)将遗传算法引入MOTCP问题是否能提高缺陷检测效率.

4.1 实验环境设计

本实验选用开源项目CDT进行实验.CDT是完全用Java实现的开源项目，作为Eclipse的平台的插件，它提供对C/C++语言的开发支持.CDT包括CDT Core、CDT Feature Eclipse在内的9个插件.CDT Core Test可实现对CDT Core插件的测试，CDT Core每个模块及其子模块均可单独执行其测试用例(总共包含12361个测试用例).本次实验选用CDT Core中的Model模块及其320个测试用例进行实验.实验环境选用Visual Studio 2015，在Win10操作系统下运行.算法参数设定参照现有研究设置.杂交概率设置为0.8，变异概率设置为0.15，种群大小为30，最大迭代次数为500.

4.2 实验结果

将本文算法与传统的遗传算法(无约简、单目标)和多目标优先级排序方法进行比较，独立重复运行30次，需求覆盖率达到100%时或者达到最大迭代次数时停止运行.然后以平均语句覆盖率、平均EET、APFD平均值以及单个缺陷所需的平均测试用例数作为评价指标，对比分析各算法的优劣.将每个评价指标的对比结果以条状图呈现如图1和图2所示，可以更加直观地对比其优劣.

图1 平均语句覆盖率和APFD平均值实验对比

图2 平均EET值和单个缺陷测试(检测)所需平均测试用例数实验对比

由图1和图2可以清楚地看到:本文算法在这4个评价目标上均优于其他两种方法，以平均EET值最为明显，相较于单目标遗传算法减少了19.077 s，相较于多目标优化方法减少了6.659 s，这说明本文算法发挥了作用，对测试用例进行聚类约简的操作在不影响测试需求的前提下减少了参与遗传算法测试用例的总数，在多目标指导种群更新的同时采用精英保留策略则减少了找到最优解的迭代时间.平均语句覆盖率的提升不明显，首先因为选用模块规模不大，其次覆盖率不可能达到100%，所以当达到循环次数时，其基本测试用例的语句覆盖率已经接近瓶颈，所以覆盖率提升不大.而APFD的平均值的增加，单个缺陷检测所需的平均测试用例数的减少说明了本文提出的算法相对于其他两种方法达到了使用较少的测试用例找到较多的软件缺陷的目的，有效地提高了软件缺陷检测的效率，达到提升回归测试效率的效果.

5 总结

本文提出了一种基于遗传算法的多目标测试用例排序方法.测试开始前对所有测试用例进行约简，采用多目标评价算法指导种群的迭代更新，通过Pareto直接比较法得到最优非劣解，从而提高缺陷检测效率，减少了测试用例运行时间，实验证明本文提出的算法在提升回归测试效率和缺陷检测上有优势.