Channels ▼
RSS

Parallel

Ant Colony Algorithms

Source Code Accompanies This Article. Download It Now.


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.


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