simulated annealing
In plain wordsAn optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops.
A probabilistic local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch. method for optimization that, at each step, proposes a random neighbor of the current solution, always accepts it if it is better, and accepts a worse one with probability exp(−Δ/T), where Δ is the increase in cost and T a temperature parameter. T starts high, so the search roams widely and can escape local optima, and is lowered according to a cooling schedule, so the search settles into a good region and finally behaves like hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak.. With a sufficiently slow (logarithmic) schedule it converges in probability to a global optimum, although practical schedules are far faster and carry no such guarantee. It is widely used for placement and routing in chip design, scheduling and other combinatorial problems.
Simulated annealing cut total wire length by 12 percent over the greedy placement.
Origin
Introduced by Scott Kirkpatrick, C. Daniel Gelatt and Mario Vecchi of IBM in Science (1983), and independently by Vladimír Černý (1985), adapting the Metropolis algorithm of 1953 for simulating atoms in thermal equilibrium. The name alludes to annealing in metallurgy, where slow cooling yields a low-energy crystal structure.
Usage note
Distinct from learning-rate annealingannealing, n.: The last stretch of training, when the model's learning is slowed to a stop — often while it is fed a small helping of the best data — so it settles into its final, sharpest version. in neural-network training, which borrows the metaphor for gradually shrinking step sizes, though both descend from the same statistical-physics idea as sampling temperaturetemperature, n.: A setting that controls how adventurous an AI model's word choices are. Low temperature makes it pick the safest, most likely words; high temperature makes it more varied and surprising, but more error-prone..
Related
- hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak.
- local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch.
- metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one.
- Markov chain Monte CarloMarkov chain Monte Carlo, n.: A family of methods for drawing random examples from a complicated probability distribution by taking a long, carefully designed random walk that eventually visits each region in proportion to its probability.
- genetic algorithmgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve.
- tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends.
Sources
- Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science 220(4598), 671–680.
- Černý, V. (1985). Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm. Journal of Optimization Theory and Applications 45(1), 41–51.
Mentioned in
temperaturetemperature, n.: A setting that controls how adventurous an AI model's word choices are. Low temperature makes it pick the safest, most likely words; high temperature makes it more varied and surprising, but more error-prone., annealingannealing, n.: The last stretch of training, when the model's learning is slowed to a stop — often while it is fed a small helping of the best data — so it settles into its final, sharpest version., Boltzmann machineBoltzmann machine, n.: A network of randomly flipping on–off units, including hidden ones, that learns the statistical patterns in its training data and can then produce new examples like them., cosine annealingcosine annealing, n.: A popular plan for shrinking a model's step size during training: steps start large, shrink slowly, then faster, then level off near zero, following the shape of half a wave., genetic algorithmgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve., heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak., traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added., evolution strategiesevolution strategies, n.: A family of evolution-inspired methods for tuning a list of numbers: try many random variations of the current best settings, keep those that work better, and adjust how big the variations are as you go., local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch., metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one., tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends.