A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem

Andrew M. Sutton, Frank Neumann

Abstract

Evolutionary Algorithms (EAs) are widely used for solving the Traveling Salesperson Problem (TSP), yet their theoretical performance on Euclidean instances remains poorly understood. This paper provides a parameterized runtime analysis of simple EAs on the Euclidean TSP. By introducing the number of interior points $k$ (points inside the convex hull) as a parameter, the authors prove that the (1+1)-EA is a randomized XP-algorithm. Specifically, for a fixed $k$, the algorithm finds the global optimum in polynomial time. This work bridges the gap between empirical success and rigorous complexity theory by exploiting the geometric structure of Euclidean space.

Introduction

The Traveling Salesperson Problem (TSP) is a cornerstone of NP-hard combinatorial optimization. Despite its general hardness, real-world Euclidean instances—where distances satisfy the triangle inequality—often prove more tractable for heuristics like Evolutionary Algorithms (EAs) and Randomized Local Search (RLS). While empirical evidence supports their efficacy, theoretical analysis has historically focused on simplified "toy" problems. This paper addresses this gap by providing rigorous runtime bounds for EAs on Euclidean TSP, utilizing the geometric properties of the 2D plane.

Methodology and Geometric Constraints

The authors employ parameterized runtime analysis, focusing on the number of interior points $k$ relative to the convex hull. They analyze two specific algorithms:

  1. Randomized Local Search (RLS): An algorithm that performs a single "inversion" (a 2-opt move that reverses a segment of the tour) in each step.
  2. The (1+1)-EA: A simple evolutionary algorithm that can perform multiple inversions in a single mutation step, with the number of inversions following a Poisson distribution.

A critical challenge in analyzing continuous or high-resolution discrete spaces is avoiding "Zeno’s paradox," where an algorithm makes an infinite sequence of infinitesimal improvements. To ensure a minimum progress per step, the authors assume the point sets are either embedded on a grid or are "angle-bounded," meaning no three points form an arbitrarily small angle.

Figure 1: Geometric construction illustrating the angle-bounded constraint, where the angle θ between points is bounded to ensure non-negligible tour length improvements.

Key Insights

The analysis hinges on several structural properties of Euclidean TSP:

  • Convex Hull Dominance: If all $n$ points lie on the convex hull ($k=0$), any intersection-free tour is optimal. The authors show that for such points on an $m \times m$ grid, EAs find the optimum in $O(n^3 m^5)$ time.
  • Intersection Removal: A fundamental property of optimal Euclidean tours is the absence of self-intersecting edges. The authors prove that 2-opt moves (inversions) are highly effective at eliminating these intersections.
  • Hull-Respecting Tours: Any tour without intersections must visit convex hull points in their natural cyclic order. This property significantly restricts the search space for the $k$ interior points, facilitating the parameterized analysis.

Key Results

The paper establishes concrete expected runtime bounds that scale with the number of interior points:

  • Convex Position ($k=0$): On an $m \times m$ grid, both RLS and (1+1)-EA solve the problem in $O(n^3 m^5)$.
  • Local Optima (RLS): For an instance with $k$ interior points and a fixed angle bound, RLS reaches a 2-opt local optimum in $O(n^{2k} k!)$ iterations.
  • Global Optima ((1+1)-EA): The (1+1)-EA finds the global optimum in $O(n^{4k} (2k-1)!)$ iterations.

These results categorize the (1+1)-EA as an XP-algorithm with respect to $k$. While the bounds are exponential in $k$, they remain polynomial in $n$ for any fixed $k$, marking a significant theoretical milestone.

Conclusion and Future Work

This research demonstrates that the "hardness" of Euclidean TSP for simple EAs is directly tied to the number of interior points. While the current bounds are XP, a major open question is whether Euclidean TSP is Fixed-Parameter Tractable (FPT) for EAs, which would imply a runtime where the exponent of $n$ is independent of $k$. Additionally, extending this geometric analysis to higher dimensions and more complex EAs with populations and crossover operators remains a fertile ground for future study.

Summary updated

Abstract

Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, 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 investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound the runtime of simple evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points $k$ and shows that $(\mu + \lambda)$ evolutionary algorithms solve the Euclidean TSP in expected time $O((\mu/\lambda) \cdot n^3\gamma(\epsilon) + n\gamma(\epsilon) + (\mu/\lambda) \cdot n^{4k}(2k-1)!)$ where $\gamma$ is a function of the minimum angle $\epsilon$ between any three points. Finally, our analysis provides insights into designing a mutation operator that improves the upper bound on expected runtime. We show that a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps results in an upper bound of $O((\mu/\lambda) \cdot n^3\gamma(\epsilon) + n\gamma(\epsilon) + (\mu/\lambda) \cdot n^{2k}(k-1)!)$ for the $(\mu+\lambda)$ EA.
BibTeX
@inproceedings{sutton2012parameterized,
  author = {Andrew M. Sutton and Frank Neumann},
  title = {{A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2012},
  doi = {10.1609/aaai.v26i1.8273},
}
Figure