Exploring hyper-heuristic methodologies with genetic programming

Citation

Burke E, Hyde M, Kendall G, Ochoa G, Ozcan E & Woodward J (2009) Exploring hyper-heuristic methodologies with genetic programming. In: Mumford C & Jain L (eds.) Computational Intelligence: Collaboration, Fusion and Emergence. Intelligent Systems Reference Library, 1, Volume 1. Berlin and Heidelberg: Springer, pp. 177-201. http://www.springerlink.com/content/j11565558t12900u/

Abstract
Hyper-heuristics represent a novel search methodology that is motivated by the goal of automating the process of selecting or combining simpler heuristics in order to solve hard computational search problems. An extension of the original hyper-heuristic idea is to generate new heuristics which are not currently known. These approaches operate on a search space of heuristics rather than directly on a search space of solutions to the underlying problem which is the case with most meta-heuristics implementations. In the majority of hyper-heuristic studies so far, a framework is provided with a set of human designed heuristics, taken from the literature, and with good measures of performance in practice. A less well studied approach aims to generate new heuristics from a set of potential heuristic components. The purpose of this chapter is to discuss this class of hyper-heuristics, in which Genetic Programming is the most widely used methodology. A detailed discussion is presented including the steps needed to apply this technique, some representative case studies, a literature review of related work, and a discussion of relevant issues. Our aim is to convey the exciting potential of this innovative approach for automating the heuristic design process.

Keywords
Genetic programming (Computer science); Artificial intelligence

People

Professor Gabriela Ochoa

Professor, Computing Science