Jeroens blog

To practice some AI methods I’ve been reading about, I created a genetic algorithm (GA) implementation to tackle the travelling salesman problem (TSP). I decided to do this in C#, to practice myself in some more advanced aspects of the language, and mess some more around with the new stuff of .Net 4.0, and with WPF as interface to get a better grip on the basics of WPF and XAML.

I started with creating a general data structure for any GA algorithm (Classes Population and Individual, interface IIndividual and some others), and then added handling for the TSP problem by creating a Route class. This class holds the crossover, mutation and random initialization methods for routes. Each instance of Route, which derives from Individual and implements IIndividual, contains it’s own genotype, which is a List<Int64>. This list contains the numbers of the ‘cities’ the ‘salesman’ travels along. In the code behind my main window, I then create an instance of a Population<Route>, and do a calculation of the distances between all points, which is then stored in a static field of Route.

I’m going to put the complete project on SourceForge when it’s a little more finished. Although the algorithm is working it can still be optimized a lot (especially the genetic operations). Also, the interface is far from ready, and I’d like to do another simple implementation with the general GA structure to tackle some other problem.

In any case, here are some nice sceenshots

The dots represent cities.

The shortest route after several generations. The gray line represents an attempted, but failed, mutation or combination.

After a while the shortest route, or at least one that's very close, is found.

.

1. FeebleMindedNessInc says:

   January 3, 2010 at 2:39 pm

   quite epical… next step: skynet