基于改进遗传算法的测试用例进化生成方法研究＊

林亚娜

(福州理工学院，福建 福州 350506)

0 引言

软件测试中的路径覆盖测试是在单元测试阶段比较常用的方法，测试用例的自动生成可以提高软件测试效率，路径覆盖是一种重要的覆盖标准，其目的是寻找覆盖所有可能路径的测试用例，进而发现软件中存在的缺陷[1]。寻找覆盖路径的测试用例可抽象为寻求最优路径的问题，遗传算法是目前用于测试用例自动生成的有效的常用方法，遗传算法在解决寻找最优路径问题中有一定优势。

Ahmed等[2]于2008 年首次提出基于遗传算法（Genetic Algorithm）多路径测试数据进化生成的方法，提出由层接近度和分支距离两部分构成适应度函数，这种方法虽然能够进化生成测试数据，但是计算量较大，效率不高。巩敦卫等[3]提出一种用于多路径覆盖的测试数据生成方法，设计的适应度函数综合考虑了个体穿越路径与目标路径的匹配程度，该方法可以通过较小的计算量高效地生成测试数据，而在匹配目标路径的时候没有考虑不可达路径的问题。范书平等[4]提出利用种群中个体穿越程序分支的均衡度调整进化过程，使得对程序均衡度影响大的个体具有更多机会参与到后续进化中，提高测试数据的生成效率。夏春艳等[5]提出基于否定选择遗传算法的路径覆盖测试数据生成方法，动态优化遗传算法的种群数据，减少冗余数据生成。黄陈辉[6]等提出一种混沌遗传算法进行测试用例的进化生成，运用反向学习策略初始化种群，与简单遗传算法比较结果表明，这种方法可以提升测试用例生成方面的全局寻找最优解能力。

本文所提方法的核心由两部分组成：①通过分析被测程序的流程图得到可能的目标路径集合，过滤不可达路径以便节省进化数据匹配的资源成本；②对遗传算法的适应度函数进行改进，通过分析分支走向以及加路径权重的方式设计新的适应度函数，最后利用矩阵计算方法计算出适应度。当遗传算法生成的测试数据路径与目标路径不匹配时，通过分析路径走向以及路径加权的计算，可以拉大测试数据路径与目标路径的差距，加速算法收敛速度，提高生成可用测试用例的效率。

1 改进遗传算法生成测试用例的方法

1.1 路径的构建

路径的构建是通过分析程序流程图，程序结构基本分三类：顺序结构、选择（分支）结构、循环结构。其中顺序结构的程序不涉及路径变化，在构建路径过程中无需区分这类结构；选择（分支）结构和循环结构是区分路径的关键，循环结构采用Z 路径覆盖原则[7]，简化了循环的次数，只考虑循环1 次和0 次两种情况。本文主要针对这两类结构分析目标路径集合，首先定义两个概念。

定义1路径中节点的方向系数α，表示程序结构的走向，为1或-1。

针对选择（分支）结构：

定义2路径中的节点权值β，表示每个节点在当前路径中所占的权重，越靠近起始点的节点，其影响越大，进而权重越大。假设当前路径有n 个节点，第i个节点的权值为：

权值按照节点个数降序排列，即第1 个节点的权值β1为n，第2 个节点权值β2为n-1，以此类推。将路径集合表示为一个n行m列的矩阵P，P[i][j]（i=1,2,...,n；j=1,2,...,m）表示第i 条路径中第j 个节点所对应的值，该值由定义1 的节点方向系数与定义2 的节点权值相乘组成。

根据公式⑷可以构建出被测程序中所有目标路径的矩阵P[i][j]以及进化生成的测试数据实际经过的路径PA[i][j]。

1.2 适应度函数设计

适应度函数主要的任务是对比实际路径与目标路径的差异。差异越小，证明实际数据路径与目标路径越匹配，适应度值越接近1。目标路径应是一个集合，首先排除目标路径集合中分支点数与实际路径分支点数不同的路径，分支不同必然不可能匹配；其次，用实际路径分别与目标路径集合中的路径做匹配并计算适应度，如得到完全匹配的数据，则保存当前的测试数据，并将已经匹配的目标路径从目标路径集合中删除，将该条实际路径的适应度设置为1；如未完全匹配，则通过计算实际路径与各个目标路径的适应度，计算其平均值即为该条实际路径的适应度。

利用路径的构建方法，将第t 代测试数据代入被测程序，通过程序插桩构建出第t 代测试数据的实际路径，即1行r列矩阵PA,r表示该条实际路径经过的分支点个数；目标路径表示为矩阵P，其中P[i]表示目标路径集合中的第i条路径构建的矩阵，为1行r列矩阵，通过矩阵计算得到第t 代测试数据实际路径的适应度函数：

