Learning Combinatorial Interaction Test Generation Strategies Using Hyperheuristic Search
Authors:
- Yue JiaYJYue Jia
- Myra B. CohenMCMyra B. Cohen
- Mark HarmanMHMark Harman
- Justyna PetkeJPJustyna Petke
- 1 May 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (02705257) , 540-550
Abstract
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.Keywords
This publication has 32 references indexed in Scilit:
- T‐wise combinatorial interaction test suites construction based on coverage inheritanceSoftware Testing, Verification and Reliability, 2011
- Constructing Interaction Test Suites for Highly-Configurable Systems in the Presence of Constraints: A Greedy ApproachIEEE Transactions on Software Engineering, 2008
- Interaction testing of highly-configurable systems in the presence of constraints2007
- Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential ImpactEmpirical Software Engineering, 2005
- Augmenting simulated annealing to build interaction test suites2005
- Upper bounds for covering arrays by tabu searchDiscrete Applied Mathematics, 2004
- Constructing test suites for interaction testing2003
- Automating test case generation for the new generation mission software system2002
- On the state of strength‐three covering arraysJournal of Combinatorial Designs, 2002
- New Optimization HeuristicsJournal of Computational Physics, 1993