Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Simulated AnnealingGeneral Idea: 1) Start with an initial solution2) Generate a neighboring solution. -If the neighbor is better, move to it.-If the neighbor is not better move to it with some probability, else stay put.3) Repeat step 2 for n iterations, however continually reduce the probability of moving to a poorer neighbor over time. The continuous reduction in the probability of moving to a poorer neighbor over time effectively reduces the annealing process to a local improvement in the end.Simulated AnnealingIssue 1: What to use as the initial solution x?Options: a) Heuristic b) Randomly generatedIssue 2: What defines a neighbor or neighborhood?Same as local improvement.Issue 3: Search strategy.Randomly generate a neighbor or simple programmatic approach.Simulated AnnealingIssue 4: Evaluation Function – How do you know theadjacent (or neighboring) solution is better or not?Speed – need efficient mechanism to evaluate solutions.Simulated AnnealingIssue 5: Probability Function - What probability function to use for determining whether to move to a poorer solution or not?Let V be the value of the current solution and V’ the value of the neighboring solution. Then Johnson et al proposed using the following:for minimization problem,let = V’ – Vif  <= 0, then downhill move, so take it.if  > 0, then uphill move, move with probability e-/T,where T is some value referred to as the temperature."e(-d/T)Tempdelta 100.0 75.0 56.3 42.2 31.6 23.7 17.8 13.3 10.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.005 0.95 0.94 0.91 0.89 0.85 0.81 0.76 0.69 0.6110 0.90 0.88 0.84 0.79 0.73 0.66 0.57 0.47 0.3715 0.86 0.82 0.77 0.70 0.62 0.53 0.43 0.33 0.2220 0.82 0.77 0.70 0.62 0.53 0.43 0.33 0.22 0.1425 0.78 0.72 0.64 0.55 0.45 0.35 0.25 0.15 0.0830 0.74 0.67 0.59 0.49 0.39 0.28 0.19 0.11 0.0535 0.70 0.63 0.54 0.44 0.33 0.23 0.14 0.07 0.0340 0.67 0.59 0.49 0.39 0.28 0.19 0.11 0.05 0.0245 0.64 0.55 0.45 0.34 0.24 0.15 0.08 0.03 0.0150 0.61 0.51 0.41 0.31 0.21 0.12 0.06 0.02 0.0155 0.58 0.48 0.38 0.27 0.18 0.10 0.05 0.02 0.0060 0.55 0.45 0.34 0.24 0.15 0.08 0.03 0.01 0.0065 0.52 0.42 0.31 0.21 0.13 0.06 0.03 0.01 0.0070 0.50 0.39 0.29 0.19 0.11 0.05 0.02 0.01 0.00Simulated AnnealingSimulated AnnealingIssue 6: Cooling Function – How to reduce the temperature as the annealing process runs.After n iterations, set T =rT, where r < 1. r is typically set somewhere between .95 and .8Simulated AnnealingThe classic Johnson, et al. simulated annealing algorithm:1. Get an initial solution S.2. Get an initial temperature T > 0.3. While not yet frozen do the following:3.1 Perform the following loop l time.3.1.1 Pick a random neighbor S’ of S.3.1.2 Let = cost(S’) – cost(S)3.1.3 If  <= 0 (downhill move), Set S = S’.3.1.4 If  > 0 (uphill move), Set S = S’ with probability e-/T.3.2 Set T = rT (reduce temperature).4. Return S.Simulated AnnealingIssue 7: What should the initial temperature T be?Large enough to make some uphill moves. This becomes problem instance specific.Could be found programmatically by finding comparing the value of S to the value of several neighboring solutions and then ensuring that: where X is some value say 0.8 or 0.9XeT /Simulated AnnealingIssue 8: How do you perform the probability test to see if an uphill move is to be made?Generate a random number R between 0 and 1.If, then set S = S, move uphill. else, do not move.Sample C++ code:ReT / x = (rand( )%1000)/1000.0; if(x < exp(-float(result - finalreport->BestLmax)/Temp)) { Accepted++; newjoblist = true; } else { rev_seq_switch(Mach_1,Seq_1,CenterList,offset,n); NotAccepted++; }Simulated AnnealingIssue 9: How do you know if the process if frozen?Rules of thumb –- If loop 3 completes 3 times without any move being accepted (uphill or downhill).- No move being accepted after M iterations.-Minimum temperature reached.Issue 10: How many iterations per temperature, or what is the value of l?Use experimentation to determine good value. Possible numbers are 50,000 or 100,000, or 200,000, etc…Simulated AnnealingExtensions to Johnson et al. algorithm –A)Alternately heat up and cool down the process.B) Use a re-centering approach. For example when the process has become frozen, replace the current solution with the best solution found so far, S = S*, then restart the annealing process by setting the T back to the original temperature. C) Use a different probability function.D)Vary the number of iterations l as a function of temperature T.E)