A parameterized runtime analysis of evolutionary algorithms for the Euclidean traveling salesperson problem

Andrew M. Sutton, Frank Neumann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points k and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time O(n 4k(2k - 1)!). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2-opt tour can be found by randomized local search in expected time O(n 2kk!).

Original languageEnglish (US)
Title of host publicationAAAI-12 / IAAI-12 - Proceedings of the 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference
Pages1105-1111
Number of pages7
StatePublished - Nov 7 2012
Event26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12 - Toronto, ON, Canada
Duration: Jul 22 2012Jul 26 2012

Publication series

NameProceedings of the National Conference on Artificial Intelligence
Volume2

Other

Other26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12
CountryCanada
CityToronto, ON
Period7/22/127/26/12

Fingerprint Dive into the research topics of 'A parameterized runtime analysis of evolutionary algorithms for the Euclidean traveling salesperson problem'. Together they form a unique fingerprint.

Cite this