Geoscience Reference
In-Depth Information
Fig. 10.6 Annealing in a physical
process: grains of brass tend to
re-organize as the metal cools
rithms, because these go for nearby, perhaps short-term solu-
tions, and stop. That is, they go immediately downhill as far
as possible in any step. Annealing may not go immediately
downhill (Fig. 10.6 ).
The Boltzmann probability distribution expresses the idea
that a system in thermal equilibrium has its energy probabi-
listically distributed among all different energy states: even
at low temperature (T), there is a small chance of being in a
high energy (E) state:
E
kT
PE
()
e
Fig. 10.7 Probability function of a change in energy state according to
Metropolis' algorithm
Therefore, there is a chance to get out of a local energy
minimum in favor of finding a better, more global, one.
Boltzmann's constant (k) is a constant of nature that relates
temperature to energy.
In 1953, Metropolis and coworkers first incorporated
these principles into numerical calculations. The idea was to
provide a succession of options; a simulated thermodynamic
system will change configuration from energy E1 to energy
E2 with a probability given by (Fig. 10.7 ):
values. For example, the schedule defines how many ran-
dom changes are necessary before is a downward step in T is
taken, and how large is that step.
Consider the traveling salesman problem. The salesman
visit N cities with given positions (x i, y i ) returning finally to
city of origin. The objective is to visit each city only once
and to make the route as short as possible.
This problem is known as an NP-complete problem,
whose computation time for an exact solution increases with
N as
c e . Thankfully, the simulated annealing method lim-
its calculations to a small power of N. To solve this problem,
the annealing procedure is implemented as follows:
1. By numbering the cities from i = 1,…,N, the initial con-
figuration is defined. Any other configuration is the per-
mutation of the numbers 1,…,N.
2. A rearrangement is the swapping of the order of two cit-
ies. There are more and less efficient procedures to rear-
range the order of the cities.
3. The Objective Function is defined as total distance traveled:
(* )
š
EE
k e
−−
(
)
21
if
EE
>
PE
()
=
2
1
1, otherwise
This general scheme of always taking a downhill step and
sometimes taking an uphill step has come to be known as the
Metropolis algorithm.
In order to implement this idea, a few key elements are
needed: (a) The possible system configurations should be
described; (b) A random generator of changes is required to
present options to the system; (c) An objective function O
(analogous to thermodynamic energy) is defined; the goal
of the procedure is to minimize this function; (d) A control
parameter T (analog of temperature) and (e) an annealing
schedule which tells how T is lowered from high to low
N
2
2
E
= − +−
(
xx
)
(
yy
)
i
i
+
1
i
i
+
1
i
=
1
with the last city point N + 1 identified to the first city, i.e.,
back to the original starting place.
 
Search WWH ::




Custom Search