Saturday, March 3, 2018

Genetic Algorithms 1

A genetic algorithm is an algorithm based on biological theory of natural selection.  Genetic algos are meta-heuristics, or "good enough" solutions for optimizing a process.  A program using genetic algorithms starts off with a 'population' of algorithms, with randomly valued characteristics.  The algorithms with the least desired behavior are discarded.  The rest of the algorithms are 'bred' in which two algos combine their behavior, with a chance of random mutation.  This process repeats over and over in which the worst performers are discarded and the best performers carry on their 'genes' to the next generation.

To illustrate this behavior, I coded a very basic genetic algorithm to optimize playing the infamous Flappy Bird game.  In this simulation, each bird has two genes: one gene determines how often the bird jumps when the pipe is in front of the bird, and another gene for how often the bird should jump when the pipe is above or below the bird.  For cosmetic purposes, each initial bird starts off with a random color.  Newly born birds have a mixed color between their parents.

For the first seconds in the video, the initial birds have a wide variety of genes.  Some of the birds instantly dive into the ground or fly off the screen.  Since crashing before the pipes even appear on screen is an unfavorable trait, these birds are not given the chance to reproduce.  Since the population shrinks every time birds crash, a random surviving bird will mate with another bird and produce an offspring with traits similar to its parents.

When the first pipe comes on screen, about two thirds of the birds fail to fly through the gap.  The survivors then instantly reproduce.  You can see the bird genes are evolving because after the tenth pipe, almost no birds collide into the obstacles.  You may also notice that unlike the brightly colored birds at the beginning of the simulation, the current generation of birds are all the same dull yellow color due to an evolutionary bottleneck (the obstacles).

As the simulation goes on, fewer and fewer birds crashed into obstacles.  In the first ten seconds, 114 birds crashed. In the next ten seconds, only 46 more birds were lost.  By 30 seconds, only an additional 15 birds hit a pipe.

Many genetic algorithms rely on neural networks for calculation.  Neural nets involve complex functions that have multiple inputs (the environment) and multiple outputs (how the individual should act).  This Flappy simulator did not use a neural net since there were only two inputs and 1 output.  Because the inputs and outputs were linearly related, their movement could be calculated using linear regression.

The purpose of this simulator is to show a very basic demonstration of what a genetic algorithm can do with just a couple hours of programming.

Here is the source code and executable file:
Source code
Downloadable game

No comments:

Post a Comment