Local search

Simulated Annealing

Wander boldly at first, then settle down to find the best spot.

Interactive demo coming soon — read the theory below

The idea

Simulated Annealing is a local search method that tweaks one candidate solution over and over, keeping better tweaks and sometimes accepting worse ones so it can escape traps. A "temperature" starts high (lots of risky moves, wide exploration) and slowly cools (fewer risky moves, careful fine-tuning). The chance of accepting a worse move is e^(-deltaE/T), so bad moves get rarer as things cool. Cool slowly enough and, in theory, it lands on the global best.

How it works

Start with any solution (even a random one) and set the temperature T high.
Make a small random change to get a neighbour solution.
Measure deltaE = neighbour's cost minus current cost (how much worse the new one is; negative means better).
If the neighbour is better (deltaE < 0), always move to it.
If it's worse, move to it anyway with probability e^(-deltaE/T) - roll a random number and accept if it falls under that probability.
Cool the temperature a little (for example multiply T by 0.95).
Repeat: high T early means many worse moves accepted (explore); low T later means almost only better moves accepted (exploit).
Stop when T is near zero or a step limit is hit, and return the best solution seen.

OPEN, CLOSED & the data structures

A single current state (the solution being tweaked) and its cost/energy; a temperature variable T that decreases over time following a cooling schedule; a way to generate a random neighbour; and usually a separate "best-so-far" state so you never lose the best solution you stumbled on.

Pseudocode

function SimulatedAnnealing(start, T, cooling):
    current = start
    best = current
    while T > T_min:
        next = random_neighbour(current)
        deltaE = cost(next) - cost(current)
        if deltaE < 0:                     # better: always take it
            current = next
        else if random(0,1) < exp(-deltaE / T):   # worse: sometimes take it
            current = next
        if cost(current) < cost(best):
            best = current
        T = T * cooling                    # cool down (e.g. 0.95)
    return best

At a glance

Complete?Not guaranteed in a strict sense - it returns whatever it has when time or temperature runs out. In practice it almost always returns a usable solution, and it keeps a "best-so-far" so the answer never gets worse than the best it found.

Optimal?In theory yes: with a slow enough cooling schedule it converges to the global optimum. In practice no - real runs cool faster than theory demands, so you get a very good solution but not a guaranteed perfect one.

TimeDepends on the cooling schedule and steps per temperature, not on problem size directly. Roughly O(steps) cost evaluations; slower cooling means more steps and better results. The theoretical global-optimum guarantee needs impractically slow cooling.

SpaceO(1) extra beyond the problem - it only stores the current state, the best-so-far state, and the temperature. This tiny memory footprint is a key advantage over search methods that keep large frontiers.

👍 When to use it

Big optimization problems where the search space is huge and you just need a very good answer, not a provably perfect one (e.g. scheduling, routing, layout).
Landscapes full of local optima where plain hill-climbing gets stuck on small bumps.
When memory is tight - it only ever holds one current solution plus the best found.
When you can cheaply generate a small random change and score how good a solution is.

⚠️ Watch out for

The cooling schedule matters most: cool too fast and you freeze in a local optimum; cool too slow and it takes forever.
e^(-deltaE/T) applies only to worse moves; better moves are always accepted, so don't gate them behind the probability.
deltaE is defined so a positive value means worse - keep your sign convention straight or the accept rule flips.
It's randomized, so two runs give different results; run it several times and keep the best.
Always track a best-so-far separately, because the current state can wander to a worse spot right before you stop.
The global-optimum guarantee is theoretical only; real-world runs trade that guarantee for speed.