Simulated Annealing Algorithm

Simulated annealing is a probabilistic optimization algorithm that searches for a near-optimal solution to a problem with many competing local optima, such as the traveling salesman problem, by modeling the physical process of annealing a metal, where slow controlled cooling settles the material into a low-energy, well-ordered state. The algorithm starts its search at a high notional temperature, at which it will often accept a move to a worse solution as well as a better one, and gradually lowers that temperature over the course of the run so the probability of accepting a worse move falls off, until the search settles on a solution near a good optimum. Accepting occasional worse moves early on is what lets the algorithm escape a local optimum that a method which only ever improves would get stuck in. The technique traces its mathematical root to the Metropolis-Hastings algorithm, a 1953 Monte Carlo method, and was independently explored by several researchers in the 1970s before Scott Kirkpatrick, C. Daniel Gelatt and Mario Vecchi gave it its current name and applied it to the traveling salesman problem in a widely cited 1983 paper.