PARTICLE SWARM OPTIMIZATION

  This blog throws light on a simple optimization technique which is Particle Swarm Optimization (PSO). The post is written keeping in mind the layman so no prior knowledge is required. We start with the concept of Swarm Intelligence (SI). SI is a collective performance of any organized system- natural or artificial. This system consists of a population of agents or candidates that interact locally with each other or with their environment. These agents follow some simple rules and though there is no boss or any controlling structure above them dictating that how a certain individual should behave or act yet their intelligence help in optimizing the performance and results in robustness. This helps in the division of tasks and labour. The inspiration for SI comes from natural systems like flock of birds, School of fish, animal herding etc.

There are different algorithms for SI:

• Genetic Algorithm
• Particle Swarm Optimization
• Artificial Bee Colony
• Ant Colony Optimization (discussed earlier)
• Harmony Search etc.

Let’s discuss PSO now. Particle Swarm Optimization was originally developed by James Kennedy and Russell Eberhart in 1995. It is an algorithm that helps in finding the optimal values and follows the animal society which has no leader but works on the concept of teamwork! The following picture helps in depicting the said concept in a more interesting manner:

The picture above explains the basic idea of social behavior: the flock of birds (population) head out randomly in search of food and each bird in the swarm searches the food (optimal solution) independently and gains knowledge about the presence of food and their other members. All these birds know their current location i.e. away from the food, but they do not know where the real food is. So the best and efficient strategy would be to head out in search of food in the surrounding area or simply follow the distance the food birds covered like in the above example.

Concept of PSO is inspired from the above natural behavior and is used to solve optimization problems. In PSO, each optimization problem is like the search of food by birds in that space. It is called as “particles” (birds). All particles have a separate function to be optimized (fitness value). Each particle has an individual speed that helps in determining the direction and the distance it needs to cover. The particle then follows the current optimum particles in the search space. PSO is initialized to a group of random particles i.e. the random solution (swarm) and then optimal solution is found by various iterations in every random generation. During iterations, particles keep on updating their velocity and position based on two things (extremums):

• Particle itself finds the optimal solution, this is called as individual extremum (P_best) and
• Optimal solution found by the entire population called as global extremum (G_best).

To find the optimal solutions, the steps for PSO are as follows:

1. According to the specific problem, desired population is generated.
2. After initial number is set, initial velocity and position of the particles is randomly generated and all the other parameters and iteration number will also be set.
3. Best fitness value of the particle will be compared with best particle solution. If the individual optimal solution is better P_best= Particle fitness and the value of fitness is recorded. Past optimal solution of the particle is compared with G_best solution and if the new value is better than old value will be replaced when the fitness value of the optimal solution of the next group will be recorded.
4. To calculate the new speed and new position of the particle, following formula will be used:

The symbols used in the above equations have the following meaning:

The flow chart given will help you understand the steps in a better way.

Following is a simple MATLAB code that uses PSO algorithm. Comments are also written for your understanding.

————————————————————————————————–

Try running this MATLAB code and see the interesting results!

Also, an external PSO toolbox is available on Mathworks website. It could be used as well for the same purpose after making few changes in the system memory and setting few variables.