Theoretical analysis of two ACO approaches for the traveling salesman problem

Publication: Research - peer-reviewJournal article – Annual report year: 2012

View graph of relations

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
Issue number1
Pages (from-to)1-21
StatePublished - 2012
CitationsWeb of Science® Times Cited: 19


  • Run time analysis, Ant colony optimization, Traveling salesperson problem, Approximation
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 6442341