Did you know that there is an entire field of information technology based on biology, natural processes and works of people like Darwin and Mendel? For a long time, I did not either. Now I am trying to use bio-inspired algorithms as much as possible, because they are super cool – among other things they can be used to train neural networks or find unusual solutions to problems of all industries, like this weird but allegedly perfect antenna for NASA:

Let’s learn some basics!

Sample problem

Consider the plot above. The y value (vertical axis) is dependent on the value on the horizontal axis X. How dependent? In this exact case, y = 100 - 5(x-2)^2, but that is not really important. What can be real application of this equation? For simplified example, let’s say x is the amount of salt in grams and y defines how delicious the prepared meal is. Now can you tell what value of x gives the highest value of y? Easily, from the plot you can see that x must be equal to 2. It is logical that some amount of salt is beneficial, but overdo it and you can throw your meal away.

This is not always that easy. The equation and the plot might be so complicated that you simply cannot be certain. There can also be multiple solutions (even infinite number). Last, but not least, while this problem can be visualized in 2-dimensional space – horizontal axis for variable and vertical axis for result, there may be more variables in the game (food deliciousness is not based solely on the amount of salt). Two variables will require 3D visualization (that is still easy), three variables leads to 4D visualization (manageable, but sometimes quite unclear even with 3D model). Problems with more variables cannot be grasped with average human brain. See 3D and 4D visualizations of our function below.

Enter Evolution

Evolutionary algorithms can help solve such problems – problems where we need to optimize variables (x value in our simple case) so that we get the best result (highest y value). There is a condition – the relation between variables and the result must be described (with equation, some method, or basically anything that can say something about the quality of given variables). The result value is usually called fitness and we are looking for the highest possible value. Or lowest – it does not matter – problems can be easily transformed. We can flip our problem by saying that y depicts how disgusting our meal is based on the amount of salt. The equation will be multiplied by -1 and this will result in inverted plot as shown below. You can adjust constants to get results between 0 and 100 but it is not that important – the desired value we are looking for is still 2.

Evolutionary algorithms generally work like this:

1. Create random individuals (sets of variable values) and compute their fitness. Visually, you will see points on the plot.
2. Do some interactions between individuals – that is specific for each evolutionary algorithm. Recompute the fitness.
3. Repeat step 2 until good enough solution is found.

The way of interaction between individuals is where the evolution is hidden, because it is usually inspired by real life nature processes (molecule structure changes under temperature influence or gene recombination to name a few). How would you solve it if you do not know any of these algorithms?

Basic Algorithms

How about picking random 20 values, remembering the one with the best resulting fitness, then picking 19 new random values, remembering the best again and so on? Congratulations, this is an existing algorithm and is called Blind Search. It is quite stupid, but it will work.

Another easy-to-grasp algorithm is the Hill Climbing. Imagine a hill climber (=individual) that desires to reach the top of the hill (or the bottom – again, it does not matter). But there is a mist everywhere and he cannot see anything. What can he do? He can do one step in every direction and then choose the direction where the result was best (where he reached the highest point). And repeat that over and over again, until there is simply no hill to climb. It is much better than the Blind Search, but still having problems – in variable terrain you might get stuck on smaller hill standing in the way (local extreme in math words) or you might enter an infinite loop.

SOMA

Let’s mention one more algorithm now, the Self-Organizing Migrating Algorithm, or SOMA. This algorithm is solid, logical (especially in 3D space), fun and also czech. Imagine a forest where a deer herd is living. Each deer (=individual) is randomly positioned at the beginning and the position is the set of variables. Deers want to find the place with the best food source (again, on the plot it would be the highest or the lowest point). So the deer currently at the best spot cries out: “Over here!” (or “вот здесь!” if it is a russian deer) and all the other deers run to them. But at each step they will look at the ground and if their current spot is even better, they call the herd to them. And repeat.

By the way it is easy to imagine a 4D space with this algorithm. While deers do not levitate and therefore only 2 parameters apply to them (latitude, longitude), imagine a sea world instead – fish can move even up and down (that is latitude, longitude, altitude). Quality of food in given location is the 4th dimension. You are welcome.

This is the basic principle of SOMA. In reality, modifications are usually present – for example the following deers may not run directly to the leader or there are even multiple leaders. Later I might dive into thorough experiments with the options, here I wanted to describe basics and emphasize that a leader can influence other individuals, because I feel this concept is also very important from a philosophical point of view.