Hyper-heuristics and cross-domain optimization

Citation

Ochoa G (2012) Hyper-heuristics and cross-domain optimization. In: Soule T (ed.) GECCO '12 - Proceedings of the 14th annual conference companion on Genetic and Evolutionary Computation. 14th Annual Genetic and Evolutionary Computation Conference, Philadelphia, 07.07.2012-11.07.2012. New York: ACM, pp. 1197-1214. http://dl.acm.org/citation.cfm?id=2330937; https://doi.org/10.1145/2330784.2330937

Abstract
Hyper-heuristics comprise a set of approaches which are motivated (at least in part) by the goal of automating the design of heuristic methods to solve hard computational search problems. An underlying strategic research challenge is to develop more generally applicable search methodologies. The term hyper-heuristic is relatively new; it was firstly used in 2000 to describe 'heuristics to choose heuristics' in the context of combinatorial optimization. However, the idea of automating the design of heuristics is not new; it can be traced back to the 1960s and 1970s, and a number of related research areas can be identified. The definition of hyper-heuristics has been recently extended to refer to 'a search method or learning mechanism for selecting or generating heuristics to solve computational search problems'. Two main hyper-heuristic categories can be considered: heuristic selection and heuristic generation. The distinguishing feature of hyper-heuristics is that they operate on a search space of heuristics (or heuristic components) rather than directly on the search space of solutions to the underlying problem that is being addressed. This tutorial will discuss the motivation, definition and classification of hyper-heuristics. The tutorial will also cover a recent international research competition: the first 'Cross-domain Heuristic Search Challenge'(CHeSC 2011) (http://www.asap.cs.nott.ac.uk/chesc2011). The challenge was to design a search algorithm that works well, not only across different instances of the same problem, but also across different problem domains. Using a sport metaphor, it is the 'Decathlon' challenge of search heuristics. To support the competition, and to promote research in this area, a software framework (HyFlex) was developed, which features a common interface for dealing with different optimization problems. The tutorial will summarize the main features of HyFlex and the competition; and will present an analysis of the results, highlighting the design principles of the most successful cross-domain hyper-heuristics.