基于混沌遗传算法的测试用例自动生成研究*

黄陈辉 吴海涛 阮江涛 钱 程

（上海师范大学信息与机电工程学院 上海 200234）

1 引言

软件测试自动化是对程序自动生成测试数据，近些年越来越引起计算机研究员的关注。智能寻优算法［1］能更好、更快地解决复杂的软件测试问题，如蚁群算法［2］、模拟退火［3］、遗传算法［4］等。其中遗传算法使用最为广泛，因为它可以高效处理全局优化、多峰值等问题［5］。

遗传算法解决测试用例自动生成问题是学者们争先研究的热点。例如郑超群等提出改进的交叉、变异算子，增加种群多样性来避免过早收敛［6］，但改进效果不明显；丁蕊等［7］使用启发式搜索来提高测试用例生成效率，但算法并行性没有充分利用，性能改进不明显；高雪笛等［8］改进算法适应度函数设计，提高算法收敛速度，但仍不能很好解决大规模计算量的问题，使算法迭代后期种群失去多样性。同时他们忽略了遗传算法对初始种群有一定依赖性，随机生成方式已限制了寻找最优解过程［9］。针对上述方法不足，本文设计了以下改进策略：1）反向学习机制初始化种群，使得初始种群更靠近最优解；2）改进适应度函数设计方式；3）使用混沌序列优化遗传算子的交叉、变异操作，提高算法的全局寻优能力。

2 相关背景知识

2.1 反向数字

反向学习概念是Tizhoosh. H 于2005 年提出的，并证明它在现有学习方法的上的有效性［10］。假设正在搜索估算x（给定问题的解），那么先应该计算相反的数字。

定义1（反向数字）

a，b分别是 [a，b]区间中的上下限，x是源数，x~ 是源数的反向数字。

基于反向学习定义如下：假设f(x)为适应度函数，g为评价函数，为x∈[a，b]的反向值，每次迭 代 中 计 算 的 是f(x) 与的 值 ，当时，学习继续，否则用。

考虑反向个体，选中更靠近的作为种群最初个体，那就是每个个体都离最优解更近一步。

2.2 Logistic映射

混沌的遍历性可以根据自己规律遍历非重复的所有状态［11～12］这一特性可以用来避免陷入局部最小解。本文使用logistic映射生成混沌序列。Logistic混沌映射概述如下。

Logistic 映射是一个一维映射，却具有混沌模型所拥有特征和性质。方程如式（2）所示：

式中μ为控制参数，且0 ≤μ≤ 4，0 ≤x≤ 1。该模型能准确表现出生物群体数的波动与时代变化的关系。若n表示进化代数，那么xn表示第n代的出生数，xn+1表示第n+1 代的出生数。μ∈（3.56994，4］，映射处于混沌状态。映射不变集为区间（0，1）。本文使用参数值为μ=4。

2.3 遗传算法

遗传算法在实际应用中需要目标语言的合理子集［13］。因此将遗传算法形式化表示为

表1 符号的含义

3 基于混沌遗传算法生成测试用例

3.1 测试用例生成模型

测试用例集表示为测试用例ti集合T。给定|T|=n，有T={t1，t2，…，tn}。其方法模型如下：

图1 混沌遗传算法的测试用例自动生成方法模型

首先分析被测程序，生成T的结构和属性说明。其次，插入变量动态跟踪T的行为，具体操作：程序分支子关键点（即分支节点的两个互为兄弟的后置关键点）插装变量，赋初值1，当执行经过该分支节点，值赋值为0。测试数据执行路径101010，101001，100110，100101，011010，011001，010110，010101。测试反馈信息是构造适应度函数的重要依据，目标路径剔除不可行路径和随机法很容易生成测试数据的路径。最后，用正确表示的测试数据运行插装后程序，利用混沌遗传算法遗传操作测试数据，使得可以生成针对目标路径的测试用例。

3.2 编码方式

本文采用二进制编码级联法，三角形分类程序参数类型为数值型。设被测程序三个输入取值范围为［0，63］，那么二进制表示参数有6位，即6个基因，分别为 10010，010010，111000，二进制级联编码后就是10010010010111000，它们形成的整体称为个体，即该问题的染色体。

3.3 反向学习种群初始化策略

求解测试用例自动生成问题中，需使用反向学习的策略来初始化随机生成的最初种群。需求解个体基因的反向基因，具体表述如下：设程序输入范围为［0，2n-1］，那么有

式（6）生成个体基因反向数字，生成新个体（反向个体）。方法步骤如下：

算法1 基于反向学习的种群初始化算法

输入：均匀随机数

输出：初始种群p0

step1均匀生成一批随机数，组成最初种群Initial_P；

step2对Initial_P每个个体基因利用公式（6），取反向基因，生成新个体，即反向个体；

step3 将step2 生成的反向个体组成反向种群Initial_P'；

step4 从最初种群Initial_P 和反向种群Initial_P'中依次取个体，计算适应度函数值，得到适应度函数值，再组合适应度更高的个体，将其放进最终初始种群的对应位置中；

step5生成初始种群p0，参与遗传算法进化。

3.4 适应度函数的设计

测试数据生成可以描述如下：对于给定程序P和P的路径，认为D是P的输入空间，当x(x∈D)作为输入数据时，程序执行期间将会导致路径u被覆盖。适应度函数的形式化表示：

其中，u(x)表示个体x覆盖的路径；ui为待覆盖的第i条路径；b(ui，u(x))表示两条路径的层接近度，其值为从第1 个分岔点开始ui与u(x)的不同分支语句的个数；|ui|是目标路径ui中包含的分支点的数目；m(ui)是路径ui测试数据集中测试数据的个数，越易覆盖的路径会有越大的测试数据集，将会导致是适应度函数越低。

