M 6899 E08 Multidisciplinary System Design Optimization(MSDO) Simulated Annealing Lecture 5 March 2004 Dr. Cyrus D Jilla Professor olivier de weck O Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
Multidisciplinary System Multidisciplinary System Design Optimization (MSDO) Design Optimization (MSDO) Simulated Annealing Lecture 5 March 2004 by Dr. Cyrus D. Jilla Professor Olivier de Weck © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 1
M Today's Topics 6899 E08 What are Heuristics? The Origin and analogy of Simulated Annealing The Simulated annealing algorithm An Example: The terrestrial planet finder mission Sample results Ways to Tailor the Simulated Algorithm Summary References O Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
Today’s Topics Today’s Topics • What are Heuristics? • The Origin and Analogy of Simulated Annealing • The Simulated Annealing Algorithm • An Example: The Terrestrial Planet Finder Mission • Sample Results • Ways to Tailor the Simulated Algorithm • Summary • References © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 2
M What is a Heuristic? 6899 E508 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 such as the simplex algorithm)in a convex trade 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 Reference: Schulz, A.S., " Metaheuristics, 15.057 Systems Optimization Course Notes, MIT, 1999 O Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
What is a Heuristic? 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 (such as the simplex algorithm) in a convex trade 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. • Reference: – Schulz, A.S., “Metaheuristics,” 15.057 Systems Optimization Course Notes, MIT, 1999. © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 3
M Types of Heuristics 6899 E08 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 O Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
Types of Heuristics 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 © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 4
M| d Origin of Simulated Annealing(SA)歐路 Definition: A heuristic technique that mathematically mirrors the cooling of a material 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 metal 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 May1983,pp.671-680. Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
Origin of Simulated Annealing (SA) Origin of Simulated Annealing (SA) • Definition: A heuristic technique that mathematically mirrors the cooling of a material 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 metal 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. © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 5