Biomedical Engineering Reference
In-Depth Information
needed to formulate or understand the method. Simulated annealing
differs from gradient search techniques in that it does not try to find
the fastest way down the slope. Rather, it involves making random
guesses as to where the minimum is.
This process is shown schematically in Figure 9.9. Imagine that, as
usual, we start at point S.
We make a random guess
at where a “better” point
might be, drawing our step
size randomly from a
distribution characterized
by a “throw parameter”.
If the guess yields a point,
such as P
1
, at which the
value of the score function
is less than it is at S
(throw
“1” in Figure 9.9), then we
accept it, move to P
1
,
and
start the process over
again. On the other hand,
the guess may yield a
point, such as P
2
or P
3
, at which the value of the score function is
more than it is at S
(throws “2” and “3” in Figure 9.9). In most
optimization schemes, such points, being worse, would be
immediately rejected. In simulated annealing, paradoxically, one
sometimes accepts such a point. With some probability whose
magnitude is randomly drawn from a distribution characterized by a
“cooling parameter”, one may elect to accept the worse solution
objective
function, f(x)
objective
function, f(x)
3
3
2
2
P
3
P
3
P
2
P
2
1
1
S
S
P
1
P
1
L
L
G
G
x (distance)
x (distance)
Figure
9.9.
Simulated
annealing:
random guesses are made as to where
the minimum is - and sometimes
“uphill” (i.e. apparently worse) guesses
are accepted (see text).
although, of course, P
1
won't be forgotten; it could yet be our
candidate for the minimum. That is, we have a chance of moving to
P
2
−
−
which won't be all that great
−
or, much more promisingly, to P
3
−
a point from which we obviously have a much better chance at
ending up at G, where we'd like to be.
In order to converge, as the process proceeds, one must both reduce
the average distance over which throws are made, thus reducing the
incidence of wild throws, and must reduce the probability of
accepting uphill throws. The parameters that control these must not
only be given starting values; they also need to have a defined
schedule by which they are reduced.
