PSOPPT with example (pso optimization with solved problem) .pptx

pso optimization with solved problem

1. Particle Swarm optimization

2. Conten t s Introduction to Optimization Particl e Swar m Optimization Illustration o f Algorithm Mathematical Interpretation Example Dataset Illustration

3. Introduction to Optimization 🠶 The optimization can be defined as a mechanism through which the maximum or minimum value of a given function or process can be found. 🠶 The function that we try to minimize or maximize is called as objective function. 🠶 Variable and parameters. 🠶 Statement of optimization problem Minimize f(x) subject to g(x)<=0 h(x)=0. 🠶 Two main phases Exploration and Exploitation

4. Introduction to Optimization Application to optimization: Particle Swarm Optimization Pro pos e d b y J a mes Ke nn e d y & Rus s e l l E b e r h a rt ( 199 5 ) Comb i n e s s e l f - e xp e r i e n c e s w it h s o c i a l e xp e r i e n c e s

5. Particle Swarm Optimization(PSO) 🠶 Inspired from the nature social behavior and dynamic movements with communications of insects, birds and fish.

6. Particle Swarm Optimization(PSO) Uses a number of agents ( particles ) that constitute a swarm moving around in the search space looking for the best solution Each par 🠶 ticle in search space adjusts its “flying” according to its own flying experience as well as the flying experience of other particles. Each particle has three parameters position, velocity, and previous best position, particle with best fitness value is called as global best position.

7. Cont d .. Collection of flying particles (swarm) - Changing solutions Search area - Possible solutions Movement towards a promising area to get the global optimum. Each particle adjusts its travelling speed dynamically corresponding to the flying experiences of itself and its colleagues. Each particle keeps track: its best solution, personal best, pbest. the best value of any particle, global best, gbest. 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.

8. Algorithm - Parameters f : Objective function Xi: Position of the particle or agent. Vi: Velocity of the particle or agent. A: Population of agents. W: Inertia weight. C1: cognitive constant. R1, R2: random numbers. C2: social constant.

