Abstract
This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents called ants cooperate to find good solutions to TSPs. Ants cooperate using an indirect form of communication mediated by a pheromone they deposit on the edges of the TSP graph while building solutions. We study the ACS by running experiments to understand its operation. The results show that the ACS outperforms other nature-inspired algorithms such as simulated annealing and evolutionary computation, and we conclude comparing ACS-3-opt, a version of the ACS augmented with a local search procedure, to some of the best performing algorithms for symmetric and asymmetric TSPs.
Keywords
Travelling salesman problemSimulated annealingAnt colony optimization algorithmsComputer scienceMathematical optimizationAnt colonyExtremal optimizationComputationEvolutionary computationGraph2-optCombinatorial optimizationSet (abstract data type)MetaheuristicArtificial intelligenceTheoretical computer scienceMathematicsAlgorithm
Affiliated Institutions
Related Publications
A modified particle swarm optimizer
Evolutionary computation techniques, genetic algorithms, evolutionary strategies and genetic programming are motivated by the evolution of nature. A population of individuals, w...
Handbook of Genetic Algorithms
This book sets out to explain what genetic algorithms are and how they can be used to solve real-world problems. The first objective is tackled by the editor, Lawrence Davis. Th...
Performance evaluation of genetic algorithms for flowshop scheduling problems
The aim of this paper is to evaluate the performance of genetic algorithms for the flowshop scheduling problem with an objective of minimizing the makespan. First we examine var...
A new optimizer using particle swarm theory
The optimization of nonlinear functions using particle swarm methodology is described. Implementations of two paradigms are discussed and compared, including a recently develope...
Genetic Programming: On the Programming of Computers by Means of Natural Selection
Background on genetic algorithms, LISP, and genetic programming hierarchical problem-solving introduction to automatically-defined functions - the two-boxes problem problems tha...
Publication Info
- Year
- 1997
- Type
- article
- Volume
- 1
- Issue
- 1
- Pages
- 53-66
- Citations
- 7855
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
7855
OpenAlex
Cite This
Marco Dorigo,
Luca Maria Gambardella
(1997).
Ant colony system: a cooperative learning approach to the traveling salesman problem.
IEEE Transactions on Evolutionary Computation
, 1
(1)
, 53-66.
https://doi.org/10.1109/4235.585892
Identifiers
- DOI
- 10.1109/4235.585892