Particle Swarm Optimization: Method and Applications

1 1 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyRania HassanRania HassanPostPost--doctoral Associatedoctoral AssociateEngineering Systems DivisionEngineering Systems DivisionParticle Swarm optimization : Method and ApplicationsParticle Swarm Optimization: Particle Swarm optimization : Method and ApplicationsMethod and Applications2 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyParticle Swarm OptimizationParticle Swarm OptimizationA pseudo- optimization Method (heuristic) inspired by the collective intelligence of swarms of biological of BirdsColonies of Insects3 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyParticle Swarm OptimizationParticle Swarm OptimizationA pseudo- optimization Method (heuristic)

2 Inspired by the collective intelligence of swarms of biological of FishHerds of Animals4 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyInventorsInventorsJames KennedySocial PsychologistUS Department of LaborRussell EberhartDean of Engineering Research Indiana Univ. Purdue Univ. IndianapolisIntroduced in 1995: Kennedy, J. and Eberhart, R., Particle Swarm optimization , Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia 1995, pp. Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologySwarming in System DesignSwarming in System Design Swarming theory has been used in system design.

3 Examples of aerospace systems utilizing swarming theory include formation flying of aircraft and of birds fly in V-shaped formations to reduce drag and save energy on long Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologySwarming in System DesignSwarming in System DesignA 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. 7 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologySwarming in System DesignSwarming in System Design A space system in formation flying combines data from several spacecraft rather than flying all the instruments on one costly satellite.

4 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 taken from NASA's website. Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyLecture OverviewLecture 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 References9 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of Technology Personal MotivationPersonal MotivationPSO is a zero-order, non-calculus-based Method (no gradients are needed).

5 Can solve discontinuous, mutlimodal, non- convex problems. includes some probabilistic features in the motion of particles . is a population-basedsearch Method , 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).

6 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 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyPSO Conceptual DevelopmentPSO Conceptual Development Social Behavior SimulationOptimizer 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?

7 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 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyPSO Conceptual DevelopmentPSO Conceptual Development How do large numbers of birds produce seamless, graceful flocking choreography, while often, but suddenly changing direction, scattering and regrouping? Decentralized local processes.

8 Manipulation of inter-individual distances (keep pace and avoid collision). Are there any advantages to the swarming behavior for an individual in a Swarm ? Can profit from the discoveries and previous experience of other Swarm members in search for food, avoiding predators, adjusting to the environment, information sharing yields evolutionary advantage. Do humans exhibit social interaction similar to the swarming behavior in other species? Absolutely, humans learn to imitate physical motion early on; as they grow older, they imitate their peers on a more abstract level by adjusting their beliefs and attitudes to conform with societal Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyPSO Conceptual DevelopmentPSO Conceptual Development Phase I: Randomly generated Particle positions in 2-d space.

9 Randomly generated velocity vectors for each Particle in 2-d space. For each Swarm movement (iteration), each Particle (agent) matches the velocity of its nearest neighbor to provide synchrony. Random changes in velocities (craziness) are added in each iteration to provide variation in motion and life-like appearance Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyPSO Conceptual DevelopmentPSO Conceptual Development Phase II: Heppner s simulation used a roost (cornfield), that the birds flocked around before landing there eliminating the need for craziness.

10 The mathematical formulation for the roosting model included: each Particle evaluates its current fitness by comparing its position to the roost position (100, 100). each Particle remembers its best ever fitness value, , and theposition associated with it, , and adjusts its velocity accordingly. ()() + =ikikikyxfkthtime unitithparticleif@ >iiiyxp=randcVxVxxxrandcVxVxxxikikiikiki kiik LI LI += < = >++Uniformly distributed random numberupdate the velocity in the y-direction in the same manner14 Rania Hassan 3/2004 Engineering Systems Division - Massachusetts Institute of TechnologyPSO Conceptual DevelopmentPSO Conceptual Development Phase II: each Particle knows the position of the best Particle in the current Swarm .