Ant colony system: a cooperative learning approach to the traveling salesman problem

1997/04/01 by Marco Dorigo, Luca Maria Gambardella · 22 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Metaheuristic Optimization Algorithms Research #Insect and Arachnid Ecology and Behavior #Evolutionary Algorithms and Applications

paper · doi:10.1109/4235.585892

openalex publication_date 1997/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

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.

Citations

• Self-organized shortcuts in the Argentine ant
• La reconstruction du nid et les coordinations interindividuelles chezBellicositermes natalensis etCubitermes sp. la théorie de la stigmergie: Essai d'interprétation du comportement des termites constructeurs
• An Analysis of Several Heuristics for the Traveling Salesman Problem

Cited by

• Energy Efficient Ant Colony Algorithms for Data Aggregation in Wireless Sensor Networks
• Evolutionary Computation in Astronomy and Astrophysics: A Review
• Evolutionary Algorithms: Concepts, Designs, and Applications in Bioinformatics: Evolutionary Algorithms for Bioinformatics
• Internet of Things for Residential Areas: Toward Personalized Energy\n Management Using Big Data
• Global optimization-based dimer method for finding saddle points
• Apply Local Clustering Method to Improve the Running Speed of Ant Colony Optimization
• Contemporary Approaches to Artificial General Intelligence
• An ant colony optimization algorithm for partitioning graphs with supply and demand
• Image Registration Techniques: A Survey
• The SP Theory of Intelligence: An Overview
• A Parameter Control Strategy for Parallel Island‐Based Metaheuristics
• Traveling baseball players’ problem in Korea
• MuEvo: LLM-Driven Evolution of Multi-Heuristic Ensemble
• Solving optimization problems by the public goods game
• Toward Smart Power Grids: Communication Network Design for Power Grids\n Synchronization
• A 2-DIMENSIONAL CELLULAR AUTOMATON FOR AGENTS MOVING FROM ORIGINS TO DESTINATIONS
• Multi-Agent Algorithms for Collective Behavior: A structural and application-focused atlas
• Continuous relaxations for the traveling salesman problem
• Sensitive Ants in Solving the Generalized Vehicle Routing Problem
• Parallel ACO with a Ring Neighborhood for Dynamic TSP
• When the Path Is Never Shortest: A Reality Check on Shortest Path Biocomputation
• Open Loop Layout Optimization: Feasible Path Planning and Exact Door-to-Door Distance Calculation
• Luca Maria Gambardella [wikipedia]