An Implementation of ACO System for Solving NP-Complete Problem; TSP

This paper presents an ant colonies optimization (ACO) system as a distributed computation for the solution of NP-complete problem, which was inspired by the observation of real colonies of ants. The main characteristics of this model are positive feedback, distributed computation, and the use of a constructive greedy heuristic. Positive feedback accounts for rapid discovery of good solutions, distributed computation avoids premature convergence, and the greedy heuristic helps find acceptable solutions in the early stages of the search process. The authors apply the methodology to the travelling salesman problem (TSP) (Lawler et al., 1985) and report simulation results. The paper also discusses parameter selection and the early setups of the model and compares it with tabu search.