Information Technology Reference
In-Depth Information
5.4 Simulated Annealing
Simulated Annealing (SA) [
31
] is a probabilistic method for solving global opti-
mization problems. It is inspired from the annealing technique in metallurgy, which
involves heating and controlled cooling of materials. The annealing process results
in low-energy structure of crystals. We can simulate this process and obtain an algo-
rithm to
minimize
some cost or energy function. The cost corresponds to the energy
of some crystalline solid.
The SA algorithm takes randomwalks in the search space, looking for points with
low energies. We start with an initial candidate solution
s
0
, and repeatedly move to
new points. At each step, we randomly generate an alternative candidate solution and
measure its cost/energy. If the newenergy
E
is lower than the current one
E
, we move
to that point and update the candidate solution; otherwise, we move to the new point,
with probability
e
−
(
E
−
E
)/(
kT
)
. Here,
T
is the “temperature”, and
k
is Boltzmann's
constant. Initially the temperature is high, making the candidate solution more likely
to change; then the temperature is lowered very slightly according to some cooling
schedule.
Some implementations of SA are available. For example, an implementation is
contained in the GNU Scientific Library (GSL),
1
which is a numerical library for C
and C
programmers.
Stevens [
46
] uses SA to construct small covering arrays (transversal covers). The
cost function is the number of uncovered pairs. The algorithm starts with a random
matrix. Eachmove is just selecting a random row and changing a randomvalue in that
row. The proposed move is accepted with a probability that decreases exponentially
with time. The matrix cools until the probability becomes zero. If we obtain a matrix
whose cost is zero, we have found a covering array.
Typically, before we apply the SA algorithm, we have to guess an initial size of
the covering array. During the annealing process, the number of rows is fixed (as
some constant
N
). If the algorithm finds a covering array, the size is decreased by
one and a new run of the SA process is started.
Garvin et al. [
17
] studied how to improve the SAalgorithm to deal with constraints.
In addition, they discussed how to determine the size of the covering array. That is
called the
outer search
, which is concerned with the minimization of
N
. It takes
an upper bound and a lower bound on the size of the covering array, and performs
a binary search within this range. The
inner search
performs SA, and explores the
space of
Nk
arrays by changing one entry at a time, guided by the cost function.
Recently, Torres-Jimenez and Rodriguez-Tello [
47
] described an improved imple-
mentation of the SA algorithm, called ISA, for constructing
binary
covering arrays
of strengths 3-6. Using ISA, they obtained 104 new bounds.
ISA has two key features:
++
Search WWH ::
Custom Search