Jump to ContentJump to Main Navigation
Swarm IntelligenceFrom Natural to Artificial Systems$
Users without a subscription are not able to see the full content.

Eric Bonabeau, Marco Dorigo, and Guy Theraulaz

Print publication date: 1999

Print ISBN-13: 9780195131581

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780195131581.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 24 June 2021

Ant Foraging Behavior, Combinatorial Optimization, and Routing in Communications Networks

Ant Foraging Behavior, Combinatorial Optimization, and Routing in Communications Networks

Chapter:
(p.25) Chapter 2 Ant Foraging Behavior, Combinatorial Optimization, and Routing in Communications Networks
Source:
Swarm Intelligence
Author(s):

Eric Bonabeau

Marco Dorigo

Guy Theraulaz

Publisher:
Oxford University Press
DOI:10.1093/oso/9780195131581.003.0006

This chapter is dedicated to the description of the collective foraging behavior of ants and to the discussion of several computational models inspired by that behavior—ant-based algorithms or ant colony optimization (AGO) algorithms. In the first part of the chapter, several examples of cooperative foraging in ants are described and modeled. In particular, in some species a colony self-organizes to find and exploit the food source that is closest to the nest. A set of conveniently defined artificial ants, the behavior of which is designed after that of their real counterparts, can be used to solve combinatorial optimization problems. A detailed introduction to ant-based algorithms is given by using the traveling salesman problem (TSP) as an application problem. Ant-based algorithms have been applied to other combinatorial optimization problems such as the quadratic assignment problem, graph coloring, job-shop scheduling, sequential ordering, and vehicle routing. Results obtained with ant-based algorithms are often as good as those obtained with other general-purpose heuristics. Application to the quadratic assignment problem is described in detail. Coupling ant-based algorithms with local optimizers obtains, in some cases, world-class results. Parallels are drawn between ant-based optimization algorithms and other nature-inspired optimization techniques, such as neural nets and evolutionary computation. All the combinatorial problems mentioned above are static, that is, their characteristics do not change over time. In the last part of the chapter, the application of ant-based algorithms to a class of stochastic time-varying problems is investigated: routing in telecommunications networks. Given the adaptive capabilities built into the ant-based algorithms, they may be more competitive in stochastic time-varying domains, in which solutions must be adapted online to changing conditions, than in static problems. The performance of AntNet, an ant-based algorithm designed to adaptively build routing tables in packet-switching communications networks, is the best of a number of state-of-the-art algorithms compared on an extensive set of experimental conditions. Many ant species have trail-laying trail-following behavior when foraging: individual ants deposit a chemical substance called pheromone as they move from a food source to their nest, and foragers follow such pheromone trails.

Keywords:   ant-based routing algorithms, candidate lists, diversification, elitist ants, foraging model, generating vector, heuristic desirability, intensification, learned desirability, mass recruitment

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .