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.
S. Harris et al., "A Comparison of Genetic Programming Variants for Hyper-Heuristics," Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1043-1050, Association for Computing Machinery (ACM), Jan 2015.
The definitive version is available at https://doi.org/10.1145/2739482.2768456
17th Annual Conference Companion on Genetic and Evolutionalry Computation (GECCO'15) (2015: Jul. 11-15, Madrid, Spain)
Center for High Performance Computing Research
International Standard Book Number (ISBN)
Article - Conference proceedings
© 2015 Association for Computing Machinery (ACM), All rights reserved.