基于遗传算法的测试用例自动生成方法综述

赫彦文，刘紫阳*，李建义，彭新宇

（1.北华航天工业学院，河北 廊坊 065000；2.北华航天工业学院航天软件联合创新中心，河北 廊坊 065000）

0 引言

软件测试是软件整个生命周期中不可或缺的一环，而测试用例生成是软件测试工作中的关键任务和难点之一。对于复杂程序，设计大量测试用例是一项耗时费力的工作。另外，软件版本的不断迭代更新对软件测试的质量与效率提出了更高的要求。倘若用例设计完全依赖人工，一方面导致测试成本高，另一方面用例可靠性难以保证。为应对这些挑战，自动化测试应运而生。而用例数据的自动生成一直是自动化测试中的难点，它不仅对测试的质量有着重要影响，而且能大幅度提高测试效率，为降低软件成本、提高软件可靠性带来很大帮助。因此，用例数据的自动生成是自动化测试领域非常具有研究价值的问题。

软件技术的快速发展以及软件功能的需求细化使得现在软件的程序结构愈加复杂，代码量愈加庞大，甚至有些程序的数据类型还由若干个成员组成，这些都给用例数据的自动生成增加了困难。近年来，随着群体智能优化算法的出现以及在解决非线性复杂问题方面的出色表现，测试用例自动生成问题的研究方向逐渐转化为通过群体智能优化算法寻优问题，即将用例生成过程转换为目标路径的搜索过程。在这方面已经有许多学者进行研究，取得了大量成果，其中，遗传算法（Genetic Algorithm，GA）解决了一系列的测试用例生成问题［1-4］，应用最多。本文主要针对遗传算法及其改进算法在软件测试用例自动生成中的应用进行系统分析总结。

1 标准遗传算法的应用

遗传算法是由美国科学家于1975 年提出的一种全局寻优算法，其思想源于达尔文的生物进化论。与其他群体智能优化算法相比，遗传算法具有较强的全局搜索能力和鲁棒性，因此广泛应用于用例数据生成。

使用遗传算法生成测试数据的主要原理是，通过构造适应度函数，使得算法不断对编码后的参数进行搜索寻优，直到找到最优解或达到最大进化代数。首先对待测程序进行静态分析，获取程序所需参数的类型、数量以及范围等信息，根据控制流程图，确定要进行测试的目标分支路径。然后，根据测试要求构造适应度函数，利用插桩技术对程序进行插桩操作，生成桩程序。最后，通过遗传算法生成覆盖目标路径的测试数据。基于遗传算法的测试用例自动生成系统模型主要分为三个模块：测试环境构造、算法模块以及测试运行，系统结构如图1所示。

图1 基于遗传算法的测试用例生成系统结构图

与人工模式相比，基于遗传算法的用例数据生成大量削减了测试用例设计所需的时间，节约了人力成本。

2 改进遗传算法的应用

2.1 改进遗传算子

遗传算子是遗传算法的核心部分，很大程度上决定着GA 的搜索能力和效率。因此，选择好的遗传算子对遗传算法的结果有着举足轻重的影响。在标准遗传算法中，交叉概率和变异概率都为固定值，导致后期种群多样性差、搜索能力差，文献［5］引入个体环境适应度和个体对种群的贡献度，通过交叉算子和变异算子的自适应变化，保证了在种群迭代过程中，即使在进化末期仍具有较强的进化能力，丰富了种群多样性，解决了算法早熟问题。文献［6］采用单点交叉，不同于标准遗传算法固定的交叉概率，适应度值未达到种群平均值的个体以一个较大的概率交叉，而达到的个体通过种群多样性函数动态调整交叉概率，当种群多样性较低时提高交叉概率，反之，降低交叉概率，在变异操作中，采用二进制基本位变异，变异规则同交叉类似，以保证个体中的优秀基因不被破坏。针对标准遗传算法的交叉算子只考虑父代的基因编码形式、却忽略个体的学习能力以及环境对个体影响的问题，文献［7］将幂律法则应用到选择算子改造中，又在交叉算子中引入环境变量，使得个体能够修复自身环境，还受环境变量的反作用，改进后的算法具有一定的学习能力。于博等人［8］对上一文献中的环境-基因双演化交叉算子又进一步修正，更改了环境变量的取值规则，算法不止面向较优个体进行群体进化，还可以在较优个体周围的空间内进行搜索。固定的遗传算子取值在后期可能会破坏较优个体或降低种群多样性，以上方法通过对遗传算子的动态改进，对算法的搜索能力起到了积极作用。

