An Overview of Particle swarm optimization (PSO)

September 8, 2017

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.

Definition

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.

Definitions

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

 Pseudo Code For each particle { Initialize 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 }

References

[1] 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

[2] “Particle Swarm Optimization”, online available at: http://mnemstudio.org/particle-swarm-introduction.htm

[3] 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.

[4] Saini, Sanjay, et al. “A review on particle swarm optimization algorithm and its variants to human motion tracking”, Mathematical Problems in Engineering 2014 (2014).

13 Comments

• legacyofdiscordhackios October 31, 2017 at 6:37 am

Great, this is what I was looking for in google

• show me how November 6, 2017 at 1:34 pm

Your site has proven useful to me.

• cuphead download free android November 25, 2017 at 3:50 pm

Just wanna input on few general things, The website layout is perfect, the articles is very superb : D.

• express vpn activation code generator February 17, 2018 at 2:19 am

I dugg some of you post as I thought they were very beneficial invaluable

• summertime saga 14.5.2 save  April 3, 2018 at 11:59 pm

I like this website its a master peace ! Glad I found this on google .

• istripper free credits April 4, 2018 at 6:02 pm

I have interest in this, danke.

• btc stealer 4.3 download April 12, 2018 at 9:36 pm

I must say, as a lot as I enjoyed reading what you had to say, I couldnt help but lose interest after a while.

• I consider something really special in this site.

• Fortnite fails April 24, 2018 at 3:17 pm

Ni hao, i really think i will be back to your site

• pop over to this website May 3, 2018 at 8:40 pm

I simply want to say I am just beginner to blogging and absolutely liked this blog. Very likely I’m likely to bookmark your blog . You actually have great posts. Kudos for revealing your blog.

• view publisher site May 4, 2018 at 1:03 am

I just want to mention I am newbie to blogging and site-building and actually savored this page. Almost certainly I’m likely to bookmark your site . You certainly have exceptional articles and reviews. Regards for sharing your web-site.

• minecraft July 31, 2018 at 9:29 am

Hi to all, it’s truly a pleasant for me to pay a quick visit this site, it includes useful Information.

• minecraft July 31, 2018 at 9:42 am

Awesome issues here. I am very glad to look your article.

Thanks so much and I am looking ahead to contact you.
Will you please drop me a e-mail?

Insert math as
Additional settings
Formula color
Type math using LaTeX
Preview
$${}$$
Nothing to preview
Insert