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
Mlesd Matlab GA demo("peaks") 16gg8 ESD.77 ntia Genation Maximize "peaks"function · Population size:40 · Generations:20 · Mutation rate:0.002 Observe convergence Notice“ mutants Compare to gradient search o Massachusetts Institute of Technology -Prof de Weck and Prof. Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
6 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Matlab GA demo (“peaks”) Matlab GA demo (“peaks”) • Maximize “peaks” function • Population size: 40 • Generations: 20 • Mutation Rate: 0.002 -Observe convergence -Notice “mutants” -Compare to gradient search
M Natural selection 16gg8 ESD.77 Charles Darwin( 1809-1882 Extremely controversial and influential book(1859) On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life Observations Species are continually developing Homo sapiens sapiens comes from ape-like stock Variations between species are enormous Huge potential for production of offspring, but only a small percentage survives to adulthood Evolution natural selection of inheritable variations o Massachusetts Institute of Technology -Prof. de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
7 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Natural Selection Natural Selection Charles Darwin (1809-1882) Extremely controversial and influential book (1859) On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life Observations: • Species are continually developing • Homo sapiens sapiens comes from ape-like stock • Variations between species are enormous • Huge potential for production of offspring, but only a small percentage survives to adulthood Evolution = natural selection of inheritable variations
M esd Inheritance of Characteristics 16gg8 ESD.77 Gregor Mendel ( 1822-1884) Investigated the inheritance of characteristics (traits") Conducted extensive experiments with pea plants EXamined hybrids from different strains of plant short short short tall short Character(gene) for tallness is dominant Character(gene)for shortness is recessive o Massachusetts Institute of Technology -Prof. de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
8 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Inheritance of Characteristics Inheritance of Characteristics Gregor Mendel (1822-1884) Investigated the inheritance of characteristics (“traits”) Conducted extensive experiments with pea plants Examined hybrids from different strains of plant tall tall tall tall tall short short short short Character (gene) for tallness is dominant Character (gene) for shortness is recessive
M Genetics 16gg8 ESD.77 the great unknown. Walter Sutton(1877-1916) Discovered that genes are part of the chromosomes inside the nucleus of cells still unexplained.. Darwin predicted continuous variation within species. In nature we often observe discontinuous variations strikingly different, unexpected variants sometimes appear, how to explain??? Hugo de Varis (1848-1935 developed a theory of mutation -at first seemingly at odds with Darwinism How has this dilemma been resolved? o Massachusetts Institute of Technology-Prof de Weck and Prof Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
9 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Genetics Genetics … the great unknown …. Walter Sutton (1877-1916) • Discovered that genes are part of the chromosomes inside the nucleus of cells … still unexplained … Darwin predicted continuous variation within species. In nature we often observe discontinuous variations … strinkingly different, unexpected variants sometimes appear, how to explain ??? Hugo de Varis (1848-1935) developed a theory of mutation - at first seemingly at odds with Darwinism How has this dilemma been resolved?
M GA Terminology 16gg8 ESD.77 chromosome l「 population gene individuals selection crossover insertion mutation genetic operators Generation n Generation n+1 o Massachusetts Institute of Technology -Prof de Weck and Prof. Willcox Engineering Systems Division and Dept of Aeronautics and Astronautics
11 © Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics GA Terminology GA Terminology chromosome gene population Generation n Generation n+1 selection crossover insertion mutation genetic operators individuals