自适应遗传算法_【分享吧】基于遗传算法的测试数据生成应用研究

基于遗传算法的测试数据生成应用研究 一、引言

在测试用例设计过程中，测试数据选取与生成是一项极具挑战性的工作，随着软件规模不断扩大、复杂程度不断提高，如何在测试中尽可能地覆盖所有业务流程，往往需要经验丰富的测试人员对测试数据进行人工定义。对于非线性问题传统的数据生成方法具有效率低、冗余大、测试覆盖不完全等缺点，为此学者们提出很多解决思路，其中基于遗传算法指导测试数据自动生成是一种较为有效的方法，对提高测试质量和效率具有十分重要的意义。

二、遗传算法

1、遗传算法简介

遗传算法(Genetic Algorithm，GA)是由美国J . Holland教授在20世纪70年代提出的，通过模拟达尔文生物进化论的自然选择和遗传机制原理，用来寻找最优解的自组织、自适应搜索算法。具体操作是从初始种群出发，根据适者生存的原则，将染色体中的基因进行交叉、变异等操作机制，以实现后代个体适应度提高，直至满足预先指定的适应度阈值。

2、遗传算法中包含的基本概念

1)个体(individual)：模拟生物个体，表示所处理的基本对象、结构(这里表示一条测试用例)。

2)种群(population)：模拟生物种群，若干个体组成的集合(这里表示一组测试用例)。

3)染色体(chromosome)：个体的抽象表示形式，遗传算法中通常用字符串形式的编码表示。

4)基因(gene)：用于表示个体的特征，是染色体的构成元素。

5)后代(offspring)：种群中的个体经过遗传操作后形成的新的个体。

6)适应度(fitness)：表示个体对环境的适应程度，适应度的值是待求解问题对某个个体的满意程度。

3、遗传算法的基本要素及处理流程

遗传算法广泛应用于众多领域，究其应用方法需要针对具体问题的不同对5个基本要素进行调节：参数编码；初始种群的设定；适应度函数的设计；遗传操作算子设计；控制参数设定。遗传算法解决问题一般处理流程如图1所示：

1)将个体抽象表示为染色体的基因进行参数编码，随机选取一定数目的个体作为初始种群；

图1 参数编码处理

2)计算每个个体的适应度并判断是否符合优化标准，若符合或达到迭代次数则输出最优解并结束计算，否则转向下一步；

3)依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；

4)对适应度高的个体进行交叉和变异等操作，产生新的个体；

图2 交叉、变异运算操作

5)得到新一代的种群，返回到第2步。

图3 遗传算法处理流程

三、应用研究

以交易所业务为例，委托报入时，限仓检查流程如图4所示。为便于研究，在不考虑限仓模式、交易类型、订单类型等因素影响的前提下，取品种合约最小下单手数为1，设置各限仓参数值分别为X、Y、Z，单次委托下单手数为Q，各限仓参数设置值及单次委托下单笔数范围均为1~1000手。

图4 限仓检查流程

设计思想是将测试数据的生成问题，转化为利用遗传算法进行求解一组优化的路径覆盖。把测试数据路径覆盖的问题域映射到遗传算法的搜索空间，跟踪并记录每一组测试数据的执行路径，以最大化执行程序路径的覆盖为目标，将这些适应值归并到构造出的遗传算法评价函数进行评价，就可以在少量人工干预的情况下经过多次迭代后，高效地生成满足测试目标的测试数据集。构建基于遗传算法的测试数据生成模型，其主要包含被测程序分析部分、遗传算法搜索部分、测试环境运行部分。基于遗传算法的测试数据生成系统模型如图5所示。

图5 基于遗传算法的测试数据生成系统模型

1、被测环境分析部分

被测环境分析部分是根据测试需求对被测程序进行静态分析，是整个测试模型的基础。分析程序结构确定待测试覆盖的目标路径，通过梳理程序的顺序、分支、循环等逻辑关系，对路径分支进行插桩生成桩程序，并将程序分析提取出来的参数按照编码规则进行编码。

1)被测程序静态分析：以上经过分析得到限仓检查程序流程图如图6所示，对各程序分支进行插桩“a、b、c、d、e、f、g、h”，得到四条路径“a-c-h、a-b-e-h、a-b-d-g-h、a-b-d-f”。

2)参数编码：采用二进制对参数编码，由于29≤103≤210，所以每个参数至少需要10位二进制表示(如下单678手，则编码为1010100110)，委托手数及各限仓参数值进行级联后，个体的编码需要40位二进制串表示。

图6 程序流程图

2、遗传算法搜索部分****

遗传算法搜索是测试数据生成模型的核心部分。首先根据提取出的参数范围定义初始总群及规模，将其中个体进行解码操作后生成的测试数据参数传递给测试运行部分，然后通过跟踪程序运行得到的反馈信息进行适应度值计算，根据运行后的分支覆盖率评价种群中每个个体的优劣，并通过遗传算子(选择、交叉、变异)的操作不断进化，得到最优解或达到限定的运行次数结束运行。

1)参数定义：预设种群大小为40，交叉概率为0.8，变异概率为0.05，最大进化代数为100。

2)适应度计算：由于每个参数取值区间为0 ~ 210-24，精度为1，所以对于解码后存在参数值为0及超过1000的个体进行淘汰。

3)评价函数：设被测程序中共有 m 个分支路径及 n 个输入参数，则分支函数表达式为： f 1 __(x 1 __,x 2 __,…,x n ) ,…, f m __(x 1 __,x 2 __,…,x n )，当代群体中的某个体进行解码操作后，若测试数据在运行程序中经过第 i __条路径则定义 f i=1，否则 f i=0。该问题的求解目标是最大化的进行测试路径的覆盖，那么可设计评价函数为：

根据桩程序反馈的跟踪信息，就可以得到覆盖所有分支路径的测试数据。此外，还可以自由调节各分支路径的覆盖率占比大小，如根据流程图观察可知路径“a-b-d-f”较难被覆盖，则可设置在满足全面覆盖的前提下，当目标路径的执行次数 _C abdf _与总执行次数 _C a _的比值达到设置值 k 结束运行。

**3、**测试环境运行部分

测试环境运行部分主要是运用解码后的实际参数值驱动被测程序执行，调用插桩后的被测程序将跟踪记录的信息传递给遗传算法进行适应度计算和最优种群评估，根据评判标准决定程序的运行与终止。

四、结束语

遗传算法作为人工智能领域的后起之秀，近年来已崭露头角，本文将遗传算法的思想融入基于路径覆盖的测试数据生成中，目的为测试数据自动生成带来新的解决思路，遗传算法具有传统方法不具备的强壮性和高效性，相信会对提高测试质量和效率具有十分重要的意义。
参考文献

[1] LIN T Y.Granular computing：practices,theories,and future directions[M].New York：Springer,2009：4339-4355

[2] 姚尧.一种基于遗传算法的软件测试用例生成新方法[J].计算机与数字工程,2009,37(1)：18-21

[3] 易云辉,汪闰六.基于遗传算法的软件测试用例生成系统模型[J].科技广场,2005,6(3)：18-20

[4] 张小松,王钰,曹跃.软件测试[M].北京：机器工业出版社,2006,3-40

[5] 赵明,张毅坤,沈建雄,等.基于遗传算法的测试用例生成工具的研究[J].计算机工程,2005,31(1)：13-15