A Theoretical and Empirical Study of Search-Based Testing: Local, Global, and Hybrid Search
A Theoretical and Empirical Study of Search-Based Testing: Local, Global, and Hybrid Search
复制标题
DOI：
10.1109/tse.2009.71
复制
发表时间：
2010-03-01
影响因子：
7.4
通讯作者：
McMinn, Phil
中科院分区：
文献类型：
--
作者：
Harman, Mark;McMinn, Phil
自 1992 年以来，基于搜索的优化技术已应用于结构软件测试数据生成，最近该领域的兴趣和活动激增。然而，尽管最近对不同的基于搜索的优化方法的适用性进行了大量研究，但对这些技术非常适合的测试问题类型的理论分析却很少。也很少有实证研究展示大型项目的结果。本文对研究最广泛的方法——遗传算法所体现的全局搜索技术——进行了理论探索。它还提供了一项大型实证研究的结果，该研究比较了现实世界程序中基于全局和局部搜索的优化的行为。这项研究的结果表明，存在适合每种算法的测试数据生成问题的案例，从而表明混合全局局部搜索（模因算法）可能是合适的。本文提出了一种模因算法以及研究其性能的进一步实证结果。
Search-based optimization techniques have been applied to structural software test data generation since 1992, with a recent upsurge in interest and activity within this area. However, despite the large number of recent studies on the applicability of different search-based optimization approaches, there has been very little theoretical analysis of the types of testing problem for which these techniques are well suited. There are also few empirical studies that present results for larger programs. This paper presents a theoretical exploration of the most widely studied approach, the global search technique embodied by Genetic Algorithms. It also presents results from a large empirical study that compares the behavior of both global and local search-based optimization on real-world programs. The results of this study reveal that cases exist of test data generation problem that suit each algorithm, thereby suggesting that a hybrid global-local search (a Memetic Algorithm) may be appropriate. The paper presents a Memetic Algorithm along with further empirical results studying its performance.