其中，n表示目标路径集合过滤后的路径条数，过滤指目标路径集合中去掉不可达路径及路径中节点数与实际路径不一致的路径，PA表示实际路径矩阵，P 表示过滤后的目标路径矩阵，i 指P 中的第i 条路径，T 上标表示矩阵的转置。式⑸得到的结果为一个自然数，为了便于比较，将结果限定在一个范围，做归一化处理，将式⑸得到的结果分布到实际路径矩阵的秩的平方中，将适应度值限定在[-1，1]闭区间内，最终得到归一化后的适应度函数如下：

适应度函数的设计综合考虑了不匹配节点出现的前后位置，不匹配出现的越靠前，则代表实际路径与目标路径集合中的路径不匹配程度越大，经过公式⑹计算得到的适应度值越接近-1，表示该数据匹配程度低，在遗传算法中被选择为亲代数据的几率越小。将路径抽象为矩阵，经过矩阵计算，根据不匹配节点出现的位置，计算适应度，能够体现路径之间的匹配程度，通过式⑴、式⑵方向系数和式⑶权值的设计，可适当拉大匹配路径的差异，加速算法收敛。

预制装配式建筑施工技术及其配套装备的创新研究…………………………………………………… 王润华（10-203）

1.3 改进的遗传算法生成测试用例方法

改进的遗传算法流程图如图1所示：

图1 改进遗传算法的流程图

算法的实现步骤共分六步：

步骤1在待测程序中插桩，构建出目标路径集合，判断分支节点处是否存在相关性因素，找出不可达路径并从目标路径集合中删除，构建最终的目标路径矩阵；

步骤2通过遗传算法初始化种群，生成第一代种群的测试数据，代入测试数据执行被测程序，获取每条测试数据的实际执行路径；

步骤3评价实际路径与目标路径的匹配程度，如有完全匹配的测试数据，则保留该条数据作为测试用例，并将匹配上的目标路径从目标路径集合中删除；如未完全匹配，根据公式⑸、⑹计算个体的适应度进而计算第一代测试数据的整体适应度；

步骤4判断遗传终止条件是否满足，如已经满足转至步骤6，如未满足终止条件，则继续执行步骤5；遗传终止条件为当前目标路径集合中已无待匹配路径，表示所有与目标路径匹配的测试用例均已经生成或达到指定的进化代数上限；

步骤5根据初始化设置的交叉率、变异率执行遗传算法中的交叉、变异程序，再次计算整体适应度；生成下一代种群进化的测试数据，跳转回步骤4，再次判断遗传条件是否终止；

步骤6终止遗传算法，输出生成的测试数据。

2 实验仿真分析

2.1 实验准备

为了评价本文提出的改进的遗传算法的有效性以及性能，选取四个基本测试进行测试，被测程序的基本信息如表1所示。

表1 待测程序基本信息

本文改进的遗传算法采用轮盘赌选择交叉的亲代，单点交叉、单点变异进而生成下一代测试数据。每次实验的参数设置如表2所示。实验运行环境基本配置为2.3GHz 四核 Inter（R）i5-6300HQ 处理器，8GB 内存，Windows10 操作系统，JVM 版本1.8.0_121，开发语言为Java语言，集成平台为Eclipse2019-09。

表2 实验参数设置

2.2 算法可行性验证

本文算法与随机算法做比较，分别针对四个基本测试程序构建路径并生成测试用例。对生成数据的覆盖率、生成的测试用例数量、迭代的次数以及生成测试数据的时间等几个关键指标进行对比，由于算法存在不确定性，每个算法得到的测试数据为该算法执行100次的平均结果，详细数据如表3所示。

表3 改进的遗传算法与随机算法针对四组待测程序执行结果对比

通过分析实验结果可得，在程序简单、分支较少的程序中，本文算法与随机算法的覆盖率、生成测试用例个数与运行时间相差无几，但是在分支数较多的程序中，比如在判断三角形Angles 程序中，在生成测试用例数相同的情况下，本文算法的覆盖率为100%，随机算法为91%，本文算法覆盖率高于随机算法。在获取下一天NextDate 程序中，本文算法生成的测试用例个数少于随机算法，在此情况下，本文算法的覆盖率仍高于随机算法。当程序分支数变多时，在生成测试用例数量相同时，改进的算法覆盖率仍可保持100%覆盖路径。在复杂程序中，改机的算法与随机算法相比，覆盖率提升4%～9%。通过本文改进遗传算法生成数据，可以针对待测程序的具体情况，调整交叉率及变异率，改善算法的收敛速度，这是随机算法无法做到的。

3 结束语

自动生成测试用例是自动化测试研究中的核心环节，本文将测试用例自动生成的问题抽象为寻求最优解问题，通过改进遗传算法的适应度函数计算方法加快遗传算法收敛，与随机算法相比，能够更快速的寻找到最适合的测试数据。设计适应度函数，拉大不匹配路径之间的差距，从而快速获得符合条件的测试数据，减少冗余测试数据的生成，提高测试覆盖率。

将本文算法应用到基础测试代码中实验，经过与随机算法对比，得出本文算法在测试覆盖率和进化代数方面具有一定的优越性。在过滤不可达路径的过程中，尚未使用程序自动化完成，未来将针对这一步骤做进一步研究。