智能优化算法在回归测试关键技术中的应用现状研究

马宝英 杨禹军 范书平

摘  要： 近些年，智能优化算法在软件工程领域得到了广泛的应用，基于搜索的软件工程技术往往通过设计具体问题的适应值函数，并基于该函数在问题的可行解空间中使用优化算法寻求最优解。本文首先介绍了常用的智能优化算法，包括遗传算法、爬山算法、粒子群算法以及蚁群算法，之后分析并研究这些算法在测试数据生成、测试用例选择以及测试用例优先级排序技术中的应用，为有效解决基于搜索的软件工程问题奠定基础，促进回归测试效率的提高。

关键词： 回归测试;智能优化算法;关键技术;应用

中图分类号： TP311.52    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.01.004

本文著录格式：马宝英，杨禹军，范书平，等. 智能优化算法在回归测试关键技术中的应用现状研究[J]. 软件，2020，41（01）：1820

【Abstract】： In recent years， intelligent optimization algorithms have been widely used in the field of software engineering. Search based software engineering technology often designs the fitness function of a specific problem and uses optimization algorithm to find the optimal solution in the feasible solution space of the problem based on the function. This paper first introduces the common intelligent optimization algorithms， including genetic algorithm， hill-climbing algorithm， particle swarm optimization algorithm and ant colony algorithm， then analyzes and studies the application of these algorithms in test data generation， test case selection and test case prioritization technology. It lays a foundation for effectively solving the search based software engineering problems and promotes the efficiency of regression testing.

【Key words】： Regression testing; Intelligent optimization algorithms; Key technologies; Application

0  引言

软件测试是软件产品质量的重要保证方法，其主要目标是在满足测试准则的基础上，用尽可能少的测试数据发现更多的缺陷，以降低软件开发的成本[1]。回归测试是软件测试的重要组成部分，尤其是對于大型复杂软件系统，在每次修改后往往要进行大量的回归测试，已有研究表明，回归测试开销占整个软件维护预算的50%以上[2]，为了降低回归测试代价，提高软件测试效率[3]，近些年国内外学者对高效自动的回归测试技术展开了深入的研究，测试用例选择、测试用例的生成以及测试用例的优先级排序均是回归测试的关键技术。

近年来，各种基于启发式搜索的优化技术被应用到软件测试中，设法将软件测试问题转化成一个基于搜索的优化问题，遗传算法、爬山算法、粒子群算法以及蚁群算法是常用的智能优化算法，这些优化算法已经广泛应用于基于搜索的回归测试关键技术中，首先介绍这些算法的基本概念。

1  常用的智能优化算法概述

1.1  遗传算法

遗传算法[4]模拟了生物在自然环境中的进化和遗传，是一种启发式的全局优化算法。该算法最初是借鉴了进化生物学中的一些现象而发展起来的，该算法应用群体搜索方式，通过将遗传算子对当前群体内个体进行交叉、变异、选择等遗传运算，产生下一代种群，并通过进化使种群进化到包含或接近最优解[5]。遗传算法由于其计算过程简单、时间短而得到了广泛的应用，但与此同时，遗传算法存在局部搜索能力不强，收敛早等问题。因此，近些年，众多学者研究将遗传算法与一些局部搜索算法如梯度法、爬山算法等相结合。

1.2  爬山算法

爬山算法是一种简单的贪心算法[6]，贪心算法在对问题求解时总是做出在当前看来是最好的选择，也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解，该算法广泛应用于求解最优解或近似最优解问题，涉及到测试用例的优化问题，主要包括基本贪心算法、额外贪心算法。爬山算法则常用于通过局部搜索来达到某个分支条件。该算法从搜索空间中的一个可行解出发，将当前节点与其周围邻节点的值进行比较，返回二者中最大值对应的节点 （山峰最高点），从而逐渐爬向山峰的高处，该过程通过不断迭代，直至达到局部最优解为止[7]。

1.3  粒子群算法

粒子群算法是一种全局随机搜索算法，该算法模拟鸟群觅食过程中的群体智能行为。该算法的基本思想是：通过随机选择粒子，并由这些粒子构成初始种群， 初始化种群，获得粒子的方向与距离信息，每个粒子均有一个适应值，粒子在每一次迭代过程中，通过比较个体适应值，粒子追寻群体中最优的粒子来逐步优化候选解，通过多次迭代找到全局最优解[8]。