2.2 改善适应度函数

适应度函数是遗传算法寻优的关键要素，且具有唯一性，是连接算法与测试用例生成问题的桥梁，通过适应度函数可以评估相应启发式搜索算法输入参数的性能优劣。因此，对适应度函数的改善可以有效提高算法性能。郑超群［9］构造适应度函数时，在Tracey 分支距离的计算方法基础上，将分支函数进行求和，并对函数进行幂指数变换作为适应度函数，转换为求最大值的问题。夏春艳等人［10］采用分支距离与层接近度结合的方法设计适应度函数，为权衡分支距离与层接近度的大小，统一为最小化运算并做规范化处理。针对具体的测试目标特点，王丹等人［11］设计适应度函数为代码覆盖与测试用例触发的新的源码行数的和，该设计避免了过早收敛，同时增强了全局搜索能力。对于生成多路径测试用例问题，孙建华、姜淑娟［12］采用矩阵存储个体经过的路径，对适应度函数做出改善，若产生某条路径的测试用例数量多了，则降低适应度，使种群朝着测试用例数量少的路径方向进化，由此产生多条路径的测试用例，但是当程序结构复杂、路径较多时，矩阵的维数也会增加，不利于维护，该方法在功能上做到了提升，但就效率而言还有很大进步空间。通常来说，适应度函数的改善会结合其他方向的改进共同实现遗传算法生成测试用例的应用改进。

2.3 融合其他算法

为进一步提升遗传算法的性能，大量研究人员将其他群体智能优化算法的思想融入到遗传算法中，以发挥其他算法的优势，同时克服遗传算法的不足。吴昊等人［13］在使用差分求个体适应度值的方法基础上结合禁忌搜索算法，将优先需要遗传的个体添加到禁忌表中，将种群中最优解以及接近最优解的个体保存下来，提升了收敛性，加快了最优解的搜索、进化速度，弥补了GA局部搜索能力差的劣势，还强化了全局搜索能力。文献［14］将混沌序列引入到交叉、变异操作中控制是否进行操作以及操作点，实验证明，与标准遗传算法相比，改进的混沌遗传算法平均迭代次数更低，将GA 的效率提升了10.8%。王文等人［15］分别采用遗传蚁群算法和标准遗传算法对被测程序进行20 次实验，结果表明，无论是在迭代次数上还是在平均搜索时间上，遗传蚁群算法的测试用例生成效率都要比标准遗传算法更好。在多路径测试用例生成问题上，相较于文献［12］只在功能上做出改进，仲晓敏等人［16］在效率上也做出了改进，将测试路径、相应用例的中间态以及不同路径的适应度值存储到数据库中，减少了适应度函数的计算次数，从而实现效率的提高，此外，将模拟退火算法引入变异操作，搜索过程中除了接收优化解，还依据Metropolis 准则以一定概率接收非最优解，算法运行一次产生多路径的测试用例，大大降低了GA陷入局部最优的概率，增强了选择优化解、跳出局部最优的能力，实验证明，种群规模越大，所需迭代次数越小，该算法的优势越明显。总之，与其他算法的融合发挥了遗传算法全局搜索能力强的优点，改善了局部搜索能力弱、易早熟收敛的缺点。

2.4 GA并行化

