### Simulated Annealing

The **Simulated Annealing** (SA)
was proposed by *S. Kirkpatrik, C. D. Gelatt *and* M. P. Vecchi* on
1983. SA is a stochastic relaxation technique, which has its origin in statistical
mechanics. It is based on an analogy from the annealing process of solids, where
a solid is heated to a high temperature and gradually cooled in order for it
to crystallize in a low energy configuration. SA can be seen as one way of trying
to allow the basic dynamics of hill-climbing to also be able to escape local
optima of poor solution quality. SA guides the original local search method
in the following way. The solution s'
is accepted as the new current solution if delta
< 0, where delta = f(s')-f(s).
To allow the search to escape a local optimum, moves that increase the objective
function value are accepted with a probability exp(-delta/T)
if delta > 0, where
T is a parameter called the "temperature".
The value of T varies from a
relatively large value to a small value close to zero. These values are controlled
by a cooling schedule, which specifies the initial, and temperature values at
each stage of the algorithm. Depending on the temperature upgrade function,
we have one or another version of the algorithm. For example, if T
is constant it would be obtained the *Metropolis heuristic*.

1 t = 0

2 initialize(T)

3 s0 = Initial_Solution()

4 v0 = Evaluate(s0)

5 repeat

6 repeat

7 t = t + 1

8 s1 = Generate(s0,T)

9 v1 = Evaluate(s0,T)

10 if Accept(v0,v1,T)

11 s0 = s1

12 v0 = v1

13 until t mod Markov_Chain_length == 0

14 T = Update(T)

15 until 'loop stop criterion' satisfied

The Simulated Annealing skeleton (**SA**) requires the classes:

**Problem****Solution****DefaultMove**

The class **Problem** corresponds to the definition of a problem instance.
The skeleton filler must provide a complete definition of this class.

The class **Solution** corresponds to the definition of a solution
(feasible or not) of a problem instance. The skeleton filler must provide a
complete definition of the class **Solution**.

And finally, the class **DefaultMove** corresponds to the definition
of a movement (generation of a new solution from the current solution). The
skeleton filler must provide a complete definition of this class.

In adition, the user must configure the following algorithm parameters
(in file **SA.cfg**):

- number of independent runs.
- number of evaluations.
- Markov-Chain Length (temperature is updated in every number of evaluations).

- temperature decay factor.
- Parallel Configuracion: interval of iterations to refresh global state,
running mode (synchronized or asyncronized) and interval of iterations to
cooperate (if 0 no cooperation)

There are several basic steps to running a problem solve with **SA**
skeleton:

1. Change to the problem directory

cd Mallba/rep/SA/problem

2. Compile skeleton.

make

3. Configure algorithm parameters (

SA.cfgfile)

4. Run problem:

4.1 Sequential Version:make SEQ

or

MainSeq SA.cfg_path instance_path res_file_path4.2 Parallel Version:

4.2.1 ConfigureConfig.cfgfile.

4.2.2 ConfigurepgfileLan(orpgfileWan) : machines where we run the program.

4.2.3 Runmake LAN

or

make WAN