1.4  蚁群算法

蚁群算法借鉴了现实中蚂蚁集体寻找路径的行为，蚂蚁觅食过程中会分泌出“信息素”[9]，该物质会随着时间不断挥发，蚂蚁间利用该信息素进行沟通，一般而言，一条路径上经过的蚁群数量越多，该路径上信息素的浓度越大，结果是后来蚂蚁会选择该路径的概率就会提高，从而得到最短觅食路  径[10]。蚁群算法参数少且设置容易，其求解过程无需人工参与，初始路线对搜索结果影响不大，目前，该算法已成为分布式人工智能的热点研究问题。

2  智能优化算法在回归测试关键技术中的应用

2.1  在测试数据自动生成中的应用

近些年，众多学者研究满足路径覆盖准则的测试数据生成方法[11]。基于遗传算法的测试数据生成基本思想是[7]：首先在程序的输入域中随机生成一定数量（即：种群大小）的测试数据，对这些数据进行编码，成为初始种群;然后循环执行以下操作：将解码后的进化个体作为程序的输入，执行插装后的待测程序，通过适应度函数评价个体的优劣，采用选择、变异、交叉等遗传算子以生成新的进化种群。重复上述操作，直到达到终止条件（一般是最大迭代次数或者是达到适应度函数的目标值），解码后的优化解可能即为满足覆盖准则的测试数据。如张岩等[12]通过统计个体穿越目标路径上节点数目，计算个体对生成穿越目标路径测试数据的影响，进而提出“个体贡献度”，之后将贡献度进行量化为个体适应值的一部分，保证了穿越难覆盖节点的个体有更高概率被保留下来，该方法通过设计实验验证了所提出方法在测试数据生成的成功率与运行时间等方面的优势。Deepak等[13]则应用遗传算法与爬山算法来进化生成测试数据，该方法的适应值函数计算考虑了分支距离与层接近度，并通过将层接近度乘以一个常数来提高其在适应值计算中的比重。

2.2  在测试用例选择中的应用

截止到目前，许多学者已经提出多种方法来解决测试用例的选择问题，其基本思想是：首先根据测试目标中的每个测试需求确定出相应的测试用例，所有这些测试用例组成初步的、满足测试目标的测试用例集;然后针对这个测试用例集采用贪心算法、一些启发式算法或整数规划等方法来进行精简，去掉一些冗余的测试用例。章晓芳等[14]提出应用贪心算法进行测试用例的约简与优化方法，依次选择能最大限度地满足测试需求集中尚未被满足的测试需求，然后将已满足的测试需求进行删除，直到满足所有的测试需求为止;也有一些学者研究应用优化算法进化选择用例子集，主要思想是应用一些优化算法及交互策略在测试用例集中搜索符合既定覆盖标准的极小化的测试用例子集，构造优化模型，以剔除冗余测试用例，缩减待执行的测试用例集规模[15]，李泽雪等[16]将Markov决策模型应用到软件测试过程当中，采用测试用例约简技术对测试用例集进行简化，利用贪心算法求得的较优解增强蚁群算法初始时刻信息素，通过改进的蚁群算法求得最优解。

2.3  在测试用例排序中的应用

测试用例优先排序技术对测试过程中用例执行的先后进行排序，目标是尽早的检测出程序中的缺陷。智能优化算法常用于基于代码覆盖的排序技术中，这类方法对测试用例重新排序来尽可能早的实现代码覆盖，这些算法中有的应用贪心算法和附加贪心算法来实现基于覆盖的排序，然而这可能会产生次优解，因为结果会在局部较小的搜索空间内产生。为了解决这个问题，目前常用的优化技术包括遗傳算法与爬山算法等[17]。

