1Simulated AnnealingA Basic IntroductionOlivier de Weck, Ph.D.Massachusetts Institute of TechnologyLecture 102Outline• Heuristics• Background in Statistical Mechanics– Atom Configuration Problem– Metropolis Algorithm• Simulated Annealing Algorithm• Sample Problems and Applications• Summary3Learning Objectives• Review background in Statistical Mechanics: configuration, ensemble, entropy, heat capacity• Understand the basic assumptions and steps in Simulated Annealing (SA)• Be able to transform design problems into a combinatorial optimization problem suitable to SA• Understand strengths and weaknesses of SA4Heuristics5What is a Heuristic?• A Heuristic is simply a rule of thumb that hopefully will find a good answer.• Why use a Heuristic?– Heuristics are typically used to solve complex (large, nonlinear, non-convex (i.e. contain local minima)) multivariate combinatorial optimization problems that are difficult to solve to optimality.• Unlike gradient-based methods in a convex design space, heuristics are NOT guaranteed to find the true global optimal solution in a single objective problem, but should find many good solutions (the mathematician's answer vs. the engineer’s answer)• Heuristics are good at dealing with local optima without getting stuck in them while searching for the global optimum.6Types of Heuristics• Heuristics Often Incorporate Randomization• Two Special Cases of Heuristics– Construction Methods• Must first find a feasible solution and then improve it.– Improvement Methods• Start with a feasible solution and just try to improve it.• 3 Most Common Heuristic Techniques– Simulated Annealing– Genetic Algorithms– Tabu Search– New Methods: Particle Swarm Optimization, etc…7Origin of Simulated Annealing (SA)• Definition: A heuristic technique that mathematically mirrors the cooling of a set of atoms to a state of minimum energy.• Origin: Applying the field of Statistical Mechanics to the field of Combinatorial Optimization (1983)• Draws an analogy between the cooling of a material (search for minimum energy state) and the solving of an optimization problem.• Original Paper Introducing the Concept– Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P., “Optimization by Simulated Annealing,” Science, Volume 220, Number 4598, 13 May 1983, pp. 671-680.8MATLAB® “peaks” function • Difficult due to plateau at z=0, local maxima• SAdemo1• xo=[-2,-2]• Optimum at• x*=[ 0.012, 1.524]• z*=8.0484-3 -2 -1 0 1 2 3-3-2-10123xPeaksyStart PointMaximum9“peaks” convergence• Initially ~ nearly random search• Later ~ gradient search0 50 100 150 200 250 300-10-8-6-4-202Iteration NumberSystem EnergySA convergence historycurrent configurationnew best configuration10Statistical Mechanics11The Analogy• Statistical Mechanics: The behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature.• Combinatorial Optimization: Finding the minimum of a given function depending on many variables.• Analogy: If a liquid material cools and anneals too quickly, then the material will solidify into a sub-optimal configuration. If the liquid material cools slowly, the crystals within the material will solidify optimally into a state of minimum energy (i.e. ground state).– This ground state corresponds to the minimum of the cost function in an optimization problem.12Sample Atom Configuration-1 0 1 2 3 4 5 6 7-1012345671234Atom Configuration - Sample ProblemE=133.67-1 0 1 2 3 4 5 6 7-1012345671234Atom Configuration - Sample ProblemOriginal Configuration Perturbed ConfigurationE=109.04Perturbing = move a random atom to a new random (unoccupied) slotEnergy of original (configuration)13Configurations• Mathematically describe a configuration– Specify coordinates of each “atom”– Specify a slot for each atom1 2 3 41 3 4 5 with i=1,..,4 , , ,1 2 4 3ir r r r r with i=1,..,4 1 12 19 23irR14Energy of a state• Each state (configuration) has an energy level associated with ittotH T V E, , , ,iiiH q q t q p L q q tHamiltonianEnergy of configuration= Objective function value of designkinetic potentialEnergy15Energy sample problem• Define energy function for “atom” sample problem1222potentialenergykineticenergyNi i i j i jjiE mgy x x y y1NiiiE R E rAbsolute and relative position ofeach atom contributes to Energy16Compute Energy of Config. A• Energy of initial configuration12341 10 1 5 18 20 20.951 10 2 5 5 5 26.711 10 4 18 5 2 47.891 10 3 20 5 2 38.12EEEETotal Energy Configuration A: E({rA})= 133.67-1 0 1 2 3 4 5 6 7-1012345671234Atom Configuration - Sample Problem17Boltzmann Probability!!RPNPNNumber of configurationsWhat is the likelihood that a particular configuration willexist in a large ensemble of configurations?P=# of slots=25N=# of atoms =4NR=6,375,600({ }){ } expBErPrkTBoltzmann probabilitydepends on energyand temperature18Boltzmann Collapse at low T0 20 40 60 80 100 120 140 160 180 20002000400060008000100001200014000EnergyOccurencesT=10 - Eavg=58.9245T=100 20 40 60 80 100 120 140 160 180 20002000400060008000100001200014000EnergyOccurencesT=1 - Eavg=38.1017T=10 20 40 60 80 100 120 140 160 180 200020004000600080001000012000EnergyOccurencesT=100 - Eavg=100.1184Boltzmann Distribution collapses to the lowest energystate(s) in the limit of low temperatureBasis of search by Simulated AnnealingT=100T highT low19Partition Function Z• Ensemble of configurations can be described statistically• Partition function, Z, generates the ensemble average1Trexp expRNiiiBBEEZk T k TInitially (at T>>0) equal to the number of possible configurations20Free Energyln ( )BF T k T Z E T TS1()RNavg iiE E T E T1expln()1RNiiiBavgBETETkTdZE E TZ d k TRelates average Energy at T with Entropy SAverage Energy of allConfigurations in anensemble21Specific Heat and Entropy• Specific Heat• Entropy22221221()()()RNiiRBBE T E TE T E TNdE TCTdT k T k T( ) ( )dS T C TdT T11()( ) ( )TTCTS T S T dTTEntropy is ~ equal to ln(# of unique configurations)22Low Temperature Statistics100102104100105Temperature# of configurations, NT1001021040246810TemperatureSpecific Heat C and Entropy S100102104-150-100-50050100150TemperatureFree Energy, F100102104-150-100-50050100150TemperatureAverage Energy, EavgApproachesE* frombelowApproachesE* fromaboveEntropy Sdecreaseswith lower THt. Capacity# configsdecreases23Minimum Energy Configurations• Sample Atom Placement Problem-1 0 1 2 3 4 5 6 7-1012345671234Atom