TY - JOUR

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

AU - Sutton, Andrew M.

AU - Neumann, Frank

AU - Nallaperuma, Samadhi

PY - 2014/12/10

Y1 - 2014/12/10

N2 - 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 their runtime. We analyze the runtime in dependence of the number of inner points k. In the first part of the paper, we study a (μ + λ) EAin a strictly black box setting and show that it can solve the Euclidean TSP in expected time O (n · A(∈) · max {(μ/λ) · n2, 1} + (μ/λ) · n4k(2k − 1)!) where A is a function of the minimum angle { between any three points. Based on insights provided by the analysis, we improve this upper bound by introducing a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps. This strategy improves the upper bound to O (n · A(∈) · max {(μ/λ) · n2, 1} + (μ/λ) · n2k(k − 1)!). In the second part of the paper, we use the information gained in the analysis to incorporate domain knowledge to design two fixed-parameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a (μ + λ) EA based on an analysis by M. Theile, 2009, ”Exact solutions to the traveling salesperson problem by a populationbased evolutionary algorithm,” Lecture notes in computer science, Vol. 5482 (pp. 145–155), that solves the TSP with k inner points in O(max{2kk2n2λ-1, n}) generations with probability 1 − e-Ω(n).We then design a (μ + λ) EAthat incorporates a dynamic programming step into the fitness evaluation.We prove that a variant of this evolutionary algorithm using 2-opt mutation solves the problem after O(max{(k − 2)!k2k-2λ-1, 1}) steps in expectation with a cost of O(nk) for each fitness evaluation.

AB - 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 their runtime. We analyze the runtime in dependence of the number of inner points k. In the first part of the paper, we study a (μ + λ) EAin a strictly black box setting and show that it can solve the Euclidean TSP in expected time O (n · A(∈) · max {(μ/λ) · n2, 1} + (μ/λ) · n4k(2k − 1)!) where A is a function of the minimum angle { between any three points. Based on insights provided by the analysis, we improve this upper bound by introducing a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps. This strategy improves the upper bound to O (n · A(∈) · max {(μ/λ) · n2, 1} + (μ/λ) · n2k(k − 1)!). In the second part of the paper, we use the information gained in the analysis to incorporate domain knowledge to design two fixed-parameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a (μ + λ) EA based on an analysis by M. Theile, 2009, ”Exact solutions to the traveling salesperson problem by a populationbased evolutionary algorithm,” Lecture notes in computer science, Vol. 5482 (pp. 145–155), that solves the TSP with k inner points in O(max{2kk2n2λ-1, n}) generations with probability 1 − e-Ω(n).We then design a (μ + λ) EAthat incorporates a dynamic programming step into the fitness evaluation.We prove that a variant of this evolutionary algorithm using 2-opt mutation solves the problem after O(max{(k − 2)!k2k-2λ-1, 1}) steps in expectation with a cost of O(nk) for each fitness evaluation.

KW - Combinatorial optimization

KW - Evolutionary algorithms

KW - Parameterized analysis

KW - Runtime analysis

UR - http://www.scopus.com/inward/record.url?scp=84905662137&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905662137&partnerID=8YFLogxK

U2 - 10.1162/EVCO_a_00119

DO - 10.1162/EVCO_a_00119

M3 - Article

C2 - 24479542

AN - SCOPUS:84905662137

VL - 22

SP - 595

EP - 628

JO - Evolutionary Computation

JF - Evolutionary Computation

SN - 1063-6560

IS - 4

ER -