近年来，许多智能优化算法均被用于测试用例的优先级排序中，如有的方法应用蚁群优化技术进行测试用例排序，方法中分别建立了缺陷-测试用例矩阵，执行时间-测试用例矩阵，使用率矩阵等，并通过优先选择覆盖最大缺陷的用例，再选择覆盖剩余缺陷的其他用例进行排序，结果表明该方法能减少时间，降低测试代价，与此同时能揭露软件中的最大缺陷[18]。 也有的方法提出了针对测试点覆盖的测试用例优先排序技术评价指标，并以此为基础提出一种基于遗传算法的测试用例排序方法，该方法通过设置遗传算法的操作算子，并进行了实验验证，结果表明该方法可以有效提高软件测试效率[19]。

3  总结

本文在介绍常用的智能优化算法基础上，给出了智能优化算法在回归测试数据生成、测试用例选择及排序中应用的一般过程，分析并研究了优化算法在回归测试关键技术中的应用情况，不难得出，智能优化算法适应值设置是实现回归测试关键技术的重点，今后将进一步研究如何设置适应值函数，以提高回归测试的效率。

参考文献

[1] 颜乐鸣. 基于工作流的软件测试过程模型研究[J]. 软件， 2018， 39（5）： 160-165.

[2] Panigrahi Chhabi Rani， Mall Rajib. A heuristic-based regression test case prioritization approach for object-oriented programs[J]. Innovations in Systems & Software Engineering， 2014， 10（3）： 155-163.

[3] 张琪. 大数据背景下软件测试的挑战与展望[J]. 软件， 2018， 39（6）： 181-183.

[4] 聂敬云， 李春青， 李威威， 等. 关于遗传算法优化的最小二乘支持向量机在MBR仿真预测中的研究[J]. 软件， 2015， 36（5）： 40-44.

[5] 周明， 孙树栋. 遗传算法原理及应用[M]. 北京：国防工业出版社， 2002， 1-20.

[6] 黄玉涵， 曾凡平， 潘能刚等. 基于搜索算法的测试用例优化问题研究[J]. 小型微型计算机系统. 2011， 32（5） ： 840-844.

[7] 薛猛， 姜淑娟， 王荣存. 基于智能优化算法的测试数据生成综述[J]. 计算机工程与应用. 2018， 54（17）： 16-23.

[8] 陈晓文. 基于粒子群算法的FIR滤波器的优化设计[J]. 宁德师范学院学报（自然科学版） ， 2019， 31（3）： 257-262.

[9] 丁顺， 陈世平. 云计算中基于包簇映射的多目标蚁群资源分配算法[J]. 软件， 2018， 39（11）： 01-06.

[10] 朱俚治. 基于相似性算法与蚁群算法的聚类算法[J]. 计算机测量与控制. 2018， 26（6） ： 149-151.

[11] 杨子健， 赵逢禹. 基于数据流约简的测试用例生成策略研究[J]. 软件， 2018， 39（4）： 191-195.

[12] 张岩， 巩敦卫. 基于稀有数据扑捉的路径覆盖测试数据进化生成方法[J]. 电子学报， 2013， 36（12）： 2429-2440.

[13] Deepak Garg， Pallvi Garg. Basis Path Testing Using SGC&HGA with ExLB Fitness Function[C]. 4th International Conference on Eco-friendly Computing and Communication Systems， 2015： 593-602.

[14] 章晓芳， 徐宝文， 聂长海等. 一种基于测试需求约简的测试用例集优化方法[J]. 软件学报， 2007， 18（4）： 821-831.

[15] 成亚玲， 李健， 彭湘华. 基于传统H算法改进的回归测试用例优化算法.湖南工业职业技术学院学报， 2015， 15（2）： 13-20.

[16] 李泽雪， 薛亮， 李相民. 基于改进蚁群算法的软件测试方法[J]. 兵工自动化， 2017， 36（2）： 70-74.

[17] Chunrong Fang， Zhenyu Chen， Kun Wu， et al. Similarity- based test case prioritization using ordered sequences of program entities[J]. Software Quality Journal， 2014， 22（2）： 335-361.

[18] Ahlam Ansari， Anam Khan， Alisha Khan， etal. Optimized Regression Test using Test Case Prioritization[J]. Procedia Computer Science， 2016， 79： 152-160.

[19] 張卫祥， 魏波， 杜会森. 一种基于遗传算法的测试用例优先排序方法[J]. 小型微型计算机系统. 2015， 36（9）： 1999-2000.