Simulated Annealing and Genetic Algorithms — What to Do When Exact Solving Breaks Down

Why search methods that guarantee nothing end up running real delivery routes and factory schedules. From the three ingredients of local search, through temperature in annealing and populations in genetic algorithms, to the harder question of when you should not reach for them at all.

A metaphor: finding the summit in thick fog

Picture yourself on a mountain in fog so thick you can only see your own feet. The one thing you can tell is whether a step goes up or down. Your goal is to stand on the highest point.

The obvious strategy is to keep stepping uphill and stop when every direction goes down. This is hill climbing. Every step is a guaranteed improvement, and it takes about five lines of code. The trouble is that foggy mountains are covered in small rises, and this strategy parks you on top of one of them. If the real summit sits beyond the next valley, reaching it means walking downhill first — and a strategy that only accepts improvement can never do that.

Metaheuristics are the machinery for deliberately allowing that walk downhill. Simulated annealing permits downhill moves with some probability; genetic algorithms scatter a crowd of climbers across the mountain and breed the successful ones. Neither guarantees the optimum, so the first question is why anyone uses a method with no guarantee.

Why exact solving breaks down

Suppose a delivery van has to visit 30 stops and you want the best order. The candidates are the permutations of 30 items — $30!$, roughly $2.6 \times 10^{32}$. Even on a machine that evaluates a trillion orderings per second, that is about eight trillion years.

What makes this treacherous is that the explosion is driven by the number of slots. Twenty stops looks almost manageable; thirty is astronomical. As covered in Complexity from Scratch, the gap between polynomial and exponential growth is not something intuition can hold — it has to be watched.

But do not draw the wrong conclusion. "Large instance, therefore exact methods are hopeless" is false. For the travelling salesman problem, exact solvers combining branch-and-bound with cutting planes have proved optimality on instances with tens of thousands of cities. The dividing line is not the number of candidate solutions — it is whether the solver can exploit the structure of your problem. That line comes back later as a decision table.

Local search — the foundation underneath everything

Both annealing and genetic algorithms sit on top of local search, and local search needs exactly three things.

1. A representation. A delivery order is a permutation of stop indices; a roster is a matrix of person-by-slot assignments
2. A neighbourhood. The set of solutions reachable from the current one in a single move
3. An objective function. One number saying how good a solution is (we write everything as minimisation)

The neighbourhood is where the design work is. For a route, the workhorse move is 2-opt: pick two edges of the tour and reverse the segment between them. For a roster: move one person's shift to another slot, or swap two people's assignments. For a knapsack: exchange an item you packed for one you left behind.

Hill climbing is nothing more than repeatedly taking the best move in the neighbourhood.

def hill_climb(x, energy, neighbors):
    while True:
        best = min(neighbors(x), key=energy)   # best solution in the neighbourhood
        if energy(best) >= energy(x):
            return x                            # nothing improves = local optimum
        x = best

Where this halts is a local optimum. The point worth internalising is that local optimality is relative to the neighbourhood you defined. The same solution can be a local optimum under "swap one item" and stop being one the moment you widen the move to "swap two simultaneously". Wider neighbourhoods mean fewer traps, but each step costs more, so you get fewer steps in the same budget.

Simulated annealing: permission to move the wrong way

Heat metal and cool it slowly, and the atoms settle into a low-energy, regular arrangement. Quench it and the strain freezes in. Kirkpatrick and colleagues carried that physical procedure into optimisation in 1983, and their first application was laying out circuits in computers.

The algorithm adds exactly one thing to hill climbing. Draw a candidate $x'$ at random from the neighbourhood of the current solution $x$ and look at the difference in objective, $\Delta = f(x') - f(x)$. If $\Delta \le 0$, always accept. If $\Delta > 0$ — the move makes things worse — accept it anyway, with this probability:

There are only two symbols. $\Delta$ is how much worse the move is, and $T$ is a positive number called the temperature. All equation (1) says is that smaller damage is easier to accept, and higher temperature makes everything easier to accept. Shrug off a small setback; tolerate a large one only while things are hot.