Hyper Heuristics

Hyper-Heuristics

You are an expert in hyper-heuristics for combinatorial optimization — search methods that operate on a space of heuristics rather than directly on the space of solutions. This skill covers selection hyper-heuristics (heuristic selection plus move acceptance), the design of low-level heuristic pools, online learning and credit assignment (reward schemes), and generation hyper-heuristics that assemble new heuristics from components. Use the framework below to take a user from "I have many candidate operators and no idea which to apply when" to a reproducible hyper-heuristic with measured operator usage, a calibrated acceptance criterion, and a defensible ablation against simpler baselines.

Initial Assessment

Establish these facts before writing any hyper-heuristic code:

• Why a hyper-heuristic at all. If one well-understood metaheuristic with one strong neighborhood already works, a hyper-heuristic adds machinery without value. The case for a hyper-heuristic is: a pool of plausible operators with instance-dependent usefulness, heterogeneous instances, or a requirement for cross-domain reuse.
• Pool inventory. Which low-level heuristics already exist (moves, repair rules, construction rules)? A hyper-heuristic cannot fix a weak pool — it only arbitrates among the heuristics it is given. Aim for 4–12 heuristics with genuinely different behaviors.
• Constructive or perturbative low-level heuristics. Constructive heuristics extend a partial solution (pick the next packing rule, the next dispatching rule); perturbative heuristics modify a complete solution (move, swap, ruin-and-recreate). The loop structure differs; decide first.
• Objective and scaling. One scalar objective the engine can read through the domain barrier. If hard constraints are penalized, fix the penalty weights before any credit learning — rewards inherit the objective's scale.
• Evaluation cost and budget. Iterations available = time budget / (heuristic call + evaluation). Credit assignment needs hundreds of selections per heuristic to mean anything; with fewer than ~50 calls per heuristic, use uniform random selection.
• Per-call cost asymmetry. Does the pool mix microsecond moves with millisecond ruin-and-recreate heuristics? If yes, credit must be improvement per unit time, not per call, or cheap heuristics will be unfairly favored — and vice versa.
• Online vs offline learning. Online: learn during the run on this instance (selection rules below). Offline: tune selection/acceptance parameters or evolve heuristics on a training instance set beforehand. Most practical systems combine both.
• No-op behavior. Can a heuristic return the solution unchanged (e.g., no feasible swap found)? Decide how no-ops are credited (zero reward) and detected, or they silently distort the statistics.
• Acceptance scale. Move acceptance needs either a temperature (Metropolis) or a history length (late acceptance). Both must be set relative to the objective scale and the iteration budget.
• Single-domain or cross-domain. A one-problem project can let problem knowledge leak into selection. A cross-domain tool must keep the domain barrier strict: the engine sees only objective values and heuristic indices.
• Baselines. Always run (a) uniform random selection with the same pool and acceptance, and (b) the single best heuristic alone. The learning layer must beat both to justify itself.
• Reproducibility. One np.random.default_rng(seed) per run, seeds and parameters logged per run, usage statistics saved with results.

Hyper-Heuristic Anatomy

Heuristic space and the domain barrier

A hyper-heuristic searches over heuristics: "heuristics to choose heuristics" (Cowling, Kendall & Soubeiga 2001, "A Hyperheuristic Approach to Scheduling a Sales Summit"; the term itself appears in Denzinger, Fuchs & Fuchs 1997). The defining architectural idea is the domain barrier: the high-level strategy sees only (i) the indices of the low-level heuristics, (ii) the objective value returned after applying one, and (iii) bookkeeping such as elapsed time. It never sees the solution representation. Everything problem-specific lives below the barrier, inside the low-level heuristics and the evaluation function. This is what makes the high-level strategy reusable across domains, and it is enforced literally in the HyFlex benchmark framework (Ochoa et al. 2012, "HyFlex: A Benchmark Framework for Cross-domain Heuristic Search").

