A Comparison of Genetic Programming Variants for Hyper-Heuristics


General-purpose optimization algorithms are often not well suited for real-world scenarios where many instances of the same problem class need to be repeatedly and efficiently solved. Hyper-heuristics automate the design of algorithms for a particular scenario, making them a good match for real-world problem solving. For instance, hardware model checking induced Boolean Satisfiability Problem (SAT) instances have a very specific distribution which general SAT solvers are not necessarily well targeted to. Hyper-heuristics can automate the design of a SAT solver customized to a specific distribution of SAT instances.
The first step in employing a hyper-heuristic is creating a set of algorithmic primitives appropriate for tackling a specific problem class. The second step is searching the associated algorithmic primitive space. Hyper-heuristics have typically employed Genetic Programming (GP) to execute the second step, but even in GP there are many alternatives. This paper reports on an investigation of the relationship between the choice of GP type and the performance obtained by a hyper-heuristic employing it. Results are presented on SAT, demonstrating the existence of problems for which there is a statistically significant performance differential between the use of different GP types.

Meeting Name

17th Annual Conference Companion on Genetic and Evolutionalry Computation (GECCO'15) (2015: Jul. 11-15, Madrid, Spain)


Computer Science

International Standard Book Number (ISBN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2015 Association for Computing Machinery (ACM), All rights reserved.