Balanced Reposition Mutation Particle Swarm Optimization

The rastrigin cost function.
The sphere cost function.
A comparison of fitness output between BRMPSO and PSO when optimizing the rastrigin function.
A comparison of positional accuracy between BRMPSO and PSO when optimizing the rastrigin function.
A comparison of positional accuracy between BRMPSO and PSO when optimizing the sphere function.
A comparison of fitness output between BRMPSO and PSO when optimizing the sphere function.

Inspiration

Our team was inspired to improve the Particle Swarm Optimization (PSO) algorithm after finding out it was one of the prominent algorithms using in swarm robotics. Due to the recent trend in natural disasters and climate change in our world, the number of casualties caused by these events have been on an upward trend as well. It is not very effective for humans to search for survivors during these situations, and because of this swarm robotics has been implemented in such scenarios. Our team believed the most effective way to address the need for improvement in search and rescue was to research ways to develop PSO to be more accurate, as it would directly influence swarm robotics in search and rescue applications.

What it does

Our improved PSO, the Balanced Reposition Mutation Particle Swarm Optimization (BRMPSO) algorithm, implements three different methods to improve PSO's accuracy at converging upon the target, which it currently has issues with. The first method is calculating the center of mass of the particle swarm, and using that value in one of the main equations of PSO, the velocity calculations. This would lead to a more cohesive swarm with greater consistency in output. The second method was implementing a dynamic inertial weight, or the amount of influence one particle or robot has upon the entire swarm's movement. By doing this, we were able to achieve a greater balance between exploiting the swarm's vicinity and exploring new areas for the global best solution, which is desirable for an effective PSO algorithm. Finally, we implemented a reposition mutation, which randomly reset a particle's position (with a probability factor), to increase the diversity of exploration, and avoid convergence on local solutions rather than the global solution, a common error for PSO. We used the Rastrigin and Sphere mathematical functions to test our program, and after running our code, the algorithm would output the best position of the swarm (in a two-dimensional plane) and its best fitness (how accurate the swarm was, or the z-value of the three dimensional mathematical function).

How we built it

We used the Python programming language to build off the original PSO algorithm in the Visual Studio Code IDE. The main library we used to implement the mathematical functions and the various equations in PSO was the NumPy library. Although the complexity of our program wasn't as complicated as others, a thorough knowledge of Python fundamentals was still required to structure our program. Additionally, various mathematical and conceptual topics were researched prior to the programming. The planning of various different methods to improve PSO was a time consuming process outside of programming, and could even be considered one of the hardest parts of this research project.

Challenges we ran into

Some of the main challenges we ran into during the research process was figuring out different methods to use to improve PSO, and the extensive testing that was needed to finally achieve the accuracy present in BRMPSO. For example, our research team tested the concept of derivatives (from calculus) to try to prevent convergence upon a local solution. However, when implemented in the program, this method was ultimately deemed useless, due to the sheer inconsistency in the distances from the global best solution which PSO converged. Eventually however, we were able to address this issue after researching the contribution a center of mass calculation would have upon the program's consistency.

Accomplishments that we're proud of

Some accomplishments that our team is proud of is being able to overcome challenges, as described above, and being able to persevere through many failed test attempts. We are also proud of the fact that we were able to stay coordinated offline and complete our assigned tasks, accomplishing a product of a finished research paper. These accomplishments will definitely stand as something our team can look back to, and refer to as we continue our academic careers and roles as researchers.

What we learned

Some things that our team was able to learn as a whole while executing this project was effective collaboration and writing techniques. When given a complex task in a short amount of time, our team had to learn how to adapt and manage our time even with school and other extracurriculars. Additionally, there was a learning curve when it came to writing a research paper, which was structured differently than the argumentative or narrative essays that were commonly taught in school. Finally, some technical knowledge was gained, as our entire team became more familiar with PSO, and the process/equations that were used to get an entire swarm to solve a complex optimization problem.

What's next for Balanced Reposition Mutation Particle Swarm Optimization

In the future, or if more time were to be provided for our project, our team would explore how to further improve the accuracy of BRMPSO. We may consider additional metrics such as time, which is essential in a search and rescue operation, and will delve into more advanced programming techniques in order to obtain substantial improvements from BRMPSO. We will research more complex equations and build off of prior success in PSO advancement, as well.