Heuristics: Simulated Annealing 3

Theory

Simulated annealing (SA) is a method of the solution space search. SA ,a heuristic optimisation procedure, is a meta-algorithm, that is applicable for combinational problems. The method of SA has it's origin in physics expertises (especially in thermodynamics) from nature (Metropolis 1953). After 30 years S. Kirkpatrick used the metropolis-algorithm for general valid theoretical and practical problems of the optimisation. Assumption from the nature was that the system accepts a declination of the bilanz during it's cooling process to reach a better optimazation.

Simulated annealing methods in physics duplicate a method for the cooling of solid bodies, fluids and gases. With regard to the cautious cooling, the body reaches an absolute zero point (the minimal energy-niveau). In general, worse values are'nt used in optimization heuristics than the predetermined. For the optimal solution, the local minimum can be neglected and the search fot the global minimum has to be continued. Even if the temporary values get worse.

The algorithm only works efficient if the parameters are concerted:

• - if the starting temperature is too low the risk of sticking in a local optimum exists
• - neighboorhodd too big --> enormous computing time
• - the cooling of the starting temperature must be slowly
• - starting temperature should not be too high due to the optimum is achieved too often

Example

In practise, simulated annealing, is also usefull for the traveling salesman problem and for floorplanning (i.e. chip-layout). The metal industry utilise simulated annealing for freezing of metal. The better a ordered crystal structure is developed, the harder the metal is. During the slow freezing the crystal structure is constructed better.

To get more concretely the following example should explain the problem step by step:

Initial situation:

The metal firm "Metall SE" wants to improve their metals with simulated annealing. With regard to the production of metals, the freezing of metals start at a starting temperature (Ts) and should slowly sink to the end temperature (Te) to get a high quality metal. The process of annealing to produce a state of lowest possible energy is simulated - hence the name simulated annealing - obtained an optimization method. We expect that the firm wants to produce iron with a starting temperature(Ts) of 125°CIn the end of the proceess the end temperature of the iron should be at standat conditions (Te=0°C). The cooling function is C(x). Form a random starting solution Ss. Afterwards a new random starting solution Ss' with regard to ancient one. If Ss'<Ss then replace Ss with Ss'. On the other hand if Si'>Ss or Ss'=Ss you have to compute p(probability)=e^{(-(deltaE/t))}>r ( DeltaE=the difference between two energy balances). Ss' is the new best solution. If p<r reject Ss'. Messured with a hightech thermometer the temperature (T) of the iron slowly gets cooled down. If the appropiate temperature is higher than the end temperature (Te) a new random solution Ss' has to be formed. The process is finished if the temperature of 0° is reached.

The cooling function C(T)= T-30, Ts=150 (iron), Te=0 Form a random solution Ss with F(Ss)=800

T=150

Form a new solution Ss' with F(Ss')=750

F(Ss')=750 < F(Ss)=800, so we replace Ss with Ss'

T=C(T)= 150-30=120

The iron has not reached the temperature of 0°C

T=120

Form a new solution with F(Ss')= 780

F(Ss')=780 > F(Ss)=750, deltaE must be calculated: deltaE=780-750=30 and p=e^(-30/90)=0,71653

Form a random number r= 0,7

p=0,716531 > r=0,7, therefore Ss must be replaced (Ss=Ss')

T=C(T)=120-30=90

The iron has not reached the temperature of 0°C

T=90

Form a new solution Ss' with F(Ss')= 700

F(Ss')= 700 < F(Ss)= 780, therefore Ss must be replaced (Ss=Ss')

T=C(T)=90-30=60

The iron has not reached the temperature of 0°C

T=60

Form a new solution Ss' with F(Ss')= 735

F(Ss')= 730 > F(Ss)= 700, deltaE must be calculated: deltaE= 735-700=35 and p=e^(-35/30)=0,311403224

Form a random number r= 0,4

p= 0,311403224 < r= 0,4, therefore reject Ss'

T=C(T)=60-30=30

The iron has not reached the temperature of 0°C

T=30

Form a new solution Ss' with F(Ss')=680

F(Ss')= 680 < F(Ss)=700, therefore Ss must be replaced (Ss=Ss')

T=C(T)=30-30=0°

The iron has reached the temperature of 0°C

Sources

http://de.wikipedia.org/wiki/Simulated_Annealing http://isgwww.cs.uni-magdeburg.de/sim/vilab/2003/presentations/martin.pdf http://page.mi.fu-berlin.de/brittadb/lehre/proseminar08/simulatedannealing.pdf