Theoretical analysis of two ACO approaches for the traveling salesman problem

Timo Kötzing, Frank Neumann, Heiko Röglin, Carsten Witt

    Research output: Contribution to journalJournal articleResearchpeer-review

    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.
    Original languageEnglish
    JournalSwarm Intelligence
    Volume6
    Issue number1
    Pages (from-to)1-21
    ISSN1935-3812
    DOIs
    Publication statusPublished - 2012

    Keywords

    • Run time analysis
    • Ant colony optimization
    • Traveling salesperson problem
    • Approximation

    Fingerprint Dive into the research topics of 'Theoretical analysis of two ACO approaches for the traveling salesman problem'. Together they form a unique fingerprint.

    Cite this