TY - GEN

T1 - Fixed-parameter evolutionary algorithms for the Euclidean Traveling Salesperson problem

AU - Nallaperuma, Samadhi

AU - Sutton, Andrew M.

AU - Neumann, Frank

PY - 2013

Y1 - 2013

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

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

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

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

U2 - 10.1109/CEC.2013.6557809

DO - 10.1109/CEC.2013.6557809

M3 - Conference contribution

AN - SCOPUS:84881576351

SN - 9781479904549

T3 - 2013 IEEE Congress on Evolutionary Computation, CEC 2013

SP - 2037

EP - 2044

BT - 2013 IEEE Congress on Evolutionary Computation, CEC 2013

T2 - 2013 IEEE Congress on Evolutionary Computation, CEC 2013

Y2 - 20 June 2013 through 23 June 2013

ER -