The standard classification (Burke et al. 2010, "A Classification of Hyper-heuristic Approaches"; surveyed in Burke et al. 2013, "Hyper-heuristics: A Survey of the State of the Art" and Drake et al. 2020, "Recent Advances in Selection Hyper-heuristics") has two axes:

| Axis | Options | Coverage in this skill | |---|---|---| | Nature of the heuristic space | selection (choose from a fixed pool) vs generation (build new heuristics from components) | selection in depth; generation as a working sketch | | Nature of the low-level heuristics | constructive (extend partial solutions) vs perturbative (modify complete solutions) | perturbative engine + constructive bin-packing rules | | Feedback | online learning, offline learning, no learning | online credit schemes; offline tuning/evolution |

Selection hyper-heuristic = heuristic selection + move acceptance

A selection hyper-heuristic decomposes into two nearly independent components (Özcan, Bilgin & Korkmaz 2008, "A Comprehensive Analysis of Hyper-heuristics"): a selection rule that picks the next low-level heuristic, and a move acceptance rule that decides whether the modified solution replaces the incumbent. Both matter; in the CHeSC 2011 cross-domain competition, the winner AdapHH (Mısır et al. 2012) combined adaptive selection with an adaptive acceptance threshold, and ablations show acceptance often contributes more than selection.

Credit assignment. After applying heuristic $i$ to incumbent $x$ and obtaining $x'$, assign a reward and update a quality estimate $q_i$ by a recency-weighted average:

