Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/108874
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem |
Author: | Nallaperuma, S. Neumann, F. Sudholt, D. |
Citation: | Evolutionary Computation, 2017; 25(4):673-705 |
Publisher: | MIT Press |
Issue Date: | 2017 |
ISSN: | 1063-6560 1530-9304 |
Statement of Responsibility: | Samadhi Nallaperuma, Frank Neumann and Dirk Sudholt |
Abstract: | Randomized search heuristics are frequently applied to NP-hard combinatorial optimization problems. The runtime analysis of randomized search heuristics has contributed tremendously to their theoretical understanding. Recently, randomized search heuristics have been examined regarding their achievable progress within a fixed time budget. We follow this approach and present a fixed budget analysis for an NP-hard combinatorial optimization problem. We consider the well-known Traveling Salesperson problem (TSP) and analyze the fitness increase that randomized search heuristics are able to achieve within a given fixed time budget. In particular, we analyze Manhattan and Euclidean TSP instances and Randomized Local Search (RLS), (1 + 1) EA and (1 + λ) EA algorithms for the TSP in a smoothed complexity setting and derive the lower bounds of the expected fitness gain for a specified number of generations. |
Keywords: | Traveling Salesperson Problem fitness gain fixed-budget analysis runtime analysis theory |
Rights: | © Massachusetts Institute of Technology |
DOI: | 10.1162/EVCO_a_00199 |
Grant ID: | http://purl.org/au-research/grants/arc/DP130104395 http://purl.org/au-research/grants/arc/DP140103400 |
Published version: | http://dx.doi.org/10.1162/evco_a_00199 |
Appears in Collections: | Aurora harvest 8 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.