Particle Swarm Optimisation
Performance under Different Variables

By David Chui (BEng Biomedical Engineering (2nd Year))

Introduction

Nature's complex web of life never fails to amaze, particularly when it comes to the concept of collective intelligence. Whether it's the formations by a bustling ant colony or the synchronised flight of a flock of birds, nature demonstrates the art of collaboration and harmony. This exhibition of collective behaviour has inspired scientists and researchers to delve into the mysteries of swarm intelligence. Through their endeavours, revolutionary findings and inventive approaches to problem-solving have emerged, pushing the limits of our understanding.

Example of swarm - Flock of Birds

What is Swarm Intelligence?

Swarm intelligence are decentralised or self-organised systems inspired by the collective behaviour observed in nature. It ranges from social insects, herd/flocking behaviour, social interactions and even evolution. Because of its decentralised specialty, swarms are more robust, adaptable and scalable in dynamic environments.

Example of Swarm Intelligence used on robotics

Emergence of swarms describes the spontaneous formation of behaviours from the interactions between individual agents. Like the demo in the title banner, the little white dots were not explicitly programmed to surround the mouse pointer but it naturally emerges as they interact individually. These naturally-occurring phenomenons are studied by scientist to come up with computational solutions in practical problems. One of them is using it as an optimisation method, Particle Swarm Optimisation (PSO) to solve complex mathematical problems.

Introduction to Particle Swarm Optimisation (PSO)

Particle Swarm Optimisation (PSO), Conceived by Dr. James Kennedy and Dr. Russell Eberhart in 1995, PSO mimics the social behaviour of bird flocks and fish schools to efficiently explore and exploit search spaces in pursuit of optimal solutions. At its heart, PSO embodies the essence of cooperation and competition, as particles navigate the solution space guided by their own experiences and those of their neighbours.

How it works - The PSO Algorithm

1. Initialisation

  • Particle Positions and Velocities
    A swarm of particles is randomly initialised within the search space. Each particle is assigned a position vector representing a potential solution and a velocity vector indicating the direction and magnitude of movement.

  • Set Personal Best for Each Particle
    Each particle's personal best position (pbest) is initially set to its current position. This represents the best solution found by that particle so far.

  • Set Global Best
    Identify the particle with the best fitness value among all particles in the swarm. This global best position (gbest) represents the overall best solution found by any particle in the swarm.

2. Iterative Optimisation

Update according to the formula:

Particle Swarm Optimization (PSO) Visually Explained | by ⭐Axel Thevenot | Towards Data Science
PSO Algorithm Equation

Variables:
Pi means the position of the ith particle.
Vi means the velocity of the ith particle.
t means the current time, whereas t+1 means the next second.
w is the inertia weight, controlling the particle's tendency to continue in its current direction.
c1​ and c2​ are acceleration coefficients that control the influence of personal and social components, respectively.
best(i) is the best value of the ith particle.
bestglobal is the best value from all particles.

3. Termination

Repeat step 2 until reach a satisfactory solution or exceeding a maximum number of iterations.

The results can either be plotted as a line graph from start to finish or output the the optimised result.

It is also possible to visualise the process on a 3D graph. The individual blog posts explores the performance of PSO on a 3D graph.

Take example of the PSO on an Ackley function. Feel free to Try PSO by clicking the buttons in order!

Best position found: NA, NA
Minimum value: NA

Following the above formula, the particles can be programmed to change position following the best particle in the swarm (social) at its own pace (cognitive).

Exploring PSO Performance under Different Variables

How would PSO performance var if we mess around with the above variables?

  • Population Size

    In PSO, the population size refers to the number of particles (or individuals) within the swarm. It has significant impact on speed of convergence and quality of solution. Convergence Speed Larger population sizes tend to lead to faster convergence because of the coverage of the search space. However, the convergence speed diminishes as the population…

    Read more: Population Size

  • Acceleration Coefficients (c1 and c2)

    In Particle Swarm Optimisation (PSO), acceleration coefficients c1 and c2 play crucial roles in influencing the cognitive and social components, respectively. These components represent the individual and collective learning aspects of PSO, contributing to the balance between local and global search. The cognitive component (c1) represents each particle’s individual learning, emphasising the importance of personal…

    Read more: Acceleration Coefficients (c1 and c2)

  • Inertia Weight (w)

    The inertia weight (w) in Particle Swarm Optimisation (PSO) is a crucial parameter that significantly impacts the algorithm’s efficiency. It plays a pivotal role in balancing exploration and exploitation during the optimisation process. Exploration meaning searching in the global space. Exploitation meaning searching within the local space. Essentially, the inertia weight regulates the particle’s tendency…

    Read more: Inertia Weight (w)

  • PSO Sandbox

    In conclusion, understanding the interplay between Population Size, Acceleration Coefficients (c1 and c2), and Inertia Weight (w) is crucial for effectively using PSO in solving optimisation problems. By fine-tuning these parameters based on problem characteristics and optimisation objectives, scientists can enhance PSO’s convergence speed and solution quality across a wide range of applications. In other…

    Read more: PSO Sandbox

Conclusion

PSO same as many optimisation algorithms are useful in various disciplines. In biomedical engineering, it would be useful to optimise retrieved signals from the human body, such as analysing MRI, CT scans to finely extract and optimise its image or interpreting EEG and ECG signals from brain and muscles. Yet, before going to future applications, it is crucial to understand the basics of its mechanics to fully utilise optimisation algorithm's potential. Hope you enjoyed the demo in simulating PSO!

References

Kennedy, J. (2006). Swarm intelligence. In Handbook of nature-inspired and innovative computing: integrating classical models with emerging technologies (pp. 187-219). Boston, MA: Springer US.

Bansal, J. C., Singh, P. K., Saraswat, M., Verma, A., Jadon, S. S., & Abraham, A. (2011, October). Inertia weight strategies in particle swarm optimization. In 2011 Third world congress on nature and biologically inspired computing (pp. 633-640). IEEE.

Kennedy, J., & Eberhart, R. (1995, November). Particle swarm optimization. In Proceedings of ICNN'95-international conference on neural networks (Vol. 4, pp. 1942-1948). ieee.