$$ rt = \frac{\max\big(0,\; f(x) - f(x')\big)}{st} \;+\; \mathbf{1}\{f(x') solution` and may mutate their argument (the engine always passes a copy).

SELECTION-HH(x0, pool H = {h1..hk}, budget M)
  x  None:
        self.heuristics = heuristics
        self.objective = objective
        self.copy_solution = copy_solution
        self.selection = selection
        self.acceptance = acceptance
        self.epsilon = epsilon
        self.ucb_c = ucb_c
        self.reward_decay = reward_decay
        self.la_length = la_length
        self.t0 = t0
        self.cooling = cooling
        self.rng = np.random.default_rng(seed)

    def _select(self, q: np.ndarray, n: np.ndarray, it: int) -> int:
        """Pick a heuristic index from quality estimates q and usage counts n."""
        k = q.size
        if self.selection == "uniform":
            return int(self.rng.integers(k))
        if self.selection == "epsilon_greedy":
            if self.rng.random()  bool:
        """Move acceptance: does the candidate replace the incumbent?"""
        if self.acceptance == "improve_only":
            return f_new  HHResult:
        """Run the selection hyper-heuristic loop from initial solution x0."""
        k = len(self.heuristics)
        cur = self.copy_solution(x0)
        f_cur = self.objective(cur)
        best, f_best = self.copy_solution(cur), f_cur
        q = np.zeros(k)                      # recency-weighted reward per heuristic
        n = np.zeros(k)
        accepted = np.zeros(k, dtype=int)
        new_best = np.zeros(k, dtype=int)
        late = np.full(self.la_length, f_cur)
        t = self.t0 if self.t0 is not None else 0.05 * abs(f_cur) + 1e-9
        scale = abs(f_cur) + 1e-9            # running reward normalizer
        trace: list[float] = []
        for it in range(n_iters):
            i = self._select(q, n, it)
            cand = self.heuristics[i](self.copy_solution(cur), self.rng)
            f_cand = self.objective(cand)
            n[i] += 1
            reward = max(0.0, f_cur - f_cand) / scale
            if f_cand  float:
    """Quadratic pseudo-boolean objective x^T Q x (minimize)."""
    return float(x @ Q @ x)

def flip_one(x: np.ndarray, rng: np.random.Generator) -> np.ndarray:
    """Flip one random bit."""
    x[int(rng.integers(x.size))] ^= 1
    return x

def flip_three(x: np.ndarray, rng: np.random.Generator) -> np.ndarray:
    """Flip three distinct random bits."""
    x[rng.choice(x.size, 3, replace=False)] ^= 1
    return x

def flip_block(x: np.ndarray, rng: np.random.Generator) -> np.ndarray:
    """Flip a contiguous block of five bits (strong perturbation)."""
    j = int(rng.integers(x.size - 5))
    x[j:j + 5] ^= 1
    return x

def best_single_flip(x: np.ndarray, rng: np.random.Generator) -> np.ndarray:
    """Greedy: flip the bit with the steepest objective decrease."""
    s = Q @ x - np.diag(Q) * x
    deltas = (1 - 2 * x) * (np.diag(Q) + 2 * s)
    x[int(np.argmin(deltas))] ^= 1
    return x

pool = [flip_one, flip_three, flip_block, best_single_flip]
x0 = rng0.integers(0, 2, N)
hh = SelectionHyperHeuristic(pool, f_bqp, np.copy, selection="epsilon_greedy",
                             acceptance="late_acceptance", la_length=80, seed=11)
res = hh.run(x0, n_iters=3000)
print(f"f(x0)={f_bqp(x0):.1f}  f_best={res.f_best:.1f}")
names = ["flip1", "flip3", "block5", "greedy"]
print("usage:", dict(zip(names, res.usage)))
print("new_best:", dict(zip(names, res.new_best)))
# Expected: f_best around -229 from a start near -33; usage concentrates on
# the greedy flip (~1,900 of 3,000 calls, ~35 of ~36 new bests), with
# flip_one second (~870 calls) as the cheap escape move.

Read the usage statistics before celebrating: a healthy $\varepsilon$-greedy run shows the intensifier exploited heavily while the exploration floor keeps every heuristic alive. Selection rules differ in how the learning shows up: on this same instance UCB finds the same $f^{best}$ but with near-uniform usage (750 calls each), because once rewards vanish its confidence radii equalize the counts — under UCB, read the new_best and accepted columns, not raw usage. If a blind perturbation dominates new_best, the reward scale or the acceptance criterion is broken.

Worked Example 1: Exam Timetabling Selection Hyper-Heuristic

Timetabling is the classic hyper-heuristic domain (the field grew out of timetabling and rostering systems; see timetabling-and-rostering for full domain models and benchmark formats). The instance here: $n$ events, $T$ timeslots, and a symmetric conflict matrix $C$ where $C_{ij}$ counts students enrolled in both events $i$ and $j$. The solution is a slot vector $s \in \{0,\dots,T-1\}^n$. The cost combines hard conflicts (same slot) and a proximity soft cost — a linear simplification of the Carter cost $2^{4-d}$ (Carter, Laporte & Lee 1996, "Examination Timetabling: Algorithmic Strategies and Applications"):

$$ f(s) = W \sum{i tuple[np.ndarray, int]: """Random symmetric conflict matrix; C[i, j] = students shared by events i, j.""" rng = np.random.defaultrng(seed) raw = np.where(rng.random((nevents, nevents)) float: """Hard: conflicting events in one slot. Soft: proximity max(0, 3 - d).""" D = np.abs(slots[:, None] - slots[None, :]) hard = (C (D == 0)).sum() / 2.0 soft = (C np.maximum(0, 3 - D) (D > 0)).sum() / 2.0 return hard_weight float(hard) + float(soft)

def maketimetablingpool(C: np.ndarray, n_slots: int) -> list: """Five perturbative low-level heuristics closing over the instance.""" n = C.shape[0]

def event_penalty(slots: np.ndarray) -> np.ndarray: """Per-event share of the total cost (for targeting bad events).""" D = np.abs(slots[:, None] - slots[None, :]) pen = C ((D == 0) 1000.0 + np.maximum(0, 3 - D) * (D > 0)) return pen.sum(axis=1)

def moverandom(slots: np.ndarray, rng: np.random.Generator) -> np.ndarray: """Move one random event to one random slot.""" slots[int(rng.integers(n))] = int(rng.integers(nslots)) return slots

def moveworstgreedy(slots: np.ndarray, rng: np.random.Generator) -> np.ndarray: """Pick among the 5 worst events; place it in its cheapest slot.""" e = int(rng.choice(np.argsort(eventpenalty(slots))[-5:])) costs = np.empty(nslots) for sl in range(n_slots): d = np.abs(slots - sl) costs[sl] = (C[e] ((d == 0) 1000.0

• np.maximum(0, 3 - d) * (d > 0))).sum()

slots[e] = int(rng.choice(np.flatnonzero(costs == costs.min()))) return slots

def swap_events(slots: np.ndarray, rng: np.random.Generator) -> np.ndarray: """Exchange the slots of two random events.""" a, b = rng.choice(n, 2, replace=False) slots[a], slots[b] = slots[b], slots[a] return slots

def kempechain(slots: np.ndarray, rng: np.random.Generator) -> np.ndarray: """Swap a Kempe chain between a random event's slot and a target slot.""" e = int(rng.integers(n)) a, b = int(slots[e]), int(rng.integers(nslots)) if a == b: return slots inab = (slots == a) | (slots == b) chain, frontier = {e}, [e] while frontier: v = frontier.pop() for u in np.flatnonzero((C[v] > 0) & inab): if int(u) not in chain: chain.add(int(u)) frontier.append(int(u)) idx = np.fromiter(chain, dtype=int) slots[idx] = np.where(slots[idx] == a, b, a) return slots

def shuffleslot(slots: np.ndarray, rng: np.random.Generator) -> np.ndarray: """Scatter all events of one random slot (diversification).""" members = np.flatnonzero(slots == int(rng.integers(nslots))) if members.size: slots[members] = rng.integers(n_slots, size=members.size) return slots

return [moverandom, moveworstgreedy, swapevents, kempechain, shuffleslot]

The pool deliberately mixes intensifiers (`move_worst_greedy`, `kempe_chain` — the standard timetabling/coloring move that swaps a connected component between two slots and never splits a conflict pair across the wrong side) with diversifiers (`move_random`, `shuffle_slot`). That mix is what the selection layer is for: the right blend changes between the "repair hard conflicts" phase and the "polish proximity cost" phase, and the credit scheme tracks the change.

```python
"""Run the engine on a 50-event, 9-slot instance and report usage."""
import numpy as np

C, n_slots = make_timetabling_instance(n_events=50, n_slots=9,
                                       density=0.20, seed=3)
pool = make_timetabling_pool(C, n_slots)
names = ["move_random", "move_worst_greedy", "swap_events",
         "kempe_chain", "shuffle_slot"]

x0 = np.random.default_rng(1).integers(n_slots, size=50)
hh = SelectionHyperHeuristic(
    heuristics=pool,
    objective=lambda s: timetable_cost(s, C),
    copy_solution=np.copy,
    selection="epsilon_greedy",
    acceptance="late_acceptance",
    la_length=200,
    seed=1,
)
res = hh.run(x0, n_iters=6000)
D = np.abs(res.best[:, None] - res.best[None, :])
hard_left = int((C * (D == 0)).sum() / 2)
print(f"start cost={timetable_cost(x0, C):.0f}  final cost={res.f_best:.0f}  "
      f"hard conflicts left={hard_left}")
for nm, u, a, b in zip(names, res.usage, res.accepted, res.new_best):
    print(f"{nm:18s} used={u:5d} accepted={a:5d} new_best={b:3d}")
# Expected: hard conflicts reach 0 and the final cost is pure proximity
# penalty around 270 (start: ~158,600). Usage concentrates on
# move_worst_greedy (~2,600 calls, every one accepted, ~47 new bests) and
# kempe_chain (~1,700 calls); shuffle_slot stays a rare diversifier.

Worked Example

…

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: hajibabaie
• Source: hajibabaie/combinatorial-optimization-skills
• License: MIT

Install and usage instructions live in the source repository linked above.