Jeroens blog

Over the last week, I’ve been rewriting my Genetic Algorithm (GA) implementation of the Travelling Salesman Problem (TSP). I’ve rewritten pretty much everything, but the two most notable changes are:

1. I split the code into 2 projects: one holding the general GA code, which is now called GALib, and one holding the code specific to the TSP, now called Skynet (lol ). This allows for making any other GA implementation using GALib, even in .Net languages different from C#. The underneath diagram should give you a good idea of how the who thing works. The 4 most left classes are of Skynet, all remaining classes and interfaces are of GALib.

2. I rewrote the genotype of the Route individual type, the core of the TSP implementation. Instead of having a list of integers, referring to cities, I now have a list of Connection, each containing 2 instances of Location. I’ve done this to allow smarter crossover, decreasing the chance of not finding a better solution while it’s still in the converged search space significantly. As a result of this change, I also had to rewrite pretty much everything else of the Route class, including random initialization, mutation and fitness assessment. The biggest challenge here was preventing the creation of multiple loops in the crossover algorithm.

The interface of the TSP app (now called Skynet) also has seen quite some work. I figured out quite a lot of WPF stuff by further creating it. Some extra controls and progress indicators still need to be added though, and I also haven’t created the Cancel/Stop functionality.

Although the algorithm is efficient in the way that it takes relatively few generations to find a close to optimal solution, there remain a few mayor performance issues. If I compare the speed of evolution (measured in generations) with similar applications tackling the TSP, there are those performing up to 3 orders of magnitude faster. Although the fastest of those are written in C++ or C, I should be able to significantly speed up my application. Tracking down resource eating parts of code will be one of my next steps in developing this app. Another possible issue is diversity of the population. I have the suspicion that the diversity shrinks pretty fast, resulting into evolution driven only by mutation. I’m not sure of this though, and also have to investigate how I can prevent this from happening.

Here you have a few screenshots of the app in action

1. FeebleMindedNessInc says:

   January 10, 2010 at 5:08 pm

   wow it haz a take over the world function? :O

   not that it is new, I mean, Apple has an app for taking over the world
2. Deleted_screen says:

   January 18, 2010 at 8:47 pm

   Goddamn epic… As I said on Xfire, you > me ^ 1000

   Gotta teach myself how to do this.
3. BN's blog » Blog Archive » GALib available now! says:

   January 19, 2010 at 12:37 am

   [...] going to release the TSP implementation I made with this lib on-line in a similar fashion, after the interface is fully [...]