Particle swarm optimization (PSO): introduction
Particle swarm optimization (PSO) simulates the behaviors of bird flocking. Suppose the following scenario: a group of birds are randomly searching food in an area. There is only one piece of food in the area being searched. All the birds do not know where the food is. But they know how far the food is in each iteration. So what’s the best strategy to find the food? The effective one is to follow the bird which is nearest to the food. Particle swarm optimization (PSO) is a population based stochastic optimization technique developed by Dr. Eberhart and Dr. Kennedy in 1995.
Theory of particle swarm optimization (PSO) has been growing rapidly. PSO has been used by many applications of several problems. The algorithm of PSO emulates from behavior of animals societies that don’t have any leader in their group or swarm, such as bird flocking and fish schooling. Typically, a flock of animals that have no leaders will find food by random, follow one of the members of the group that has the closest position with a food source (potential solution). The flocks achieve their best condition simultaneously through communication among members who already have a better situation. Animal which has a better condition will inform it to its flocks and the others will move simultaneously to that place. This would happen repeatedly until the best conditions or a food source discovered. The process of PSO algorithm in finding optimal values follows the work of this animal society. Particle swarm optimization consists of a swarm of particles, where particle represent a potential solution.
PSO shares many similarities with evolutionary computation techniques such as Genetic Algorithms (GA). The system is initialized with a population of random solutions and searches for optima by updating generations. However, unlike GA, PSO has no evolution operators such as crossover and mutation. In PSO, the potential solutions, called particles, fly through the problem space by following the current optimum particles. The detailed information will be given in following sections.
Particle Swarm Optimization might sound complicated, but it’s really a very simple algorithm. Over a number of iterations, a group of variables have their values adjusted closer to the member whose value is closest to the target at any given moment. Imagine a flock of birds circling over an area where they can smell a hidden source of food. The one who is closest to the food chirps the loudest and the other birds swing around in his direction. If any of the other circling birds comes closer to the target than the first, it chirps louder and the others veer over toward him. This tightening pattern continues until one of the birds happens upon the food. It’s an algorithm that’s simple and easy to implement.
Particle Swarm Optimization is an algorithm capable of optimizing a non-linear and multidimensional problem which usually reaches good solutions efficiently while requiring minimal parameterization. The basic concept of the algorithm is to create a swarm of particles which move in the space around them (the problem space) searching for their goal, the place which best suits their needs given by a fitness function. The algorithm keeps track of three global variables:
- Target value or condition
- Global best (gBest) value indicating which particle’s data is currently closest to the Target
- Stopping value indicating when the algorithm should stop if the Target isn’t found
Each particle consists of:
- Data representing a possible solution
- A Velocity value indicating how much the Data can be changed
- A personal best (pBest) value indicating the closest the particle’s Data has ever come to the Target
The particles’ data could be anything. In the flocking birds example above, the data would be the X, Y, Z coordinates of each bird. The individual coordinates of each bird would try to move closer to the coordinates of the bird which is closer to the food’s coordinates (gBest). If the data is a pattern or sequence, then individual pieces of the data would be manipulated until the pattern matches the target pattern.
The velocity value is calculated according to how far an individual’s data is from the target. The further it is, the larger the velocity value. In the birds example, the individuals furthest from the food would make an effort to keep up with the others by flying faster toward the gBest bird. If the data is a pattern or sequence, the velocity would describe how different the pattern is from the target, and thus, how much it needs to be changed to match the target.
Each particle’s pBest value only indicates the closest the data has ever come to the target since the algorithm started. Figure 1 shows the working of the PSO model.
Figure 1: Flow of PSO Model
Pseudo Code of PSO
|For each particle
Do until maximum iterations or minimum error criteria
For each particle
Calculate Data fitness value
If the fitness value is better than pBest
Set pBest = current fitness value
If pBest is better than gBest
Set gBest = pBest
For each particle
Calculate particle Velocity
Use gBest and Velocity to update particle Data
 Dian Palupi Rini and Siti Mariyam Shamsuddin, “Particle Swarm Optimization: Technique, System and Challenges”, International Journal of Computer Applications (IJCA) Volume 14– No.1, January 2011
 “Particle Swarm Optimization”, online available at: http://mnemstudio.org/particle-swarm-introduction.htm
 Xuesong Yan and Qinghua Wu, “An Improved Particle Swarm Optimization Algorithm and Its Application”, IJCSI International Journal of Computer Science Issues, Vol. 10, Issue 1, No 1, January 2013.
 Saini, Sanjay, et al. “A review on particle swarm optimization algorithm and its variants to human motion tracking”, Mathematical Problems in Engineering 2014 (2014).