05-11-2016, 04:49 PM
1465572468-SimulatedannealingWikipediathefreeencyclopedia.pdf (Size: 438.67 KB / Downloads: 7)
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given
function. Specifically, it is a metaheuristic to approximate global optimization in a large search space. It is
often used when the search space is discrete (e.g., all tours that visit a given set of cities). For problems
where finding the precise global optimum is less important than finding an acceptable local optimum in a
fixed amount of time, simulated annealing may be preferable to alternatives such as bruteforce search or
gradient descent.
Simulated annealing interprets slow cooling as a slow decrease in the probability of accepting worse
solutions as it explores the solution space. Accepting worse solutions is a fundamental property of
metaheuristics because it allows for a more extensive search for the optimal solution.
The method was independently described by Scott Kirkpatrick, C. Daniel Gelatt and Mario P. Vecchi in
1983,
[1] and by Vlado Černý in 1985.
[2] The method is an adaptation of the Metropolis–Hastings algorithm,
a Monte Carlo method to generate sample states of a thermodynamic system, invented by M.N. Rosenbluth
and published by N. Metropolis et al. in 1953.
[3]
The basic iteration
At each step, the SA heuristic considers some neighbouring state s' of the current state s, and
probabilistically decides between moving the system to state s' or staying in state s. These probabilities
ultimately lead the system to move to states of lower energy. Typically this step is repeated until the system
reaches a state that is good enough for the application, or until a given computation budget has been
exhausted.
The neighbours of a state
The neighbours of a state are new states of the problem that are produced after altering a given state in
some welldefined way. For example, in the traveling salesman problem each state is typically defined as a
permutation of the cities to be visited. The neighbours of a state are the set of permutations that are
produced, for example, by reversing the order of any two successive cities. The welldefined way in which
the states are altered in order to find neighbouring states is called a "move" and different moves give
different sets of neighbouring states. These moves usually result in minimal alterations of the last state, as
the previous example depicts, in order to help the algorithm keep the better parts of the solution and change
only the worse parts. In the traveling salesman problem, the parts of the solution are the city connections.
Searching for neighbours of a state is fundamental to optimization because the final solution will come after
a tour of successive neighbours. Simple heuristics move by finding best neighbour after best neighbour and
stop when they have reached a solution which has no neighbours that are better solutions. The problem with
this approach is that the neighbours of a state are not guaranteed to contain any of the existing better
solutions. This means that failure to find a better solution among them does not guarantee that no better
solution exists. This is why the best solution found by such algorithms is called a local optimum in contrast
with the actual best solution which is called a global optimum. Metaheuristics use the neighbours of a
solution as a way to explore the solutions space, and although they prefer better neighbours, they also
accept worse neighbours in order to avoid getting stuck in local optima. If the algorithm were run for an
infinite amount of time, the global optimum would be found.
Acceptance probabilities
The probability of making the transition from the current state to a candidate new state is specified by
an acceptance probability function , that depends on the energies and of
the two states, and on a global timevarying parameter called the temperature. States with a smaller
energy are better than those with a greater energy. The probability function must be positive even when
is greater than . This feature prevents the method from becoming stuck at a local minimum that is worse
than the global one.
When tends to zero, the probability must tend to zero if and to a positive value
otherwise. For sufficiently small values of , the system will then increasingly favor moves that go
"downhill" (i.e., to lower energy values), and avoid those that go "uphill." With the procedure
reduces to the greedy algorithm, which makes only the downhill transitions.
In the original description of SA, the probability was equal to 1 when — i.e., the
procedure always moved downhill when it found a way to do so, irrespective of the temperature. Many
descriptions and implementations of SA still take this condition as part of the method's definition. However,
this condition is not essential for the method to work.
The function is usually chosen so that the probability of accepting a move decreases when the difference
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 temperature plays a crucial role in controlling the evolution of the state of
the system with regard to its sensitivity to the variations of system energies. To be precise, for a large , the
evolution of is sensitive to coarser energy variations, while it is sensitive to finer energy variations when
is small.
The annealing schedule
The name and inspiration of the algorithm demand an interesting feature related to the temperature variation
to be embedded in the operational characteristics of the algorithm. This necessitates a gradual reduction of
the temperature as the simulation proceeds. The algorithm starts initially with set to a high value (or
infinity), and then it is decreased at each step following some annealing schedule—which may be specified
by the user, but must end with 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 lowenergy regions that become narrower and
narrower; and finally move downhill according to the steepest descent heuristic.
Related methods
Interacting MetropolisHasting algorithms (a.k.a. Sequential Monte Carlo
[5]
) combined simulated
annealing moves with an acceptancerejection of the best fitted individuals equipped with an
interacting recycling mechanism.
Quantum annealing uses "quantum fluctuations" instead of thermal fluctuations to get through high
but thin barriers in the target function.
Stochastic tunneling attempts to overcome the increasing difficulty simulated annealing runs have in
escaping from local minima as the temperature decreases, by 'tunneling' through barriers.
Tabu search normally moves to neighbouring states of lower energy, but will take uphill moves when
it finds itself stuck in a local minimum; and avoids cycles by keeping a "taboo list" of solutions
already seen.
Dualphase evolution is a family of algorithms and processes (to which simulated annealing belongs)
that mediate between local and global search by exploiting phase changes in the search space.
Reactive search optimization focuses on combining machine learning with optimization, by adding an
internal feedback loop to selftune the free parameters of an algorithm to the characteristics of the
problem, of the instance, and of the local situation around the current solution.
Stochastic gradient descent runs many greedy searches from random initial locations.
Genetic algorithms maintain a pool of solutions rather than just one. New candidate solutions are
generated not only by "mutation" (as in SA), but also by "recombination" 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.
Graduated optimization digressively "smooths" the target function while optimizing.
Ant colony optimization (ACO) uses many ants (or agents) to traverse the solution space and find
locally productive areas.
The crossentropy method (CE) generates candidates solutions via a parameterized probability
distribution. The parameters are updated via crossentropy minimization, so as to generate better
samples in the next iteration.
Harmony search mimics musicians in improvisation process where each musician plays a note for
finding a best harmony all together.
Stochastic optimization is an umbrella set of methods that includes simulated annealing and
numerous other approaches.
Particle swarm optimization is an algorithm modelled on swarm intelligence that finds a solution to
an optimization problem in a search space, or model and predict social behavior in the presence of
objectives.
The RunnerRoot Algorithm (RRA) is a metaheuristic optimization algorithm for solving unimodal
and multimodal problems inspired by the runners and roots of plants in nature.
Intelligent Water Drops (IWD) which mimics the behavior of natural water drops to solve
optimization problems
Parallel tempering is a simulation of model copies at different temperatures (or Hamiltonians) to
overcome the potential barriers.