An ACO In Action
To illustrate a simple ACO in action, I present an implementation in C that finds the shortest closed route between 50 cities (also available electronically). This data is from the EILON50 dataset, a standard benchmark for the Traveling Salesman problem. The shortest tour known for this dataset is 427.96. This and other datasets can be found in the TSPLIB archive (http://www.iwr.uni-heidelberg.de/ groups/comopt/software/ TSPLIB95/).
The code has been written to compile with Microsoft Visual C++, but it should be readily portable to other environments. The supplied code has alpha set to 1, beta to 2, and rho to 0.5. The program always converges to within a few percent of the best solution known within 100 or fewer passes over the training set. To achieve this sort of solution in seconds on a desktop PC is an impressive testament to the power of the algorithm.
This implementation of the ACO algorithm is simple by design, and many improvements on the basic idea have been found in the last few years. For instance, some researchers have linked the ACO algorithm with the ability to perform local optimization. A good starting place for interested readers is Marco Dorigo et al.'s book Ant Colony Optimization (MIT Press, 2004).
DDJ
|
Understanding ACO Algorithms
The key to understanding ACO algorithms is that they are a deceptively subtle mix between a greedy, short-term search and an altruistic, evenhanded search. Using either type of search in isolation doesn't work. Only when they are put together do the bad features of each cancel out and the true power of the algorithm emerge.
How does this work? Suppose the attractiveness equation just included a distance term, and ignored the pheromone term. The result will be that the ants immediately go for whichever local route is shortest (a "greedy" search). This is a good strategy for very small networks, but typically fails abysmally when more complex network topologies are being considered because the ants cannot consider the broader implications of looking further afield.
Conversely, suppose the attractiveness of links is just measured by pheromone concentration, and ignores distance to the next city. Typically, the algorithm will stagnate, which means that the ants stop searching for new solutions and become stuck on suboptimal tours. This happens because the amounts of pheromone on some links are so high that the probability of choosing any others is virtually zero, so the links have more pheromone added, and so on. In other words, the algorithm gets stuck in a positive feedback loop and cannot break out to find better solutions.
Fortunately, the exact values of alpha and beta are not too critical. Values for each between 1 and 5 give consistent convergence for this problem. To see what happens when either term is taken out of our search, try setting its exponent to zero in the source code (available at http://www.ddj.com/code/).
—A.C. |
