基于佳点集遗传算法的多路径覆盖测试用例生成*

程孟飞 丁 蕊

（牡丹江师范学院 牡丹江 157011）

1 引言

在软件开发的整个进程中，软件测试是保障软件质量的重要手段［1］。随着软件规模的不断增加，人工进行软件测试需要消耗大量时间和资源。对于面向路径覆盖的测试，如何在降低测试数据自动生成成本的同时提高软件质量，是具有重要意义的研究问题。

基于遗传算法的多路径覆盖的测试用例生成是指通过一次运行遗传算法搜索到覆盖被测程序中所有可行路径的测试用例，以提高软件测试效率，降低人工测试成本。软件工程领域的众多学者对智能优化算法多路径覆盖测试数据生成技术进行了深入的研究。Ahmed［2］首次提出多路径覆盖测试数据生成方法，设计层接近度与分支距离相结合的适应度函数，与单路径覆盖测试数据生成方法相比，多路径方法只需一次运行就能找到覆盖所有目标路径的测试数据，大大提高了测试效率；我们曾提出一种基于关键点的多路径测试数据生成方法［3］，通过易覆盖路径和测试数据提供的信息用遗传算法生成难覆盖路径的测试数据，提高了测试效率，基于此，又提出一种基于烟花爆炸的测试数据生成方法［4］，将启发式信息融入烟花爆炸算法，进一步提高了测试效率。

Liu［5］等认为基于路径覆盖的测试用例自动生成是一个黑盒优化问题；为此，姚香娟［6］等训练神经网络模拟适应度值生成过程，降低了运行程序带来的时间消耗；因此，面向路径覆盖的测试用例生成作为一个黑盒问题是NP难问题，遗传算法能有效解决此类复杂系统问题。但遗传算法的搜索能力及迭代速度有限，在进化过程中容易出现过早收敛以及收敛速度慢等问题。

佳点集遗传算法（Good Point Set Genetic Algorithm，GPSAG）是张铃教授提出的一种改进的遗传算法［7］，其作为一种改进的遗传算法已被成功应用到特征选择［8］、测试用例优先级排序［9］等研究领域。该算法通过佳点集理论构造出了一种佳点集交叉算子，佳点集交叉算子生成的个体不仅保留了双亲优秀的基因，还能通过佳点算子产生佳点序列，避免种群个体寻优抖振，陷入局部最优解，使遗传算法在收敛速度以及搜索精度都得到提升。因此，本文提出将佳点集遗传算法融入到面向路径的测试用例生成中，针对白盒测试中的路径覆盖测试用例生成问题，利用个体穿越路径与未覆盖路径的相似度和分支距离作为适应度，采用佳点集交叉算子和混沌交叉算子进行交叉操作生成子代个体，以加快遗传算法效率。

2 相关背景知识及定义

2.1 混沌映射

混沌映射［10］是一种确定性系统产生的随机序列，遍历性和普适性的性质使它用来代替随机生成方法，可以使元素均匀的分布在空间中，避免随机方法产生序列的不均匀以及盲目性问题。本文用Logistic映射生成混沌序列来代替佳点序列。式（1）给出了Logistic映射产生的混沌序列：

其中zn表示生成的第n个种群个体，μ用来控制zn在［0，1］范围内，一般取μ∈[0，4]。

2.2 佳点集的定义与性质［7］

定义1佳点集

令r∈Gt为t维欧氏空间中的单位立方体中一点集，若形为Gt中的一点集Pn(i)={(r1×i，r2×i，…，ri×i，)，i=1，2，…，n}的 偏 差O(n)满 足O(n)=C(r，X)n(-1+X)，其中C(r，X)是只与r，X（X是任意小的正数）有关的常数，则称Pn(i)为佳点集，r称为佳点。取rk=2 cos(2πμ/p)，1≤μ≤t，p是满足(p-t)/2≥t的最小素数，则r是佳点。取rk=ek，1≤k≤t，则r也是佳点（分圆域）。

2.3 遗传算法

遗传算法（Genetic Algorithm，GA）是一种全局启发式优化算法，被广泛用于函数优化、组合优化、机器学习、信号处理、自动控制和软件测试数据自动化生成等领域。基于遗传算法的测试用例自动生成的步骤是：首先在程序输入域中随机生成初始种群；然后对初始种群中个体进行编码，对被测程序进行插装，运行被测程序获得适应度值，方便后续的选择、交叉和变异操作；最后个体染色体进行一系列选择、交叉、变异使所有个体（待最优解）一同向着最优解靠近，直至找到最优测试用例集或达到最大迭代次数。因此基于遗传算法的测试用例生成是一个全局收敛算法，但标准遗传算法在进化过程中容易出现过早收敛和收敛速度慢的问题，影响算法进化效率。

3 基于佳点集遗传算法的测试用例生成方法

3.1 面向多路径覆盖测试用例生成的佳点集遗传算法

本文借鉴佳点集理论设计佳点集交叉算子进行面向多路径覆盖的测试用例自动生成，并提出两点改进：一是根据个体穿越路径与未覆盖路径集之间的相似度构造层接近度和改进分支距离的适应度函数；二是针对佳点集遗传算法在实数编码的情况下，出现佳点集交叉个体溢出问题，提出一种适于实数编码的混沌交叉方法，提高算法搜索效率。

本文提出的基于佳点集遗传算法的测试用例生成方法模型如图1所示。

图1 基于佳点集遗传算法的测试用例生成模型

3.2 混沌交叉算子

交叉是增加种群多样性的重要途径，在佳点集交叉过程中，k值是构建佳点集序列的重要参数，不同k参数会生成不同的佳点集交叉后代。若选择多个交叉后代作为子代个体，容易造成子代个体中相似度过高，导致个体失去竞争力而过早收敛；但对于目标路径相似度低的程序，多个子代个体又可以加快种群进化。因此，根据不同程序选择不同数量的交叉个体是提高种群进化效率的关键。本文中选择k取1时的单子代以及k取1和k取2时产生的双个体进行测试用例生成，以比较说明佳点集遗传算法的实用性，并针对不同被测程序的编码方式设计不同的交叉方式。

对于二进制编码的程序，选择佳点集交叉算子［7］。

对于实数编码的程序，由于二进制编码中生成的佳点集处于［0，1］之间，将佳点集映射到实数搜索范围会导致个体跳出搜索范围，为此本文提出一种混沌交叉算子，其与佳点集交叉算子类似，认为相同基因片段为优秀片段，并将其遗传到子代个体的相同位置。即混沌交叉算子与佳点集交叉算子的不同之处在于，将个体不同位置的元素用混沌映射生成的混沌序列替换，生成子代个体，参与进化，基因保留策略和混沌的遍历性可以使生成的个体既保留双亲优秀基因又能防止个体基因单一造成的过早收敛问题。图2给出了混沌交叉过程。

图2 混沌交叉过程

3.3 适应度函数

在遗传算法进化过程中，适应度函数指的是在遗传算法进化过程中对个体进行评价，是体现优胜劣汰的重要过程。本文设计个体穿越路径与未覆盖路径的相似度与分支距离相结合的适应度函数，宏观上，综合考虑个体穿越路径与所有未覆盖路径之间的相似度之和作为个体适应度值，可以使已覆盖路径的测试数据启发式信息引导搜索未覆盖路径，微观上，鉴于分支距离过大可能会使相似度信息无法发挥作用［11］，设计规范化的层接近度［12］设计适应度函数，以提高搜索效率。适应度函数形式化如下。

其中，b(x，xi)Ci表示第i个个体穿越路径与未被覆盖路径的相似度，cj表示第i个个体与第j条目标路径之间的层接近度di，bi表示分支距离［13］，branch指的是个体在所有路径上的分支距离和的规范化处理，bi越小branch就越大，个体越优，因此适应度函数越大，个体就越好。

3.4 基于佳点集遗传算法的测试用例生成方法伪代码

算法2给出了GPSGA的伪代码，其中，算法终止条件设置为找到覆盖所有目标路径的测试数据或达到设定的最大迭代次数［14］。

4 实验

为验证所提方法的性能，本文选择基准程序和工业程序进行实验。所有程序在Matlab2016软件环境下运行，Windows XP操作系统，机器主频是2.80GHz，内存为8 GB，混沌控制参数μ=4。应用遗传算法（GA）、双后代佳点集遗传算法（Two Offspring Good Point Set Inheritance，TOGA，指使用k取1和2时的双后代作为子代个体）、和本文提出的方法（GPSGA）生成测试用例，通过实验旨在回答以下三个问题：

1）所提算法的进化代数是否低于遗传算法？

2）所提算法在时间损耗方面是否优于遗传算法？

3）所提算法的覆盖率是否优于遗传算法？

实验选择三角形分类程序、冒泡排序、sed和flex为被测程序，它们被广泛应用于软件测试研究领域［15］。三角形分类初始种群规模设置为50，最大迭代次数50，冒泡程序种群规模为30，最大迭代次数20，其他参数设置如下：交叉概率0.9，变异概率0.1，搜索范围［0，255］，二进制编码，混沌交叉，单点变异，每种算法运行50次，取平均值，sed和flex程序都采用实数编码，混沌交叉，单点变异。当实验终止时，记录所有算法的进化代数、运行时间和覆盖率。表1给出工业程序的基本信息，表2给出了被测程序的实验结果。

表1 工业程序信息

至此，根据上表中的实验数据结果，我们可以逐一回答之前的问题：

1）由表2可以看出，GPSGA和TOGA运行的进化代数都少于GA算法，这是因为使用具有启发式信息的适应度函数以及实数编码下的混沌交叉算子，说明基于佳点集遗传算法的测试用例生成方法能提高进化效率。

2）表2实验数据表明，在三角形分类和flex程序中，TOGA运行时间最长，这是因为佳点集交叉后生成的双后代个体导致种群相似度高，降低了种群的多样性；但在所有程序中GPSGA运行时间均少于GA和TOGA，这是因为设计的佳点集交叉算子能够防止个体单一，陷入局部最优解，说明基于佳点集遗传算法的测试用例生成方法能加快收敛速度。

表2 被测程序实验结果

3）由表2可知，GPSGA和TOGA运行的覆盖率都高于GA算法，说明基于佳点集遗传算法的测试用例生成方法提高了路径覆盖率。

值得一提的是，在sed程序中TOGA算法占优势，而在flex程序中，GPSGA算法较好，这是因为sed程序目标路径之间相似度低，局部最优解少，不易陷入局部最优，而flex程序中目标路径之间相似度大，种群中个体相似度过高会导致算法减慢，因此针对易陷入局部最优的程序采用GPSGA算法，局部最优解少的程序采用TOGA算法。

5 结语

本文利用佳点集误差小精度高的优点，将佳点集遗传算法融合到面向多路径覆盖的测试用例生成中，设计混沌交叉算子以及相似度信息引导搜索的适应度函数，实验表明，本文方法能够有效减少进化代数和测试数据搜索时间，并获得更高的路径覆盖率。

未来，我们将通过动态增加种群多样性来改善单位空间中佳点集算子产生个体的稀疏性问题，以期能进一步加快测试用例生成效率。