Can I read Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem on EtoBox?

Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem by Samadhi Nallaperuma; Frank Neumann; Dirk Sudholt is a Computer Science article available to read on EtoBox.

What is Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem about?

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.

Who reads Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem?

Author

Samadhi Nallaperuma; Frank Neumann; Dirk Sudholt

Publisher

MIT Press - Journals

Published

2016

Language

EN

Field

Computer Science (Physical Sciences)