Channels ▼
RSS

Parallel

Ant Colony Algorithms

Source Code Accompanies This Article. Download It Now.


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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video