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
- Each particle has a fitness value. Our aim is to optimize this fitness value as evaluated by the fitness function.
- Each particle has its own position and velocity calculated by the position and velocity function respectively.
- Initially, the PSO is initialized with group of particles whose parameters are altered during each iteration.
- In each iteration, every particle updates its fitness value and its pbest (personal best value)
- 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
- PSO does not guarantee that an optimal solution is ever found.
- 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. )
- It’s similar to Genetic Algorithms.
- It’s easier to implement
- 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
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: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:
Input: (x2 +6x+9)
Output: (x = -3)Prepared by: Archana Devi
Amrita School of Engineering, Coimbatore
Email id: archana.shiva@gmail.com
Mentored by: Prof T.Senthil.Kumar
Dept of Computer Science & Engineering
Amrita School of Engineering, Coimbatore
Email id: sapne21@yahoo.com