DocumentCode :
1548706
Title :
Ant colony system: a cooperative learning approach to the traveling salesman problem
Author :
Dorigo, Marco ; Gambardella, Luca Maria
Author_Institution :
IRIDIA, Vrije Univ., Brussels, Belgium
Volume :
1
Issue :
1
fYear :
1997
fDate :
4/1/1997 12:00:00 AM
Firstpage :
53
Lastpage :
66
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 :
cooperative systems; distributed algorithms; learning (artificial intelligence); search problems; travelling salesman problems; ACS-3-opt; ant colony system; cooperating agents; cooperative learning approach; distributed algorithm; evolutionary computation; local search procedure; nature-inspired algorithms; pheromone; simulated annealing; traveling salesman problem; Ant colony optimization; Computational modeling; Distributed algorithms; Evolutionary computation; Feedback; Global communication; Helium; Legged locomotion; Simulated annealing; Traveling salesman problems;
fLanguage :
English
Journal_Title :
Evolutionary Computation, IEEE Transactions on
Publisher :
ieee
ISSN :
1089-778X
Type :
jour
DOI :
10.1109/4235.585892
Filename :
585892
Link To Document :
بازگشت