title: Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem.
abstract: Randomized search heuristics are frequently applied to NP-hard combinatorial optimization problems. The runtime analysis of randomized search heuristics has contributed tremendously to our 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+[Formula: see text]) 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.
authors.affiliation: Algorithms, Department of Computer Science, The University of Sheffield, Sheffield, S1 4DP, United Kingdom s.nallaperuma@sheffield.ac.uk.
authors.forename: Samadhi
authors.initials: S
authors.lastname: Nallaperuma
authors.affiliation: Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, SA 5005, Australia frank.neumann@adelaide.edu.au.
authors.forename: Frank
authors.initials: F
authors.lastname: Neumann
authors.affiliation: Algorithms, Department of Computer Science, The University of Sheffield, Sheffield, S1 4DP, United Kingdom d.sudholt@sheffield.ac.uk.
authors.forename: Dirk
authors.initials: D
authors.lastname: Sudholt
mesh_terms: D000066506:Heuristics; D008962:Models, Theoretical; D011897:Random Allocation
keywords: Traveling Salesperson Problem; fitness gain; fixed-budget analysis; runtime analysis theory