Please use this identifier to cite or link to this item:
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
Statement of
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:
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.