Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/82586
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Fixed-parameter evolutionary algorithms for the euclidean traveling salesperson problem |
Author: | Nallaperuma, S. Sutton, A. Neumann, F. |
Citation: | 2013 IEEE Congress on Evolutionary Computation, Cancun, Mexico, 20-23 June 2013: pp.2037-2044 |
Publisher: | IEEE |
Publisher Place: | United States |
Issue Date: | 2013 |
ISBN: | 9781479904525 |
Conference Name: | IEEE Congress on Evolutionary Computation (2013 : Cancun, Mexico) |
Statement of Responsibility: | Samadhi Nallaperuma, Andrew M. Sutton, Frank Neumann |
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(ng(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. |
Rights: | © 2013 IEEE |
DOI: | 10.1109/CEC.2013.6557809 |
Description (link): | http://www.cec2013.org/ |
Published version: | http://dx.doi.org/10.1109/cec.2013.6557809 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_82586.pdf Restricted Access | Restricted Access | 796.77 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.