An Ant Colony Optimisation Algorithm

I have been playing with an ant colony algorithm to solve a traveling salesman problem, and have always had inconsistent results (once ants decide on a route the route is strengthened and they are less likely to explore other options - they hit a local minima and reinforce it)

A few weeks back I tried to inject a little entropy back into a colony that was getting lazy, by using a "black sheep" ant that bucks the trend and randomly picks one these algorithms instead:

1. Random - ignores distances between towns, and just randomly chooses a town
   
2. Closest Town - chooses the closest town regardless of the prefered route
   
3. Least Followed - chooses the town that other ants are avoiding

This simple change drastically improved the algorithm to such an extent that I thought it might actually be able to compete with a brute force algorithm.

So, the tests.... I ran 2 of them.

In both cases there was a 10 minute cut off for the colony and 10 colonies were run against each brute force solution. Also, the colony had to get to the optimum solution - not a "close enough" answer.

To provide some degree of confidence that it was working, the best solution was rendered in 3 space by visual python to provide a quick, visual sanity check. (Also, its fun to watch the ants trying different routes)

The first test: 10 towns, 3,628,800 possible routes ,146 different solutions. Brute force was solved in an average of 2 minutes 8 seconds. The colony did it in 13 seconds average, with 81% of tests solved in under a second.

The second test: 11 towns, 39,916,800 possible routes for each solutions, 16 different solutions
Brute force was solved in an average of 23 minutes 55 seconds. The colony did it in 18 seconds average, with 83% of tests solved in under a second.

I tried with 12 towns, but I wasn't patient enough to wait 3 hours for the brute force algorithm to finish.

Anyway, its clear that the ant colony beats the brute force algorithm hands down!

Now what's the problem that this solution solves.....

(Code available on request)