hyperheuristics

Hyperheuristics are a class of methods designed to solve computational search problems by operating on the space of heuristics themselves rather than directly on candidate solutions. The goal is to achieve greater generality and robustness, enabling a solver to adapt to different problem instances or related problems without extensive manual tuning.

A typical hyperheuristic framework consists of two components: a high-level system that selects or constructs low-level heuristics, and a set of low-level heuristics that actually manipulate solutions. The high-level component acts as a manager that guides the search process by choosing which low-level heuristic to apply next, or by creating new operators. The low-level heuristics are problem-specific operators such as local search moves or constructive rules that modify solutions.

Hyperheuristics are commonly categorized into selection-based and generation-based approaches. Selection-based methods choose from a predefined pool of low-level heuristics using a high-level strategy (for example, a chooser, a penalty-based selector, or reinforcement-learning-guided selection). Generation-based approaches attempt to create or evolve new heuristics themselves, typically using evolutionary or learning techniques. Hybrid approaches combine elements of both.

Applications of hyperheuristics span many domains, including scheduling, vehicle routing, timetabling, bin packing, and other combinatorial optimization problems. They are valued for their ability to perform well across diverse instances and to reduce manual effort in solver design, though they can incur higher computational overhead and require careful design of both the heuristic pool and the high-level control strategy.

The concept emerged in the late 1990s and early 2000s, with foundational surveys and frameworks by researchers such as Burke and Kendall, who helped formalize the taxonomy and evaluation of hyperheuristic methods.