Please use this identifier to cite or link to this item: http://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
RMID: 0030059264
DOI: 10.1162/EVCO_a_00199
Grant ID: http://purl.org/au-research/grants/arc/DP130104395
http://purl.org/au-research/grants/arc/DP140103400
Appears in Collections: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.