Introduction to Simulated Annealing 22c:145Simulated AnnealingDifferences to Hill ClimbingThe Problem with Hill ClimbingTo accept or not to accept - SA?Slide 6Slide 7SA AlgorithmSlide 9SA Algorithm (for maximum-value solutions)SA Algorithm - ObservationsSA Cooling ScheduleStarting TemperatureFinal TemperatureTemperature DecrementIterations at each temperatureSlide 17Performance IssuesAcceptance ProbabilityIntroduction to Simulated Annealing22c:145Simulated Annealing-Motivated by the physical annealing process-Material is heated and slowly cooled into a uniform structure-Simulated annealing mimics this process-The first SA algorithm was developed in 1953 (Metropolis)Differences to Hill Climbing-The main difference is that SA allows downwards steps-In SA, a move is selected at random and then decides whether to accept it-In SA better moves are always accepted. Worse moves are not always accepted.The Problem with Hill Climbing-Gets stuck at local minima-Possible solutions-Try several runs, starting at different positions-Increase the size of the neighbourhood (e.g. in TSP try 3-opt rather than 2-opt)To accept or not to accept - SA?P = e-c/t > rWherec is change in the evaluation functiont is the current temperaturer is a random number between 0 and 1To accept or not to accept - SA?Change Temp exp(-C/T) Change Temp exp(-C/T)0.2 0.95 0.810157735 0.2 0.1 0.1353352830.4 0.95 0.656355555 0.4 0.1 0.0183156390.6 0.95 0.53175153 0.6 0.1 0.0024787520.8 0.95 0.430802615 0.8 0.1 0.000335463To accept or not to accept - SA?-The probability of accepting a worse state is a function of both the temperature of the system and the change in the cost function-As the temperature decreases, the probability of accepting worse moves decreases-If t=0, no worse moves are accepted (i.e. hill climbing)SA Algorithm-The most common way of implementing an SA algorithm is to implement hill climbing with an accept function and modify it for SA by introducing a cooling schedule.SA AlgorithmFunction SIMULATED-ANNEALING(Problem, Schedule) returns a solution stateInputs: Problem, a problemSchedule, a mapping from time to temperatureLocal Variables : Current, a nodeNext, a nodeT, a “temperature” controlling the probability of downward stepsCurrent = MAKE-NODE(INITIAL-STATE[Problem])SA Algorithm (for maximum-value solutions)For t = 1 to doT = Schedule[t]If T = 0 then return CurrentNext = a randomly selected successor of CurrentE = VALUE[Next] – VALUE[Current]if E > 0 then Current = Nextelse Current = Next only with probability exp(-E/T)SA Algorithm - ObservationsThe cooling schedule is hidden in this algorithm - but it is important (more later)The algorithm assumes that annealing will continue until temperature is zero - this is not necessarily the caseSA Cooling ScheduleStarting TemperatureFinal TemperatureTemperature DecrementIterations at each temperatureStarting TemperatureMust be hot enough to allow moves to almost neighbourhood state (else we are in danger of implementing hill climbing)Must not be so hot that we conduct a random search for a period of timeTrial-and-error to find a suitable starting temperatureFinal TemperatureIt is usual to let the temperature decrease until it reaches zero.However, this can make the algorithm run for a lot longer, especially when a geometric cooling schedule is being usedIn practise, it is not necessary to let the temperature reach zero because the chances of accepting a worse move are almost the same as the temperature being equal to zeroTemperature DecrementLineartemp = temp - xGeometrictemp = temp * xExperience has shown that x should be between 0.8 and 0.99, with better results being found in the higher end of the range. Of course, the higher the value of x, the longer it will take to decrement the temperature to the stopping criterionIterations at each temperatureA constant number of iterations at each temperature to only do one iteration at each temperature, but to decrease the temperature very slowly.E.g., t = t/(1 + βt)where β is a suitably small value.Iterations at each temperatureAn alternative is to dynamically change the number of iterations as the algorithm progressesAt lower temperatures it is important that a large number of iterations are done so that the local optimum can be fully exploredAt higher temperatures, the number of iterations can be lessPerformance IssuesQuality of the solution returnedTime taken by the algorithmWe already have the problem of finding suitable SA parameters (cooling schedule).Acceptance ProbabilityWhy cannot we use a different acceptance criteria?The exponential calculation is computationally expensive.(Johnson, 1991) found that the acceptance calculation took about one third of the computation time.Johnson experimented withP(δ) = 1 – δ/tThis approximates the
View Full Document