A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem
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(nk(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(n2kk!).
Cite
Text
Sutton and Neumann. "A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8273Markdown
[Sutton and Neumann. "A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/sutton2012aaai-parameterized/) doi:10.1609/AAAI.V26I1.8273BibTeX
@inproceedings{sutton2012aaai-parameterized,
title = {{A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem}},
author = {Sutton, Andrew M. and Neumann, Frank},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {1105-1111},
doi = {10.1609/AAAI.V26I1.8273},
url = {https://mlanthology.org/aaai/2012/sutton2012aaai-parameterized/}
}