Parameterized runtime analyses of evolutionary algorithms for the planar euclidean traveling salesperson problem

Area of Science:

• Computer Science
• Artificial Intelligence
• Operations Research

Background:

• Parameterized runtime analysis investigates how problem structure affects algorithm efficiency.
• Evolutionary algorithms (EAs) are heuristic approaches for optimization problems.
• The Euclidean Traveling Salesperson Problem (TSP) is a classic NP-hard problem.

Purpose of the Study:

• To provide a parameterized analysis of evolutionary algorithms for the Euclidean TSP.
• To understand structural properties influencing EA performance on TSP instances.
• To develop and bound the runtime of fixed-parameter tractable (FPT) EAs for the planar Euclidean TSP.

Main Methods:

• Analysis of a [Formula: see text] EA in a black-box setting.
• Introduction of a mixed mutation strategy (2-opt and permutation jumps).
• Design of two FPT EAs incorporating domain knowledge and dynamic programming.

Main Results:

• An initial upper bound of [Formula: see text] for solving Euclidean TSP with a [Formula: see text] EA.
• An improved upper bound of [Formula: see text] using the mixed mutation strategy.
• An FPT EA solving TSP with k inner points in [Formula: see text] generations with probability [Formula: see text].
• A second FPT EA variant solving TSP in [Formula: see text] expected steps with a fitness evaluation cost of [Formula: see text].

Conclusions:

• Problem structure significantly influences EA runtime for Euclidean TSP.
• Mixed mutation strategies and domain knowledge integration enhance EA performance.
• Developed FPT EAs provide theoretically bounded and efficient solutions for the planar Euclidean TSP.