Transcript S c

Simulated Annealing (SA)
Contents
1. Basic Concepts
2. Algorithm
3. Practical considerations
1
Literature
1. Modern Heuristic Techniques for Combinatorial Problems,
(Ed) C.Reeves 1995, McGraw-Hill. Chapter 3.
2. Scheduling, Theory, Algorithms, and Systems, Second Addition,
Michael Pinedo, Prentice Hall, 2002, Chapter 14.4
3. Simulated Annealing:Theory and Applications, P.J.M. van
Laarhoven and E.H.L. Aarts, Kluwer Academic Publishers, 1988.
2
Basic Concepts
1. Allows moves to inferior solutions in order not to get stuck in a
poor local optimum.
△c = F(Snew) - F(Sold)
F is to be minimized.
inferior solution (△c >0) still accepted if U < e
 c
t
U is a random number from (0, 1) interval
t is a cooling parameter:
t is initially high - many moves are accepted
t is decreasing - inferior moves are nearly always rejected.
2. As the temperature decreases, the probability of accepting worse
moves decreases.
3
△c > 0
- △c <0
inferior solution
t
 c

t
 c
e t

4
Algorithm
Step 1. k=1.
Select an initial schedule S1 using some heuristic and set Sbest = S1
Select an initial temperature t0 > 0
Select a temperature reduction function  (t)
Step 2. Select Sc N(Sk).
If F(Sbest) < F(Sc)
If F(Sc) < F(Sk) then Sk+1 = Sc
else
generate acrandom uniform number Uk  
If Uk < e t
then Sk+1 = Sc (where △c = F(Sc) - F(Sk) )
else Sk+1 = Sk
else
Sbest = Sc
Sk+1 = Sc.
5
Step 3.
tk =  (t)
k = k+1 ;
If stopping condition = true then STOP
else go to Step 2.
6
Example
Consider the following scheduling problem 1 | | wjTj .
j
1
2
3
4
pj 9
9 12 3
dj 10
8
5 28
wj 14 12
1 12
Apply the simulated annealing to the problem starting out with the
3, 1, 4, 2 as an initial sequence.
Neighborhood: all schedules that can be obtained through adjacent
pairwise interchanges. (Connectivity)
7
Select neighbors within neighborhood at random.
Choose  (t) = 0.9 * t
t0 = 0.9
Use the following numbers as random numbers: 0.17, 0.91, ...
Sbest = S1 = 3, 1, 4, 2
F(S1) = wjTj = 1· 7 + 14·11 + 12·0+ 12 ·25 = 461 = F(Sbest)
t0 = 0.9
Sc = 1, 3, 4, 2
F(Sc) = 316 < F(Sbest)
8
Sbest = 1, 3, 4, 2
F(Sbest) = 316
S2 = 1, 3, 4, 2
t = 0.9 · 0.9 = 0.81
Sc = 1, 3, 2, 4
F(Sc) = 340 > F(Sbest)
U1 = 0.17 >
 ( 340316)
e 0.81
(= 1.35*10-13)
S3= 1, 3, 4, 2
t = 0.81 · 0.9 = 0.729
9
Sc = 1, 4, 3, 2
F(Sc) = 319 > F(Sbest)
U3 = 0.91
 ( 319 316)
> e 0.729
(= 0.016)
S4= 1, 3, 4, 2
t = 0.729 · 0.9 = 0.6561
...
10
Practical considerations
Initial temperature:
• must be "high"
• acceptance rate: 40%-60% seems to give good results in many
situations
Cooling schedule:
• single or multiple moves at each temperature
t= ·t
t=
t
1  t
 is typically in the interval [0.9, 0.99]
 is typically close to 0
11
Stopping condition:
• given number of iterations
• given minimum temperature
• no improvement has been obtained for a given number of
iterations
Note: SA often returns high quality solutions, in spite of its
slow convergence.
Threshold Accepting:
- t = threshold value
- if F(Sc)<F(Sk)+t, then Sk+1=Sc.
12