Follow @Graham_Kendall

Graham Kendall: Hyper-Heuristics

Introduction

There are often two problems faced by researchers and users who wish to implement a search/optimisation algorithm:

1. If a search algorithm is developed for one particular domain (or even a single problem instance) it is often difficult to use that algorithm for another problem/instance. That is, the algorithm is a bespoke algorithm that works well for the domain for which it was developed, but cannot be generalised to other problems/instances (at least not easily).


2. Many algorithms (such as genetic algorithms, simulated annealing, tabu search etc.) require various parameters to be tuned (e.g. the cooling scheduling in simulated annealing, the size of the tabu tenure in tabu search and the population size, crossover rates in genetic algorithms etc.). This is not only time consuming but often requires some insight into the problem or some intuition as to what values to use/try.

One of the key aims of hyper-heuristics is to develop more general algorithms that can be utilised across a range of problem domains, rather than typical meta-heuristic methodologies which tend to be customised to a particular problem or a narrow class of problems. That is, we wish to investigate whether we can develop algorithms that:

1. work well across different instances of the same problem.
2. are able to adapt to different problem domains, without the search algorithm having to change.
3. do not require parameters to be tuned. Rather the hyper-heuristic algorithm is able to adapt and tune the parameters at run time.

There are many ways to categorise hyper-heuristics but two common classifications are heuristics to choose heuristics and heuristics to generate heuristics.

Heuristics to Choose Heuristics

One definition of hyper-heuristics is "Heuristics to Choose Heuristics". Whereas meta-heuristics operate on a direct representation of a problem. Consider examination timetabling, where a meta-heuristic manipulates a representation of a timetable (i.e. some suitable representation which stores rooms, timeslots, students, examinations etc.). By comparison, a hyper-heuristic searches over the heuristic space. Therefore, it searches through heuristic space by deciding which heuristic to employ at each decision point.

One way to visualise a heuristics to choose heuristics framework is presented in Figure 1 (from Eric Soubeiga'a PhD thesis, page 110)

Figure 1: From: Soubeiga, E Development and Application of Hyperheuristics to Personnel Scheduling. Ph.D. Thesis, School of Computer Science, University of Nottingham, UK, 2003, page 110

Heuristics to Generate Heuristics

My Research Focus

Publications

You can see all my hyper-heuristic publications here.

Funding

1. EP/H000968/1: Towards More Effective Computational Search
2. EP/D027039/1: Hyper-heuristics for Scheduling, Rostering and Routing: An International Collaboration: A Visiting fellowship (Michel Gendreau)
3. GR/S70197/01: PLATFORM: Towards More General Optimisation/Search Systems
4. GR/N36837/01: An Investigation of Hyper-Heuristic Methods