Angel \”Java\” Lopez on Blog

January 27, 2009

AjGa: a genetic algorithm library

Filed under: Artificial Intelligence, C Sharp, Software Development — ajlopez @ 7:15 am

I was coding a genetic algorithm library, using C#. The code is in my AjCodeKatas Google Code project, at:

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjGa

The main project is AjGa (with AjGa.Tests for testing):

The main interfaces are:

I use generics, with two generic types: G, as the gene implementation type, and V, as the value type (e.g. int, double), that it will be used to catalog the genomes.

IPopulation is a colletion of genomes.

IGenome  is a collection of genes, that is evaluated to value.

IEvaluator is in charge of evaluate a genome.

The implementation of IEvolution runs generations over a population, employing mutator, crossover operators, to change the population composition after each run.

There are operator interfaces, to generate one genome, mutate an existing one, or apply a crossover over two genomes.

To test the ideas, I implemented a project with gene, genome, and operators, to attack the classical Travelling Salesman Problem:

In this example, an evaluator has a list of positions of cities to visit:

 

public class Evaluator : IEvaluator<int, int> { private List<Position> positions; public Evaluator(List<Position> positions) { this.positions = positions; }

The gene type is int, and tha value of each genome is expressed as a int. The genome keeps a list of integers, representing the ordinal number of the cities to visit:

 

using AjGa; public class Genome : BaseGenome<int, int> { public Genome(int size) { for (int k = 0; k < size; k++) { AddGene(k); } }

That is, each gene is an int, and a genome with 2, 0, 1 represents: visit the third city, then the first one, and finish the trip in the second city.

You can run the WinForm project, to test the library:

The above run has a random distribution of cities. The cities can be distributed in a grid:

This way, you can test the efficient of the algorithm to reach the optimum solution.

If you want to implement a new GA project, you should:

– Define the gene type

– Define the value type

– Some operators (creators, mutators, crossovers)

Tests are green:

Code coverage in fine:

I spent 4 hours in the first version, 3 hours exploring TSP, and around 8 hours preparing and tuning the TSP WinForm application.

As usual, I enjoyed write this software!

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

3 Comments »

  1. […] AjGa- a genetic algorithm library […]

    Pingback by Artificial Intelligence links and resources « Angel “Java” Lopez on Blog — February 11, 2009 @ 10:19 am

  2. privet 🙂

    Comment by Andreuskas — December 22, 2011 @ 10:09 am

  3. My brother recommended I might like this blog. He was entirely right.
    This post truly made my day. You can not imagine just how much time I had spent for this information!
    Thanks!

    Comment by Maxwell — June 16, 2013 @ 1:46 am


RSS feed for comments on this post. TrackBack URI

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: