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.cfg file)
4. Run problem:
       4.1 Sequential Version:

make SEQ
     or
MainSeq SA.cfg_path instance_path res_file_path

        4.2 Parallel Version:
                     4.2.1 Configure Config.cfg file.
                     4.2.2 Configure pgfileLan (or pgfileWan) : machines where we run the program.
                     4.2.3 Run

make LAN
     or
make WAN

[Up]