Current studentsExisting staffContact us
 

Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem

Simple item page
dc.contributor.authorNallaperuma, S.
dc.contributor.authorNeumann, F.
dc.contributor.authorSudholt, D.
dc.date.issued2017
dc.description.abstractRandomized 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.statementofresponsibilitySamadhi Nallaperuma, Frank Neumann and Dirk Sudholt
dc.identifier.citationEvolutionary Computation, 2017; 25(4):673-705
dc.identifier.doi10.1162/EVCO_a_00199
dc.identifier.issn1063-6560
dc.identifier.issn1530-9304
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttp://hdl.handle.net/2440/108874
dc.language.isoen
dc.publisherMIT Press
dc.relation.granthttp://purl.org/au-research/grants/arc/DP130104395
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140103400
dc.rights© Massachusetts Institute of Technology
dc.source.urihttps://doi.org/10.1162/evco_a_00199
dc.subjectTraveling Salesperson Problem
dc.subjectfitness gain
dc.subjectfixed-budget analysis
dc.subjectruntime analysis theory
dc.titleExpected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem
dc.typeJournal article
pubs.publication-statusPublished

Files

Collections

Computer Science publications