A Brief Look At Genetic Algorithms

This post is sort of a continuation of my work on natural selection and evolution as a tool for image compression. Genetic algorithms are an extremely interesting area of study, and over the next few weeks I'll be exploring the kinds of things that can be achieved in the field using actionscript and the flash player. Genetic algorithms are being used to evolve some of the most advanced robots in the world, as well as being used in route finding and compression applications.

So what is a genetic algorithm? In a nutshell it is a computational technique through which solutions to optimization problems can be found. It is an evolutionary method that can be compared to the way evolution and natural selection work in the biological world. A genetic algorithm requires two things to work, a genetic representation of the thing you are trying to evolve, and what is known as a fitness function to compare your genes against.

Lets take the example found in the video below (click the image and it should start up):

Each creature is represented by a set of genetic data. This determines everything about that creature, how big it is, where it has joints, any muscles it might have and how it decides to use them and so on.

By comparing the phenotype (the physical outcome of the genes) to a fitness function, we are able to determine how suited a certain version of the creature is to performing a certain task. Examples of fitness functions include the ability to swim fast, the ability to jump, or the ability to win in a game of football.

Currently there is no evolution going on at all, so we need to introduce random mutations in the genetic data. You should be able to see that a random mutation might cause a creature to be more effective at carrying out the fitness function, if it is we can stick to the new set of genes, otherwise lets go back to the original.

In my program to evolve an image from a few polygons the fitness function was the similarity to the comparison image.

So now that we've discussed computational genetics briefly, how am I going to work this all into a flash project. The first issue is creating a physical world in which my creatures can evolve. Clearly I don't have the computational power to test millions of creatures in 3D with a 3D physics engine, so that isn't an option. I have decided to stick with a simple 2D Verlet Integration based particle engine with constraints and muscles (no line-line or polygon-polygon collisions) and see what happens.

I am quite excited about seeing where this one is going to go, so stay tuned!