I was tooling around on Wikipedia to pass some time and I came across this
page on the Travelling Salesman Problem. I find the problem fascinating as well as all the different solutions (although my math finds them quite the opposite), but while reading I noticed one possible search method called Ant Colony Optimization or Ant Colony System.
Just wondering if anyone else has heard of it or has experience with it, and could talk about it a little bit. I think it'd be kind of cool to build up a little app that actually showed the ants going along the various routes with some graphics showing the amount of pheromone building up on each path.
I found an applet that does it in a way, but never seems to end. There also seems to be a good number of Google returns when searching for it to a number of academic sources.
Quoted from Wikipedia --
Artificial intelligence researcher Marco Dorigo described in 1997 a method of heuristically generating "good solutions" to the TSP using a simulation of an ant colony called ACS (Ant Colony System). It uses some of the same ideas used by real ants to find short paths between food sources and their nest, an emergent behaviour resulting from each ant's preference to follow trail pheromones deposited by other ants.
ACS sends out a large number of virtual ant agents to explore many possible routes on the map. Each ant probabilistically chooses the next city to visit based on a heuristic combining the distance to the city and the amount of virtual pheromone deposited on the edge to the city. The ants explore, depositing pheromone on each edge that they cross, until they have all completed a tour. At this point the ant which completed the shortest tour deposits virtual pheromone along its complete tour route (global trail updating). The amount of pheromone deposited is inversely proportional to the tour length; the shorter the tour, the more it deposits.
One possible implementation I had in mind was finding the average distance between all cities and putting this distance into each ant plus a % as the ant's "stamina" so to speak. Each city the ant visits would reset the stamina, but an ant that spends too much time before reaching a city would die, allowing another ant/thread to start. I was thinking that might speed it up a little bit. However, I also wonder if there could mathematically be a leg in the optimal route that is
longer than the average of all the distances, and this would cause it to fail.
So, anyone have any thoughts or ever tried to/successfully implemented this? I'd like to see what the JavaRanch community has to say.