面向软件回归测试用例集优化的混合进化方法研究

With the rapid development of national "Internet +" plan, software has become indispensable for multiple areas as the important support. However, the quality of software is not optimistic. Regression test is effective for timely detecting whether new bugs are generated because of the code modification on the program under test, and is an important technology for ensuring the quality of software. Meanwhile, regression test is one of the software testing technologies that cost the largest. Search based regression test suite optimization technology can improve the efficiency of regression test while reducing the costs. However, there are still many challenges for regression test suite optimization technology. For example, there are too many optimization objectives and heuristic search algorithms for regression test suite optimization to use. In addition, it is difficult to choose the most efficient algorithm for a certain testing scenarios in the practical application process. Thus, this project aims at seeking a general hybrid evolutionary approach for regression test suite optimization based on the hybrid evolutionary theory, through automatic integrating multiple heuristic search algorithms. The hybrid evolutionary approach can finally form a highly automated and versatile software regression test suite optimization technology. We will investigate a dynamic decision method for the hybrid evolutionary approach to ensure that the existing heuristic search algorithms can be fully advantaged in the optimization process. In addition, we will build a hybrid evolutionary model for regression test suite optimization to improve its performance and efficiency. Finally, we will develop a relevant tool and construct a large number of experimental researches to evaluate the effectiveness and efficiency of our approach, which can lay the foundation for exploring the practical application of the hybrid evolutionary approach in software engineering field.

随着国家“互联网+”计划的大力推进，软件已经成为多个领域不可或缺的重要基础，但软件质量不容乐观。软件回归测试可以及时发现代码修改对被测程序产生的影响，是保证软件质量的重要手段，同时也是成本占比最大的测试技术之一。基于搜索的回归测试用例集优化技术可以有效提高回归测试效率，但现有研究涉及的优化目标众多，采用的启发式搜索算法诸多，在实际应用过程中面临着算法选择困难、实施技术成本高等挑战。因此，本申请旨在以混合进化理论为指引，自动融合多启发式搜索算法，探讨一种面向回归测试的优化算法混合进化方法，形成具有高度自动化和通用性的软件回归测试用例集优化技术。项目将研究基于混合进化的优化算法动态决策方法，充分发挥各算法在迭代进化中的优势；构建回归测试用例集优化算法混合进化模型，实现回归测试用例集优化算法性能和效率的大幅度提升；进行相关实证研究，为探索混合进化方法在软件工程领域的实用化奠定基础。

本课题的研究目标是针对回归测试用例集优化技术涉及的启发式搜索算法繁多，优化目标众多，算法设计与具体优化问题、优化目标关联密切等特点，探讨一种具有普适性的启发式搜索算法混合进化方法，充分发挥各启发式搜索算法在回归测试用例集优化中的优势;探讨一种启发式搜索算法融合模式，构建回归测试用例集优化算法混合进化模型，实现回归测试用例集优化算法性能和效率的大幅度提升;进行基于混合进化的回归测试用例集优化实证研究，为探索混合进化方法在软件工程领域的实用化奠定基础。.首先，通过对现有启发式搜索算法的搜索空间特征、进化特征、优化目标数等进行分析，对多启发式搜索算法的无缝切换技术及融合模式进行研究，并完成原形实现。研究首先分别针对基于演化的多目标进化算法无缝切换策略和基于群体智能的多目标进化算法无缝切换策略进行研究；然后定义了超启发式算法库的复杂性，进而构造了四种不同复杂性的超启发式算法库进行实验以研究最佳融合模式。.其次，对超启发式框架的决策层，分别进行了评价策略、更新策略和调度策略的研究。提出了4种新的评价函数可以更全面的比较每一次演化后获得的种群相较之前结果的优劣，并通过实验验证了方法的有效性，及最佳策略的发掘。从利用即时值和历史值两个角度提出了4种不同的更新策略来记录历史评价值。从“探索”和“利用”2个不同的角度尝试4种不同的调度策略设计。设计2种强化学习策略作为上层调度策略。并将上述各种方法的不同组合作为超启发式框架的决策层进行实证研究。结果表明，本研究提出的ESPC-2评价策略、加时间窗的历史平均值更新策略和ϵRoulette-Greedy调度策略构成的超启发式框架上层（决策层）表现最优。而本研究设计的强化学习策略的表现优于加时间窗的历史平均值更新策略和ϵRoulette-Greedy调度策略的组合。.最后，基于上述研究成果，开发了用于MOTCP的超启发式原型工具，并与现有多目标优化算法对8个不同的被测目标进行实验比较。结果显示，对于不同的被测目标，本研究的成果对7个被测程序都排名前2位，其中40%排名第一。因此可以说本研究团队完成了既定目标，设计了一种具有普适性的回归测试用例集优化框架方法。