Fixed-parameter evolutionary algorithms for the Euclidean Traveling Salesperson problem

Samadhi Nallaperuma, Andrew M. Sutton, Frank Neumann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

Recently, Sutton and Neumann [1] have studied evolutionary algorithms for the Euclidean traveling salesman problem by parameterized runtime analyses taking into account the number of inner points k and the number of cities n. They have shown that simple evolutionary algorithms are XP-algorithms for the problem, i. e., they obtain an optimal solution in expected time O(n g(k)) where g(k) is a function only depending on k. We extend these investigations and design two evolutionary algorithms for the Euclidean Traveling Salesperson problem that run in expected time g(k)·poly(n) where k is a parameter denoting the number inner points for the given TSP instance, i. e., they are fixed-parameter tractable evolutionary algorithms for the Euclidean TSP parameterized by the number of inner points. While our first approach is mainly of theoretical interest, our second approach leverages problem structure by directly searching for good orderings of the inner points and provides a novel and highly effective way of tackling this important problem. Our experimental results show that searching for a permutation on the inner points is a significantly powerful practical strategy.

Original languageEnglish (US)
Title of host publication2013 IEEE Congress on Evolutionary Computation, CEC 2013
Pages2037-2044
Number of pages8
DOIs
StatePublished - 2013
Event2013 IEEE Congress on Evolutionary Computation, CEC 2013 - Cancun, Mexico
Duration: Jun 20 2013Jun 23 2013

Publication series

Name2013 IEEE Congress on Evolutionary Computation, CEC 2013

Other

Other2013 IEEE Congress on Evolutionary Computation, CEC 2013
CountryMexico
CityCancun
Period6/20/136/23/13

Fingerprint Dive into the research topics of 'Fixed-parameter evolutionary algorithms for the Euclidean Traveling Salesperson problem'. Together they form a unique fingerprint.

Cite this