M 16gg8 ESD.77 Multidisciplinary System Design Optimization Heuristic Techniques A Basic Introduction to Genetic Algorithms Lecture 11 March 8. 2004 Olivier de eck o Massachusetts Institute of Technology -Prof. de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
1 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Heuristic Techniques: Heuristic Techniques: A Basic Introduction to Genetic Algorithms A Basic Introduction to Genetic Algorithms Lecture 11 March 8, 2004 Olivier de Weck Multidisciplinary System Design Optimization
M esd Heuristic Search Techniques 16gg8 ESD.77 Main Motivation for heuristic Techniques (1)To deal with local optima and not get trapped in them (2 To allow optimization for systems, where the design variables are not only continuous, but discrete, integer or even boolean xER X;=1, 2, 3, 4, 5 ,X=A, B, C)X;true, false] These techniques do not guarantee that global optimum can be found. Generally Karush-Kuhn-Tucker conditions do not apply o Massachusetts Institute of Technology -Prof. de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
2 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Heuristic Search Techniques Heuristic Search Techniques Main Motivation for Heuristic Techniques: (1) To deal with local optima and not get trapped in them (2) To allow optimization for systems, where the design variables are not only continuous, but discrete, integer or even Boolean These techniques do not guarantee that global optimum can be found. Generally Karush-Kuhn-Tucker conditions do not apply. i x ∉ \ xi ={1,2,3,4,5}, xi ={‘A’,’B’,’C’} xi ={true, false} x J
Mlesd Principal Heuristic Algorithms歐别 Genetic Algorithms Holland-1975 spired by genetics and natural selection Simulated Annealing(Kirkpatrick -1983) Inspired by molecular dynamics-energy minimization Particle Swarm Optimization Eberhart and Kennedy -1995) Inspired by the social behavior of swarms of insects or flocks of birds These techniques all use a combination of randomness and heuristic rules"to guide the search for global maxima or minima o Massachusetts Institute of Technology -Prof de Weck and Prof. Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
3 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Principal Heuristic Algorithms Principal Heuristic Algorithms • Genetic Algorithms (Holland – 1975) – Inspired by genetics and natural selection • Simulated Annealing (Kirkpatrick – 1983) – Inspired by molecular dynamics – energy minimization • Particle Swarm Optimization (Eberhart and Kennedy - 1995) – Inspired by the social behavior of swarms of insects or flocks of birds These techniques all use a combination of randomness and heuristic “rules” to guide the search for global maxima or minima
M esd Today: Genetic Algorithms 16gg8 ESD.77 Part 1- Introduction Genetics and Natural selection A simple genetic algorithm (SGA The Genetic Algorithm Game Encoding-Decoding(Representation) Fitness function- Selection Crossover- Insertion - Termination o Massachusetts Institute of Technology -Prof de Weck and Prof. Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
4 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Today: Genetic Algorithms Today: Genetic Algorithms • Genetics and Natural Selection • A simple genetic algorithm (SGA) • “The Genetic Algorithm Game” • Encoding - Decoding (Representation) • Fitness Function - Selection • Crossover – Insertion - Termination Part 1 - Introduction
M Premise of gas 16gg8 ESD.77 Natural Selection is a very successful organizing principle for optimizing individuals and populations of individuals If we can mimic natural selection then we will be able to optimize more successfully A possible design of a system-as represented by its design vector x- can be considered as an individual who is fighting for survival within a larger population Only the fittest survive -Fitness is assessed via objective function J o Massachusetts Institute of Technology -Prof. de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
5 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Premise of GAs Premise of GAs • Natural Selection is a very successful organizing principle for optimizing individuals and populations of individuals • If we can mimic natural selection, then we will be able to optimize more successfully • A possible design of a system – as represented by its design vector x - can be considered as an individual who is fighting for survival within a larger population. • Only the fittest survive – Fitness is assessed via objective function J