AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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