{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T12:06:23Z","timestamp":1763726783848},"reference-count":34,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p> Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, we contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound their runtime. We analyze the runtime in dependence of the number of inner points k. In the first part of the paper, we study a [Formula: see text] EA in a strictly black box setting and show that it can solve the Euclidean TSP in expected time [Formula: see text] where A is a function of the minimum angle [Formula: see text] between any three points. Based on insights provided by the analysis, we improve this upper bound by introducing a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps. This strategy improves the upper bound to [Formula: see text]. In the second part of the paper, we use the information gained in the analysis to incorporate domain knowledge to design two fixed-parameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a [Formula: see text] EA based on an analysis by M. Theile, 2009, \u201dExact solutions to the traveling salesperson problem by a population-based evolutionary algorithm,\u201d Lecture notes in computer science, Vol. 5482 (pp. 145\u2013155), that solves the TSP with k inner points in [Formula: see text] generations with probability [Formula: see text]. We then design a [Formula: see text] EA that incorporates a dynamic programming step into the fitness evaluation. We prove that a variant of this evolutionary algorithm using 2-opt mutation solves the problem after [Formula: see text] steps in expectation with a cost of [Formula: see text] for each fitness evaluation. <\/jats:p>","DOI":"10.1162\/evco_a_00119","type":"journal-article","created":{"date-parts":[[2014,1,30]],"date-time":"2014-01-30T21:18:33Z","timestamp":1391116713000},"page":"595-628","source":"Crossref","is-referenced-by-count":28,"title":["Parameterized Runtime Analyses of Evolutionary Algorithms for the Planar Euclidean Traveling Salesperson Problem"],"prefix":"10.1162","volume":"22","author":[{"given":"Andrew M.","family":"Sutton","sequence":"first","affiliation":[{"name":"Department of Computer Science, Colorado State University, Fort Collins, CO, USA"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[{"name":"Optimisation and Logistics, School of Computer Science, University of Adelaide, Adelaide, Australia"}]},{"given":"Samadhi","family":"Nallaperuma","sequence":"additional","affiliation":[{"name":"Optimisation and Logistics, School of Computer Science, University of Adelaide, Adelaide, Australia"}]}],"member":"281","reference":[{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1142\/7438"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250627"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251244"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.01.002"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.07.024"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00047"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"B12","first-page":"1","volume-title":"Proceedings of Combinatorics, Computation and Logic, DMTCS\u201999 and CATS\u201999. Australian computer science communications","volume":"21","author":"Downey R. G.","year":"1999"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056845"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00182-7"},{"key":"B15","first-page":"1295","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM\u201907)","author":"Englert M.","year":"2007"},{"key":"B16","volume-title":"Parameterized complexity theory","author":"Flum J.","year":"2006"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00058-3"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00381-8"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1162\/106365605774666921"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-011-0059-7"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15844-5_21"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.02.008"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2013.6557809"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.08.005"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-006-9004-x"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.002"},{"key":"B28","volume-title":"Bioinspired computation in combinatorial optimization\u2014Algorithms and their computational complexity","author":"Neumann F.","year":"2010"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1965.11970655"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1023\/B:JMMA.0000049379.14872.f5"},{"key":"B33","first-page":"1105","volume-title":"Proceedings of the Twenty-Sixth Conference on Artificial Intelligence, AAAI\u201912","author":"Sutton A. M.","year":"2012"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32937-1_6"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01009-5_13"},{"key":"B36","volume-title":"Proceedings of the Seventh International Workshop on Graph-Theoretic Concepts in Computer Science, WG\u201981","author":"van Leeuwen J.","year":"1981"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_4"},{"key":"B39","first-page":"555","volume-title":"Proceedings of the Twenty-First Conference on Artificial Intelligence, AAAI\u201906,","author":"Yu Y.","year":"2006"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:30Z","timestamp":1615586310000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/22\/4\/595-628\/999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1162\/EVCO_a_00119"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00119","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}