Automated heuristic design

Citation

Ochoa G, Hyde M & Burke E (2011) Automated heuristic design. In: GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation. 13th annual conference on Genetic and evolutionary computation, Dublin, Ireland, 12.07.2011-16.07.2011. New York, NY: ACM, pp. 1321-1341. http://dl.acm.org/citation.cfm?doid=2001858.2002139; https://doi.org/10.1145/2001858.2002139

Abstract
This tutorial will discuss state-of-the-art techniques for automating the design of heuristic search methods, in order to remove or reduce the need for a human expert in the process of designing an effective algorithm to solve a search problem. Using machine learning or meta-level search, several approaches have been proposed in computer science, artificial intelligence and operational research. The aim is to develop methodologies which can adapt to different environments without manually having to customise the search, or its parameters, for each particular problem domain. This can be seen as one of the drawbacks of many current metaheuristic and evolutionary implementations, which tend to have to be customised for a particular class of problems or even specific problem instances. We have identified two main types of approaches to this challenge: heuristic selection, and heuristic generation. In heuristic selection the idea is to automatically combine fixed pre-existing simple heuristics or neighbourhood structures to solve the problem at hand; whereas in heuristic generation the idea is to automatically create new heuristics (or heuristic components) suited to a given problem or class of problems. This latter approach is typically achieved by combining, through the use of genetic programming for example, components or building-blocks of human designed heuristics. This tutorial will go over the intellectual roots and origins of both automated heuristic selection and generation, before discussing work carried out to date in these two directions and then focusing on some observations and promising research directions.