Learning Combinatorial Interaction Test Generation Strategies Using Hyperheuristic Search
Learning Combinatorial Interaction Test Generation Strategies Using Hyperheuristic Search
复制标题
DOI：
10.1109/icse.2015.71
复制
发表时间：
2015-05
期刊：
影响因子：
--
通讯作者：
Yue Jia;Myra B. Cohen;M. Harman;J. Petke
中科院分区：
文献类型：
--
作者：
Yue Jia;Myra B. Cohen;M. Harman;J. Petke
基于搜索的软件工程研究的激增受到了为同一问题的不同类别开发定制搜索算法的需求的阻碍。例如，二十年的定制组合交互测试（CIT）算法开发，我们的典型问题，已经留给软件工程师一个令人困惑的选择CIT技术，每一个专门针对一个特定的任务。本文提出了使用一个单一的超启发式算法，学习搜索策略在广泛的问题实例，提供了一个单一的通才的方法。我们已经开发了一个超启发式算法的CIT，并报告实验表明，我们的算法竞争与已知的最佳解决方案在约束和无约束的问题：对于所有26个现实世界的主题，它等于或优于以前在文献中报道的最佳结果。我们还提出证据表明，我们的算法的强大的通用性能的结果，其无监督学习。因此，超启发式搜索是将CIT设计智能从人类转移到机器的一种有前途的方法。
The surge of search based software engineering research has been hampered by the need to develop customized search algorithms for different classes of the same problem. For instance, two decades of bespoke Combinatorial Interaction Testing (CIT) algorithm development, our exemplar problem, has left software engineers with a bewildering choice of CIT techniques, each specialized for a particular task. This paper proposes the use of a single hyperheuristic algorithm that learns search strategies across a broad range of problem instances, providing a single generalist approach. We have developed a Hyperheuristic algorithm for CIT, and report experiments that show that our algorithm competes with known best solutions across constrained and unconstrained problems: For all 26 real-world subjects, it equals or outperforms the best result previously reported in the literature. We also present evidence that our algorithm's strong generic performance results from its unsupervised learning. Hyperheuristic search is thus a promising way to relocate CIT design intelligence from human to machine.