Many real optimisation problems are too large or too complicated for an exact method: school timetables with dozens of constraints, delivery rounds with time windows, the layout of machinery in a factory. Metaheuristics are general strategies for finding good solutions in these cases. They do not guarantee the optimum, but in reasonable time they often find very good solutions, and they adapt to different problems by changing just a few ingredients.
The starting point: local search
Almost all metaheuristics start from local search. Three things are needed:
- a representation of the solution (for the travelling salesman, the order of the cities);
- a cost function to minimise (the length of the tour, plus any penalties for violated constraints);
- a neighbourhood: the solutions reachable with a small change (for example a 2-opt move, or swapping two elements).
The simplest local search, called descent or hill climbing, starts from a solution and moves to a better neighbour as long as one exists. The limit is obvious: it stops at the first local optimum, a solution better than all its neighbours but potentially much worse than the global optimum. It is like a hiker in the fog who always walks downhill and stops in the first hollow, unaware that a much deeper valley lies further on.
Metaheuristics are, in essence, different ways of getting out of those hollows.
Simulated annealing
Simulated annealing borrows its idea from metallurgy: a metal cooled slowly forms a more ordered structure than one cooled quickly. The algorithm:
- picks a random neighbour;
- if it is better, accepts it;
- if it is worse by an amount Δ, accepts it anyway with probability e^(−Δ/T), where T is the «temperature»;
- gradually lowers T.
import math, random
def annealing(sol, cost, neighbour, T=100.0, alpha=0.995, steps=100000):
best = current = sol
for _ in range(steps):
cand = neighbour(current)
delta = cost(cand) - cost(current)
if delta < 0 or random.random() < math.exp(-delta / T):
current = cand
if cost(current) < cost(best):
best = current
T *= alpha
return best
At the start, with T high, worse moves are often accepted and the search explores freely. As T falls, worse moves are accepted less and less and the search settles down. The most delicate choice is the cooling schedule: too fast and you get stuck in a local optimum, too slow and you waste time.
Tabu search
Tabu search is deterministic and uses memory. At each step it moves to the best neighbour, even if it is worse than the current solution. To avoid going straight back and circling, it keeps a tabu list of recent moves, which stay forbidden for a certain number of iterations.
Typical elements:
- tabu tenure: how many iterations a move stays forbidden; small values risk cycles, large values restrict the search too much;
- aspiration criterion: a tabu move is allowed anyway if it leads to a solution better than any seen so far;
- diversification: if the search stagnates, rarely used moves are favoured to move into new regions.
Tabu search is very effective on scheduling and assignment problems, where evaluating all neighbours is reasonably fast.
Genetic algorithms
Genetic algorithms work on a population of solutions instead of a single one, imitating natural selection in an abstract way:
- selection: better solutions are more likely to be chosen as «parents»;
- crossover: two parents combine to produce children that inherit parts of both;
- mutation: small random changes preserve diversity;
- replacement: the children take the place of part of the population.
The critical point is crossover. For many problems, naively combining two valid solutions produces invalid ones: joining half of one travelling salesman tour with half of another gives repeated cities and missing cities. Operators designed for the problem are needed, such as order crossover for permutations. In practice, genetic algorithms work best when each child is also improved with local search: these are called memetic algorithms.
Comparison
| Method | Active solutions | How it escapes local optima | Delicate point |
|---|---|---|---|
| Simulated annealing | one | accepts worse moves with decreasing probability | cooling schedule |
| Tabu search | one | forbids recent moves | tabu tenure and neighbourhood |
| Genetic algorithms | many | recombines different solutions | crossover operators |
Practical tips
- The neighbourhood matters more than the metaheuristic: a good set of moves, evaluated incrementally (computing only the change in cost), is worth more than any well-chosen parameter.
- Constraints as penalties: it often pays to allow solutions that violate some constraints, adding a penalty to the cost, instead of forbidding them. The search moves more freely.
- Compare against a simple baseline: a greedy followed by descent with random restarts is an honest reference. If the metaheuristic does not beat it, something needs revisiting.
- Several runs: randomised methods give different results on each run; compare means and spread over several trials, not a single lucky result.
- Lower bounds: where possible, a linear relaxation or a combinatorial bound tells you how far you are from the optimum.
In short
- Local search improves a solution with small moves but stops at the first local optimum.
- Simulated annealing accepts worse moves with a probability that falls with the temperature.
- Tabu search always moves to the best neighbour and temporarily forbids recent moves.
- Genetic algorithms evolve a population and perform better when combined with local search.
- A well-designed neighbourhood, penalties on constraints and honest comparisons matter more than parameters.
