基于遗传算法的测试用例自动生成技术研究

马志兵　余荣学　周丽平

摘 要 本文对应用遗传算法解决测试用例生成过程中的关键技术进行了分析，在突变因子选择、染色体编码和适应度函数设计等方面进行了分析、改进，最后结合经典算例对改进进行了验证。

【关键词】测试数据自动生成 GA 控制变异位置 改进自适应遗传算法

1 引言

遗传算法作为一种基于自然选择原理和遗传机制的通用搜索算法，与其它搜索算法的不同之处在于它在整个搜索空间随机采样，按一定的评估策略对每一样本评价，并采用特定的算子进行样本优化，直至产生最优解。本文阐述了用遗传算法作为核心搜索算法生成软件测试数据的方法和技术，对突变因子选择、编码策略和评价函数构造等问题进行了分析和改进，最后通过经典三角形判别问题检验了改进算法的有效性和使用效率。

2 遗传操作

2.1 编码策略

遗传算法工作于参数的编码而非参数本身，要求把问题的解空间表示为在某个有限字母表上的有限长度的串.因此用遗传算法生成测试数据时，首要的问题是寻求适当的映射方式f，使得被测程序的输人参数{x1，x2...xn}， 能够表示成一种适当的编码形式：

f：{x1，x2...xn}→{cI，c2，.. ，cn}

遗传算法在运行时，遗传算子g对参数编码进行操作，改变其结构，形成新的编码：

g：{cI，c2，.. ，cn}→ {cI`，c2`，.. ，cn`}

f逆映射f-l解码得输人参数的当前值 ，{x1`，x2`...xn`}即

f-1：{cI`，c2`，.. ，cn`}→ {x1`，x2`...xn`}

