Wednesday, 10 November 2010

Genetic Algorithms (GA)

This semester I am expanding knowledge in terms of Artificial Intelligence and one of the concepts that most captivated me was the resolution of problems using genetic algorithms. These are based on coding the problem in chromosomes and genes into packages. After applying a series of functions, we need to mutate the population to reach our goal. and find the best solution. The definition from wikipedia is: "The genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover".
Basically the algorithm works like this:

There are several examples on the net which uses GA to solve common problems such as these:
One of the examples that best shows the use of GA is the solution from Roger Alsing where the algorithm is trying to copy an image generating polygons. These polygons are created in a population of chromosomes and they try to evolve to fit the source image. I've been playing with it and it's great!. You can download the source code and the binaries from here.

Here you can see the results of playing with the application:

Genetic Vectorizer Example by Roger Alsing:

Using my image (40h of running time):

using Einstein image (20h of running time):
Video showing the start of the algorithm:

In the video you can see the different steps the algorithm is doing by creating a population of chromosomes as polygons and trying to fit them by shape and by colour from the source image. The result of the application is the image shown  above.

Sodorace game:
Sodarace is the on-line Olympics pitting human creativity against machine learning in a competition to design robots that race over 2D terrains using the Sodaconstructor virtual construction kit.

Enjoy the learning!.

Related articles: