Overview

After reading an interesting tutorial by Chris Stones on Artificial Intelligence, I decided to follow this up with a different problem-solving technique, known as the Genetic Algorithm. Genetic Algorithms, or GAs, have been around since the 1970’s, and provide a method of solving vast problems quickly.

The solution to any problem may be found eventually by simply considering every possibility in turn.  Imagine a combination lock with only two numbers each accepting the digits 0 – 9, the possible combinations are:

Although this may work when trying to discover a two digit combination, if this is increased to a forty digit combination the time needed to discover the combination is greatly increased.  Genetic Algorithms are just one of a number of tools which aim to discover answers to problems in a much quicker time. 

Before we demonstrate how a GA works it is necessary to define the term “Problem Space”: consider the combination example above, instead of representing the possible answers in a list as we have above, consider them in a grid:

This is what is called a problem space, i.e. the solution to the combination problem lies somewhere in this grid.  In order to find the solution we potentially have to look at every position in this grid.  Simply put - Genetic Algorithms just “bounce around” until they find the answer.