Hyper-heuristic

A hyper-heuristic is a high-level automated methodology that operates on the space of heuristics rather than directly on the problem domain. Where conventional heuristics are hand-crafted rules tailored to a specific problem type, hyper-heuristics sit one level above, either selecting from a pool of existing low-level heuristics or generating new ones on the fly based on feedback from the ongoing search process. This meta-level perspective allows a single hyper-heuristic framework to be applied across a wide range of problem types without requiring deep domain-specific knowledge at design time.

Hyper-heuristics are broadly categorized into two families: selection hyper-heuristics, which choose which existing heuristic to apply at each decision point, and generation hyper-heuristics, which combine or evolve heuristic components to construct novel strategies. Selection methods typically rely on reinforcement learning, tabu search, or simple choice functions that reward heuristics that have recently improved the solution. Generation methods often employ genetic programming or other evolutionary techniques to synthesize new heuristics from primitive building blocks. Both families use a learning or adaptive component to improve performance over time, guided by feedback signals such as solution quality or search stagnation.

The practical appeal of hyper-heuristics lies in their generality and reusability. They have been successfully applied to scheduling, timetabling, bin packing, vehicle routing, and combinatorial auction problems, frequently matching or outperforming problem-specific algorithms without requiring expert tuning for each new domain. In machine learning contexts, hyper-heuristics intersect with neural architecture search and automated machine learning (AutoML), where the goal is similarly to automate the selection or construction of algorithmic components. As optimization problems grow in scale and complexity, hyper-heuristics represent a principled approach to building solvers that adapt rather than requiring constant human redesign.