Ant Colony System (Heuristic Search)?

[Nathan Leniz]

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).[19] 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.

[Nathan Leniz]

So I started to really think about the problem and how to code it. The first thing I realized when I was making a map to test it with is that it'd be a huge pain in the but to enter each point and the distances to other points manually. So I made this little distance calculator that figures out the distance between two points on an X Y coordinate system.

Anyway, here is what I made up to calculate the distances between coordinates. It creates a temporary internal point to form a right triangle on the X Y grid, gets the distances of the edges, then used the Pythagorean theorem to figure out the actual distance. At least I think it does, it's worked so far with everything I've thrown at it. I apologize for horrid style or comments, I'm rusty and it makes sense to me.

// A much more simple distance calculator than the first one
public class ACDistance
{
	private static ACDistance ref;
	
	private ACDistance(){}
	
	public static ACDistance getACDistance()
	{
		if (ref == null)
		{
			ref = new ACDistance();
			return ref;
		}
		else
		{
			return ref;
		}
	}
	
	/** Returns the edgeLength of an edge connection two vertices
	 * 
	 * @param ACVertice alpha
	 * @param ACVertice bravo
	 * @return the edge length between alpha and bravo
	 */
	public double getEdgeLength(ACVertice alpha, ACVertice bravo)
	{
		return calculateDistance(alpha, bravo);
		
	}
	
	private double calculateDistance(ACVertice start, ACVertice end)
	{
		double alphaX = start.getXCoordinate();
		double alphaY = start.getYCoordinate();
		double bravoX = end.getXCoordinate();
		double bravoY = end.getYCoordinate();
		
		return Math.sqrt(Math.pow(alphaX - bravoX, 2d) + Math.pow(alphaY - bravoY, 2d));
	}
}

Now to move on to the ant colony. Any ideas? Also, anyone else happen to have worked on or be working on some nifty algorithms? This kind of stuff is pretty interesting, but unfortunately a lot of my Army buddies aren't really all that into it.