Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Theoretical analysis of two ACO approaches for the traveling salesman problem
Author: Kotzing, T.
Neumann, F.
Roglin, H.
Witt, C.
Citation: Swarm Intelligence, 2012; 6(1):1-21
Publisher: Springer New York LLC
Issue Date: 2012
ISSN: 1935-3812
Statement of
Timo Kötzing, Frank Neumann, Heiko Röglin, Carsten Witt
Abstract: Bioinspired algorithms, such as evolutionary algorithms and ant colony optimization, are widely used for different combinatorial optimization problems. These algorithms rely heavily on the use of randomness and are hard to understand from a theoretical point of view. This paper contributes to the theoretical analysis of ant colony optimization and studies this type of algorithm on one of the most prominent combinatorial optimization problems, namely the traveling salesperson problem (TSP). We present a new construction graph and show that it has a stronger local property than one commonly used for constructing solutions of the TSP. The rigorous runtime analysis for two ant colony optimization algorithms, based on these two construction procedures, shows that they lead to good approximation in expected polynomial time on random instances. Furthermore, we point out in which situations our algorithms get trapped in local optima and show where the use of the right amount of heuristic information is provably beneficial. © 2011 Springer Science + Business Media, LLC.
Keywords: Ant colony optimization
Traveling salesperson problem
Run time analysis
Rights: © Springer Science + Business Media, LLC 2011
DOI: 10.1007/s11721-011-0059-7
Published version:
Appears in Collections:Aurora harvest 5
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.