Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem|
|Citation:||Evolutionary Computation, 2017; 25(4):673-705|
|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|
|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.