Genetic Algorithms: Introduction - Part 1
This series will show you how to create genetic algorithms. Genetic algorithms allow A.I. to become better at a task/challenge by evolution. We start off by generating around 10 random organisms. They are usually very bad at performing the task. The best one will then effectively 'asexually reproduce' with mutations/variations to create the next generation of 10 organisms. After many generations, they evolve to be much better at the task.
I have designed a genetic algorithm where organisms learn to fly. This has involved creating some very crude and unrealistic physics. Every organism is what I call a bird, shown on the left. It is comprised of a central dot (in green), blue 'elbows' and red 'hands'. The organisms vary in terms of how they move as opposed to how they look. The organisms are mirrored so that each wing moves in exactly the same way.
Their movement is controlled by angles; there are two angles: one between the central dot, the elbow and the hand, and one between the elbow, central dot and an imaginary north-south line. Variations in these two angles over time can create a flapping motion.
Their aim is to reach as high as possible in 300 frames (5 seconds at 60 fps) . There is a small amount of gravity pulling them constantly. The amount of lift they generate is calculated by multiplying the amount that the hands move downwards by the distance the hands are from the central body. This can also push the bird downwards when the hands move up. The body will also move upwards if the hands move below the window, effectively making the bottom of the screen the ground. That is all of the physics.
Each organism has its own DNA. This instructs how to change the angles. For both angles, the organism has a time period, which dictates how many frames until the cycle of flapping repeats. The body-elbow angle doesn't necessarily have the same time period as the elbow-hand angle. The DNA stores a number of angles that the bird will transition to throughout the time period.
For example, a bird with DNA which included [164, 32, 64, 112, 70, 171, 164] would have an angle over time graph of:
The DNA is an array of integers, composed in the following way. The first integer is the number of angles points there are; the above example has six since the seventh is just there to finish off the time period so it starts the next period in the correct position (it will always be the same as the starting angle). The next integer is the time period in frames. The remaining digits are all angle points. A whole new array is created for the second angle and both arrays are stored in one over-arching array which is the complete DNA. The above example could have the DNA: [[6, 229, 164, 32, 64, 112, 70, 171, 164], [3, 95, 18, 76, 140, 18]].
This concludes the introduction. The next part will involve programming the physics. Click here for part 2.