A main concern in optimization problems is whether the solution obtained
by a certain algorithm is a local minimum or a global one. If function
#tex2html_wrap_inline8246# to be optimized is quadratic and definite (either positive
or negative definite), then any local extremum (either minimum or maximum)
is the unique and global extremum. However, if #tex2html_wrap_inline8248# is not
quadratic, then a local minimum found by the algorithm may not be global.
In such a case, the <#3597#>simulated annealing (SA)<#3597#> algorithm can be
used to search for the global minimum, by allowing up-hill moves in
the iteration to avoid getting stuck at a local minimum. SA mimics the
annealing process in metallurgy, in which the temperature is carefully
controlled to decrease slowly so that the material reaches a state with
minimum free energy.
The way the SA method avoids getting stuck at a local minimum is to
allow the iteration steps to go up-hill. Specifically, the objective
function #tex2html_wrap_inline8250# evaluated at #tex2html_wrap_inline8252# is treated as the energy
at #tex2html_wrap_inline8254#, and an up-hill move corresponding to an energy increase
#math745##tex2html_wrap_inline8256# can be accepted if some
probability function #math746##tex2html_wrap_inline8258# defined below is greater than
a threshold value Th within a certain range comparable with #tex2html_wrap_inline8260#:
#math747# #tex2html_wrap_indisplay19719#
(150)
where #tex2html_wrap_inline8262# represents the temperature. Obviously smaller #tex2html_wrap_inline8264#
and higher #tex2html_wrap_inline8266# will cause higher #tex2html_wrap_inline8268#, it is more probable for a move
to be accepted.
During the entire search process, the temperature #tex2html_wrap_inline8270# gradually reduces
so that the probability of accepting an up-hill move also gradually
reduces. In the early stage of the search, it is more probable to go
up-hill, thereby getting out of a local minimum; but toward the later
part of the search process, such a move is less likely to happen, as
presumably in this late stage of the search, the energy level is already
low, not likely to be at a local minimum with high energy level. Through
out the search, the best result corresponding to he lowest energy level
is always updated, to be returned to as the final solution at the end
of the process.