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