Put Simply: Particle Swarm Optimisation

Welcome back to another article in the Put Simply series, where I, a complete Machine Learning Beginner, attempt to explain ML concepts as layman and simply as I can.

Today’s topic (as with the inspiration of any other article I write) stems from my recent exploration with an interesting optimisation algorithm; Particle Swarm Optimisation (or PSO). If, like me, you’ve never heard of it and require a primer, as Mario would say, “Letsa Go!”

Purpose and Intuition

PSO has two unique factors as suggested by the name; the particle and the swarm. These two are not exclusive, however, but work in harmony to achieve a common goal, that is, to balance exploration and exploitation.

Exploration refers to the method of searching new areas on a graph or plane to find an objective. This could be looking for a maxima on a graph on a new section. Exploration increases the likelihood of convergence (or finding a solution) in an optimisation problem, but is very expensive as an effective search requires many “finders”.

Exploitation refers to using shared resources and common knowledge to enhance one’s optimisation. A common example is using the current best minima found by multiple “finders” and searching near there. Excessive exploitation, whilst not as computationally expensive as exploration, can restrict the search area to a local solution, but not necessarily the best global one.

The analogy is obvious now, PSO involves initialising multiple particles or “finders”, and have them find the nearest solution closest to them. These particles are guided by:

1. The nearest local solution they have found thus far (exploration)
2. The global solution the entire swarm has found thus far (exploitation)

Balancing exploitation and exploration enables the particles to expand their search area to prevent misleading local solutions, but not so much as to overly risk missing the global solution due to limited “manpower”.

Visualisation

Handy gif to visualise PSO by Jason Brownlee

Ignoring my shameless stealing of this gif generated by Dr. Jason Brownlee over on Machine Learning Mastery (if you’re reading this I apologise), we can see that over time, the swarm (blue dots) guided by vectors (blue arrows) is able to achieve the global minimum on the contour plot (white cross).

It is interesting to see how similar (as Dr. Brownlee points out in the referenced article) the PSO algorithm behaves to an actual swarm of bees or migratory birds. It is also curious as to why and how a vector (or the velocity of the particles) influences the particles to update.

Algorithm

Assuming the example of the 2D contour plot of a 3D graph (and also using the nomenclature of the article, sorry again), we firstly represent the initial positions of a particle i at time t as follows:

where x and y are our 2D coordinates. Note that the 3D graph has the equation:

For every timestep, each ith particle’s position is updated by a vector V (as seen in the gif earlier) given:

Where the vector V is given:

V consists of three terms:

1. A weighted component of the previous vector (or the inertia of the particle)
2. A weighted exploration (or local) term (local i) which pulls the vector towards the closest local solution the particle i has found
3. A weighted exploitation (or global) term which influences the particle to approach the global solution found thus far

The weights for the exploration and exploitation consist of a preset weight component (c1 and c2) multiplied by a random component to enable the particle to “break out” of a false solution in the global scope.

All weights are initialised and determined between 0 and 1, and are used for controlling the influence the priority of the particles (whether to focus on inertia, local solutions or global ones).

In summary, PSO is essentially an exclusive inclusive optimisation algorithm in the sense that optimisers with exclusive “minds” work together “inclusively” to attempt to find the best solution possible.

Once again, I strongly recommend the article by Dr. Brownlee: “A Gentle Introduction to Particle Swarm Optimization”.

Feel free to check out my earlier article on Put Simply regarding Variational/Standard Autoencoders as well as my article exploring Adversarial Attacks on Neural Networks.

Once again, Zao-skis.