Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **Artificial Intelligence** | Simulated Annealing

Annealing is a process of producing very strong glass or metal, which involves heating the material to a very high temperature and then allowing it to cool very slowly.

**Simulated Annealing**

Annealing
is a process of producing very strong glass or metal, which involves heating
the material to a very high temperature and then allowing it to cool very
slowly.

In this
way, the atoms are able to form the most stable structures, giving the material
great strength.

Simulated
annealing is a local search metaheuristic based on this method and is an
extension of a process called metropolisMonteCarlo simulation.

Simulated
annealing is applied to a multi-value combinatorial problem where values need
to be chosen for many variables to produce a particular value for some global
function, dependent on all the variables in the system.

This
value is thought of as the energy of the system, and in general the aim of
simulated annealing is to find a minimum energy for a system.

Simple
Monte Carlo simulation is a method of learning information (such as shape)
about the shape of a search space. The process involves randomly selecting
points within the search space.

An
example of its use is as follows: A square is
partially contained within a circle. Simple
Monte Carlo simulation can be used to identify what proportion of the square is
within the circle and what proportion is outside the circle. This is done by
randomly sampling points within the square and checking which ones are within
the circle and which are not.

Metropolis Monte Carlo simulation extends this simple method as
follows: Rather than selecting new states from the search space at random, a
new state is chosen by making a small change to the current state.

If the new state means that the system as a whole has a lower
energy than it did in the previous state, then it is accepted.

If the energy is higher than for the previous state, then a
probability is applied to determine whether the new state is accepted or not.
This probability is called a Boltzmann acceptance criterion and is calculated
as follows: e(_dE/T) where T is the current temperature of the system, and dE
is the increase in energy that has been produced by moving from the previous
state to the new state.

The temperature in this context refers to the percentage of
steps that can be taken that lead to a rise in energy: At a higher temperature,
more steps will be accepted that lead to a rise in energy than at low
temperature.

To determine whether to move to a higher energy state or not,
the probability e(_dE/T) is calculated, and a random number is generated
between 0 and 1. If this random number is lower than the probability function,
the new state is accepted. In cases where the increase in energy is very high,
or the temperature is very low, this means that very few states will be
accepted that involve an increase in energy, as e(_dE/T) approaches zero.

The fact that some steps are allowed that increase the energy of
the system enables the process to escape from local minima, which means that
simulated annealing often can be an extremely powerful method for solving
complex problems with many local maxima.

Some systems use e(_dE/kT) as the probability that the search
will progress to a state with a higher energy, where k is Boltzmann’s constant
(Boltzmann’s constant is approximately 1.3807 _ 10_23 Joules per Kelvin).

Simulated annealing usesMonte Carlo simulation to identify the
most stable state (the state with the lowest energy) for a system.

This is done by running successive iterations
of metropolis Monte Carlo simulation, using progressively lower temperatures. Hence, in successive
iterations, fewer and fewer steps are allowed that lead to an overall increase
in energy for the system.

A cooling
schedule (or annealing schedule) is applied, which determines the manner in
which the temperature will be lowered for successive iterations.

Two
popular cooling schedules are as follows:

Tnew =
Told _ dT

**Tnew = C _ Told (where C < 1.0)**

The
cooling schedule is extremely important, as is the choice of the number of
steps of metropolis Monte Carlo simulation that are applied in each iteration.

These
help to determine whether the system will be trapped by local minima (known as
quenching). The number of times the metropolis Monte Carlo simulation is
applied per iteration is for later iterations.

Also
important in determining the success of simulated annealing are the choice of
the initial temperature of the system and the amount by which the temperature
is decreased for each iteration.

These
values need to be chosen carefully according to the nature of the problem being
solved. When the temperature, T, has reached zero, the system is frozen, and if
the simulated annealing process has been successful, it will have identified a
minimum for the total energy of the system.

Simulated
annealing has a number of practical applications in solving problems with large
numbers of interdependent variables, such as circuit design.

It has
also been successfully applied to the traveling salesman problem.

**Uses of Simulated Annealing**

Simulated
annealing was invented in 1983 by Kirkpatrick, Gelatt, and Vecchi.

It was
first used for placing VLSI* components on a circuit board.

Simulated
annealing has also been used to solve the traveling salesman problem, although
this approach has proved to be less efficient than using heuristic methods that
know more about the problem.

It has been used much more successfully in scheduling problems and other large combinatorial problems where values need to be assigned to a large number of variables to maximize (or minimize) some function of those variables.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.