{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T18:57:54Z","timestamp":1772564274989,"version":"3.50.1"},"reference-count":50,"publisher":"MIT Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2016,6]]},"abstract":"<jats:p>The fitness landscape of the travelling salesman problem is investigated for 11 different types of the problem. The types differ in how the distances between cities are generated. Many different properties of the landscape are studied. The properties chosen are all potentially relevant to choosing an appropriate search algorithm. The analysis includes a scaling study of the time to reach a local optimum, the number of local optima, the expected probability of reaching a local optimum as a function of its fitness, the expected fitness found by local search and the best fitness, the probability of reaching a global optimum, the distance between the local optima and the global optimum, the expected fitness as a function of the distance from an optimum, their basins of attraction and a principal component analysis of the local optima. The principal component analysis shows the correlation of the local optima in the component space. We show how the properties of the principal components of the local optima change from one problem type to another.<\/jats:p>","DOI":"10.1162\/evco_a_00154","type":"journal-article","created":{"date-parts":[[2015,6,12]],"date-time":"2015-06-12T17:13:11Z","timestamp":1434129191000},"page":"347-384","source":"Crossref","is-referenced-by-count":27,"title":["An Analysis of the Fitness Landscape of Travelling Salesman Problem"],"prefix":"10.1162","volume":"24","author":[{"given":"Mohammad-H.","family":"Tayarani-N.","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Science, University of Southampton, Southampton, UK."}]},{"given":"Adam","family":"Pr\u00fcgel-Bennett","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Science, University of Southampton, Southampton, UK."}]}],"member":"281","reference":[{"key":"B1","first-page":"459","author":"Alander J. T.","year":"1999","journal-title":"Practical handbook of genetic algorithms: Complex coding systems"},{"key":"B2","first-page":"363","author":"Alander J. T.","year":"2002","journal-title":"Proceedings of the IEEE International Conference on Artificial Intelligence Systems"},{"key":"B3","first-page":"57","author":"Altenberg L.","year":"1997","journal-title":"Proceedings of the International Conference on Genetic Algorithms"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00176-X"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"B6","author":"Boese K. D.","year":"1995","journal-title":"Cost versus distance in the traveling salesman problem"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(94)90065-5"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9249-2"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44808-X_3"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-010-9155-x"},{"key":"B12","first-page":"321","author":"Fonlupt C.","year":"1997","journal-title":"Proceedings of Evolution Artificielle 1997"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993046"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9473(98)00030-9"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90049-9"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2010.116"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90212-7"},{"key":"B18","first-page":"243","author":"Horn J.","year":"1995","journal-title":"Proceedings of the Workshop on Foundations of Genetic Algorithms"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008874222544"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1145\/1621076.1621080"},{"key":"B22","first-page":"184","author":"Jones T.","year":"1995","journal-title":"Proceedings of the 6th International Conference on Genetic Algorithms"},{"key":"B23","first-page":"172","volume":"2037","author":"Lehn R.","year":"2001","journal-title":"Proceedings of Evo Workshops: Applications of Evolutionary Computing"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20364-0_10"},{"key":"B25","volume":"1","author":"Martin W.","year":"1999","journal-title":"Proceedings of the Congress on Evolutionary Computation"},{"key":"B26","first-page":"219","author":"Mathias K.","year":"1992","journal-title":"Parallel Problem Solving from Nature"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1162\/1063656041774956"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056918"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1109\/4235.887234"},{"key":"B30","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/1276958.1277075","author":"Po\u0161\u00edk P.","year":"2007","journal-title":"Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO)"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2011.2163638"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2009.2033579"},{"key":"B33","first-page":"388","author":"Rardin R. L.","year":"1993","journal-title":"Complexity in Numerical Optimization"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056852"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2010.5586013"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2010.5586414"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0103571"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01165154"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9601(92)90557-3"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1109\/TAI.1997.632276"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2006.1688593"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2013.2281502"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2015.01.005"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71605-1_22"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.01.001"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-1665-5_20"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1007\/BF00202749"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1162\/artl.2006.12.2.211"},{"key":"B50","first-page":"356","author":"Wright S.","year":"1932","journal-title":"Proceedings of Sixth International Congress of Genetics"},{"key":"B51","first-page":"981","author":"Wu Y.","year":"2011","journal-title":"Proceedings of the IEEE Congress on Evolutionary Computation"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.001"},{"key":"B53","first-page":"1179","author":"Zhang W.","year":"2003","journal-title":"Proceedings of the International Joint Conference on Artificial Intelligence"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T11:25:28Z","timestamp":1691753128000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/24\/2\/347-384\/1012"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["10.1162\/EVCO_a_00154"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00154","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6]]}}}