PSO Pseudo Code

The pseudo code of the procedure is as follows



For each particle 
    Initialize particle
END

Do
    For each particle 
        Calculate fitness value
        If the fitness value is better than the best fitness value (pBest) in history
            set current value as the new pBest
    End

    Choose the particle with the best fitness value of all the particles as the gBest
    For each particle 
        Calculate particle velocity according equation (a)
        Update particle position according equation (b)
    End 

While maximum iterations or minimum error criteria is not attained

Particles' velocities on each dimension are clamped to a maximum velocity Vmax. If the sum of accelerations would cause the velocity on that dimension to exceed Vmax, which is a parameter specified by the user. Then the velocity on that dimension is limited to Vmax.


source: http://www.swarmintelligence.org/tutorials.php

Mathematical Proof for PSO Algorithm Calculation

Problem:

In a search space there are 5 particles with the position coordinates x₁₌2_,x₂₌3_,x₃₌-4_,x₄₌1_,x₅₌5 _. State P_best and G_best after first iteration for objective function

f(x)= -x² + 5

Solution

Let the give position of particle i.e X_i

x₁₌2
x₂₌3

x₃₌-4

x₄₌ 1

x₅₌5

by using following equation

v_i = ω+ c₁*r₁()*(P_best-x_i ^t)+ c₂*r₂()*(G_best-x_i ^t);

x_i = x_i+ v_i^t+1;

Let’s assume c₁=c₂=1 (c₁=c₂ are Constant coefficients)

Random function is R₁=.213

                              R₂=.876

f(x_i)=  -x² + 5 putting the values of X_{1 to} X₅

f(x₁) =f(2) = (2)²+5=9

          f(3) = 14

          f(-4)= 21

          f(1) = 16

          f(5) = 30 as  f(5) have highest fitness value based on which

Gbest = min (Pbest)

Therefore Gbest = 5

Initially all particle have 0 velocity and positions as mentioned above

Initially all particles holds Pbest value

Velocity Updation for each particle is calculated as

v_i = ω+ c₁*r₁()*(P_best-x_i ^t)+ c₂*r₂()*(G_best-x_i ^t);

V₁ = 0 + 0.213 (2-2) + 0.876(5-2) =2.68

Similarly

V₂ = 1.75

V₃ = 7.884

V₄ = -0.87

V₅ = 0

New Position Updation based on velocity

x_i = x_i+ v_i^t+1;

x₁₌ 2+2.68 =4.68

x₂₌  4.752

x₃₌ 3.884                                  New P_best

x₄₌ 0.124

x₅₌  5

Calculating Again Objective function value

f(x₁) =f(4.68) = (4.68)²+5=26.9

            f(4.752) = 27.56

            f(3.884)= 19.44

            f(0.124) = 5.015

            f(5) = 30

f(5) have highest fitness value based on which Gbest = min (Pbest)

Therefore Gbest = 5

v_i = ω+ c₁*r₁()*(P_best-x_i ^t)+ c₂*r₂()*(G_best-x_i ^t);

x_i = x_i+ v_i^t+1; 

Few words about PSO

Particle Swarm Optimization

Few words about PSO:

In PSO, the potential solutions, called particles, fly through the problem space by following the current optimum particles. Each particle keeps track of its coordinates in the problem space which are associated with the best solution (fitness) it has achieved so far. The fitness value called pbest is then stored. Another value that is tracked by the particle swarm optimizer is the best value, obtained so far by any particle in the neighbors of the particle. This location is called lbest. When a particle takes all the population as its topological neighbors, the best value is a global best, called gbest.
The particle swarm optimization concept consists of updating the velocity of accelerating each particle toward its pbest and lbest locations at each time step. Acceleration is weighted by a random term, with separate random numbers being generated for acceleration toward pbest and lbest locations. Imagine now that each PSO particle can also change its dimension, which means that they have the ability to jump to another (solution space) dimension as they see fit. In that dimension they simply do regular PSO moves but in any iteration they can still jump to any other dimension.

In upcoming post we will share some good article related to PSO stay tuned.