Travelling Salesman Problem

I have been extremely busy over the last few weeks with various University projects, so the genetic algorithm work has moved to the bottom of the stack. The ideas and problems are still quite fresh in my mind, so without going straight into programming the physics based evolving creatures, I'm going to have a look at something else quite closely related. It is linked in to both evolution and optimization. There is a very old mathematical problem, known as the travelling salesman problem (TSP). The TSP involves finding the shortest route between a number of cities, visiting each city only once.

Finding fast solutions to the problem is vital for applications such as route finding on maps. Anyway, I recently read an interesting paper one approach to solving the TSP ( Ant colonies for the traveling salesman problem ). The paper shows that using ant agents, which lay virtual pheremones, a shortest path can be found. Ants prefer to follow paths with more pheremones on them - this means that shorter paths will build up more pheremones because more ants will travel along them.

When I get back to my computer I will have a look at creating a similar solution to the problem in flash, and see the kinds of results that can be produced.

It might also be interesting to look at the effects of changing the properties of ants on how well the system optimizes itself.

I'll get back to you with any results!