Partical swarm optimization (PSO).pptx

Partical swarm optimization (PSO).pptx

1. Particle Swarm Optimization Dr. Ahmed Fouad Ali Faculty of Computers and Informatics Suez Canal University

2. Outline 1. Swarm Intelligence (Main idea) 2. History of Particle Swarm Optimization 3. Particle Swarm Optimization (PSO ) Concepts 4. PSO Algorithm 5. Advantage / Disadvantage 6. Comparison with Genetic Algorithm 7. References

3. Swarm Intelligence (Main Idea) Suppose you and a group of friends are on a treasure finding mission . Each one in the group has a metal detector and can communicate the signal and current position to the n nearest neighbors. Each person therefore knows whether one of his neighbors is nearer to the treasure than him. If this is the case, you can move closer to that neighbor. In doing so, your chances are improved to find the treasure . Also, the treasure may be found more quickly than if you were on your own.

4. A swarm can be defined as a structured collection of interacting organisms (or agents). Within the computational study of swarm intelligence, individual organisms have included ants , bees , wasps , termites , fish (in schools) and birds (in flocks). Swarm Intelligence (Main Idea) (Cont.)

5. The global behavior of a swarm of social organisms therefore emerges in a nonlinear manner from the behavior of the individuals in that swarm The interaction among individuals plays a vital role in shaping the swarm's behavior. Interaction among individuals aids in refining experiential knowledge about the environment , and enhances the progress of the swarm toward optimality . Swarm Intelligence (Main Idea) (Cont.)

6. History of Particle Swarm Optimization Proposed by James Kennedy & Russell Eberhart in 1995 Inspired by simulation social behavior Related to bird flocking , fish schooling and swarming theory - steer toward the center - match neighbors’ velocity - avoid collisions Combines self-experience with social experience Population-based optimization

7. Particle swarm optimization (concepts) Set of agents ( particles ) that constitute a swarm moving around in the search space looking for the best solution Each particle in search space adjusts its “ flying ” according to its own flying experience as well as the flying experience of other particles

8. Particle Swarm Optimization (concepts ) (Cont.) Movement towards a promising area to get the global optimum Each particle keeps track: Its best solution, personal best , pbest The best value of any particle, global best, gbest

9. Each particle modifies its position according to: its current position its current velocity the distance between its current position and pbest the distance between its current position and gbest Particle Swarm Optimization (concepts) (Cont.)

10. Swarm : a set of particles (S) Particle : a potential solution Position, Velocity: Each particle maintains Individual best position ( PBest ) Swarm maintains its global best ( GBest ) Particle Swarm Optimization (concepts ) (Cont.)

11. Particle Swarm Optimization Algorithm P = Particle_Initialization(); For i=1 t o i t_ma x For each particle p in P do fp = f( p ); If fp is better than f( pBest )             pBest = p ; end end gBe st = best p in P ; For each particle p in P do v = v + c1 * rand *( pBest – p ) + c2 * rand *(gBest – p ); p = p + v ; end end

12. v i (t+1) = v i (t)+ c 1 *r a nd*(pBest(t) – p(t)) + c 2 *rand*(gBest(t) – p(t)) ; Social influence Personal influences Inertia Particle’s velocity Particle Swarm Optimization Algorithm (Cont.)

13. PSO Algorithm (parameter setting) The right way This way Or this way Number of particles (10—50) are reported as usually sufficient. C1 (importance of personal best) C2 (importance of neighborhood best) Usually C1+C2 = 4. Vmax – too low: too slow too high: too unstable.

14. Advantage / D isadvantage Advantage Disadvantage Simple implementation Slow convergence in refined search stage Few parameters to adjust Weak local search ability Efficient in global search

15. Comparison with Genetic Algorithm (GA) Commonalities PSO and GA are both population based stochastic optimization B oth algorithms start with a group of a randomly generated population, B oth have fitness values to evaluate the population. B oth update the population and search for the optimium with random techniques. Both systems do not guarantee success .

16. Comparison with Genetic Algorithm (GA) Differences PSO does not have genetic operators like crossover and mutation . Particles update themselves with the internal velocity. Particles do not die. T he information sharing mechanism in PSO is significantly different There is no selection in PSO

17. References Computational Intelligence An Introduction Andries P. Engelbrecht , University of Pretoria South Africa Some slides adapted from a presentation “ The Particle Swarm Optimization Algorithm” By Andry Pinto, Hugo Alves, Inês Domingues , Luís Rocha Susana Cruz. Particle Swarm Optimization http://www.particleswarm.info/ http://www.swarmintelligence.org