What are hyper-heuristics, and how are they different from meta-heuristics?

Question

I wanted to know what the differences between hyper-heuristics and meta-heuristics are, and what their main applications are. Which problems are suited to be solved by hyper-heuristics?

Answer 1

TL:DR: Hyper-heuristics are metaheuristics, suited for solving the same kind of optimization problems, but (in principle) affording a "rapid prototyping" approach for non-expert practitioners. In practice, there are issues with the prevailing approach, motivating an emerging perspective on 'whitebox' hyper-heuristics.

In more detail:

Metaheuristics are methods for searching an intractably large space of possible solutions in order to find a 'high quality' solution. Popular metaheuristics include Simulated Annealing, Tabu Search, Genetic Algorithms etc.

The essential difference between metaheuristics and hyper-heuristics is the addition of a level of search indirection: informally, hyper-heuristics can be described as 'heuristics for searching the space of heuristics'. One can therefore use any metaheuristic as a hyper-heuristic, providing the nature of the 'space of heuristics' to be searched is appropriately defined.

The application area for hyper-heuristics is therefore the same as metaheuristics. Their applicability (relative to metaheuristics) is as a 'rapid prototyping tool': the original motivation was to allow non-expert practitioners to apply metaheuristics to their specific optimization problem (e.g. "Travelling-Salesman (TSP) plus time-windows plus bin-packing") without requiring expertise in the highly-specific problem domain. The idea was that this could be done by:

1. Allowing practitioners to implement only very simple (effectively, randomized) heuristics for transforming potential solutions. For example, for the TSP: "swap two random cities" rather than (say) the more complex Lin-Kernighan heuristic.
2. Achieve effective results (despite using these simple heuristics) by combining/sequencing them in an intelligent way, typically by employing some form of learning mechanism.

Hyper-heuristics can be described as 'selective' or 'generative' depending on whether the heuristics are (respectively) sequenced or combined. Generative hyper-heuristics thus often use methods such as Genetic Programming to combine primitive heuristics and are therefore typically customized by the practitioner to solve a specific problem. For example, the original paper on generative hyper-heuristics used a Learning Classifier System to combine heuristics for bin-packing. Because generative approaches are problem-specific, the comments below do not apply to them.

In contrast, the original motivator for selective hyper-heuristics was that researchers would be able to create a hyper-heuristic solver that was then likely to work well in an unseen problem domain, using only simple randomized heuristics.

The way that this has traditionally been implemented was via the introduction of the 'hyper-heuristic domain barrier' (see figure, below), whereby generality across problem domains is claimed to be achievable by preventing the solver from having knowledge of the domain on which it is operating. Instead, it would solve the problem by operating only on opaque integer indices into a list of available heuristics (e.g. in the manner of the 'Multi-armed Bandit Problem').

In practice, this 'domain blind' approach has not resulted in solutions of sufficient quality. In order to achieve results anywhere comparable to problem-specific metaheuristics, hyper-heuristic researchers have had to implement complex problem-specific heuristics, thereby failing in the goal of rapid prototyping.

It is still possible in principle to create a selective hyper-heuristic solver which is capable of generalizing to new problem domains, but this has been made more difficult since the above notion of domain barrier means that only a very limited feature set is available for cross-domain learning (e.g. as exemplified by a popular selective hyper-heuristic framework).

A more recent research perspective towards 'whitebox' hyper-heuristics advocates a declarative, feature-rich approach to describing problem domains. This approach has a number of claimed advantages:

1. Practitioners now need no longer implement heuristics, but rather simply specify the problem domain.
2. It eliminates the domain-barrier, putting hyper-heuristics on the same 'informed' status about the problem as problem-specific metaheuristics.
3. With a whitebox problem description, the infamous 'No Free Lunch' theorem (which essentially states that, considered over the space of all black box problems, Simulated Annealing with an infinite annealing schedule is, on average, as good as any other approach) no longer applies.

DISCLAIMER: I work in this research area, and it is therefore impossible to remove all personal bias from the answer.