# Submission for the 13th Annual (2016) "Humies" Awards 1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result; Learning combinatorial interaction test generation strategies using hyperheuristic search 2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s); Yue Jia University College London Department of Computer Science Gower Street London WC1E 6BT United Kingdom e-mail:yue.jia@ucl.ac.uk tel: +44 (0)20 7679 3673 Myra B. Cohen University of Nebraska - Lincoln Department of Computer Science and Engineering Lincoln, NE 68588-0115, United States of America e-mail: myra@cse.unl.edu tel: +01 402-472-2305 Mark Harman University College London Department of Computer Science Gower Street London WC1E 6BT United Kingdom e-mail: mark.harman@ucl.ac.uk tel: +44 (0)20 7679 1305 Justyna Petke University College London Department of Computer Science Gower Street London WC1E 6BT United Kingdom e-mail: j.petke@ucl.ac.uk 3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition); Yue Jia 4. the abstract of the paper(s); 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. 5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies; (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created. 6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission); (B) We tackle the problem of finding minimum combinatorial interaction test suites (CIT). We compare our hyperheuristic algorithm (based on simulated annealing) with a wide range of human-developed CIT algorithms published in the literature and implemented in the following state-of-the-art CIT tools: ACTS, FoCuS, Jenny, PICT, CASA and Ttool. We gathered the best known published results for 26 real-world problems coming from a wide range of application domains such as telecommunication, healthcare, storage, banking and compiler systems, as well as best known results for 29 synthetic CIT benchamrks. Our experimental results show that our hyperheuristic CIT approach equals or outperforms the best result found by algorithms previously reported in the literature for all 26 real-world subjects and for more than 60% of the synthetic models. (D) Our results show that savings can be gained in testing real-world applications. Combinatorial Interaction Testing (CIT) is a systematic test sampling approach that seeks to detect failures caused by parameter interactions. CIT has proven to be an effective way to test software systems that are governed by large configurations, parameters and feature spaces; properties that apply to many important software systems, such as software product lines, operating systems, development environments and many other complex software systems. For the 26 real-world problems, our hyperheuristic strategy reduces the overall number of tests needed compared with the best human strategy by 55 (for 2-way or pairwise parameter interactions) and by 54 (for 3-way parameter interactions). Given that it may take hours or even days to setup and run a test in real-world applications, savings of 55 tests might turn out to be crucial. Furthermore, we show that our hyperheuristic algorithm learns and adapts during search, choosing certain mutations more frequently, depending on the stage of search. This work represents the first use of hyperheuristic learning in the generation of CIT test suites. 7. a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable); Yue Jia, Myra B. Cohen, Mark Harman, and Justyna Petke. 2015. Learning combinatorial interaction test generation strategies using hyperheuristic search. In Proceedings of the 37th International Conference on Software Engineering - Volume 1 (ICSE '15), Vol. 1. IEEE Press, Piscataway, NJ, USA, 540-550. 8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors; Any prize money, if any, is to be awarded to Yue Jia. 9. a statement stating why the authors expect that their entry would be the "best," and Research in Search Based Software Engineering (SBSE) has been growing at a rapid pace. One limitation of much of this work is that evolutionary algorithms must be customized for specific instances or equivalence classes of the problem. Hyperheuristic (HS) algorithms use dynamic adaptive optimisation to learn strategies without active supervision. This work was the first use of hyperheuristic learning in the SBSE literature. Although hyperheuristics have been successfully applied to many operational research problems, they have not been applied to any software engineering problems until this work. We selected a mature and well-studied search problem as our exemplar, Combinatorial Interaction Testing (CIT). Two decades of CIT human algorithm development has left software engineers with a bewildering choice of CIT techniques, each specialized for a particular task. We demonstrated a single hyperheuristic algorithm that learns evolution strategies across a broad range of problem instances, providing a single generalist approach. Our results show HS found strategies that equal or outperform the best strategies found by human experts previously reported in the literature. We also presented evidence that our algorithm’s strong generic performance results from its unsupervised learning. 10. an indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc. Hyperheuristic Search (HS), Evolution strategies (ES)