Thursday, 23 February 2012

Particle Swarm Optimization ( PSO ) - Introduction and Java Program


Particle Swarm Optimization is a metaheuristic optimization technique which generates a population of particles which adjusts its particle position and velocity in the search space, according to a set of mathematical formulas, so as to locate the best solution.

PSO belongs to the broad class of Swarm Intelligence Methods for solving Global Optimization problems. It was developed by James Kennedy and Russel.C.Eberhart, inspired by social behavior of bird flocking or fish schooling.



Simulation of Bird Flocking

Consider a flock of birds searching for food in an area. There is only one piece of food in that area and all the birds are searching for it. In each iteration the birds are only aware of how far the food is.
So the best approach to get the food is to follow the bird which is nearest to it.


How it Works

In PSO,
The birds are the solutions which are termed as particles
1
  1. Each particle has a fitness value. Our aim is to optimize this fitness value as evaluated by the fitness function.
  2. Each particle has its own position and velocity calculated by the position and velocity function respectively.
  3. Initially, the PSO is initialized with group of particles whose parameters are altered during each iteration.
  4. In each iteration, every particle updates its fitness value and its pbest (personal best value)
  5. Meanwhile during each iteration the PSO reviews the gbest (i.e. the best pbest value obtained by any of the particle to that point.)



Characteristics of PSO
  1. PSO does not guarantee that an optimal solution is ever found.
  2. It is a metaheuristic computational method (i.e.  it optimizes the problem by  trying to improve the candidate solution with regard to a given measure of quality. )
  3. It’s similar to Genetic Algorithms.
  4. It’s easier to implement
  5. There are only a few parameters to be adjusted



General Pseudocode

For each particle 
          Initialize particle
End

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

    gBest = particle with the best fitness value of all the particles

    For each particle 
                   Calculate particle velocity according equation (a)
                   Update particle position according equation (b)
    End 
End 



 PSO Example:

Function Optimization (Java Program)

The following is a Sample Code  for the Java implementation of a simple PSO for function optimization of one dimensional quadratic equation.

In order to perform function optimization using PSO, some of the classes that we require are:

1.     Location -  To represent the position of the particle
2.     Velocity -   To represent the velocity of the particle
3.     Particle   -  To represent the particle
4.     PSOController – performs the PSO operation.

Position class
 Velocity class:
 Particle class:

 Here the function is evaluated by the calculateFitness() function.

InitializeAbc gets the quadratic equation from the user.


Here’s the code(partial code):

 Some of the constants used:
 Finally, a sample java implementation :

 Input:  (x2 +6x+9)
 Output:  (x = -3)



Prepared by:  Archana Devi
   Amrita School of Engineering,  Coimbatore



Mentored by:    Prof T.Senthil.Kumar
  Dept of Computer Science &  Engineering
  Amrita School of Engineering, Coimbatore
  Email id: sapne21@yahoo.com
                  senthan1@yahoo.co.in