Simple AI – Genetic Algorithm

AI is one of those buzzwords we use to appear smart. But really, do any of us know what a real AI is?

AI or Artificial Intelligence is the idea of a computer learning, and functioning by itself. That is with no or nearly no human interaction. A perfect AI or a general AI would be as good as, or better than a human in nearly any field.

But that future is a long way off. The computers we have today are as dumb as you and I. However, we can tell them to do some interesting thing, such as mimicking the learning of simple things.

One of these easier to implement methods is the Genetic Algorithm.

What is The Genetic Algorithm?

The Genetic Algorithm is a problem-solving method based upon the ideas of natural selection and evolution.

In essence, we have to execute the flowing steps:

  • Make a population of individual programs.
  • Give each program a random set of instructions.
  • Take the programs which do best and combine the traits of two or more into a new population of programs.
  • Change each program in the new population slightly as to mimic evolution.
  • Take the best of that generation and repeat until an ideal program made.

But how do we know which are the best programs of a generation?

We give each program a ‘fitness’ value which is based on how well it performs a given task.

In the case of a simple maze, it might just be related to the distance a program is from the end.

Seeing This Algorithm In Action

Now being honest, most of my inspiration for this post came from CodeBullet’s Youtube channel that I would highly recommend you watch.

To show this algorithm in action, we are going to make a small maze, that will look sort of like this:

Sample maze. Here the population will start at the bottom.

Here I have randomly generated some circles to act as barriers. The goal is for a program go from the bottom of the screen and try to reach the green dot.

The programs in this test will just be simple black dots. The first generation of which will just fire off in random directions; dying when they hit a barrier or the edge.

Randomly moving generation of dots

These dots move by applying a set of accelerations from a list of instructions; which will be random during the first generation.

Now when everyone in this generation has ‘died’ or has hit a wall, the evolution will occur.

The best faring dots are taken and cloned into a new generation. This generation is then slightly mutated to allow for new and different outcomes.

The best dot of the last generation is highlighted in red to make it easier to notice.

This is repeated generation after generation until a dot has reached the goal.

12 generations in we can see how the population has improved

Once a dot has reached the goal, its fitness rating jumps dramatically and so that dot produces many children.

By generation 84 the majority of the population has reached the end

Now that the dots have reached the goal, the only way that a program can improve is to reach the goal faster.

As the program goes on we see how the number of movements taken by the program decreases over time.

We can see a gradual improvement generation after generation

Of course, this AI isn’t perfect. As the fitness only takes into account the distance from the end, it is entirely possible that the population will get stuck at a dead end.

There we have it, a simple Genetic Algorithm in action. To see download the code, please check my GitHub account here.

If you want to see a full generation from start to finish; you should watch the video below:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.