Taking advantage of the million-year process of Natural Selection to solve the numerical optimization problem

Tarlan Ahadli

Jan 17, 2020·6 min read

Table of content

• Introduction
• What is Emergent Complexity?
• Modeling Bird Swarm Intelligence
• Implementing Theory Using Python
• Conclusion
• Resources and References

Introduction

Particle Swarm Optimization (PSO) is a powerful algorithm based on Stochastic Optimization and inspired by the rules involved in large flocks of birds. In this article, the feasibility of the approach will be backed up, then an accurate model of these principles will be derived. Finally, the implementation of a mathematical model of these principles for the numerical optimization problem will be described and then realized using Python to find the global minima of Rastrigin Function [1]. If you’re coding in C++, you can refer to the link written in the Resources and References section [2] to view the project source codes.

What is Emergent Complexity?

Emergent Complexity[3] is the phenomenon that describes how individual components of large groups work together with the same but simpler rules to create diverse and intricate systems. There are a few natural complex behaviors that can be an example of emergence. For instance, ants instinctually communicate with each other to build a live bridge which minimizes the commutation distance while searching for a food source[4]. Birds are following each other and create larger groups which increase their likelihood of detecting predators as well as the food source. Unlike the usual concept of complexity which is not necessarily useful, natural complexity is the result of a million-year process of natural selection in which energy usage is the most essential factor to increase the chance of staying alive. Thus, if there are two solutions to the same problem, the way which is simpler and requires less energy will survive because of natural selection. That’s why the solution that nature suggests will be simple but still effective to decrease the energy consumption of the animals as much as possible. Hence, scientists observed each bird in a flock of starlings individually and found out that each of them takes simple actions to form complex structuring.

1. Each bird has its own position and velocity
2. Each bird has its own vision span in which it can follow the surrounding bird(s). The bird is absolutely unaware of the actions outside of this span.
3. If any of the birds spotted food all the birds in the flock will tend to that direction.

Modeling Bird Swarm Intelligence

As in nature, in a numerical problem, any of the boid’s (bird-like-object) observable vicinity is limited to some range. Therefore, it can converge to some local minima or saddle point in which the gradient (in our case velocity) will be 0. However, having more than one boid allows all the birds in a swarm to be aware of the larger surface of an error function and not getting stuck in local minima if any of them has seen a better position in terms of error. For this, we’ll mathematically model the above-mentioned principles to make the swarm find the global minima of an error function

1. Each boid has its own position and velocity. We can consider a velocity as a vector of partial derivatives of an error function.

2. Each boid keeps track of the best position that it ever experienced which contributes to the current velocity of boid to some predefined extend.

3. There’ll the best position that the whole birds of swarm ever saw. Therefore, it will affect the velocity of all the boids at a predefined rate.

By using the rules above, we can easily derive mathematical equations that will drive each boid.

In the equations above:

• w — is the inertia that determines to what extent the current velocity of boid will effect to ΔV
• c₁, c₂ — defines how boid’s and swarm’s best-recorded position will affect to ΔV respectively

w, c₁, c₂, learningRate —are the hyperparameters that should be finetuned during the optimization process.

Implementing Theory Using Python

The mathematical theory behind the swarm intelligence was discussed and modeled and it can be implemented using any modern programming language. However, because of its widespread usage, the implementation will be realized using Python. Still, at the Resources and References section of the article, the C++ project codes can be found as well. To test the algorithm, Rastrigin Function will be utilized as an error function, which is one of the most challenging functions for an optimization problem. Having a lot of cosine oscillations on the plane introduces a myriad of local minimums in which boids can get stuck.

As it was mentioned above, each boid will have a position, velocity, error, best position and best-known error. We should also write a setter function to modify parameters when it’s required.

The PSO class will consist of a list of moving particles on the surface of the error function. To initialize the function, the dimension of the function, number of boids, as well as the number of epochs is required.

Last, we write code to find a position that best optimizes the error function. Firstly, at each epoch, every particle is picked one-by-one and optimized its position. Once the position of the particle updated, “if” statement written checks if it’s the best location for the swarm.

Now, it’s time to run the PSO and observe the performance of the algorithm.

From the contour plot below, it can be easily seen that swarm takes only a few epochs to converge to the global minimum of the Rastrigin function. To obtain the code that creates contour visualization as well as an Error-Epochs plot of the process you can refer to link given the Resources and References section.

Conclusion

To sum up, Particle Swarm Optimization mimics the collective behavior of the swarm of the birds (or fish). It benefits from the way that nature forms to solve its own optimization problem to minimize energy usage. The design of nature and practical application of its principles to Computer Science problems is marvelous. Although there's a myriad of resources that can help you to gain more insight about Emergence as well as PSO, I’ll put some of the distinguishing ones that you can use to dig more into the topic of swarm intelligence.

Resources and References

[1] Wikipedia, Rastrigin Function

[2] T. Ahadli, Particle Swarm Optimization C++/Python Project Codes

[3]The Conversation, The remarkable simplicity of complexity

[4] National Geographic, How Ants Build Bridges in Mid-Air With Just Their Bodies

[5] James McCaffrey, Swarm Intelligence Optimization using Python