Hyper-Heuristics

A metaheuristic directly searches the problem solution space using problem-specific operators. A hyper-heuristic operates one level above: it searches the space of heuristics, selecting or generating which operator to apply next. This separation provides domain-independence — the same hyper-heuristic framework can be reused across entirely different problem types by simply swapping the low-level heuristic pool.

Both are possible. Selection hyper-heuristics choose from a fixed pool of predefined low-level heuristics at each decision point. Generation hyper-heuristics (e.g., using genetic programming or grammar-based evolution) automatically construct new heuristics during the search. Generation approaches offer higher flexibility but substantially greater computational cost and implementation complexity.

The pool should contain diverse, complementary operators that collectively cover the main structural features of the problem. Typical choices include local search moves (e.g., swap, insert, invert), construction heuristics, and perturbation operators. Redundant or nearly identical heuristics waste selection capacity. A domain expert should supply and validate the pool, even though the hyper-heuristic layer itself remains domain-independent.