More about the evolution of racing cars

Recently, at Habré, I ran through a post that reminded me of such a funny and quite interesting thing as BoxCar2D ( Original , Post Version ), which I first saw a couple of years ago, and which impressed me in some way. And even then I noticed one fatal flaw in it (in short, it was not I who did it), but that time the hands did not reach its correction. And now I decided to fix it.

So, I uncovered Visual Studio and set to work.
First of all, I just repeated the BoxCar2D functionality, namely: the fixed size of the population that lives its life and generates the next generation. It was possible to play around with how complicated the track is with time, what contains the genome, and how the machines cross and mutate.

I stopped at this option: each machine has its own genome, which contains information about each of the 8 peaks and each of the 4 potential wheels. Also, a separate gene is responsible for what potential wheels grow in a typewriter in fact.
When crossing each gene is taken randomly from one of the parents, and with a certain probability can mutate, having received a random value in a given range. Especially in this regard, only the gene that determines which wheels grow and which ones do not. In it, the mutation is that the state of one of the wheels can randomly change (it has grown - it has not grown), or the information about the wheels can move a bit to the right or left.

After watching what happened, I came to the conclusion that it was a bit boring. Natural selection here is pretty, sorry for the pun, artificial.
And then the memory was obligingly pulled Richard Dawkins ’s book “The Blind Watchmaker” from wide trousers of its depths, or rather, a video illustrating the experience of recreating natural selection for a watch population (the ones that show time).
In short, the way in which natural selection is modeled can be described as follows: there is a population of organisms, and after each certain period of time, three of them are randomly selected. Of these three, the two fittest kill the third and produce a descendant, after which the new troika returns to the population.
')
Of course, I instantly felt the physical need to implement just such an algorithm.

What came of it

So, in an arbitrary way, we create a population of machines without wheels, launch into our world and stock up on popcorn.
Let the primary proto-machines be completely without wheels.


They begin their life journey and at some point freeze, being unable to move further along the track. For the first machines and their near descendants this will happen very quickly. For all frozen machines, we know their "fitness" for sure and periodically make "natural selection" in the manner described above.

How often we carry out the selection has a strong influence. The more machines available for random sampling, the more honest we get, but the slower the evolution in general moves. By the method of scientific poking, I chose the border in 1/6 of the population. If the number of machines that have completed their life course is even less than this value, selection does not occur.

So, some results. In the screenshots, the upper graph shows the absolute distance record and the average value for the population. And the bottom - the number of cars with different number of wheels.



On the graph of the number of wheels, as a rule, one can observe rapid transitions between “eras”. Wheelless cars at some point are replaced by one-wheeled. Those, in turn, displace two-wheeled. But, since three or more wheels are not necessarily more effective than two, further development is not so predictable.


So, for example, in this screenshot you can see how at some point the number of three-wheeled machines began to grow rapidly and, it would seem, they are about to force out two-wheeled ones. In fact, the third wheel helped overcome one very treacherous slide, but rather soon a two-wheeled machine appeared capable of that. So in the future you can observe something similar to the competition of two types, adapted differently, but about equally good.

What else can be corrected / added (in order of increasing complexity)

• To make more parameters changeable through the program interface. Many interesting things are now hardcoded.
• Limit the number of descendants of one individual. Now the machine, which has left the farthest and brightest offspring, is until its record is broken. It is necessary to complicate her life.
• Add more genetic information. More genes! More!
• Make smarter gene crossing mechanism. For example, as in the above-mentioned JavaScript simulator, the first k genes are from the father, and the next nk are from the mother.
• It will also be interesting to try to determine the critical distance between the genomes so that individuals whose genomes are very different lose the ability to interbreed with each other. This will allow parallel evolution of several separate species.
• Introduce the "behavior" of the machines, dictated by the same genes. For example, reduce speed on a steep ledge and so on.

Where to take it all?

For those interested, I post the compiled version and source code (along with the solution for Visual Studio 2012)
4Shared:
Download and run (Win32) 1032 KB
Download and run (Linux) 1052 KB

https://github.com/shtras/BlindAM.git
Old source 1868 KB
Old Linux source 1362 KB

Dropbox:
Download and run (Win32) 1032 KB

The release assembly in me pulls populations of 300 or more individuals. At first it slows down until they all fall to the ground, and then everything goes smoothly.
The camera moves with the right mouse button, the wheel is responsible for the zoom.
Spacebar enables / disables pause. The simulation starts on a pause.
Using the 'a' and 'd' buttons you can respectively increase and decrease the speed of the simulation. It is useful at first before the appearance of the first interesting individuals.

Used technologies:
C ++, Box2D, OpenGL, SDL

Update1: In the res folder there is a file settings.txt. It is possible to customize the size of the game window.
Update2: Added a version for Linux. Fixed a bug when, when restarting without exiting the application, the seed was not reset.
Update3: Made a lot of settings in the menu. Changed the appearance of the track. Improved rendering.