9. Algorithm - Steps Create a ‘population’ of agents (particles) uniformly distributed over X Evaluate each particle’s position according to the objective function( say y=f(x)= -x^2+5x+20 If a particle’s current position is better than its previous best position, update it. Determine the best particle (according to the particle’s previous best positions). Y =F ( x) = - x ^ 2 + 5x + 20

10. Contd.. 5. Upd a te p a rtic l es’ velocities : 6 . Move particles to their new positions : 7 . Go to ste p 2 unti l stopping criteri a ar e satisfied.

11. Contd … Particle’s velocity : 1 . Inertia 2 . P e r s onal Influence 3 . Social Influence Makes the particle move in the same direction and with the same velocity Improves the individual Makes the particle return to a previous position, better than the current Conservative Makes the particle follow the best neighbors direction

12. Acceleration coefficients When , c1=c2=0 then all particles continue flying at their current speed until they hit the search space’s boundary. Therefore, the velocity update equation is calculated as: t  v ij t  1 v ij When c1>0 and c2=0 , all particles are independent. The velocity update equation will be: t  1 v ij  v ij  c 1 r 1 j  P best , i  x  t t t t ij When c1>0 and c2=0 , all particles are attracted to a single point in the entire swarm and the update velocity will become  g b e s t x ij  t t t  v i j  c 2 r 2 j t  1 v ij When c1=c2, all particles are attracted towards the average of pbest and gbest.

13. Contd … Intensification : explores the previous solutions, finds the best solution of a given region Diversification : searches new solutions, finds the regions with potentially the best solutions In PSO: 

14. Example:

15. Co n td . .

16. Co n td . .

17. Co n td . .

18. Flow chart of Algorithm

19. Mathematical Example and Interpretation Fitness Function De Jong Function m i n F ( x , y ) = x ^ 2 + y ^ 2 Where x and y are the dimensions of the problem. The surface and contour plot of the De Jong function is given as:

20. Mathematical Example and Interpretation Contd.. Rastrigi n Function The surface and contour plot of the De Jong function is given as: D ( x i  10.cos(2.  . x i )  t  1

21. Mathematical Example and Interpretation Contd … Banana Function The surface and contour plot of the Rosenbrock function or 2 nd De Jong function Or valley or banana functions given as:

22. Mathematical Example and Interpretation   1.1, f ( x )   x 2  5 x  20 Using PSO algorithm. Use 9 particles with initial positions x 1   9.6, x 2   6, x 3   2.6, x 4 x 5  0.6, x 6  2.3, x 7  2.8, x 8  8.3, x 9  10 Solution Choose the number of particles x 1   9.6, x 2   6, x 3   2.6, x 4   1.1, x 5  . 6 , x 6  2 . 3 , x 7  2 . 8 , x 8  8 . 3 , x 9  10 Evaluate the objective function   7.39, f 9   30  26.16, f 8 0 0  13.29, f 5  22.64, f 6  26.21, 0 0 0 f 1   120.16, f 2   46, f 3  0.24 f 4 f 7

23. Mathematical Example and Interpretation 9 8 7 6 5 0 0 1   v  v  v  v  0, v  v , v , v  v 1 2 3 4 v Step2. Set the iteration no as t=0+1 and go to step 3 . Step 3. Find the personal best for each particle by So   2. 6  2.3  2.8, P 1 best ,8  8.3, P 1 best ,9  10   6, P 1 best ,3  0.6, P 1 best ,6   9 . 6 , P 1 b e s t , 2   1.1, P 1 best ,5 P 1 best ,1 P 1 b e s t , 4 P 1 best ,7

24. Mathematical Example and Interpretation .. Step 4: Gbest =max(Pbest) so gbest =(2.3). Step 5: updating the velocities of the particle by considering the value of random numbers r1 = 0.213, r2= 0.876, c1=c2=1, w=1. v 1   0.213(  9.6  9.6)  0.876(2.3  9.6)  10.4244 1 1 1 1 1 1 1 1 v 2  7 . 2 7 8 , v 3  4 . 2 9 2 4 , v 5  1 . 4 8 9 2 , v 6  , v 7   . 4 3 8 , v 8  5 . 2 5 6 , v 9   6 . 7 4 5 2 Step 6: update the values of positions as well

25. Mathematical Example and Interpretation Contd.. So 1 3 1 2 1 1  3.2548  1.6924  2.3 1  3.044, x 9 1  2.362, x 8 1  2.0892, x 6 1 1 x 4  1.8784, x 5 1 x 7  1.2708, x  0.8244, x x Step7 : Find the objec t ive func t ion values of 1 3 1 1 1 2  25.5978 1 1  26.231, f 8  25.9541, f 9  25.6803 1  26.0812, f 6  26.21 1 1 f 4  2 5 . 8 6 3 6 , f 5 1 f 7  2 4 . 7 3 9 , f  2 3 . 4 4 2 4 , f f Ste p 8 : S topping cr i t e ria if the terminal rule is satisfied , go to step 2. Otherwise stop the iteration and output the results.

26.  1.6924  1.87884, P 2 best ,5  2.0892, P 2 best ,6  2.3  2.362, P 2 best ,8  3.044, P 2 best ,9  3.2548 Contd.. 🠶 Step2. Set the iteration no as t=1+1 =2 and go to step 3 Step 3. Find the personal best for each particle by 2  . 824 4 , P b e s t , 2  1 . 270 8 , P 2 b e s t , 3 P 2 b e s t , 1 P 2 b e s t , 4 P 2 b e s t , 7  2.362 Ste p 4 : find the glob a l best G best Ste p 5 : by consid e ring the random nu m ber s in range (0 , 1) as 2 2 1  0.706  . 11 3 , r r 2

27. Contd.. 🠶 Find the velocities of the particles : 2 2 2 2 3 4  3.3198 2   5.7375, v 9   7.3755 1 2 2 2 2 v 5  1 . 6 8 1 8 , v 6  . 4 3 8 , v 7   . 4 3 8 , v 8  8 . 4 1 2 , v  4 . 7 6 5 1 , v  1 1 . 5 9 9 , v v 2 Step 6: update the values of positions as well 2 3 2 2 2 1   4.12078  6.4575  2 . 3438 2   2.6935, x 9 1  3.7710, x 6 2 2 x 4  5.1982, x 5 2 2 x 7  1.9240, x 8  9.312, x  12.3343, x x

28. Contd… 🠶 Step7: Find the objective function values of  26.2256   1 7 . 5 8 3 9 2  2 4 . 6 3 4 6 , f 6 2   0. 7 2 2 4 , f 9 2  1 8 . 9 6 9 6 , f 5 2  2 5 . 9 1 8 2 , f 8 2 2 2 f 1   70.4644, f 2   20.1532, f 3  10.5882 2 f 4 2 f 7 Ste p 8 : Stopping crit e ria if the terminal rule is satisfied , go to step 2. Otherwise stop the iteration and output the results

29. Contd.. 🠶 Step2. Set the iteration no as t=1+2 =3 and go to step 3 Step 3. Find the personal best for each particle by  1.6924  2.362, P 3 best ,8  3.044, P 3 best ,9  3.2548  1.87884, P 3 best ,5  2.0892, P 3 best ,6  2.3  1 . 270 8 , P 3 b e s t , 3  0. 824 4 , P 3 b e s t , 2 P 3 b e s t , 1 P 3 b e s t , 4 P 3 b e s t , 7 Ste p 4 : find the glob a l best  2.362 G best Ste p 5 : by consid e ring the random nu m ber s in range (0 , 1) as 3 2 1  0.507  . 17 8 , r r 3

30. Find the velocities of the particles 3 3 2 3 4  1 . 2 9 9 3   2.1531, v 9   2.7759 1 3 3 3 3 v 5  . 6 6 8 1 , v 6  . 5 3 , v 7   . 1 3 8 , v 8  3 . 8 6 2 , v 3  1 . 8 4 5 , v  4 . 4 5 2 , v v 3 Step 6: update the values of positions as well 3 3 2 3 3 1  2.3968   6 . 8 9 6 7  8.298 3   4.8466, x 9 3  1.786, x 8 3 3 x 4  6.4862, x 5 3 x 7  12.3982, x 3  4.4391, x 6  16.7395, x x Step7: Find the objective function values of

31. Contd . . 3 3 3 f 1   176.5145, f 2   71.7244, f 3   7.3673 3 f 4 3 f 7 3  22.49, f 6  26..2393   27.7222, f 3   62.0471 9 3  1 . 336 7 , f 5 3  2 5 . 740 2 , f 8 Ste p 8 : S t o p p i n g cr i t e r i a if the terminal rule is satisfied , go to step 2. Otherwise stop the iteration and output the results

32. Mathematical Example and Interpretation y 2 Fitness Function :De Jong function m i n F ( x , y )  x 2 Where x and y are the dimensions of the problem , the velocities of all the particles are initialized to zero and inertia (W) = 0.3 , and the value of the cognitive and social constants are C1= 2 and C2 =2. The initial best solutions of all the particles are set to 1000 Example Iteration First: P1 fitness value = 1 2  1 2  2

33. Mathematical Example and Interpretation Example Iteration 2nd:

34. Mathematical Example and Interpretation Example Iter a ti o n 3rd:

35. Mathematical Example and Interpretation Example Iter a ti o n 3rd:

36. Psuedocode P=p a rticle initi a lizati o n(); For I = 1 to max 3 for eac h particle p in P do fp=f(p) If fp is bette r than f( pbes t ) pbest =p; end end gbes t = bes t p in P. for eac h particle p in P do 9. 10. end end

37. DataSet

38. Advantages and Disadvantages of PSO Advantages Insensitive to scaling o f design variables. Simple implementation. Easily parallelized for concurrent processing. Derivative free. Ver y few algorith m parameters. Very efficient global search algorithm. Disadvantages Slow convergence in refined search stage (weak local search ability).