如果当前参数值{x1`，x2`...xn`}不满足终止条件，遗传算子g将重复上述过程，直至找到目标参数值。参数值到编码的映射f的选取应遵循以下几个原则：

（1）输人参数所能取得的任何值都应存在相应的唯一编码；

（2）任何一个编码都应存在唯一的参数值与之对应；

（3）选择使问题得以自然表达的最小字母表进行编码；

（4）编码方法应和问题本身的相关性大、结合紧密。

2.2 遗传策略

通过遗传算法寻找最优解时，能够较快地逼近目标值，但是从逼近目标值到最终找到目标值这一步跨越是较为艰难的，所花费的代价甚至比前面逼近的过程还要大。通过对交叉算子和突变算子的改进，来提高遗传算法的搜索效率，避免陷入局部最优解。

2.2.1 交叉算子

最简单的交叉算子是单点交叉，它是在种群中任选2个个体，并在个体位串上随机选取一个交叉点，然后将2个位串的尾部互换，形成2个新的个体。当参数个数增多，位串长度加长时，仅采用单点交叉，位串的结构改变很小，不利于新信息的引入，导致搜索效率降低。为此设想对交叉算子做如下形式的改进：

（1）增加交叉点。变单点交叉为多点交叉。多点交叉较之单点交叉总体效率取得了一定的提高，但也存在着明显的问题：由于交叉点是随机确定的，因此当交叉点在整个位串上分布不均匀，特别是在交叉点过分集中于某一个或少数几个参数的位串上时，交叉操作对位串上，从而消除当突变点过分集中于少数参数的位串时，突变操作对这些位串破坏过大，而多数参数的位串却无法引入新的信息所造成的不利影响。

（2）控制突变位置。实验中发现，用遗传算法生成测试数据能够较快地逼近参数的目标值，然而实现从逼近目标值到最终找到目标值这一步决定性的跨越却是较为艰难的，所花费的代价甚至比前面逼近的过程还要大，此时如何提高搜索效率显得尤为重要.爬山法中探索性搜索的思想给我们带来了很大的启发，我们有意识地控制使参数位串上最不重要的几位（位串的末几位）发生突变 ，这相当于给参数的值增加或减少了一个小的步长。从而有可能以较小代价找到参数的目标值。因此我们在遗传操作时设定一阀值p，若某一染色体的适应值大于p，说明此染色体逼近目标值。那么使得此染色体低位发生突变。按如下公式进行变化：

i=random（n）

pos=

其中p为给定的阀值，对于不同的适应度函数p的值不同，往往把p设为最接近目标路径的适应值；f为变异染色体的适应值；n为参数个数；L为给定的单个参数的编码长度；a根据情况取2—L之间的值。

2.2.2 突变方式

M.Srinivas提出的自适应遗传算法中，交叉率Pc和变异率Pm是基于个体的适应值来自适应地进行改变。但该算法仅对群体处于进化后期时比较合适。在本文改进的自适应遗传算法中，对应于群体中最大适值的个体的交叉率和变异率分别取为Pc2和Pm2，而在基本的自适应遗传算法中最大个体的交叉率和变异率为0。这就相应地提高了群体中表现优良的个体的交叉率和变异率，使它们不会处于一种近似停滞不变的状态。交叉率和变异率的改进自适应公式如下：

Pc1 =

Pm1 =

fmax代表群体中最大适值；favg代表每代群体的平均适应值；f'代表要交叉的两个个体中较大的适值；f'代表要变异个体的适值。Pc1、Pm1分别代表个体的交叉率和变异率。

运用自适应遗传算法的一个实际问题是，最优个体仍然会以较大的交叉率和变异率进行遗传操作，从而较好的个体被破坏。本文采取最优保存策略来保留最优个体，在选择前或选择后保留当前最优解的遗传算法最终能收敛到全局最佳值。最优保存策略可保证当前的最优个体不会被交叉、变异等遗传运算破坏，这是本文改进的自适应遗传算法收敛性的一个重要保证条件。

3 适应度函数的设计

适应函数的优劣将直接影响遗传算法解决问题的效率。好的评价函数应该更好地体现背景知识，从而更有利于引导算法朝向更优的解空间搜索。在用遗传算法生成测试数据这一问题上 ，我们的目标是构造一个能更好地评价所生成的测试数据的优劣，并能引导算法最终找到覆盖指定路径的测试数据的函数。

利用海明距离来做评价函数的方法，在被测函数单元内部的各个分支点前和分支内部，通过函数插装的方法分别插入一个分支函数。该函数通过一个boolean型数组path来记录执行过程中是否执行过此分支。如果程序执行过此分支，则数组path中相应位置的值为T，否则为F。这样对不同的路径，数组path有不同的值。这样如果事先选定一条目标路径，求能满足它的测试数据。则可以有一组有序的T、F符号集合唯一标识它，假定其为α；用某组测试数据执行被测函数，可以得到一个boolean型数组path标识其执行的实际路径，假定其为 β，则实际路径和目标路径之间的差异可如下表示：

fit=

same（α，β）：数组α，β中对应位置为T的个数。

getlarge（α，β）：数组α，β中值为T的个数。

fit称为相似度，表示目标路径和实际路径之间的相似程度，越接近 1，表示测试数据越满足要求，故把fit作为适应度函数。

4 对比分析

为了对比客观，分别采用基本遗传算法、控制突变位置法和自适应遗传算法生成测试数据，基本参数指标如表1所示。

对于等边三角形问题，我们令控制突变位置参数p=0.8，a=3；改进的自适应遗传算法中Pc为0.8，Pm为0.08，Pc2为0.1，Pm2为0.01。

我们分别用基本遗传算法（BGA）、控制突变位置法（CGA）和自适应遗传算法（AGA）生成10次等边三角形用例，记录其产生目标用例的代数和执行时间，三种方法的平均代数和每代的平均执行时间如表2。

从表2数据可以看出，控制变异位置法和改进的自适应遗传算法由于包含了较多的计算过程，因此产生新一代群体时用的时间比基本遗传算法要长；控制变异位置法搜索到目标值所经历的群体代数最少，提高了搜索效率。

5 小结

本文对遗传算法用于生成测试用例的方式进行了改进。为了提高初始种群的适应度，引入了局部加速方法；针对用例生成的大空间搜索问题，引入了变长染色体编码策略；针对测试程序的参数个数和编码长度不同，对遗传算子进行了改进；介绍了控制变异位置法和改进的自适应遗传算法，来提高遗传算法的搜索效率。通过经典三角形问题实验证明改进方法有效，有利于提高种群的搜索效率。

参考文献

[1]荚伟，高仲仪.基于遗传算法的软件结构测试数据生成技术研究[J].北京航天航空大学学报，1997，23（1）.

[2]王小平，曹立明.遗传算法——理论、应用与软件实现[J].西安：西安交通大学出版社，2001.

作者单位

1.中国电波传播研究所 山东省青岛市 266071

2.青岛理工大学琴岛学院 山东省青岛市 266106