June 16, 2014 at 12:01Let's play evolution? Genetic algorithms in screensaver
Last month in the army. Gradually freed up time for various interesting projects. It remains only to decide what exactly to occupy the brain. Finished reading " The Selfish Gene " by Richard Dawkins and the idea was formulated - I want to make a visualization that uses the principles of evolution.
Figure 1. A bacterial population rebuilds the environment to fit its needs.
So go ahead!
Imagine a Petri dish with a viscous nutrient fluid spilled on a flat surface. Somewhere the concentration of food is higher, somewhere lower. In some places of the cup we added the same viscous poison, in some - the signal substance (“pheromone”), and then we evenly distributed a colony of bacteria on the surface. All that remains for us is to observe their growth, interesting mutations that increase adaptability to a certain environment. I wanted to do something similar.
With the Petri dish itself (the playing field), everything was clear from the very beginning - a two-dimensional array of concentrations of food, poison and pheromone, which each frame slowly mixes (with the usual blur). The playing field is closed - it represents the surface of the torus. But with the implementation of bacteria is not so simple. If they are discretely located on the field, each in a certain cell, I will get another cellular automaton, only with complex rules. Therefore, it is worth making an elementary physical model for them - without collisions, but with float coordinates, speed and friction. And the food, poison or pheromone with which the bacterium interacts will be selected from the nearest cell in the field.
Bacteria receive energy from the nutrient medium, are able to secrete poison and pheromone. The accumulated food is spent every second, any action (movement, turns, allocation) also spends internal resources. Bacteria reproduce asexually, by simple division, after they have accumulated a certain amount of food. In addition, the body has life points that decrease in a toxic environment or during hunger. A dying bacterium leaves behind a small supply of food. The poison will inhibit the growth of bacteria, and the signaling substance will allow one creature to tell others: "this territory is already occupied, it is not profitable to get food here" (the more bacteria in one place, the greater the concentration of pheromone and, probably, the less food there).
The idea is formulated, it is time to begin implementation.
I cheated a little and used my recent project as a starting point, at the core of which was everything I needed - working with configs, a mouse, a keyboard and a camera. Language - C ++ 11 ( GCC 4.8.1, on MinGW ), development environment - NetBeans 7.4 (and sometimes Sublime Text 3 ) I chose SFML 2.1 as the library for working with graphics (OpenGL) , and jsoncpp to save the configs . Unfortunately, at the beginning of development it was not possible to install a version control system and this greatly spoiled life. As soon as such an opportunity appeared - mercurial with tortoiseHg. As you can see, everything is cross-platform and, if desired, can be played on other systems (currently only XP is at hand).
I initially made the field for liquids as arrays of floating-point numbers, because of this, the slowest piece of the program was the blurring of this field on the CPU. However, about optimizations later. The movements of bacteria are very simple, in fact, this piece of code successfully processes all physics (I use Verlet integration ):
Now about mutational variation and behavior. I did not want to change the “physical” parameters, such as speed or size, it’s much more interesting to change the behavior. Therefore, each bacterium contains an array of actions:
Each action is a floating point number, its value determines the "strength" of the movement. Thus, when cloning a bacterium, the value of any action may change with some probability.
Obviously, you won’t cook porridge with such a “difficult” behavior, but the result is even worse than we would like. All bacteria that secrete poison quickly died without leaving offspring. Nobody (except me) paid attention to the secreted pheromone (bacteria had no sensors so far). As a result, everyone just sailed, devouring food beneath themselves and, while accumulating the food necessary for reproduction, created the same stupid creatures.
The only beautiful result was when I set the bacteria to a low resistance to poison, but a large amount of food released after the death. In this case, although they were dying from the allocated poison, they managed to leave enough offspring for procreation in a nutritious and aggressive environment.
Figure 2. Fast cloning and toxic environment
Apparently, the idea with a toxic “poison” and a signal “pheromone” works very badly:
I gave up two independent substances with different properties and instead of them made each bacterium a “point of ideal environment” - the ratio of two liquids (POISON and FEROMON, the names were left different for convenience), in which the environment does not cause bacteria damage. The stronger the ratio, the more toxic the mixture is to the creature. The value of this point (resist) is transmitted from the parent bacterium to the daughter one with slight distortion.
Scheme 1. The ideal environment for the body
Thus, entire populations of living creatures arise, which can survive in different environments and which benefit from transforming the world around them. Competition should have arisen, because the ideal environment of one population is poison for another, and each population needs to get food. So it happened:
Figure 3. Two different populations rebuild the environment
The result is interesting, but the speed leaves much to be desired: 50-60 milliseconds per frame give 16-20 FPS. For profiling, I use gprof, but even without it it is clear that the bottleneck of the program is blurring the array of "liquids" on the CPU. And the current implementation (3 fluids of different colors, should be washed out and displayed on the screen) and asks to be rewritten on the GPU. In SFML, working with shaders and rendering into textures is very easy. One drawback is that there is no support for floating-point textures. So we transfer all liquids from float (from -1.0 to 1.0) to unsigned char (0, 255) and store as sf :: Image. When updating a field, render it into a texture, with a blur shader. We write the GLSL fragment shader (to start with, the usual arithmetic average of the current texel and its neighbors is enough, perhaps with some coefficients):
The speed of work immediately increased by 2 - 2.5 times. There is room for optimizations. Using gprof , we find a few more bottlenecks.
But still, the most unpleasant bottleneck is the magic numbers in the code, because of which you have to reassemble the project every time you change the settings. Transferring all the settings to the json config is quite simple, but the result is worth it.
Figure 5. Reorganization of the environment by similar populations
Figure 6. Slow colony growth
At the moment, the bacterium cannot change its behavior. The actions array, which determines its actions, changes slightly only in the descendants of the bacterium, remaining constant throughout its life. In general, the behavior of the population is gradually changing, due to the evolutionary process - harmful mutations are cut off, useful ones accumulate. But the benefit here is a very relative concept.
For example, a bacterium is in the environment {FEROMON = -0.5, POISON = 0.2}, and its ideal environment is {FEROMON = 0.6, POISON = 0.6}. So, it is beneficial for her to produce both substances in a small amount in order to bring the environment closer to ideal. But she will not be able to stop, and after a while, continuing to synthesize poison and pheromone, she will move away from the ideal and destroy herself. What if you “teach the bacteria” to monitor the environment and make decisions?
It remains to decide how to do this. There is an idea of an assembler-like language, whose instructions will make up the bacterial genocode. But in this case, many mutations will be needed to move from one useful program of action to another, and the vast majority of mutations will be fatal at all.
Perhaps neural networks? I tried for each bacterium to make the brain from a small perceptron in 2 layers and several feedbacks. The weights of bonds when creating the first bacteria are random and mutate in their descendants. It turned out even worse than without a brain at all. I did not expect that this small experiment would bring positive results - I repent, I almost never worked with any kind of neural networks. I suppose that evolutionary selection was simply not able to leave the most adapted neural networks, because the environment around bacteria is too aggressive for a long life, and the neural networks at first were completely untrained and issue meaningless, or even harmful to the bacterium commands.
Soon a new idea came up - conditions. The condition in my case looks like this:
1 Receptor - which input data will affect the result: FOOD, FEROMON, POISON, SPEED, FAT, LIFE, FEROMON_RESIST, POISON_RESIST;
2 Conditional interval - the interval of receptor values in which the condition will be considered true
3 Action - what exactly the condition affects: MOVE, ROTATE_LEFT, ROTATE_RIGHT, CREATE_FEROMON, CREATE_POISON
4 Operation - how the action will change when the condition is fulfilled: APPEND (is added to the action value “Force of influence”), DEDUCT (“force of influence” is subtracted from the value of the action), CLEAR (value of the action becomes equal to zero)
5 Force of influence is the number by which the action will change.
So, the condition:
Let us take the situation with the bacterium in the medium {-0.5, 0.2} and with the ideal medium {0.6, 0.6}. Such a set of conditions will provide her with the creation and maintenance of an ideal environment:
And such conditions will allow you to get food quite efficiently:
Wrote a separate DNA class that stores all the genetic information. When bacteria multiply, each gene can, with a certain probability, be deleted or duplicated. There is the likelihood of adding new, happy condition genes. In addition to a set of conditions, the maximum speed of bacteria and the value of an ideal environment are stored in DNA. I tried to multiply the bacteria by another action, for the activation of which we also need to use the conditions, but the result was dull. But one feature of the use of such "conditional" genes seemed to me curious. For example, some kind of bacteria is advantageous to constantly rotate at low speed. But when moving, all receptors will change their values, how do bacteria indicate that it needs to rotate always? Evolution sometimes selected those individuals whose conditions were obviously true, for example, POSION_RESIST [0.3, 0.6] with resistance to poison 0.4. On the one hand, this approach allows bacteria to perform a certain action regardless of the environment and receptor parameters, and on the other hand, it limits the mutational variability of an ideal environment (since those bacteria whose resistance goes beyond certain limits lose all their unconditional actions).
By the way, the challenge of one condition also spends food supplies, so creating a large number of trash genes-conditions is evolutionarily unprofitable. You can notice the dependence (looking at the DNA of individual bacteria) - the more food, the more garbage genes are stored in DNA.
The minus on the visual side was the ability of bacteria to generate different colors (the ratio of pheromone and poison) depending on conditions, and beautiful splits into color populations have sunk into oblivion.
Figure 7. Food intake by a population with conditional behavior.
It was impossible not to add interactivity to the program. For example, the ability to draw poison, food or pheromone. I will describe all the management features:
The program was originally created as a micro-prototype, played for 15 minutes. But dragged on. Therefore, the code has all the disadvantages of the prototype, which, however, I plan to eliminate. The result is not as beautiful as the intermediate versions (without DNA and with multi-colored populations), it is worth considering other visualization options, for example, staining bacteria depending on their origin. Another important problem is the lack of balancing the amount of food: it is difficult to choose the settings so that the program can work all night, and the populations do not die out.
Here is what I want to change in the near future:
The latest compiled version of the program
Sources of the program (in the run folder is the compiled version), you will need SFML 2.1 and jsoncpp . It should be noted that until the last moment I used b2vec2 from box2d (a legacy of the previous project) as a vector, and only in the last commits I replaced it with a self-written vector. Therefore, if you want to build the old version, transfer the new Math :: Vector from core / math / vector.h there.
You play with the settings in ai.json, run ai.exe and follow the evolution (or actively intervene).
Have a nice evolution!
Figure 1. A bacterial population rebuilds the environment to fit its needs.
So go ahead!
- Petri dish and program idea
- Programming language, environment, libraries
- Working version too simple
- Additional ideas
- First interesting results
- Optimization, config
- Behavior programming
- Useful Features
- Debriefing, plans
- Links to the program, source codes, instructions
Petri dish and program idea
Imagine a Petri dish with a viscous nutrient fluid spilled on a flat surface. Somewhere the concentration of food is higher, somewhere lower. In some places of the cup we added the same viscous poison, in some - the signal substance (“pheromone”), and then we evenly distributed a colony of bacteria on the surface. All that remains for us is to observe their growth, interesting mutations that increase adaptability to a certain environment. I wanted to do something similar.
With the Petri dish itself (the playing field), everything was clear from the very beginning - a two-dimensional array of concentrations of food, poison and pheromone, which each frame slowly mixes (with the usual blur). The playing field is closed - it represents the surface of the torus. But with the implementation of bacteria is not so simple. If they are discretely located on the field, each in a certain cell, I will get another cellular automaton, only with complex rules. Therefore, it is worth making an elementary physical model for them - without collisions, but with float coordinates, speed and friction. And the food, poison or pheromone with which the bacterium interacts will be selected from the nearest cell in the field.
Bacteria receive energy from the nutrient medium, are able to secrete poison and pheromone. The accumulated food is spent every second, any action (movement, turns, allocation) also spends internal resources. Bacteria reproduce asexually, by simple division, after they have accumulated a certain amount of food. In addition, the body has life points that decrease in a toxic environment or during hunger. A dying bacterium leaves behind a small supply of food. The poison will inhibit the growth of bacteria, and the signaling substance will allow one creature to tell others: "this territory is already occupied, it is not profitable to get food here" (the more bacteria in one place, the greater the concentration of pheromone and, probably, the less food there).
The idea is formulated, it is time to begin implementation.
Programming language, environment, libraries
I cheated a little and used my recent project as a starting point, at the core of which was everything I needed - working with configs, a mouse, a keyboard and a camera. Language - C ++ 11 ( GCC 4.8.1, on MinGW ), development environment - NetBeans 7.4 (and sometimes Sublime Text 3 ) I chose SFML 2.1 as the library for working with graphics (OpenGL) , and jsoncpp to save the configs . Unfortunately, at the beginning of development it was not possible to install a version control system and this greatly spoiled life. As soon as such an opportunity appeared - mercurial with tortoiseHg. As you can see, everything is cross-platform and, if desired, can be played on other systems (currently only XP is at hand).
Working version too simple
I initially made the field for liquids as arrays of floating-point numbers, because of this, the slowest piece of the program was the blurring of this field on the CPU. However, about optimizations later. The movements of bacteria are very simple, in fact, this piece of code successfully processes all physics (I use Verlet integration ):
Math::Vector tmp = this->position;
this->position += this->position - this->old_position;
this->old_position = this->position - (1.0f - this->settings.friction) * (this->position - tmp);
Now about mutational variation and behavior. I did not want to change the “physical” parameters, such as speed or size, it’s much more interesting to change the behavior. Therefore, each bacterium contains an array of actions:
MOVE, ROTATE_LEFT, ROTATE_RIGHT, CREATE_FEROMON, CREATE_POISON
Each action is a floating point number, its value determines the "strength" of the movement. Thus, when cloning a bacterium, the value of any action may change with some probability.
Obviously, you won’t cook porridge with such a “difficult” behavior, but the result is even worse than we would like. All bacteria that secrete poison quickly died without leaving offspring. Nobody (except me) paid attention to the secreted pheromone (bacteria had no sensors so far). As a result, everyone just sailed, devouring food beneath themselves and, while accumulating the food necessary for reproduction, created the same stupid creatures.
The only beautiful result was when I set the bacteria to a low resistance to poison, but a large amount of food released after the death. In this case, although they were dying from the allocated poison, they managed to leave enough offspring for procreation in a nutritious and aggressive environment.
Figure 2. Fast cloning and toxic environment
Additional ideas
Apparently, the idea with a toxic “poison” and a signal “pheromone” works very badly:
- It is not profitable to produce poison that kills the manufacturer and its descendants.
- It is not profitable to produce pheromone (and in the presence of receptors, too), which gives out the presence of bacteria, but does not report its “appearance”
I gave up two independent substances with different properties and instead of them made each bacterium a “point of ideal environment” - the ratio of two liquids (POISON and FEROMON, the names were left different for convenience), in which the environment does not cause bacteria damage. The stronger the ratio, the more toxic the mixture is to the creature. The value of this point (resist) is transmitted from the parent bacterium to the daughter one with slight distortion.
Scheme 1. The ideal environment for the body
First interesting results
Thus, entire populations of living creatures arise, which can survive in different environments and which benefit from transforming the world around them. Competition should have arisen, because the ideal environment of one population is poison for another, and each population needs to get food. So it happened:
Figure 3. Two different populations rebuild the environment
Optimization
The result is interesting, but the speed leaves much to be desired: 50-60 milliseconds per frame give 16-20 FPS. For profiling, I use gprof, but even without it it is clear that the bottleneck of the program is blurring the array of "liquids" on the CPU. And the current implementation (3 fluids of different colors, should be washed out and displayed on the screen) and asks to be rewritten on the GPU. In SFML, working with shaders and rendering into textures is very easy. One drawback is that there is no support for floating-point textures. So we transfer all liquids from float (from -1.0 to 1.0) to unsigned char (0, 255) and store as sf :: Image. When updating a field, render it into a texture, with a blur shader. We write the GLSL fragment shader (to start with, the usual arithmetic average of the current texel and its neighbors is enough, perhaps with some coefficients):
uniform sampler2D texture;
uniform float blurSize;
uniform float horizontalPass;
uniform float sigma;
uniform float width;
uniform float height;
vec2 ranged(vec2 v)
{
if (v.x < 0.0)
v.x += 1.0;
else if (v.x >= 1.0)
v.x -= 1.0;
if (v.y < 0.0)
v.y += 1.0;
else if (v.y >= 1.0)
v.y -= 1.0;
return v;
}
void main()
{
vec2 texcoordOffset = vec2(1.0, 1.0) / vec2(width, height);
float k0 = 1.0;
float k1 = 0.5;
float k2 = 0.357;
vec4 avgValue =
texture2D(texture, gl_TexCoord[0].st) * k0 +
texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, -1.0))) * k1 +
texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, -1.0))) * k1 +
texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, 1.0))) * k1 +
texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, 1.0))) * k1 +
texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, 0.0))) * k2 +
texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, 0.0))) * k2 +
texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(0.0, -1.0))) * k2 +
texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(0.0, 1.0))) * k2;
gl_FragColor = avgValue / (k0 + 4.0 * k1 + 4.0 * k2);
}
The speed of work immediately increased by 2 - 2.5 times. There is room for optimizations. Using gprof , we find a few more bottlenecks.
But still, the most unpleasant bottleneck is the magic numbers in the code, because of which you have to reassemble the project every time you change the settings. Transferring all the settings to the json config is quite simple, but the result is worth it.
Figure 5. Reorganization of the environment by similar populations
Figure 6. Slow colony growth
Behavior programming
At the moment, the bacterium cannot change its behavior. The actions array, which determines its actions, changes slightly only in the descendants of the bacterium, remaining constant throughout its life. In general, the behavior of the population is gradually changing, due to the evolutionary process - harmful mutations are cut off, useful ones accumulate. But the benefit here is a very relative concept.
For example, a bacterium is in the environment {FEROMON = -0.5, POISON = 0.2}, and its ideal environment is {FEROMON = 0.6, POISON = 0.6}. So, it is beneficial for her to produce both substances in a small amount in order to bring the environment closer to ideal. But she will not be able to stop, and after a while, continuing to synthesize poison and pheromone, she will move away from the ideal and destroy herself. What if you “teach the bacteria” to monitor the environment and make decisions?
It remains to decide how to do this. There is an idea of an assembler-like language, whose instructions will make up the bacterial genocode. But in this case, many mutations will be needed to move from one useful program of action to another, and the vast majority of mutations will be fatal at all.
Perhaps neural networks? I tried for each bacterium to make the brain from a small perceptron in 2 layers and several feedbacks. The weights of bonds when creating the first bacteria are random and mutate in their descendants. It turned out even worse than without a brain at all. I did not expect that this small experiment would bring positive results - I repent, I almost never worked with any kind of neural networks. I suppose that evolutionary selection was simply not able to leave the most adapted neural networks, because the environment around bacteria is too aggressive for a long life, and the neural networks at first were completely untrained and issue meaningless, or even harmful to the bacterium commands.
Soon a new idea came up - conditions. The condition in my case looks like this:
1 Receptor - which input data will affect the result: FOOD, FEROMON, POISON, SPEED, FAT, LIFE, FEROMON_RESIST, POISON_RESIST;
2 Conditional interval - the interval of receptor values in which the condition will be considered true
3 Action - what exactly the condition affects: MOVE, ROTATE_LEFT, ROTATE_RIGHT, CREATE_FEROMON, CREATE_POISON
4 Operation - how the action will change when the condition is fulfilled: APPEND (is added to the action value “Force of influence”), DEDUCT (“force of influence” is subtracted from the value of the action), CLEAR (value of the action becomes equal to zero)
5 Force of influence is the number by which the action will change.
So, the condition:
RECEPTOR[min, max], ACTION,OPERATION,VALUE.
Let us take the situation with the bacterium in the medium {-0.5, 0.2} and with the ideal medium {0.6, 0.6}. Such a set of conditions will provide her with the creation and maintenance of an ideal environment:
FEROMON[-1.0,-0.4] CREATE_FEROMON APPEND 0.1
FEROMON[0.6,1.0] CREATE_FEROMON DEDUCT 0.1
POISON[-1.0,-0.5] CREATE_ POISON APPEND 0.1
POISON [0.7,1.0] CREATE_ POISON DEDUCT 0.1
And such conditions will allow you to get food quite efficiently:
FOOD [0.0, 2.0] MOVE APPEND 1.0 // Двигаться, если пищи вокруг мало
FOOD [2.0, 10.0] MOVE CLEAR 0.0 // Остановиться, если пищи вокруг много
Wrote a separate DNA class that stores all the genetic information. When bacteria multiply, each gene can, with a certain probability, be deleted or duplicated. There is the likelihood of adding new, happy condition genes. In addition to a set of conditions, the maximum speed of bacteria and the value of an ideal environment are stored in DNA. I tried to multiply the bacteria by another action, for the activation of which we also need to use the conditions, but the result was dull. But one feature of the use of such "conditional" genes seemed to me curious. For example, some kind of bacteria is advantageous to constantly rotate at low speed. But when moving, all receptors will change their values, how do bacteria indicate that it needs to rotate always? Evolution sometimes selected those individuals whose conditions were obviously true, for example, POSION_RESIST [0.3, 0.6] with resistance to poison 0.4. On the one hand, this approach allows bacteria to perform a certain action regardless of the environment and receptor parameters, and on the other hand, it limits the mutational variability of an ideal environment (since those bacteria whose resistance goes beyond certain limits lose all their unconditional actions).
By the way, the challenge of one condition also spends food supplies, so creating a large number of trash genes-conditions is evolutionarily unprofitable. You can notice the dependence (looking at the DNA of individual bacteria) - the more food, the more garbage genes are stored in DNA.
The minus on the visual side was the ability of bacteria to generate different colors (the ratio of pheromone and poison) depending on conditions, and beautiful splits into color populations have sunk into oblivion.
Figure 7. Food intake by a population with conditional behavior.
Useful Features
It was impossible not to add interactivity to the program. For example, the ability to draw poison, food or pheromone. I will describe all the management features:
- Camera control:
- Scroll - zoom in / out camera
- Drag with scroll key - moving the camera
- Painting:
- Left mouse button - draw with the current brush
- Up - Resize Brush
- Down - Change Ink
- Clear screen of all liquids - q
- Visualization:
- Display / show bacteria - space
- Save each frame to * .png - F8
- Dying bacteria turn red, and starving bacteria acquire a cyan hue.
- Speed:
- Switch operation mode (slow / fast / pause) - right mouse button
- Information:
- To obtain information about the DNA of the bacteria closest to the mouse (it is better to use it when time is stopped, 1/0 before the gene — whether the condition was fulfilled in the last frame) - i
- Program Settings:
- Window settings - data / settings.json
- Saving folder settings - data / screensaver.json
- Field settings, bacteria, etc. - ai.json (if the file is damaged or deleted, it will be automatically restored)
Debriefing, plans
The program was originally created as a micro-prototype, played for 15 minutes. But dragged on. Therefore, the code has all the disadvantages of the prototype, which, however, I plan to eliminate. The result is not as beautiful as the intermediate versions (without DNA and with multi-colored populations), it is worth considering other visualization options, for example, staining bacteria depending on their origin. Another important problem is the lack of balancing the amount of food: it is difficult to choose the settings so that the program can work all night, and the populations do not die out.
Here is what I want to change in the near future:
- Recovery of floating-point values of field cells (but still on the video card) to remove the constant conversion (with losses) from float to uchar
- Optimization. Many bottlenecks, such as cloning bacteria.
- Parallelization. The program runs in a single thread, while the program should be perfectly parallelized.
- Auto balance of substances. Add food to the field as needed
- The Garden of Eden. Selection of the most successful bacteria for their subsequent cultivation.
Links to the program, source codes, instructions
The latest compiled version of the program
Sources of the program (in the run folder is the compiled version), you will need SFML 2.1 and jsoncpp . It should be noted that until the last moment I used b2vec2 from box2d (a legacy of the previous project) as a vector, and only in the last commits I replaced it with a self-written vector. Therefore, if you want to build the old version, transfer the new Math :: Vector from core / math / vector.h there.
You play with the settings in ai.json, run ai.exe and follow the evolution (or actively intervene).
Have a nice evolution!