Simulated annealing is a probabilistic optimization algorithm inspired by the annealing process in metallurgy, where controlled cooling of materials leads to a more stable crystal structure. It is used to find an approximate solution to optimization problems, especially those that are discrete or combinatorial in nature. ### Key Concepts: 1. **Metaphor of Annealing**: In metallurgy, when a metal is heated and then gradually cooled, it allows the atoms to settle into a more organized and low-energy state.
Articles by others on the same topic
Simulated annealing accepts worse feasible solutions to escape a local minimum. Minimize an objective function , analogous to energy. Effective temperature has the same units as , absorbing the Boltzmann constant; it controls exploration, rather than a material's thermodynamic temperature.[ref]
Optimization by Simulated Annealing by Scott Kirkpatrick and others. Printed pp. 672–673: effective temperature and cost as energy
Given current feasible point , draw from a proposal distribution . For a symmetric proposal distribution, , use the Metropolis–Hastings acceptance probabilityAccept with this conditional probability; on rejection retain . Every downhill or equal-cost proposal is accepted. Draw a fresh uniform random variable on and accept if . The off-diagonal transition probability includes proposing .[ref]
Optimization by Simulated Annealing by Scott Kirkpatrick and others. Printed p. 672: acceptance rule and rejected proposals
For a maximization problem with objective function , set : every improving proposed neighbor is accepted, and a worsening move of loss has conditional probability of acceptance, under the same symmetry assumption. Likelihood-power annealing uses precisely this sign convention for a log-likelihood. Retain the best feasible solution seen, since the current state can worsen even after a global minimum has been visited.
If the proposal distribution is asymmetric, use the full Metropolis–Hastings acceptance probability, for ,A missing reverse proposal gives zero acceptance. Even a downhill proposal need not be accepted with probability one in this case. Choosing uniformly among a variable number of neighbors is generally asymmetric: and give the correction , where is vertex degree.[ref]
The useful idea is to separate exploring from insisting on improvement: an uphill move can open a route to a better feasible solution. Its usefulness depends on the proposal distribution, the scale of the objective function, and the cooling schedule for simulated annealing. Finite practical schedules carry no general guarantee of finding a global minimum.