English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem

Kötzing, T., Neumann, F., Röglin, H., & Witt, C. (2010). Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem. In M. Dorigo, M. Birattari, G. A. Di Caro, R. Doursat, A. P. Engelbrecht, D. Floreano, et al. (Eds.), Swarm Intelligence (pp. 324-335). Berlin: Springer. doi:10.1007/978-3-642-15461-4_28.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1709-0 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-2880-7
Genre: Conference Paper
Latex : Theoretical Properties of Two {ACO} Approaches for the Traveling Salesman Problem

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kötzing, Timo1, Author           
Neumann, Frank1, Author           
Röglin, Heiko2, Author
Witt, Carsten2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: Ant colony optimization (ACO) has been widely used for different combinatorial optimization problems. In this paper, we investigate ACO algorithms with respect to their runtime behavior for 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. Our rigorous runtime analyses for two ACO algorithms, based on these two construction procedures, show that they achieve a 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.

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 536698
DOI: 10.1007/978-3-642-15461-4_28
URI: http://dx.doi.org/10.1007/978-3-642-15461-4_28
Other: Local-ID: C1256428004B93B8-0A9161A58B6F3EF9C12577FA003BF2A4-Koe-Neu-Roe-Wit:c:10:ACOTSP
 Degree: -

Event

show
hide
Title: 7th International Conference on Swarm Intelligence
Place of Event: Brussels, Belgium
Start-/End Date: 2010-09-08 - 2010-09-10

Legal Case

show

Project information

show

Source 1

show
hide
Title: Swarm Intelligence
  Abbreviation : ANTS 2010
  Subtitle : 7th International Conference, ANTS 2010
Source Genre: Proceedings
 Creator(s):
Dorigo, Marco1, Editor
Birattari, Mauro1, Editor
Di Caro, Gianni A.1, Editor
Doursat, René1, Editor
Engelbrecht, Andries P.1, Editor
Floreano, Dario1, Editor
Gambardella, Luca Maria1, Editor
Groß, Roderich1, Editor
Sahin, Erol1, Editor
Sayama, Hiroki1, Editor
Stützle, Thomas1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 324 - 335 Identifier: ISBN: 978-3-642-15460-7

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6234 Sequence Number: - Start / End Page: - Identifier: -