以上都是串行遗传算法生成测试用例的方法，在问题维度较大的情况下，遗传算法要对较多个体进行适应度评估，计算开销较大，花费时间多［17］。而GA并行化是在群体规模较大时，改善算法性能、提高求解质量的强有力的方法之一。该方法对种群规模进行划分，每个线程负责一个子种群，各子种群并行运行遗传算法，然后在子种群进化过程中交换信息。针对GA并行化的线程池模型设计只关注线程实际执行过程，而不考虑线程与进程之间交互的问题，王微微等人［18］提出主线程在为个体分配线程的同时，也分配相应浏览器进程的GA 并行化测试用例生成方法，该方法与现有Web应用前后端融合的GA 串行化测试用例生成方法相比，种群平均执行时间减少了81.1%。陈清媛［19］等人设计实现了线程级并行遗传算法，初始化种群后对种群进行分配，每个子种群并行执行遗传操作进行路径寻优，此外，若达到指定迁移代数则进行子种群迁移，该操作使得每个核心的种群多样性增加，能够更好地全局寻优，实验证实，多核并行遗传算法的应用在运行时间、生成满足覆盖条件的用例数量方面，比串行遗传算法具有更好的效果。总而言之，在测试用例生成问题上，GA 并行化利用智能优化算法的并行性和计算资源的并行，相较于GA串行来说，时间成本会大大降低。

综上所述，遗传算法的在测试用例生成问题上的改进策略如表1所示。

表1 遗传算法改进策略

3 关键问题

随着研究人员的不断改进，遗传算法在自动化测试领域发挥了更加重要的作用，但在用例数据生成方面，遗传算法的应用依然存在三个关键问题。

第一，非数值型变量的处理。对于软件结构复杂、变量类型不同的程序，例如：参数为字符型或为类对象成员，如何选择合适的编码策略是需要研究的问题。彭叶苹［20］将字符型变量的每个字符转化成正整数（ASCII码），再将ASCII码表示成二进制的形式编码，对于类对象测试数据，将其当作包含了参数值的构造函数与成员函数调用的组合，染色体的第一部分由构造函数和一系列成员函数构成，第二部分为输入值，也就是第一部分中函数对应参数的输入。未来期待着对于非数值型变量在编码问题、适应度函数构造等方面有更深入的研究。

第二，初始参数无法确定。在遗传算法中，初始化时的种群大小、交叉概率及变异概率的设定是随机的，是否存在其他设置方式使得算法效率更高也是一个需要进一步探讨的问题。例如：在种群的迭代更新中，遗传算子的效率会受到种群规模影响，如何设置最佳初始种群大小可以成为一个探索方向。

第三，衡量算法优劣没有统一标准。在已有文献中，学者们为证实研究的有效性做了大量实验，但大家选取的测试评价函数不尽相同，有些人选择基准程序作为待测程序，而有些人选择的是工业程序，对实验结果的评判因素大多选择产生最优解所用时间、迭代次数或覆盖率等。目前还没有形成一个统一的标准来衡量不同算法在解决问题时的表现以及对比实验环境与实际工业应用之间的差异。

4 结语

当前，自动化测试领域的一个研究热点，就是基于遗传算法的测试用例生成，发展前景可观。本文对遗传算法在自动化测试领域测试用例生成方面的应用进行综述。首先给出标准遗传算法在测试用例生成中的应用步骤，随后从改进遗传算子、改善适应度函数、融合其他算法和GA 并行化四个方面总结了遗传算法的改进应用。四种改进方向在求解寻优中各有所长，在实际应用中，应根据具体问题灵活选择改进方向。尽管在自动化测试领域已经有许多研究围绕遗传算法的应用进行展开，但该领域仍然存在多个关键问题亟待解决。遗传算法与近年来新型智能算法的有效结合，例如：鸡群算法［21］、鲸鱼算法［22］以及最新提出的麻雀搜索算法［23］等，有望成为解决这些难题的可行途径之一。