The Traveling Salesman Problem is one of the best known NP complete problems, and genetic algorithms are among the best known approaches for approximating solutions for hard problems that can't be solved completely. Therefore it is a common question how to solve the Traveling Salesman Problem with Genetic Algorithms. However, the solution is not so straightforward, because any encoding of salesman routes in the form of digital genes has to make sure that no illegal routes are being created through the GA's crossover and mutation operators. Often, new and slightly awkward crossover operators are being suggested, that somehow don't break the route.

A while ago I had an idea for an encoding that seemed reasonably elegant to me: instead of encoding the routes directly, encode permutations of the route, and construct the ensuing route by applying the permutation. A long time passed, until about two years ago I finally set out to write a proof of concept program. Said program I rediscovered a few days a ago when I reinstalled my computer and went through my files and archives to create a backup.

Now that work is very much in it's infancy. It seems to work, but I haven't compared it to other approaches, I haven't tweaked the genetic algorithm at all, and so on. It seems unlikely, after so much research that has been poured into the problem, that it is really a new or worthwhile idea. Nevertheless, to make sure that it won't be lost (just in case), I have now created a google code project for it: genetic algorithm for traveling salesman.

It is also almost my first open sourced code, apart from two small Greasemonkey Scripts. I have to say, it is fun to open source: even though I don't expect much interest in that particular code, just to publish it is a good motivation to keep working on it.

I chose Google Code because I thought it would have the best chances for showing up in the google code search there. However, I am a bit disappointed that Google does not seem to have any facility for ranking projects and finding projects by popularity. The only means to discover projects hosted there appears to be the search box. SourceForge.net (the pioneer of public open source repositories) seems to be much better in that respect, although I often found their pages a bit confusing. The latest fad of course is GitHub, perhaps I'll try that for the next project. I'd like to open source my mobile games, if only I'll find the time to polish them enough.