Simulated Annealing on a Toy Problem

Escape local minima by accepting uphill moves with a probability that cools over time, mimicking metallurgical annealing.

The idea

Greedy descent gets stuck in the first local minimum it finds. Simulated annealing borrows from physics: at high temperature it accepts worse solutions freely, exploring widely; as temperature falls it becomes increasingly greedy, settling into a deep minimum.

Acceptance rule

Propose a move; if it lowers the cost, accept it. If it raises the cost by delta, accept it anyway with probability exp(-delta/T). The temperature T starts high and decays on a schedule, e.g. geometric T <- 0.99 T.

import numpy as np
# bumpy 1D cost with many local minima
cost=lambda x: x*x + 10*np.sin(3*x)**2
x=5.0; T=10.0; best=x
for i in range(20000):
    xp=x+np.random.randn()*0.5
    d=cost(xp)-cost(x)
    if d<0 or np.random.rand()<np.exp(-d/T): x=xp
    if cost(x)<cost(best): best=x
    T*=0.9995
print(round(best,3), round(cost(best),3))  # near global min

The cooling schedule

Everything depends on the schedule. Cool too fast and the search freezes in a poor local minimum (quenching); cool too slowly and you waste effort. A theoretical result guarantees convergence to the global optimum only for logarithmically slow cooling - impractically slow - so real schedules are heuristic compromises.

Where it shines

Simulated annealing needs no gradient and handles rough, discrete, or combinatorial landscapes - travelling salesman, chip placement, scheduling. It trades guarantees for generality, making it a reliable default when the objective is a black box with many local traps.