{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T20:12:04Z","timestamp":1769976724373,"version":"3.49.0"},"reference-count":31,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p>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)\u00a0EA and (1+[Formula: see text])\u00a0EA 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.<\/jats:p>","DOI":"10.1162\/evco_a_00199","type":"journal-article","created":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T19:47:21Z","timestamp":1480362441000},"page":"673-705","source":"Crossref","is-referenced-by-count":20,"title":["Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem"],"prefix":"10.1162","volume":"25","author":[{"given":"Samadhi","family":"Nallaperuma","sequence":"first","affiliation":[{"name":"Algorithms, Department of Computer Science, The University of Sheffield, Sheffield, S1 4DP, United Kingdom"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[{"name":"Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, SA 5005, Australia"}]},{"given":"Dirk","family":"Sudholt","sequence":"additional","affiliation":[{"name":"Algorithms, Department of Computer Science, The University of Sheffield, Sheffield, S1 4DP, United Kingdom"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1142\/7438"},{"key":"B2","first-page":"361","volume-title":"Parallel Problem Solving from Nature","volume":"2","author":"Beyer H.-G.","year":"1992"},{"key":"B3","first-page":"80:353","author":"Burgstaller B.","year":"2009","journal-title":"Bulletin of the Australian Mathematical Society"},{"key":"B4","first-page":"150","author":"Chandra B.","year":"1994","journal-title":"Proceedings of 5th ACM-SIAM Symposium on Discrete Algorithms"},{"key":"B5","doi-asserted-by":"crossref","first-page":"1399","DOI":"10.1145\/2739480.2754799","author":"Corus D.","year":"2015","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference, GECCO \u201915"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1145\/2463372.2463565"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05094-1"},{"key":"B8","first-page":"1295","author":"Englert M.","year":"2007","journal-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9801-4"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70807-0_15"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4"},{"key":"B12","first-page":"1","author":"Jansen T.","year":"2011","journal-title":"Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms"},{"key":"B13","first-page":"1325","author":"Jansen T.","year":"2012","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012)"},{"key":"B14","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1145\/2576768.2598344","author":"Jansen T.","year":"2014","journal-title":"Proceedings of the 2014 Conference on Genetic and Evolutionary Computation, GECCO \u201914"},{"key":"B15","first-page":"545:39","author":"Jansen T.","year":"2014","journal-title":"Theoretical Computer Science"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2014.2349160"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587089"},{"key":"B18","first-page":"52","author":"Lengler J.","year":"2015","journal-title":"Proceedings of the 11th Workshop on Foundations of Genetic Algorithms"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_54"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87700-4_92"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"B22","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1145\/2576768.2598302","author":"Nallaperuma S.","year":"2014","journal-title":"Genetic and Evolutionary Computation Conference, GECCO \u201914"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3"},{"key":"B24","first-page":"349","author":"N\u00fcrnberg H.-T.","year":"1997","journal-title":"Evolutionary Programming VI: Proceedings of the Sixth Annual Conference on Evolutionary Programming"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/s11633-007-0281-3"},{"key":"B26","first-page":"545:20","author":"Rowe J. E.","year":"2014","journal-title":"Theoretical Computer Science"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/s00287-013-0684-1"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056922"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"},{"key":"B31","first-page":"436:106","author":"Zhou D.","year":"2012","journal-title":"Theoretical Computer Science"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/evco_a_00199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T06:19:19Z","timestamp":1657865959000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/25\/4\/673-705\/1064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["10.1162\/evco_a_00199"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00199","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}