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
M he analog 6899 E508 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 parameters Analogy: If a liquid material (ie. metal)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 (ie. ground state This ground state corresponds to the minimum of the cost function in an optimization problem O Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
The Analogy 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 parameters. • Analogy: If a liquid material (ie. metal) 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 (ie. ground state). – This ground state corresponds to the minimum of the cost function in an optimization problem. © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 6
M 4 Key Ingredients for Simulated Annealing 6899 (Kirkpatrick et al, 1983) E508 A concise description of a configuration(ie architecture)of the system (Design Vector) a random generator of rearrangements of the elements in a configuration( Neighborhoods) a quantitative objective function containing the trade- offs that have to be made(simulation Model and Output Metric(s) An annealing schedule of the temperatures and the length of times for which the system is to be evolved o Massachusetts Institute of Technology- Dr. Cyrus D Jilla Prof Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
4 Key Ingredients for Simulated Annealing 4 Key Ingredients for Simulated Annealing (Kirkpatrick et al, 1983) Kirkpatrick et al, 1983) • A concise description of a configuration (ie. architecture) of the system (Design Vector). • A random generator of rearrangements of the elements in a configuration (Neighborhoods). • A quantitative objective function containing the trade-offs that have to be made (Simulation Model and Output Metric(s)). • An annealing schedule of the temperatures and the length of times for which the system is to be evolved. © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 7
M The sa algorithm 6899 E08 Terminology: T= Design Vector (ie. Design Architecture E= System Energy(ie Objective Function Valu T= System Temperature A=Difference in System Energy Between Two Design Vectors The Simulated Annealing Algorithm 1)Choose a random Ti, select the initial system temperature, and outline the cooling (ie. annealing) schedule 2)Evaluate E( i using your simulation model 3)Perturb to obtain a neighboring Design Vector( + 1) 4) Evaluate E(+1 using your simulation model 5)If E(T+ E( i), then accept +1 as the new current solution with a probability ef-At where△=E(I+)-E( 7)Reduce the system temperature according to the cooling schedule 8) Terminate the algorithm TPF Example: We will walk through each of the 8 steps 8 O Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
The SA Algorithm The SA Algorithm • Terminology: – Γ = Design Vector (ie. Design Architecture) – E = System Energy (ie. Objective Function Value) – T = System Temperature – ∆ = Difference in System Energy Between Two Design Vectors • The Simulated Annealing Algorithm 1) Choose a random Γ , select the initial system temperature, and outline the cooling i (ie. annealing) schedule 2) Evaluate E(Γ ) using your simulation model i 3) Perturb Γ to obtain a neighboring Design Vector (Γi+1) i 4) Evaluate E(Γi+1) using your simulation model 5) If E(Γi+1) E(Γ ), then accept Γi+1 as the new current solution with a probability e(- ∆/T) i where ∆ = E(Γi+1) - E(Γ ). i 7) Reduce the system temperature according to the cooling schedule. 8) Terminate the algorithm. • TPF Example: We will walk through each of the 8 steps. © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 8
M| Est Terrestrial Planet Finder(TPF)齡路 Mission Statement: To study all aspects of planets ranging from their formation and development in disks of dust and gas around newly forming stars to the presence and features of those planets orbiting the nearest stars Specifically, to conduct a search for Earth-like planets in star systems located within 15 parsecs of our solar system Primary Mission: To detect Earth-like planets around nearby stars, especially those in the habitable zone where liquid water is likely to exist Bracewell Nulling interferometer Secondary Mission: To characterize approximately 50 of these Earth-like planets Medium spectroscopy(50 planets) Detailed spectroscopy (5 planets) To image astrophysical structures to within milli-arcsecond angular resolution (Michelson interferometer) requires longer baselines http:/tpfjpl.nasagov/ O Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics& Astronautics
Terrestrial Planet Finder (TPF) Terrestrial Planet Finder (TPF) • Mission Statement: “To study all aspects of planets ranging from their formation and development in disks of dust and gas around newly forming stars to the presence and features of those planets orbiting the nearest stars. Specifically, to conduct a search for Earth-like planets in star systems located within 15 parsecs of our solar system.” • Primary Mission: To detect Earth-like planets around nearby stars, especially those in the habitable zone where liquid water is likely to exist – Bracewell Nulling interferometer • Secondary Mission: To characterize approximately 50 of these Earth-like planets – Medium spectroscopy (50 planets) – Detailed spectroscopy (5 planets) • To image astrophysical structures to within milli-arcsecond angular resolution (Michelson interferometer) requires longer baselines • http://tpf.jpl.nasa.gov/ © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 9
M 6899 esd Mathematical Formulation of the TPF Design Problem EsD. TPF Design Vector: G=In, r2 Y3 Y4] 640 unique TPF mission Variable Allowable values Heliocentric Orbital Altitude(AU) y, 1.0,1.5,,, 3.0, architectures 35,4.0,4.5,5.0,55 Collector Connectivity/Geometry Y2 SC1-1D, SCI-2D, SSI Complete enumeration 1D. SSI-2D Diameter of Collector Apertures() 4,6,8, 10 Collector Apertur res determines accuracy 1,2,3,4 MDo methods limited to the Original Optimization Formulation evaluation of 48 design ∑Fy(G vectors(7.5% of the full- Objective factorial trade space) ∑?y lere Constraints Subject to Isolation 2.5≤.≤20mili- arcsec y= year in the mission g= cost O≤10 Integrity ￥= number of" images Surveying SNR≥5 8=angular resolution Med. Spectroscopy SNR210 22= null depth Deep Spectroscopy SNr> 25 O Massachusetts Institute of Technology-Dr. Cyrus D Jilla& Prof. Olivier de Weck Engineering Systems Division and Dept of Aeronautics Astronautics
Mathematical Formulation of the TPF Design Problem TPF Design Vector: G = [γ 1 γ 2 γ 3 γ 4 ] • 640 unique TPF mission Variable Allowable Values architectures Heliocentric Orbital Altitude (AU) γ 1.0, 1.5, 2.0, 2.5, 3.0, 1 3.5, 4.0, 4.5, 5.0, 5.5 • Complete enumeration Collector Connectivity/Geometry γ SCI-1D, SCI-2D, SSI- 2 1D, SSI-2D determines accuracy # Collector Apertures γ 4, 6, 8, 10 3 Diameter of Collector Apertures(m) γ 1, 2, 3, 4 4 • MDO methods limited to the Original Optimization Formulation evaluation of 48 design 5 ∑ F y ( ) vectors (7.5% of the fullG Objective : Min y =1 factorial trade space) 5 ∑ ? y ( ) G y =1 Where Constraint :s Subject to y = year in the mission Isolation 2.5 ≤ θ r ≤ 20 milli- arcsec Φ= cost O ≤ 10 −6 Ψ= number of “images” Integrity Surveying SNR ≥ 5 θr= angular resolution Med. Spectroscopy SNR ≥10 Ω= null depth Deep Spectroscopy SNR ≥ 25 © Massachusetts Institute of Technology – Dr. Cyrus D. Jilla & Prof. Olivier de Weck Engineering Systems Division and Dept. of Aeronautics & Astronautics 10