Gourt Home::Gourt :: Simulated annealing
Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. It was independently invented by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi in 1983, and by V. Černý in 1985.
The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one.
By analogy with this physical process, each step of the SA algorithm replaces the current solution by a random "nearby" solution, chosen with a probability that depends on the difference between the corresponding function values and on a global parameter T (called the temperature), that is gradually decreased during the process. The dependency is such that the current solution changes almost randomly when T is large, but increasingly "downhill" as T goes to zero. The allowance for "uphill" moves saves the method from becoming stuck at local minima—which are the bane of greedier methods.
Overview
In the simulated annealing (SA) method, each point s of the search space is compared to a state of some physical system, and the function E(s) to be minimized is interpreted as the internal energy of the system in that state. Therefore the goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy.
The basic iteration
At each step, the SA heuristic considers some neighbour s' of the current state s, and probabilistically decides between moving the system to state s' or staying put in state s. The probabilities are chosen so that the system ultimately tends to move to states of lower energy. Typically this step is repeated until the system reaches a state which is good enough for the application, or until a given computation budget has been exhausted.The neighbours of a state
The neighbours of each state are specified by the user, usually in an application-specific way. For example, in the traveling salesman problem, each state is typically defined as a particular tour (a permutation of the cities to be visited); then one could define two tours to be neighbours if and only if one can be converted to the other by interchanging a pair of adjacent cities.Transition probabilities
The probability of making the transition from the current state s to a candidate new state s' is a function P(e, e' , T) of the energies e = E(s) and e' = E(s' ) of the two states, and of a global time-varying parameter T called the temperature.One essential requirement for the transition probability P is that it must be nonzero when e' > e, meaning that the system may move to the new state even when it is worse (has a higher energy) than the current one. It is this feature that prevents the method from becoming stuck in a local minimum — a state whose energy is far from being minimum, but is still less than that of any neighbour.
On the other hand, when T goes to zero, the probability P(e, e' , T) must tend to zero if e' > e, and to a positive value if e' < e. That way, for sufficiently small values of T, the system will increasingly favor moves that go "downhill" (to lower energy values), and avoid those that go "uphill". In particular, when T becomes 0, the procedure will reduce to the greedy algorithm — which makes the move if and only if it goes downhill.
The P function is usually chosen so that the probability of accepting a move decreases when the difference e' e increases — that is, small uphill moves are more likely than large ones. However, this requirement is not strictly necessary, provided that the above requirements are met.
Given these properties, the evolution of the state s depends crucially on the temperature T. Roughly speaking, the evolution of s is sensitive only to coarser energy variations when T is large, and to finer variations when T is small.
The annealing schedule
Another essential feature of the SA method is that the temperature is gradually reduced as the simulation proceeds. Initially, T is set to a high value (or infinity), and it is decreased at each step according to some annealing schedule — which may be specified by the user, but must end with T=0 towards the end of the allotted time budget. In this way, the system is expected to wander initially towards a broad region of the search space containing good solutions, ignoring small features of the energy function; then drift towards low-energy regions that become narrower and narrower; and finally move downhill according to the steepest descent heuristic.In plain English
Given an incredibly hard problem, such as finding a set of 100 numbers that fit some characteristic, for which attempting to brute-force the problem would result in several million years worth of computation, this technique attempts to quickly find a "pretty good" answer by adjusting the current "set" (in this case some random sequence of 100 numbers) until a "better" answer is found (the way the adjustment is done depends on the problem). The new set of numbers, or "neighbour", if more optimal, is then used as the current set and the process is repeated.Sometimes a problem may arise when one approaches what is known as a local minimum, in this case, a set of numbers that is the "most optimized" for its current "region". In an attempt to find a better optimization, this technique may use various methods to "jump out of" the current "pit", such as searching for better optimizations randomly by a factor of the inverse amount of the previous adjustment. Keep in mind that implementations of this method are strictly problem specific, and so the way in which one finds an optimization will vary from problem to problem.
Convergence to optimum
It can be shown that, for any given finite problem, the probability that the simulated annealing algorithm terminates with the global optimal solution approaches 1 as the annealing schedule is extended. This theoretical result is, however, not particularly helpful, since the annealing time required to ensure a significant probability of success will usually exceed the time required for a complete search of the solution space.
Pseudo-code
The following pseudo-code implements the simulated annealing heuristic, as described above, starting from state s0 and continuing to a maximum of kmax steps or until a state with energy emax or less is found. The call neighbour(s) should generate a randomly chosen neighbour of a given state s; the call random() should return a random value in the range
s := s0; e := E(s) // Initial state, energy.
k := 0 // Energy evaluation count.
while k < kmax and e > emax // While time remains & not good enough:
sn := neighbour(s) // Pick some neighbour.
en := E(sn) // Compute its energy.
if random() < P(e, en, temp(k/kmax)) then // Should we move to it?
s := sn; e := en // Yes, change state.
k := k + 1 // One more evaluation done
return s // Return current solution
Saving the best solution seen
As in any metaheuristic, one should keep track of the best solution seen so far, in a separate state variable. Namely:
s := s0; e := E(s) // Initial state, energy.
sb := s; eb := e // Initial "best" solution
k := 0 // Energy evaluation count.
while k < kmax and e > emax // While time remains & not good enough:
sn := neighbour(s) // Pick some neighbour.
en := E(sn) // Compute its energy.
if en < eb then // Is this a new best?
sb := sn; eb := en // Yes, save it.
if random() < P(e, en, temp(k/kmax)) then // Should we move to it?
s := sn; e := en // Yes, change state.
k := k + 1 // One more evaluation done
return sb // Return the best solution found.
While copying the state may be an expensive operation, this step happens only on a small fraction of the moves, so the change is usually worth the cost.
Restarts
Sometimes it is better to move back to a solution that was significantly better rather than always moving from the current state. This is called restarting. To do this we set s and e to sb and eb and perhaps restart the annealing schedule. The decision to restart could be based on a fixed number of steps, or based on the current energy being too high from the best energy so far.
Selecting the parameters
In order to apply the SA method to a specific problem, one must specify the state space, the neighbour selection method (which enumerates the candidates for the next state s' ), the probability transition function, and the annealing schedule. These choices can have a significant impact on the method's effectiveness. Unfortunately, there are no choices that will be good for all problems, and there is no general way to find the best choices for a given problem. About the only guidance available is that choices that maximize the correlation between the energies of neighbouring states can lead to better solutions. It has therefore been observed that applying the SA method is more of an art than a science.
State neighbours
The neighbour selection method is particularly critical. The method may be modeled as a search graph — where the states are vertices, and there is an edge from each state to each of its neighbours. Roughly speaking, it must be possible to go from the initial state to a "good enough" state by a relatively short path on this graph, and such a path must be as likely as possible to be followed by the SA iteration.In practice, one tries to achieve this criterion by using a search graph where the neighbours of s are expected to have about the same energy as s. Thus, in the traveling salesman problem above, generating the neighbour by swapping two adjacent cities is expected to be more effective than swapping two arbitrary cities. It is true that reaching the goal can always be done with only n-1 general swaps, while it may take as many as n(n-1)/2 adjacent swaps. However, if one were to apply a random general swap to a fairly good solution, one would almost certainly get a large energy increase, and thus an extremely low probability of a swap. The probability of swapping two adjacent cities is more likely to have a smaller energy increase, and thus a much greater probability of a swap. In fact, the swap probability is so much greater in the latter case that the choice of adjacent cities leads to a more efficient algorithm. This is a special case of the general heuristic that "more correlated landscapes are better", as noted above.
Transition probabilities
The transition probability function P is not as critical as the neighbourhood graph, provided that it follows the general requirements of the SA method stated before. Since the probabilities depend on the temperature T, in practice the same probability function is used for all problems, and the annealing schedule is adjusted accordingly.In the original formulation of the method by Kirkpatrick et. al, the transition probability P(e, e' , T) was defined as 1 if e' < e (i.e., downhill moves were always performed); otherwise, the probability would be exp((ee' )/T).
This formula was said to come from the Metropolis-Hastings algorithm, used here to generate samples from the Maxwell-Boltzmann distribution governing the distribution of energies of molecules in a gas. However, there is no mathematical justification for using this particular formula in SA. Even the physical analogy is misleading: since the neighbours are tested sequentially in the SA algorithm, the actual probability of the SA algorithm moving from a state s to a state s' definitely is not given by that formula.
Annealing schedule
The annealing schedule is less critical than the neighbourhood function, but still must be chosen with care. The initial temperature must be large enough to make the uphill and downhill transition probabilities about the same. To do that, one must have some estimate of the difference e' e for a random state and its neighbours.The temperature must then decrease so that it is zero, or nearly zero, at the end of the alloted time. A popular choice is the exponential schedule, where the temperature decreases by a fixed factor α < 1 at each step.
Related methods
Tabu search (TS) is similar to simulated annealing, in that both traverse the solution space by testing neighbours of the current solution. In order to prevent cycling, the TS algorithm maintains a "tabu list" of solutions already seen, and moves to those solutions are suppressed.
Stochastic hill climbing (SH) runs many hill-climbing searches from random initial locations.
Genetic algorithms (GA) maintain a pool of solutions rather than just one. New candidate solutions are generated not only by "mutation" (as in SA), but also by "combination" of two solutions from the pool. Probabilistic criteria, similar to those used in SA, are used to select the candidates for mutation or combination, and for discarding excess solutions from the pool.
Ant colony optimization (ACO) uses many ants (or agents) to traverse the solution space and find locally productive areas.
The cross-entropy method (CE) generates candidates solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.
Quantum annealing
In performing annealing, one may use quantum fluctuations instead of thermal fluctuations. The resulting method is known as quantum annealing. It has been demonstrated experimentally as well as theoretically, that quantum annealing can indeed outperform thermal annealing in certain cases, specifically, where the potential energy (cost) landscape consists of very high but thin barriers surrounding shallow local minima. Since thermal transition probabilities (~exp( − Δ / kBT); T => Temperature, kB => Boltzmann constant) depend only on the height Δ of the barriers, it is very difficult for thermal fluctuations to get the system out from such local minima. But quantum tunneling probabilities through a barrier depend not only the height Δ of the barrier, but also on its width w; if the barriers are thin enough, quantum fluctuations may bring the system out of the shallow local minima surrounded by them.
Stochastic Tunneling
As mentioned above getting out of local minima becomes increasingly difficult for a simulated annealing run. Stochastic tunneling is a particular successful approach to overcome this problem and push the optimization run out of local minima as to 'tunnel through barriers.
See also
- Markov chain
- Combinatorial optimization
- Genetic algorithm
- Tabu search
- Ant colony optimization
- Automatic label placement
- Multidisciplinary optimization
- Place and route
- Traveling Salesman Problem
- Reactive search
- Quantum annealing
- Stochastic tunneling
- Cross-entropy method
References
- S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, Vol 220, Number 4598, pages 671-680, 1983. http://citeseer.ist.psu.edu/kirkpatrick83optimization.html.
- V. Cerny, A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications, 45:41-51, 1985
- A. Das and B. K. Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)
- E. Weinberger, Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference, Biological Cybernetics, 63, No. 5, 325-336 (1990).
External links
- The Travelling Salesman Problem Discusses the use of simulated annealing to solve this problem and allows download of a DOS/Windows command-line program demonstrating problem solution.
- Simulated Annealing A Java applet that allows you to experiment with simulated annealing. Source code included.
- VisualBots - Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
- Technique Developed for Optimizing Traveling-Wave Tubes A page showing the uses of this method in the space program for long distance communications.
Simulierte Abkühlung | Simulated annealing | Recuit_simulé | 擬似焼きなまし法 | Simulated annealing | Symulowane wyżarzanie | Simulated annealing | 模拟退火
"Simulated annealing"