TY - JOUR

T1 - Theoretical analysis of two ACO approaches for the traveling salesman problem

A1 - Kötzing,Timo

A1 - Neumann,Frank

A1 - Röglin,Heiko

A1 - Witt,Carsten

AU - Kötzing,Timo

AU - Neumann,Frank

AU - Röglin,Heiko

AU - Witt,Carsten

PB - Springer New York LLC

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Run time analysis

KW - Ant colony optimization

KW - Traveling salesperson problem

KW - Approximation

U2 - 10.1007/s11721-011-0059-7

DO - 10.1007/s11721-011-0059-7

JO - Swarm Intelligence

JF - Swarm Intelligence

SN - 1935-3812

IS - 1

VL - 6

SP - 1

EP - 21

ER -