Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/108874
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Nallaperuma, S. | - |
dc.contributor.author | Neumann, F. | - |
dc.contributor.author | Sudholt, D. | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Evolutionary Computation, 2017; 25(4):673-705 | - |
dc.identifier.issn | 1063-6560 | - |
dc.identifier.issn | 1530-9304 | - |
dc.identifier.uri | http://hdl.handle.net/2440/108874 | - |
dc.description.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. | - |
dc.description.statementofresponsibility | Samadhi Nallaperuma, Frank Neumann and Dirk Sudholt | - |
dc.language.iso | en | - |
dc.publisher | MIT Press | - |
dc.rights | © Massachusetts Institute of Technology | - |
dc.source.uri | http://dx.doi.org/10.1162/evco_a_00199 | - |
dc.subject | Traveling Salesperson Problem | - |
dc.subject | fitness gain | - |
dc.subject | fixed-budget analysis | - |
dc.subject | runtime analysis theory | - |
dc.title | Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem | - |
dc.type | Journal article | - |
dc.identifier.doi | 10.1162/EVCO_a_00199 | - |
dc.relation.grant | http://purl.org/au-research/grants/arc/DP130104395 | - |
dc.relation.grant | http://purl.org/au-research/grants/arc/DP140103400 | - |
pubs.publication-status | Published | - |
dc.identifier.orcid | Neumann, F. [0000-0002-2721-3618] | - |
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.