3.5 遗传操作

1）选择操作

本文采用轮盘赌个体选择方式复制符合要求的个体到新种群，值越高被选择概率就越大。

2）混沌交叉

传统遗传算法容易陷入早熟，收敛到局部最优，同时上述适应度函数设计使测试数据易汇集在已生成测试数据的路径，需要改进交叉方式，提高遗传算法搜索范围。具体操作如下：

（1）首先控制交叉操作的频率

任取一个初值x0，如果p小于x0的情况下，可以进行交叉；反之，则不交叉。即：

式中pc是预先选定的值，将交叉概率设置为0.9，使得种群中可以较充分交叉。

（2）混沌序列确定交叉点位置

设有L 位长染色体，在（0，1）区间上随机取一个数xn为初值，产生（0，1）区间混沌序列xn+1。公式q=(int)xn+1*L把序列映射至染色体基因位空间，使交叉发生在此位置，形成新子代，仅更换部分点基因，改动较小，这样可避免在产生子代过程中种群发生寻优抖振问题。

3）混沌变异

同上所述，变异操作的进行也可以由产生的混沌序列来控制。理论基础同上，不做赘述。

对个体进行混沌交叉，混沌变异操作，首先，两两随机组合种群内的各个体，在此基础上生成的每对组合，由系统随机生成一个（0，1）之间的随机数，由交叉概率决定是否交叉，若交叉，则采用经线性映射的混沌序列xn+1，所对应的位置进行交叉操作，否则，看下一对。

混沌不重复遍历特定范围内的所有状态用来避免陷入局部最优。它对初值敏感可以保证即使两个最佳解是非常接近的，但仍然是两个完全不同的染色体，因此种群可以保持多样性。

3.6 混沌遗传算法步骤

综上所述，本文提出的生成混沌遗传算法测试用例自动生成的流程和算法流程图如图2。

图2 基于混沌遗传算法测试用例自动生成流程

1）初始化参数：随机生成最初种群，初始种群规模，交叉和变异概率，最大迭代次数；

2）种群初始化模块：先生成最初种群，利用反向学习对个体基因求解反向数字，新生成的反向个体与最初个体同时求适应度函数值，选择适应度函数值高的进行下一步操作；

3）运行插装后的程序，求解初始种群的适应度函数值；

4）遗传操作：通过轮盘赌选择策略选择进入下一代的种群，同时通过混沌序列决定遗传算法的交叉、变异操作，首先控制交叉（变异）操作的频率，决定交叉（变异）与否，如果交叉（变异），再根据随机生成的混沌序列来选择需要进行交叉或者变异的位置。

4 实验分析

本文选择了6 个不同规模程序作为被测程序，来评价提出的方法的性能，同时与其他方法对比，并进行结果分析，所有方法均采用Matlab 软件环境，实验回答了以下两个问题：

Q1：与其他方法做对比，本文提出的方法是否能够达到更高的路径覆盖率？

Q2：与其他方法做对比，本文提出的方法是否具有较少的时间消耗？

4.1 被测程序基本信息

实验分别采用三角形分类实验程序，3 个数排序，interserve，totino，spice，schedule2 为被测程序，本文选取4 个工业测试程序，它们被大量应用于测试用例的生成中［15］。

表2 被测程序的基本信息

4.2 实验方法和评价体系

本文方法（记为ICGA），通过与标准遗传算法（SGA），改进后的遗传算法（IGA）作对比，来分析改进后的算法性能。选择操作为轮盘赌。遗传操作中的交叉方式为为单点交叉，概率为0.9；变异方式为单点变异，概率为0.1。所有方法的种群规模都为50，最大迭代数为1000。

对于不同方法均采用以下指标进行性能比较（每种方法分别独立运行50次）：

1）路径覆盖率（cov），表示为测试数据覆盖的路径数与所有路径数的比值。

2）测试数据生成时间（t），是指生成测试数据所需要的时间。

4.3 实验结果

为了验证被测程序目标路径的覆盖率，运用不同方法做对比，实验结果如表3。

为了验证被测程序的测试数据生成时间，运用不同方法做对比，实验结果如表4。

表3 不同方法对被测的程序路径覆盖率

表4 不同方法对被测程序程序的测试数据生成时间（s）

4.4 实验数据分析

根据实验结果，可以逐一回答前文提到的问题Q1、Q2。

Q1：表 3 可以看出，在 3 个数排序，interserve，totino，spice，schedule2 中达到了最大路径覆盖率，就等于说本文的方法模型适合于测试数据自动生成。IGA 在三角形分类程序有轻微优势，说明对某些应用程序优先选择易覆盖路径，将进一步提升方法性能。

图3 不同方法对被测的程序路径覆盖率

图4 不同方法对被测程序程序的测试数据生成时间（s）

Q2：结合表3、表4 本文方法对于程序3 个数排序，interserve，totino，spice，schedule2，达到最高覆盖率同时，时间总是最少的，对于三角形分类程序虽然覆盖率略低于SGA 和IGA，但本文方法生成测试用例时间少于前两者。随着程序规模扩大，本文方法实用性更强。

5 结语

本文改进了种群初始化策略、遗传算法交叉、变异操作和适应度函数的设计，提高了算法的全局寻优能力。实验验证本文方法在测试用例自动生成方面优于其他方法。随着软件测试的免疫能力越强，越需要增加其他覆盖要求，这也是值得进一步研究的问题。