Let's play evolution? Genetic Algorithms in a Screensaver
Last month in the army. Gradually freeing up time for various interesting projects. It remains only to decide what exactly to occupy the brain. I finished reading Richard Dawkins's “ Selfish Gene ” and the idea was formulated - I want to make a visualization using the principles of evolution.
Figure 1. The bacterial population rearranges the environment to fit its needs.
So, go ahead!
')
Imagine a Petri dish with a viscous nutrient fluid on a flat surface. Somewhere the concentration of food is higher, somewhere - below. We added a viscous poison to some parts of the cup, a signal substance (“pheromone”) to some, and then we evenly distributed a colony of bacteria over the surface. All that remains for us is to observe their growth, interesting mutations that increase adaptability to a particular 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 ordinary blur). The game field is closed - is 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 specific cell, I will receive another cellular automaton, only with complex rules. Therefore, it is worth making for them an elementary physical model - 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 field cell.
Bacteria receive energy from the nutrient medium, capable of releasing poison and pheromone. Accumulated food is spent every second, any action (movement, turns, release) also spends internal resources. Bacteria multiply free of charge, by simple division, after having accumulated a certain amount of food. In addition, the body has glasses of life, decreasing in a toxic environment or during hunger. A dying bacterium leaves behind a small supply of food. The poison will restrain the reproduction of bacteria, and the signal substance will allow one creature to inform others: “this territory is already occupied, it is not profitable to get food here” (the more bacteria in one place, the greater the pheromone concentration there and, probably, the less food there is).
The idea is formulated, it's time to start implementation.
I cheated a little and used my recent project as a starting point, at the core of which I had everything I needed - working with configs, mouse, keyboard and 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 a library for working with graphics (OpenGL), and jsoncpp to save configuration files . 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, it will be possible to play on other systems (at the moment there is only XP at hand).
I initially made the field for liquids as arrays of floating point numbers, because of this the slowest part of the program was the blurring of this field on the CPU. However, about optimizations later. Movement of bacteria is very simple, in fact, all of physics is successfully processed by this piece of code (using Verlet integration):
Now about mutational variability and behavior. There was no wish to change “physical” parameters, such as movement speed or size, because it is much more interesting to change 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 cannot boil porridge with such a “complex” behavior, but the result was even worse than we would like. All the bacteria that released the poison, quickly died, leaving no offspring. Nobody (except for me) paid attention to the pheromone secreted (bacteria have not had sensors yet). As a result, everyone just swam, devouring food under him and with the accumulation of food needed for reproduction, they created the same confused creatures.
The only beautiful result came out when I tuned up the bacteria for low resistance to poison, but a large amount of food released after death. In this case, although they were dying from the venom excreted, they managed to leave enough offspring to continue the race in a nutrient and aggressive environment.
Figure 2. Rapid Cloning and Toxic Environment
Apparently, the idea of ​​a toxic "poison" and a signal "pheromone" works very badly:
I gave up two independent substances with different properties and instead of them made “an ideal environment point” for each bacterium - the ratio of two liquids (POISON and FEROMON, left the names different for convenience), at which the environment does not cause bacteria damage. The stronger the ratio, the more toxic this mixture is for the creature. The value of this point (resist) is transmitted from the parent bacteria to the daughter with a small distortion.
Scheme 1. The ideal environment for the body
Thus, there are whole populations of living beings that can survive in different environments and who benefit from transforming the world around them. There should have been competition, 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 rebuilding 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 without it, it is clear that the bottleneck of the program is the blurring of the array of “liquids” on the CPU. And the current implementation (3 liquids of different colors, should be blurred and displayed on the screen) and asks to be rewritten on the GPU. In SFML it is very easy to work with shaders and texture rendering. One drawback - there is no support for floating-point textures. So we transfer all fluids from float (from -1.0 to 1.0) to unsigned char (0, 255) and store as sf :: Image. When updating the field, we render it in texture, with a shader blur. We write the GLSL fragmentary shader (for a start, 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. Spaces for optimizations remain. Using gprof , we find some more bottlenecks.
But still, the most unpleasant bottleneck is the magic numbers in the code, due to which the project has to be re-compiled each time the settings are changed. Transfer all settings to json-config is quite simple, but the result is worth it.
Figure 5. Restructuring the environment with similar populations.
Figure 6. Slow Colony Growth
At the moment, the bacteria can not change their behavior. The array of actions defining its actions varies slightly only among 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 - accumulate. But the benefits here are a very relative concept.
For example, the bacterium is in the environment {FEROMON = -0.5, POISON = 0.2}, and its ideal medium is {FEROMON = 0.6, POISON = 0.6}. It means that it is advantageous to produce both substances in a small amount in order to bring the environment closer to the ideal one. 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 bacterium” to monitor the environment and make decisions?
It remains to decide how to do it. There is an idea of ​​an assembly-like language, whose instructions will constitute the genocode of the bacterium. But in this case, you need a lot of mutations to move from one useful program of action to another, and the vast majority of mutations will be completely lethal.
Perhaps neural networks? I tried for each bacterium to make a brain from a small perceptron in 2 layers and several feedbacks. The weights of bonds in the creation of the first bacteria are random and mutate in their descendants. It turned out even worse than no brain at all. I did not expect that this small experiment will bring positive results - I confess, I almost never worked with neural networks of any kind. I suppose that evolutionary selection was simply not able to leave the best-fit neural networks, since the environment around the bacteria is too aggressive for a long life, and the neural networks at first are completely untrained and give out meaningless, or even harmful, commands for the bacteria.
Soon a new idea appeared - conditions. The condition in my case looks like this:
1 Receptor - which input data will influence the result: FOOD, FEROMON, POISON, SPEED, FAT, LIFE, FEROMON_RESIST, POISON_RESIST;
2 Conditional interval - interval, 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 (the action value is added to "impact force"), DEDUCT (the action force is subtracted from the action value), CLEAR (action value becomes zero)
5 Impact force - the number by which the action will change.
So, the condition:
Take the situation with the bacterium in the environment {-0.5, 0.2} and with the ideal medium {0.6, 0.6}. Such a set of conditions will ensure that it creates and maintains an ideal environment:
And such conditions will allow you to efficiently get food:
Wrote a separate class of DNA that stores all the genetic information. When bacteria multiply, each gene can with a certain probability be deleted or duplicated. There is a possibility of adding new, happy genes conditions. In addition to a set of conditions, the maximum speed of the bacteria and the value of the ideal medium are stored in the DNA. I tried multiplication of bacteria to do another action, for the activation of which also need to use the conditions, but the result was dull. But one feature of the use of such "conditional" genes seemed curious to me. For example, some kind of bacteria is beneficial to constantly rotate at a low speed. But when moving, all receptors will change their values, as bacteria indicate that it needs to always rotate? Evolution sometimes selected those individuals whose conditions were obviously true, for example, POSION_RESIST [0.3, 0.6] with a 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, on the other hand, it limits the mutational variability of the 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 stocks, therefore creating a large amount of junk genes conditions is evolutionarily unprofitable. You can notice the dependence (by looking at the DNA of individual bacteria) - the more food, the more junk genes are stored in DNA.
On the visual side, the downside was the ability of bacteria to generate different colors (the ratio of pheromone and poison), depending on the conditions, and the beautiful division into colored populations has sunk into oblivion.
Figure 7. The absorption of food by the population with conditional behavior.
It was impossible not to add interactivity to the program. For example, the ability to draw with poison, food or pheromone. I will describe all the management features:
The program was originally created as a micro-prototype, play for 15 minutes. But tightened. Therefore, the code has all the shortcomings of the prototype, which, however, I plan to eliminate. The result was not as beautiful as the intermediate versions (without DNA and with multi-colored populations), it is worth thinking about other imaging options, for example, to stain 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 become extinct.
Here is what I want to change soon:
Last compiled version of the program
The 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 as a vector (legacy of the past project) and only in recent commits I replaced it with a samopisny 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).
Enjoyable evolution!
Figure 1. The bacterial population rearranges the environment to fit its needs.
So, go ahead!
- Petri dish and program idea
- Programming language, environment, libraries
- Working version too simple
- Additional ideas
- The first interesting results
- Optimization, config
- Behavior programming
- Useful features
- Debriefing, plans
- Links to the program, source code, instructions
')
Petri dish and program idea
Imagine a Petri dish with a viscous nutrient fluid on a flat surface. Somewhere the concentration of food is higher, somewhere - below. We added a viscous poison to some parts of the cup, a signal substance (“pheromone”) to some, and then we evenly distributed a colony of bacteria over the surface. All that remains for us is to observe their growth, interesting mutations that increase adaptability to a particular 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 ordinary blur). The game field is closed - is 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 specific cell, I will receive another cellular automaton, only with complex rules. Therefore, it is worth making for them an elementary physical model - 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 field cell.
Bacteria receive energy from the nutrient medium, capable of releasing poison and pheromone. Accumulated food is spent every second, any action (movement, turns, release) also spends internal resources. Bacteria multiply free of charge, by simple division, after having accumulated a certain amount of food. In addition, the body has glasses of life, decreasing in a toxic environment or during hunger. A dying bacterium leaves behind a small supply of food. The poison will restrain the reproduction of bacteria, and the signal substance will allow one creature to inform others: “this territory is already occupied, it is not profitable to get food here” (the more bacteria in one place, the greater the pheromone concentration there and, probably, the less food there is).
The idea is formulated, it's time to start implementation.
Programming language, environment, libraries
I cheated a little and used my recent project as a starting point, at the core of which I had everything I needed - working with configs, mouse, keyboard and 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 a library for working with graphics (OpenGL), and jsoncpp to save configuration files . 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, it will be possible to play on other systems (at the moment there is only XP at hand).
Working version too simple
I initially made the field for liquids as arrays of floating point numbers, because of this the slowest part of the program was the blurring of this field on the CPU. However, about optimizations later. Movement of bacteria is very simple, in fact, all of physics is successfully processed by this piece of code (using 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 variability and behavior. There was no wish to change “physical” parameters, such as movement speed or size, because it is much more interesting to change 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 cannot boil porridge with such a “complex” behavior, but the result was even worse than we would like. All the bacteria that released the poison, quickly died, leaving no offspring. Nobody (except for me) paid attention to the pheromone secreted (bacteria have not had sensors yet). As a result, everyone just swam, devouring food under him and with the accumulation of food needed for reproduction, they created the same confused creatures.
The only beautiful result came out when I tuned up the bacteria for low resistance to poison, but a large amount of food released after death. In this case, although they were dying from the venom excreted, they managed to leave enough offspring to continue the race in a nutrient and aggressive environment.
Figure 2. Rapid Cloning and Toxic Environment
Additional ideas
Apparently, the idea of ​​a toxic "poison" and a signal "pheromone" works very badly:
- It is not profitable to produce poison, which kills the manufacturer and its descendants.
- It is not profitable to produce pheromone (and in the presence of receptors, too), which indicates the presence of bacteria, but does not report its "form"
I gave up two independent substances with different properties and instead of them made “an ideal environment point” for each bacterium - the ratio of two liquids (POISON and FEROMON, left the names different for convenience), at which the environment does not cause bacteria damage. The stronger the ratio, the more toxic this mixture is for the creature. The value of this point (resist) is transmitted from the parent bacteria to the daughter with a small distortion.
Scheme 1. The ideal environment for the body
The first interesting results
Thus, there are whole populations of living beings that can survive in different environments and who benefit from transforming the world around them. There should have been competition, 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 rebuilding 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 without it, it is clear that the bottleneck of the program is the blurring of the array of “liquids” on the CPU. And the current implementation (3 liquids of different colors, should be blurred and displayed on the screen) and asks to be rewritten on the GPU. In SFML it is very easy to work with shaders and texture rendering. One drawback - there is no support for floating-point textures. So we transfer all fluids from float (from -1.0 to 1.0) to unsigned char (0, 255) and store as sf :: Image. When updating the field, we render it in texture, with a shader blur. We write the GLSL fragmentary shader (for a start, 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 (vx < 0.0) vx += 1.0; else if (vx >= 1.0) vx -= 1.0; if (vy < 0.0) vy += 1.0; else if (vy >= 1.0) vy -= 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. Spaces for optimizations remain. Using gprof , we find some more bottlenecks.
But still, the most unpleasant bottleneck is the magic numbers in the code, due to which the project has to be re-compiled each time the settings are changed. Transfer all settings to json-config is quite simple, but the result is worth it.
Figure 5. Restructuring the environment with similar populations.
Figure 6. Slow Colony Growth
Behavior programming
At the moment, the bacteria can not change their behavior. The array of actions defining its actions varies slightly only among 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 - accumulate. But the benefits here are a very relative concept.
For example, the bacterium is in the environment {FEROMON = -0.5, POISON = 0.2}, and its ideal medium is {FEROMON = 0.6, POISON = 0.6}. It means that it is advantageous to produce both substances in a small amount in order to bring the environment closer to the ideal one. 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 bacterium” to monitor the environment and make decisions?
It remains to decide how to do it. There is an idea of ​​an assembly-like language, whose instructions will constitute the genocode of the bacterium. But in this case, you need a lot of mutations to move from one useful program of action to another, and the vast majority of mutations will be completely lethal.
Perhaps neural networks? I tried for each bacterium to make a brain from a small perceptron in 2 layers and several feedbacks. The weights of bonds in the creation of the first bacteria are random and mutate in their descendants. It turned out even worse than no brain at all. I did not expect that this small experiment will bring positive results - I confess, I almost never worked with neural networks of any kind. I suppose that evolutionary selection was simply not able to leave the best-fit neural networks, since the environment around the bacteria is too aggressive for a long life, and the neural networks at first are completely untrained and give out meaningless, or even harmful, commands for the bacteria.
Soon a new idea appeared - conditions. The condition in my case looks like this:
1 Receptor - which input data will influence the result: FOOD, FEROMON, POISON, SPEED, FAT, LIFE, FEROMON_RESIST, POISON_RESIST;
2 Conditional interval - interval, 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 (the action value is added to "impact force"), DEDUCT (the action force is subtracted from the action value), CLEAR (action value becomes zero)
5 Impact force - the number by which the action will change.
So, the condition:
RECEPTOR[min, max], ACTION,OPERATION,VALUE. Take the situation with the bacterium in the environment {-0.5, 0.2} and with the ideal medium {0.6, 0.6}. Such a set of conditions will ensure that it creates and maintains 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 efficiently get food:
FOOD [0.0, 2.0] MOVE APPEND 1.0 // , FOOD [2.0, 10.0] MOVE CLEAR 0.0 // , Wrote a separate class of DNA that stores all the genetic information. When bacteria multiply, each gene can with a certain probability be deleted or duplicated. There is a possibility of adding new, happy genes conditions. In addition to a set of conditions, the maximum speed of the bacteria and the value of the ideal medium are stored in the DNA. I tried multiplication of bacteria to do another action, for the activation of which also need to use the conditions, but the result was dull. But one feature of the use of such "conditional" genes seemed curious to me. For example, some kind of bacteria is beneficial to constantly rotate at a low speed. But when moving, all receptors will change their values, as bacteria indicate that it needs to always rotate? Evolution sometimes selected those individuals whose conditions were obviously true, for example, POSION_RESIST [0.3, 0.6] with a 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, on the other hand, it limits the mutational variability of the 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 stocks, therefore creating a large amount of junk genes conditions is evolutionarily unprofitable. You can notice the dependence (by looking at the DNA of individual bacteria) - the more food, the more junk genes are stored in DNA.
On the visual side, the downside was the ability of bacteria to generate different colors (the ratio of pheromone and poison), depending on the conditions, and the beautiful division into colored populations has sunk into oblivion.
Figure 7. The absorption of food by the population with conditional behavior.
Useful features
It was impossible not to add interactivity to the program. For example, the ability to draw with poison, food or pheromone. I will describe all the management features:
- Camera control:
- Scroll - camera zoom in / out
- Drag with scroll pressed - camera movement
- Drawing:
- Left mouse button - draw with the current brush
- Up - change brush size
- Down - change the "ink"
- Clear all liquids from the screen - q
- Visualization:
- Display / show bacteria - space
- Save each frame in * .png - F8
- Dying bacteria turn red, and starving people take on a cyan hue
- Speed:
- Switch operation mode (slow / fast / pause) - right mouse button
- Information:
- Get information about the DNA of the bacteria closest to the mouse (it is better to use when stopping time, 1/0 before the gene - whether the condition was fulfilled in the last frame) - i
- Program settings:
- Window settings - data / settings.json
- Folder Save Settings - data / screensaver.json
- Field settings, bacteria, etc. - ai.json (if the file is damaged or deleted, it will automatically recover)
Debriefing, plans
The program was originally created as a micro-prototype, play for 15 minutes. But tightened. Therefore, the code has all the shortcomings of the prototype, which, however, I plan to eliminate. The result was not as beautiful as the intermediate versions (without DNA and with multi-colored populations), it is worth thinking about other imaging options, for example, to stain 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 become extinct.
Here is what I want to change soon:
- Restoration of the floating-point field cell values ​​(but still on the video card) in order to remove the permanent conversion (loss) from float to uchar
- Optimization. Many bottlenecks, such as the cloning of bacteria.
- Parallelization. The program works in one thread, while the program should be perfectly parallelized.
- Autobalance substances. Add food to the field if necessary
- The Garden of Eden. Selection of the most successful bacteria for their subsequent cultivation.
Links to the program, source code, instructions
Last compiled version of the program
The 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 as a vector (legacy of the past project) and only in recent commits I replaced it with a samopisny 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).
Enjoyable evolution!
Source: https://habr.com/ru/post/226337/
All Articles