Skip to main content

Heuristics and Metaheuristics

A heuristic constructs or improves feasible solutions without necessarily proving the best possible objective. A metaheuristic supplies a broader search pattern—such as tabu search, simulated annealing, or evolutionary search—but the same evidence rule applies: a best-seen solution is not an optimum unless a certificate supports it.

Prerequisites​

Complete simulation-based optimization and review routing and time windows.

Learning goals​

  • Specify representation, feasibility repair, evaluation budget, seed, and stopping rule.
  • Run multiple independent seeds and report dispersion, not only the winner.
  • Compare methods with equivalent budgets and common instances.
  • Separate feasible incumbent quality from an optimality certificate or bound.

Reproducible quality evidence​

The teaching heuristic samples 40 permutations for each of five fixed seeds. Lexicographic tie-breaking makes the retained tour deterministic. Every sampled tour is feasible because it visits each customer exactly once; a real constrained route heuristic would also need an explicit repair or rejection rule.

An evaluation budget is often more comparable than wall-clock time across machines, though evaluations can have unequal cost. Preserve the solver/library version, initialization, worker count, and stopping conditions. Parallel scheduling may change a seeded stochastic trace.

Worked example​

import numpy as np

travel = np.array([
[0, 4, 7, 3, 6],
[4, 0, 2, 5, 4],
[7, 2, 0, 6, 3],
[3, 5, 6, 0, 2],
[6, 4, 3, 2, 0],
])

def tour_cost(order):
route = (0, *order, 0)
return sum(int(travel[left, right]) for left, right in zip(route, route[1:]))

seeds = list(range(60, 65))
run_bests = []
for seed in seeds:
rng = np.random.default_rng(seed)
candidates = [tuple(rng.permutation(np.arange(1, 5)).tolist()) for _ in range(40)]
best = min((tour_cost(candidate), candidate) for candidate in candidates)
run_bests.append(best[0])
print(f"seeds={seeds} evaluations_per_run=40")
print(f"best_costs={run_bests} best_seen_cost={min(run_bests)}")
print("quality_label=best_seen optimality_proven=False")

Expected output:

seeds=[60, 61, 62, 63, 64] evaluations_per_run=40
best_costs=[14, 14, 18, 14, 14] best_seen_cost=14
quality_label=best_seen optimality_proven=False

One run returns 18 while four return 14. The verifier can exhaustively enumerate this tiny fixture and knows 14 is optimal, but the heuristic output deliberately makes no such claim: that extra enumeration is the certificate, not the observed best.

Limitations and common mistakes​

  • Reporting only the best seed is selection bias. Keep every planned run and its budget.
  • A fixed seed aids replay; it does not make a stochastic algorithm generally reliable.
  • Comparing a heavily tuned heuristic with an untuned baseline or a larger budget is not a fair benchmark.
  • Feasibility checks and operational invariants remain mandatory even when the objective improves.

Practice​

Reduce the budget to five evaluations per seed, then increase it to 200. Report success frequency and every run's best cost; do not rename the best-seen result “optimal.”

Next steps​

Learn how exact and limited runs communicate evidence in solver statuses, gaps, and time limits.

Primary sources​

Checked 2026-10-19: Storn and Price, Differential Evolution—A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces; SciPy 1.18.1, differential_evolution RNG, workers, and termination contract; Google OR-Tools, routing search options.