Introduction
The Traveling Salesperson Problem (TSP) is a foundational challenge in combinatorial optimization. While the problem is NP-hard in its general form, heuristics such as 2-opt and Evolutionary Algorithms (EAs) have demonstrated remarkable efficiency in practical applications. This research provides a theoretical bridge between this empirical success and mathematical runtime analysis by examining the Euclidean TSP through the lens of parameterized complexity.
The Geometric Parameter: Interior Points
Traditional worst-case analysis often fails to explain why EAs perform well on real-world geographic data. This paper shifts the focus from the total number of points ($n$) to the geometric distribution of those points. Specifically, the authors use the number of points ($k$) located inside the convex hull—the perimeter formed by the outermost points—as a parameter for analysis.
By parameterizing the runtime based on $k$, the authors demonstrate that Euclidean TSP instances become significantly more tractable for EAs when the majority of points lie on the boundary. This approach identifies EAs as "XP-algorithms," meaning they can solve instances in polynomial time for any fixed, small value of $k$.
Algorithmic Framework and Mutation Strategies
The study analyzes two primary optimization techniques:
- Randomized Local Search (RLS): A hill-climbing algorithm that utilizes 2-opt inversions, accepting moves only if they result in a shorter tour length.
- $(\mu + \lambda)$ EA: A population-based algorithm that employs a Poisson-distributed number of mutations to explore the search space.
To address the limitations of standard 2-opt moves—which are excellent at removing edge intersections but inefficient at reordering points—the authors introduce a Mixed Mutation Strategy. This strategy combines 2-opt inversions with "permutation jumps," where a single point is moved to a different position in the sequence. This addition is shown to be critical for efficiently placing interior points into their optimal slots.
Theoretical Insights: The Search Process
The authors identify a two-phase search process inherent in solving the Euclidean TSP:
- Phase 1: Untangling. The algorithm removes all edge intersections to reach an "intersection-free" state. A key geometric insight here is the Hull-Order Constraint: any intersection-free tour must visit the points on the convex hull in their natural cyclic order. This constraint drastically reduces the search space.
- Phase 2: Ordering. Once the tour is untangled, the algorithm must correctly position the $k$ interior points.
To ensure that improvements in tour length are mathematically significant and not infinitesimally small, the authors assume the points are angle-bounded by a value $\epsilon$. This allows for a concrete bound on the number of steps required to reach the optimum.
Key Results
The research establishes several rigorous upper bounds on the expected runtime of these algorithms:
- Convex Position ($k=0$): When all points lie on the convex hull, both RLS and EAs solve the TSP in expected polynomial time: $O(n^3 \gamma(\epsilon))$.
- General Instances: For the $(\mu + \lambda)$ EA using only 2-opt, the expected runtime is $O\left(\frac{\mu}{\lambda} \cdot n^3\gamma(\epsilon) + n\gamma(\epsilon) + \frac{\mu}{\lambda} \cdot n^{4k}(2k-1)!\right)$.
- Mixed Mutation Speedup: The introduction of the jump operator significantly improves the complexity of the second phase, reducing the $n^{4k}$ factor to $n^{2k}$.
- Grid Benchmarks: On an $m \times m$ integer grid, the geometric factor $\gamma(\epsilon)$ is bounded by $O(m^5)$, providing a polynomial runtime for quantized instances.
Conclusion and Future Directions
This work provides a rigorous theoretical justification for the use of EAs in geometric optimization. By proving that the complexity is tied to the number of interior points, the authors explain why many geographic TSP instances are solved quickly in practice.
A remaining challenge is determining whether EAs can achieve Fixed-Parameter Tractability (FPT). While XP-complexity ($n^{2k}$) is polynomial for a fixed $k$, FPT would imply a runtime where the exponential growth is entirely independent of $n$ (e.g., $f(k) \cdot n^c$). Achieving an FPT bound would represent the ultimate theoretical validation of evolutionary search for the Euclidean TSP.
Summary updated