Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Parallel

Ant Colony Algorithms


Andrew is Fixed Income Research Director for the StatPro Group plc in the United Kingdom and adjunct professor in the School of Business, Queensland University of Technology, Brisbane. He can be contacted at [email protected].


Biologically inspired computing arose around 20 years ago with the development of algorithms that simulate various aspects of natural processes to calculate useful results. For instance, neural networks imitate some aspects of learning in mammalian brains to learn complex patterns; simulated annealing simulates how metals cool into low-energy crystalline states to solve difficult minimization problems; and genetic algorithms use abstractions of mechanisms from evolution (selection, crossover, mutation) to traverse large search spaces. All have found their way into the computing mainstream, and all are regularly used in a wide range of real-world problems.

In this article, I examine a related technique that in many cases is the equal or better of existing optimization algorithms for a wide range of problems. Ant colony optimizers (ACOs) model ensembles of virtual insects that cooperate on various tasks. Remarkably, such ensembles can be used to produce answers to a range of complex problems, even though the simulated insects and the means they use to communicate are extremely simple. For instance, ACOs are currently being used to simulate complex routing problems in telecommunications networks, where the topology of the network can vary over time.

Ant colony algorithms are closely associated with Marco Dorigo, who described the concept in his Ph.D. thesis in 1992.

Ant colony optimization is an example of a swarm algorithm. If you have read Michael Crichton's thriller Prey (HarperCollins, 2002), which luridly describes swarms of semi-intelligent nanobots in competition with humans, you are familiar with some of the ideas behind this relevantly recently developed area. In a swarm algorithm, a large number of agents cooperate to achieve a global aim without requiring any central control point.

Swarm-based systems are highly fault-tolerant because the failure of one component in a swarm does not significantly degrade the overall performance of the system. This makes them particularly suitable for hazardous or remote environments, and the U.S. military and NASA are currently researching their use.


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.