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:
- 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.
- 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.
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