麻省理工学院：《Multidisciplinary System》Particle Swarm Optimization: Method and Applications

M 16sg8 ESD.77 Particle Swarm Optimization Method and Applications Rania hassan Post-doctoral Associate Engineering Systems Divisi ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

1 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Rania Hassan Rania Hassan Post-doctoral Associate doctoral Associate Engineering Systems Division Engineering Systems Division Particle Swarm Optimization: Method and Applications Particle Swarm Optimization: Particle Swarm Optimization: Method and Applications Method and Applications

M esd Particle Swarm Optimization E50. 71 A pseudo-optimization method (heuristic) inspired by the collective intelligence of swarms of biological populations Flocks of birds Colonies of insects ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

2 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Particle Swarm Optimization Particle Swarm Optimization A pseudo-optimization method (heuristic) inspired by the collective intelligence of swarms of biological populations. Flocks of Birds Colonies of Insects

M esd Particle Swarm Optimization E50. 71 A pseudo-optimization method (heuristic) inspired by the collective intelligence of swarms of biological populations Schools of fish Herds of animals ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

3 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Particle Swarm Optimization Particle Swarm Optimization A pseudo-optimization method (heuristic) inspired by the collective intelligence of swarms of biological populations. Schools of Fish Herds of Animals

M Inventors 16sg8 ESD.77 Introduced in 1995: Kennedy, J. and eberhart,R, "Particle Swarm Optimization, Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia 1995, pp .1942-1945. James Kennedy Social psychologist US Department of Labor Russell eberhart Dean of Engineering Research Indiana Univ. Purdue Univ Indianapolis ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

4 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Inventors Inventors James Kennedy Social Psychologist US Department of Labor Russell Eberhart Dean of Engineering Research Indiana Univ. Purdue Univ. Indianapolis Introduced in 1995: Kennedy, J. and Eberhart, R., “Particle Swarm Optimization,” Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia 1995, pp. 1942-1945

Mlesd Swarming in System Design 16sg8 ESD.77 Swarming theory has been used in system design Examples of aerospace systems utilizing swarming theory include formation flying of aircraft and spacecraft Flocks of birds fly in v-shaped formations to reduce drag and save energy on long migrations ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

5 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Swarming in System Design Swarming in System Design • Swarming theory has been used in system design. Examples of aerospace systems utilizing swarming theory include formation flying of aircraft and spacecraft. Flocks of birds fly in V-shaped formations to reduce drag and save energy on long migrations

Mlesd Swarming in System Design 16sg8 ESD.77 Weimerskirch, H. et al. "Energy saving in flight formation. Nature 413 (18 October2001:697-698 a study of great white pelicans has found that bird flying in formation use up to a fifth less energy than those flying solo( Weimerskirch et al. ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

6 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Swarming in System Design Swarming in System Design A study of great white pelicans has found that birds flying in formation use up to a fifth less energy than those flying solo (Weimerskirch et al.). Weimerskirch, H. et al. "Energy saving in flight formation." Nature 413, (18 October 2001): 697 - 698

Mlesd Swarming in System Design 16sg8 ESD.77 A space system in formation flying combines data from several spacecraft rather than flying all the instruments on one costly satellite It also allows for the collection of data unavailable from a single satellite, such as stereo views or simultaneously collecting data of the same ground scene at different angles Formation flying enables paired scene comparison between data from Landsat-7 and EO-1 ImagetakenfromNasa'Swebsitehttp://www.nasa.gov ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

7 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Swarming in System Design Swarming in System Design • A space system in formation flying combines data from several spacecraft rather than flying all the instruments on one costly satellite. • It also allows for the collection of data unavailable from a single satellite, such as stereo views or simultaneously collecting data of the same ground scene at different angles. Image taken from NASA's website. http://www.nasa.gov

M Lecture overview 16sg8 ESD.77 Introduction · Motivation PSO Conceptual Development PSo Algorithm Basic algorithm Constraint Handling Discretization Applications PSO Demo Benchmark test problems · Unconstrained Constrained System Problem: Spacecraft Design Final comments on pso References ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

8 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Lecture Overview Lecture Overview • Introduction • Motivation • PSO Conceptual Development • PSO Algorithm – Basic Algorithm – Constraint Handling – Discretization • Applications – PSO Demo – Benchmark test problems • Unconstrained • Constrained – System Problem: Spacecraft Design • Final Comments on PSO • References

M Persona” Motivation 16sg8 ESD.77 PSO is a zero-order, non-calculus-based method(no gradients are needed) can solve discontinuous mutlimodal, non-convex problems includes some probabilistic features in the motion of particles is a population-based search method, i.e. it moves from a set of points (particles' positions)to another set of points with likely improvement in one iteration(move). is that good or bad ?1 Does it remind you of another heuristic? The Genetic Algorithm(GA) The ga is inherently discrete(in terms of handling design variables PSo is inherently continuous(in terms of handling design variables Some researchers report that Pso requires less function evaluations than the ga (most problems studied are continuous) In Compindex: there are 18150 hits for the Ga from 1990 to 2004, whereas there are only 105 hits for PSo-many version of PSo are likely to appear ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

9 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology “Personal” Motivation Personal” Motivation PSO – is a zero-order, non-calculus-based method (no gradients are needed). – can solve discontinuous, mutlimodal, non-convex problems. – includes some probabilistic features in the motion of particles. – is a population-based search method, i.e. it moves from a set of points (particles’ positions) to another set of points with likely improvement in one iteration (move). [is that good or bad ??] Does it remind you of another heuristic? The Genetic Algorithm (GA) – The GA is inherently discrete (in terms of handling design variables) – PSO is inherently continuous (in terms of handling design variables) – Some researchers report that PSO requires less function evaluations than the GA (most problems studied are continuous). – In Compindex: there are 18150 hits for the GA from 1990 to 2004, whereas there are only 105 hits for PSO - many version of PSO are likely to appear

M esd PSO Conceptual Development E5. 77 Social behavior Simulation Optimizer The social model was intended to answer the following questions How do large numbers of birds or other populations exhibiting swarming behavior) produce seamless, graceful flocking choreography, while often, but suddenly changing direction, scattering and regrouping Are there any advantages to the swarming behavior for an individual in a swarm? Do humans exhibit social interaction similar to the swarming behavior in other species? Keep these questions in mind while watching clips from the French documentary"Winged Migration"by Jacques Perrin ⊙ Rania hassan3/2004 Engineering Systems Division -Massachusetts Institute of Technology

10 © Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology PSO Conceptual Development PSO Conceptual Development • Social Behavior Simulation Optimizer • The social model was intended to answer the following questions: – How do large numbers of birds (or other populations exhibiting swarming behavior) produce seamless, graceful flocking choreography, while often, but suddenly changing direction, scattering and regrouping? – Are there any advantages to the swarming behavior for an individual in a swarm? – Do humans exhibit social interaction similar to the swarming behavior in other species? • Keep these questions in mind while watching clips from the French documentary “Winged Migration” by Jacques Perrin