Heuristics: Simulated Annealing 1

Inhaltsverzeichnis

1 Theory
2 Example
3 Presentation of the problem
4 Detailed solution process with explanation
5 Sources

Theory

This is a graphical representation of a landscape. The objective is to find the global minimum.For reaching the global minimum you accept bad values temporarily to get from a local to the global minimum.

Simulated Annealing (SA) was developed in the 1980 as a generic probabilistic metaheuristic for global optimization problems. The basic concept is based on the field of thermodynamic that looks at the crystalline and atomic structure with respect to the temperature change. Normal optimization heuristics only accepts values, which are better than the previous one. It leads to a restriction to local areas and optimum. SA is able to find the global optimum by accepting bad values temporarily to overcome local optimum. Otherwise your solution could stick in a local optimum so that the solution would not be optimal.

Example

Initial situation:

We have a several amount of beer which we have to transport from A to B. To solve this transportation problem we generate an objective function F which determines the driven distance. The aim is to find the minimal distance between A and B (minima of F).

Presentation of the problem

Approach:

Objective: Optimization of the objective function F

1. Set a start temperature (Ts) and an end temperature (Te) as well as a cooling function C(x). Firstly the current temperature T is equal to Ts.

2. Generate a random starting solution Si

3. Generate a new random solution Si’ with respect to the former one.

4. If Si’ < Si then replace Si with Si’.

5. If Si’ > Si or Si’=Si you have to calculate the probability p=e^(-(deltaE/t)); deltaE= F(Si‘)-F(Si).

6. If p> R (0<R<1) replace Si with Si‘, if not, reject Si‘.

7. Cool down T with C(T)--> new temperature

8. If T>Te go back to step 3

9. When T=Te the algorithm stops and you obtain the solution Si from the last iteration

Detailed solution process with explanation

Ts = 75, Te = 0, C(x)=x-15 und T=Ts=75

Generate random initial solution Si with F(Si)= 2000

T=75

Generate new Solution Si‘ with F(Si‘)=1799

F(Si‘)<F(Si) (1799<2000) , so replace Si (Si=Si‘)

Cool down. T=C(T)=75-15=60

Check if target temperature is reached (60> 0), go on.

T=60

Generate new Solution Si‘ with F(Si‘)=1802

F(Si‘)>F(Si) (1802>1799); calculate ΔE=1802-1799=3 and p=e^(-3/45)= 0.9355,

Generate random number R = 0,9

p>R (0.9355>0,9); replace Si (Si=Si‘)

Cool down. T=60-15=45 >0 ,go on

T=45

Generate new Solution Si‘ with F(Si‘)=1702

F(Si‘)<F(Si) (1702<1802); replace Si (Si=Si‘)

Cool down. T=C(T)=45-15=30 >0, go on.

T=30

Generate new Solution Si‘ with F(Si‘)=1733

F(Si‘)>F(Si) (1733>1702); calculate ΔE=1733-1702=31 and p=e^(-31/30)= 0.3558

Generate random number R = 0,4

p<R (0.3558<0,4); reject Si‘

Cool down. T=30-15=15 >0 , go on

T=15

Generate new Solution Si‘ with F(Si‘)=1688

F(Si‘)<F(Si) (1688<1702); replace Si (Si=Si‘)

Cool down. T=C(T)=15-15=0 Target temperature is reached. The algorithm stops and as optimal result we obtain the solution Si with a distance of 1688.