Please use this identifier to cite or link to this item: https://hdl.handle.net/2440/70586
Citations
Scopus Web of Science® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKotzing, T.-
dc.contributor.authorNeumann, F.-
dc.contributor.authorRoglin, H.-
dc.contributor.authorWitt, C.-
dc.date.issued2012-
dc.identifier.citationSwarm Intelligence, 2012; 6(1):1-21-
dc.identifier.issn1935-3812-
dc.identifier.issn1935-3820-
dc.identifier.urihttp://hdl.handle.net/2440/70586-
dc.description.abstractBioinspired 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.-
dc.description.statementofresponsibilityTimo Kötzing, Frank Neumann, Heiko Röglin, Carsten Witt-
dc.language.isoen-
dc.publisherSpringer New York LLC-
dc.rights© Springer Science + Business Media, LLC 2011-
dc.source.urihttp://dx.doi.org/10.1007/s11721-011-0059-7-
dc.subjectAnt colony optimization-
dc.subjectTraveling salesperson problem-
dc.subjectRun time analysis-
dc.subjectApproximation-
dc.titleTheoretical analysis of two ACO approaches for the traveling salesman problem-
dc.typeJournal article-
dc.identifier.doi10.1007/s11721-011-0059-7-
pubs.publication-statusPublished-
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]-
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.