A Comparison of Genetic Programming Variants for Hyper-Heuristics

Abstract

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)

Department(s)

Computer Science

Research Center/Lab(s)

Center for High Performance Computing Research

International Standard Book Number (ISBN)

978-1450334884

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

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

Publication Date

01 Jan 2015

Link to Full Text

Share

 
COinS