Campus Event Calendar

Event Entry

New for: D3

What and Who

Ant Colony Optimization and TSP

Timo Kötzing
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI  
AG Audience

Date, Time and Location

Tuesday, 26 October 2010
30 Minutes
E1 4


Ant colony optimization (ACO) is a randomized search heuristic which has been widely used for different combinatorial optimization problems. We analyze two ACO algorithms with respect to their runtime behavior for the traveling salesperson problem (TSP) by analyzing how similar newly sampled tours are to old ones. One of the two algorithms we analyzed is a classic ACO algorithm, the other uses a new construction procedure.

We show that our new ACO variant has stronger local properties than the classic one, which leads to proofs of better runtime bounds. Further, we show that both algorithms achieve a good approximation in expected polynomial time on random instances and point out situations in which our algorithms get trapped in local optima.


Timo Kötzing
--email hidden
passcode not visible
logged in users only

Timo Kötzing, 10/25/2010 10:18
Timo Kötzing, 10/19/2010 15:33
Timo Kötzing, 10/19/2010 15:32 -- Created document.