IEEE Transactions on Evolutionary Computation · 1997 · 8K citations · 32 references
ComputingComputer ScienceAlgorithmsDistributed SystemsOptimizationCombinatorial OptimizationDistributed AlgorithmsEvolutionary ComputationHeuristic SearchMetaheuristic OptimizationMulti-agent SystemsAgent-based OptimizationAnt Colony OptimizationBio-inspired Swarm AlgorithmsEvolutionary AlgorithmsLocal SearchMultiagent Evolutionary ComputationSimulated AnnealingTraveling Salesman Problem
The ant colony system uses cooperating agents (ants) to find good solutions to traveling salesman problems. This paper introduces the ant colony system, a distributed algorithm for the traveling salesman problem. Ants build solutions by depositing pheromone on graph edges, and the authors studied the ACS through experiments to understand its operation. Experiments show that the ACS, especially the ACS‑3‑opt variant with local search, outperforms other nature‑inspired algorithms on symmetric and asymmetric TSPs.
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.
32