Simulated Annealing
Escape local minima by sometimes stepping uphill — with a probability set by a temperature that slowly cools from bold exploration to careful descent.
Simulated Annealing
Gradient descent only ever goes downhill, so it gets trapped in the first valley it falls into. Simulated annealing borrows a trick from metallurgy to escape: heat the system so it can jump around freely, then cool it slowly so it settles into a deep, low-energy configuration. Concretely, at each step you propose a random move. If it lowers the loss (energy E), you always take it. If it raises the loss by \Delta E, you take it anyway — but only with probability
When the temperature T is high, even big uphill jumps are likely, so the walker roams the whole landscape, hopping out of any trap. As T falls, uphill moves become rarer and rarer, and the walker is squeezed into the deepest basin it has found. This accept-with-probability rule makes the search a Markov Chain (the Metropolis algorithm), and choosing moves at random makes it a Monte Carlo method.
Cooling into the global minimum
Below, a walker explores a rugged one-dimensional landscape. At high temperature it leaps boldly, even uphill, sampling far-apart valleys. As the temperature bar on the right drains, its jumps shrink and uphill moves all but stop, until it settles — usually into the deepest valley, not just the nearest. The best point found so far is marked.
Click anywhere to reheat and watch a fresh anneal from a random start.