麻省理工学院：《Multidisciplinary System》Simulated Annealing A Basic Introduction

Simulated Annealing a Basic Introduction Prof, olivier de Weck Massachusetts Institute of Technology Dr. Cyrus Jilla

Simulated Annealing A Basic Introduction Prof. Olivier de Weck Massachusetts Institute of Technology Dr. Cyrus Jilla

Outline Heuristics Background in Statistical Mechanics Atom Configuration Problem Metropolis algorithm Simulated annealing algorithm Sample Problems and applications · Summary

Outline • Heuristics • Background in Statistical Mechanics – Atom Configuration Problem – Metropolis Algorithm • Simulated Annealing Algorithm • Sample Problems and Applications • Summary

Learning objectives Review background in Statistical Mechanics configuration, ensemble, entropy, heat capacity Understand the basic assumptions and steps in Simulated Annealing Be able to transform design problems into a combinatorial optimization problem suitable to SA Understand strengths and weaknesses of sa

Learning Objectives • Review background in Statistical Mechanics: configuration, ensemble, entropy, heat capacity • Understand the basic assumptions and steps in Simulated Annealing • Be able to transform design problems into a combinatorial optimization problem suitable to SA • Understand strengths and weaknesses of SA

Heuristics

Heuristics

What 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 nonconvex(ie contain many 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 engineers answer) Heuristics are good at dealing with local optima without getting stuck in them while searching for the global optimum

What 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, nonconvex (ie. contain many 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

Types of Heuristics Heuristics Often Incorporate Randomization 2 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 Genetic Algorithms Simulated Annealing Tabu search New Methods: Particle Swarm optimization etc

Types of Heuristics • Heuristics Often Incorporate Randomization • 2 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 – Genetic Algorithms – Simulated Annealing – Tabu Search – New Methods: Particle Swarm Optimization, etc…

Origin 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

Origin 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

Statistical mechanics

Statistical Mechanics

The 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

The 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

Sample atom Configuration Original Configuration Perturbed Configuration Atom Configuration - Sample Problem Atom Configuration- Sample Problem 5 632 E=13367 E=10904 Energy of original(configuration Perturbing= move a random atom to a new random(unoccupied) slot

Sample Atom Configuration Original Configuration Perturbed Configuration Atom Configuration - Sample Problem Atom Configuration - Sample Problem 7 6 5 4 3 2 1 0 -1 1 2 3 4 -1 0 1 2 3 4 5 6 7 1 3 2 4 -1 0 1 2 3 4 5 6 7 -1 0 1 2 3 4 5 6 7 E=133.67 E=109.04 Energy of original (configuration) Perturbing = move a random atom to a new random (unoccupied) slot