Ant Tracks
To avoid having to calculate actual probabilities, the next city can be chosen using roulette-wheel selection. For each possible destination city, the value of a is calculated and represented as an interval. These intervals are then placed end to end and a random point picked from this set of intervals. The wider the interval, the more likely that interval is to be hit and the corresponding city chosen as a destination. Conversely, attractiveness measuring near zero means that the city will be visited very infrequently. This is, in fact, what I've done in the code that accompanies the article (available at http://www.ddj.com/code).
The ant now repeats this process for each town, finally arriving back at its original starting point. The tour has been chosen purely in terms of probabilities, with the particular route chosen being driven by the attractiveness of each link.
After the artificial ant has completed its tour, it deposits an amount of pheromone along each link taken that is inversely proportional to the length of the tour. In other words, the shorter the tour, the more pheromone is deposited and the more attractive that particular route will be to other ants on subsequent tours.
Of course, real ants don't backtrack in this way. I update pheromone in this manner to make the algorithm simpler and to allow us to use discrete time intervals in the simulation. In reality, an ant is more likely to deposit pheromone at the same rate no matter which route it takes. (In fact, ants have been observed to deposit higher concentrations of pheromone on routes to especially rich food sources, but this refinement is unnecessary for the current problem.) However, it will follow a short route several times over in the time it takes to follow an alternative long route, so pheromone concentration will rise on the short route, which leads to the same result.
This process is now repeated for each ant in the population. I've set the number of ants equal to the number of cities in the tour, which gives quite acceptable results. Alternatively, the algorithm could be recast in terms of one ant, since ants never communicate directly.
When all ants have made a tour of the cities, a process called "evaporation" occurs. So far, I've only looked at ways in which pheromone concentrations increase. Evaporation decreases pheromone concentrations by decreasing all pheromone deposits at a constant rate p. If the concentration of pheromone at time t is ct, the concentration at time t+1 will be given by:
ct+1 = ct(1-p)
Evaporation means that, over time, a link that is barely used will see its pheromone concentration drop toward zero, thereby making it even less attractive. Links that are heavily used will continue to have pheromone deposited, which will make up for the evaporation loss. This was explained by Marco Dorigo et al. in "Ant algorithms for Discrete Optimization" (http://www.idsia.ch/~luca/ ij_23-alife99.pdf):
Pheromone evaporation allows the ant colony slowly to forget its past history so that it can direct its search toward new directions without being over-constrained by past decisions.
Now the whole process is repeated. The population quickly finds very good solutions that are typically close to the best known. Usually, the best route becomes locked in with high pheromone concentrations, while other routes see their pheromone drop to zero.
