Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem
Date
2017
Authors
Nallaperuma, S.
Neumann, F.
Sudholt, D.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Evolutionary Computation, 2017; 25(4):673-705
Statement of Responsibility
Samadhi Nallaperuma, Frank Neumann and Dirk Sudholt
Conference Name
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© Massachusetts Institute of Technology