Hyper-heuristic

Q: What are the types of hyper-heuristics?

1. Hyper-heuristics to select heuristics2. Hyper-heuristics to generate heuristics

Q: How are selection hyper-heuristics classified?

1. The nature of feedback received2. The nature of the search structure3. The nature of the low-level heuristic set4. The nature of how heuristics are grouped, chosen and applied5. The nature of solutions and objective functions6. The nature of move acceptance7. The nature of parameter setting

Q: What are the applications of hyper-heuristics?

1. Job shop scheduling2. Personnel scheduling3. Nurse rostering4. The traveling salesman problem5. The maximum cut problem6. Wind farm layout7. The boolean satisfiability problem8. 0-1 knapsack problem9. Multidimensional knapsack problem

What is hyper-heuristics?

A hyper-heuristic is a search heuristic that automates the selection, combination, generation, and adaptation of multiple simpler heuristics. It does this to solve complex computational search problems that any of those simpler heuristics could not effectively solve on their own. To achieve it, it often uses machine learning techniques.

Hyper-heuristics came on the scene as a way to increase the level of generality of search techniques for computational search problems. This stands in contrast to several approaches, which represent customised methods for a single problem domain or a narrow class of problem instances. In the early 2000s, the term hyper-heuristic was defined to be a heuristic to choose heuristics, but the idea of designing high-level heuristic methodologies goes all the way back to the early 1960s.

The state-of-the-art in hyper-heuristic research used today is made up of a set of methods that are broadly concerned with intelligently selecting or generating a suitable heuristic for a given situation. They can be considered to be s search methods that operate on lower-level heuristics or heuristic components.

Essentially, hyper-heuristics are high-level automated search methodologies that explore the search space of low-level heuristics or heuristic components to solve those difficult computational search problems.

They seek to reduce the amount of domain knowledge in search methods. The solution chosen or generated should be affordable and easy to implement, without requiring much expertise in heuristics or in the domain in which the problem lies.

A hyper heuristic is essentially a high-level automated search methodology which explores a search space of low-level heuristics (neighbourhood or move operators, or metaheuristics) or heuristic components, for the purpose of solving computationally difficult problems.

What are the types of hyper-heuristics?

There are two types of hyper-heuristics: hyper-heuristics to select heuristics and hyper-heuristics to generate heuristics.

1. Hyper-heuristics to select heuristics

In this type of hyper-heuristics, we provide the hyper-heuristic framework with a set of well-known heuristics that can be used for solving the computational problem in question.

At every stage, a component of the hyper-heuristic called the selection mechanism chooses a heuristic and applies it to an incumbent solution.

Another component of the hyper-heuristic called the acceptance criterion decides whether to accept or reject the solution that was created from the heuristic that was picked by the selection mechanism. If the solution is accepted, it is used to replace the incumbent solution, but if it is rejected, it is discarded.

2. Hyper-heuristics to generate heuristics

This type of hyper-heuristics focuses on creating new heuristics by using components from existing known heuristics. Like hyper-heuristics to select heuristics, hyper-heuristics to generate heuristics also use a set of known heuristics to start off.

But, unlike the other kind of hyper-heuristics, these ones first decompose the pre-existing heuristics into their basic components, proceeding to select components that can be used to create new heuristics to solve the problem instead of just selecting entire heuristics as they are and using them to solve computational problems.

An iterative selection hyper-heuristic makes use of a chosen low-level heuristic to the current solution at each step of a search before it decides whether to accept or reject the newly created solution. If the search stagnates (a locally optimal solution is identified), then a good selection hyper-heuristic will choose an appropriate low-level heuristic to diversify the search to another area of the solution space.

How are hyper-heuristics different from metaheuristics?

The key difference between hyper-heuristics and metaheuristics is that hyper-heuristics only search within a search space of heuristics, while metaheuristics search within a search space of problems solutions.

Essentially, metaheuristics seek to solve problems directly, while hyper-heuristics seek to find or create an appropriate method or sequence of heuristics that can be used to solve the problem.

‍

How are selection hyper-heuristics classified?

Selection hyper-heuristics can be further classifed into several types. We shall explain the extened classification of selection hyper heuristics on the basis of the original classification of Burke et al. (2010).

Selection hyper-heuristics are classified on the basis of:

The nature of feedback received

Selection hyper-heuristics embed online learning methods, offline learning methods, or even a no learning mechanism to process feedback during the search process, influencing the subsequent decisions made at the hyper-heuristic level. There are also mixed learning hyper-heuristics that combine offline as well as online learning.

The nature of the search structure

There are two types of low-level heuristics based on the search structure employed. These are the construction heuristics (which gradually build a solution from scratch, selecting between a set of pre-defined low-level heuristics to apply at each step, incrementally building a complete solution) and perturbation heuristics (which operate on complete solutions, performing local search operations using pre-defined neighbourhood structure).

The nature of the low-level heuristic set

Selection hyper-heuristics control a fixed set of low-level heuristics, every one of them is of a particular type, like mutational, ruin-recreate, local search (hill climbing), crossover or metaheuristics. Selection hyper-heuristic can be permitted to handle the entire set of predefined low-level heuristics, a reduced set of heuristics excluding some specific types of heuristics , or even an increased set of heuristics produced based on the whole set.

The nature of how heuristics are grouped, chosen and applied

Standard selection hyper-heuristics don’t group low-level heuristics, selecting and applying a single heuristic one at a time without distinction. There are other hyper-heuristic methods which group low-level heuristics together and use them separately based on their grouping.

Llow-level heuristics can be fixed and a predefined sequence of heuristic groups can be used. There even are hyper-heuristic methods which operate in a stage-based manner.

The nature of solutions and objective functions

Population (multi-point) based hyper-heuristics employ multiple current solutions since they carry out a search, while single-point based hyper-heuristics a single active current solution. There even are a few studies using a mixed approach, combining both single and multi-point based search in phased manner.

In terms of objectives, you can classify them into single objective and multi objective hyperheuristics.

The nature of move acceptance

On the basis of the nature of move acceptance, they can be classified into stochasitic hyper heuristics or non-stochastic hyper heuristics.

The nature of parameter setting

The parameters can be set in a static manner to a fixed value prior to the search process, in a dynamic manner, allowing the value to change in a predefined manner, or in an adaptive manner allowing the value to change in a reactive manner during the search process. The algorithm can adjust its behaviour, and set its parameters in a self-adaptive manner.