Saturday, September 15, 2012
Define simulated annealing?
A technique to find a good solution to an optimization problem by trying random variations of the current solution. A worse variation is accepted as the new solution with a probability that decreases as the computation proceeds. The slower the cooling schedule, or rate of decrease, the more likely the algorithm is to find an optimal or near-optimal solution.
Simulated annealing is a generalization of a
method for examining the equations of state and frozen states of n-body systems
[Metropolis et al. 1953]. The concept is based on the manner in which liquids
freeze or metals recrystalize in the process of annealing. In an annealing
process a melt, initially at high temperature and disordered, is slowly cooled
so that the system at any time is approximately in thermodynamic equilibrium.
As cooling proceeds, the system becomes more ordered and approaches a
"frozen" ground state at T=0. Hence the process can be thought of as
an adiabatic approach to the lowest energy state. If the initial temperature of
the system is too low or cooling is done insufficiently slowly the system may become
quenched forming defects or freezing out in metastable states (ie. trapped in a
local minimum energy state).
The original Metropolis scheme was that an initial state of a thermodynamic system was chosen at energy E and temperature T, holding T constant the initial configuration is perturbed and the change in energy dE is computed. If the change in energy is negative the new configuration is accepted. If the change in energy is positive it is accepted with a probability given by the Boltzmann factor exp -(dE/T). This processes is then repeated sufficient times to give good sampling statistics for the current temperature, and then the temperature is decremented and the entire process repeated until a frozen state is achieved at T=0.
By analogy the generalization of this
Monte Carlo approach to combinatorial
problems is straight forward [Kirkpatrick et al. 1983, Cerny 1985]. The current
state of the thermodynamic system is analogous to the current solution to the
combinatorial problem, the energy equation for the thermodynamic system is
analogous to at the objective function, and ground state is analogous to the
global minimum. The major difficulty (art) in implementation of the algorithm
is that there is no obvious analogy for the temperature T with respect to a
free parameter in the combinatorial problem. Furthermore, avoidance of
entrainment in local minima (quenching) is dependent on the "annealing
schedule", the choice of initial temperature, how many iterations are
performed at each temperature, and how much the temperature is decremented at
each step as cooling proceeds.
Simulated annealing has been used in various combinatorial optimization problems and has been particularly successful in circuit design problems
Posted by Gurram. Veera Raghavavaiah at 10:55 AM