Randomized Heuristics

For optimisation (“marathon”) problems where no exact algorithm fits: search the solution space stochastically and keep the best thing found.

The framework

current = initial_solution()
best = current
while (time_remains()) {
    candidate = perturb(current)
    if (accept(candidate, current)) current = candidate
    if (score(current) > score(best)) best = current
}

Three design decisions: the neighbourhood (what perturb does), the acceptance rule, and the evaluation (which must be fast, ideally incremental).

The acceptance rules

Method	Accepts
Hill climbing	only improvements
Random restarts	improvements; restart from a fresh random solution when stuck
Simulated annealing	improvements always; worsenings with probability $e^{-\Delta /T}$
Tabu search	the best neighbour, but forbids recently reversed moves
Beam search	keeps the best $k$ partial solutions
Genetic algorithms	population, crossover, mutation
MCTS	tree search guided by rollout statistics

Simulated annealing is the default. It is short, robust, and needs almost no tuning beyond a temperature schedule.

double T = T0;
auto start = chrono::steady_clock::now();
while (true) {
    double elapsed = chrono::duration<double>(chrono::steady_clock::now() - start).count();
    if (elapsed > TIME_LIMIT) break;
    T = T0 * pow(T1 / T0, elapsed / TIME_LIMIT);          // geometric cooling
 
    auto [delta, undo] = randomMove();                     // incremental delta
    if (delta > 0 || exp(delta / T) > uniform01(rng)) {
        cur += delta;
        if (cur > best) best = cur, bestState = state;
    } else undo();
}

What actually matters

In practice, ranked by impact:

1. Incremental evaluation. Computing $\Delta$ in $O(1)$ instead of rescoring in $O(n)$ multiplies the iteration count by $n$. This is nearly always the single biggest win.
2. The neighbourhood. Moves must be small enough to be evaluated cheaply, but large enough to escape local optima. Mixing several move types usually beats one.
3. The time budget. Use the whole limit; check the clock, not an iteration count.
4. The temperature schedule. Geometric cooling from $T_0$ (accepting ~50% of worsenings initially) to $T_1$ (accepting almost none).
5. The initial solution — a greedy start helps, but matters less than the above.

Neighbourhood design

Problem type	Moves
Permutation (TSP, scheduling)	swap two, 2-opt reverse a segment, Or-opt move a segment
Assignment	reassign one item, swap two assignments
Subset selection	add, remove, or swap one element
Placement / layout	move one object, swap two, rotate
Graph partition	move a vertex, swap a pair across the cut
Continuous parameters	Gaussian perturbation with a shrinking radius

For TSP specifically, 2-opt (reverse the segment between two edges) is the canonical move, and its $\Delta$ is $O(1)$:

delta = d(a,c) + d(b,d) - d(a,b) - d(c,d);

Escaping local optima

Technique	Idea
Annealing	accept worsenings, decreasingly
Random restarts	start over from a new random solution
Perturbation / kicks	make a large random change, then re-optimise (iterated local search)
Tabu list	forbid undoing recent moves
Population	maintain diverse solutions

Iterated local search — hill-climb to a local optimum, apply a big random kick, hill-climb again, keep the better — is remarkably strong for its simplicity and often beats plain annealing.

Practical checklist

• Seed from the clock, never a fixed value.
• Track the best-ever solution separately — the current state may be worse when time runs out.
• Check the clock, not iterations; judges vary in speed.
• Leave a safety margin (use ~90% of the limit).
• Make the move undoable in $O(1)$ so rejection is free.
• Test with different seeds; high variance means the search is not converging.
• Precompute everything the evaluation needs.

When heuristics are appropriate

Signal
The problem asks to maximise a score, not to match an exact answer	✔
Partial credit / relative scoring	✔
$n$ is large and the problem is NP-hard	✔
A long time limit (several seconds)	✔
The checker verifies validity, not optimality	✔
The problem has a unique correct answer	✘ — do not use a heuristic

On a standard “output the exact answer” problem, a heuristic that is usually right is still a wrong-answer verdict. Use them only where the scoring rewards quality.

See also: Simulated Annealing · MCTS · Approximation Algorithms