{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T16:43:24Z","timestamp":1751993004363,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,12,19]],"date-time":"2020-12-19T00:00:00Z","timestamp":1608336000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,19]],"date-time":"2020-12-19T00:00:00Z","timestamp":1608336000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>local optima network<\/jats:italic> (LON) encodes local optima connectivity in the fitness landscape of a combinatorial optimisation problem. Recently, LONs have been studied for their <jats:italic>fractal dimension<\/jats:italic>. Fractal dimension is a complexity index where a non-integer dimension can be assigned to a pattern. This paper investigates the fractal nature of LONs and how that nature relates to metaheuristic performance on the underlying problem. We use visual analysis, correlation analysis, and machine learning techniques to demonstrate that relationships exist and that fractal features of LONs can contribute to explaining and predicting algorithm performance. The results show that the extent of multifractality and high fractal dimensions in the LON can contribute in this way when placed in regression models with other predictors. Features are also individually correlated with search performance, and visual analysis of LONs shows insight into this relationship.<\/jats:p>","DOI":"10.1007\/s11047-020-09834-y","type":"journal-article","created":{"date-parts":[[2020,12,19]],"date-time":"2020-12-19T08:02:40Z","timestamp":1608364960000},"page":"317-333","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The fractal geometry of fitness landscapes at the local optima level"],"prefix":"10.1007","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6971-7817","authenticated-orcid":false,"given":"Sarah L.","family":"Thomson","sequence":"first","affiliation":[]},{"given":"Gabriela","family":"Ochoa","sequence":"additional","affiliation":[]},{"given":"S\u00e9bastien","family":"Verel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,12,19]]},"reference":[{"key":"9834_CR1","doi-asserted-by":"crossref","unstructured":"Bo\u017cejko W, Gnatowski A, Ni\u017cy\u0144ski T, Affenzeller M, Beham A (2018) Local optima networks in solving algorithm selection problem for tsp. In: International conference on dependability and complex systems, Springer, pp 83\u201393","DOI":"10.1007\/978-3-319-91446-6_9"},{"issue":"4","key":"9834_CR2","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1023\/A:1008293323270","volume":"10","author":"RE Burkard","year":"1997","unstructured":"Burkard RE, Karisch SE, Rendl F (1997) Qaplib-a quadratic assignment problem library. J Global Optim 10(4):391\u2013403","journal-title":"J Global Optim"},{"issue":"2","key":"9834_CR3","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1088\/0031-9155\/35\/2\/004","volume":"35","author":"CB Caldwell","year":"1990","unstructured":"Caldwell CB, Stapleton SJ, Holdsworth DW, Jong RA, Weiser WJ, Cooke G, Yaffe MJ (1990) Characterisation of mammographic parenchymal pattern by fractal dimension. Phys Med Biol 35(2):235","journal-title":"Phys Med Biol"},{"key":"9834_CR4","doi-asserted-by":"crossref","unstructured":"Chicano F, Daolio F, Ochoa G, V\u00e9rel S, Tomassini M, Alba E (2012) Local optima networks, landscape autocorrelation and heuristic search performance. In: International conference on parallel problem solving from nature, Springer, pp 337\u2013347","DOI":"10.1007\/978-3-642-32964-7_34"},{"key":"9834_CR5","doi-asserted-by":"crossref","unstructured":"Daolio F, Verel S, Ochoa G, Tomassini M (2010) Local optima networks of the quadratic assignment problem. In: IEEE congress on evolutionary computation, IEEE, pp 1\u20138","DOI":"10.1109\/CEC.2010.5586481"},{"issue":"9","key":"9834_CR6","doi-asserted-by":"publisher","first-page":"1684","DOI":"10.1016\/j.physa.2011.01.005","volume":"390","author":"F Daolio","year":"2011","unstructured":"Daolio F, Tomassini M, V\u00e9rel S, Ochoa G (2011) Communities of minima in local optima networks of combinatorial spaces. Phys A 390(9):1684\u20131694","journal-title":"Phys A"},{"issue":"4","key":"9834_CR7","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1111\/j.1365-3032.1988.tb01122.x","volume":"13","author":"M Dicke","year":"1988","unstructured":"Dicke M, Burrough PA (1988) Using fractal dimensions for characterizing tortuosity of animal trails. Physiol Entomol 13(4):393\u2013398","journal-title":"Physiol Entomol"},{"issue":"1","key":"9834_CR8","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/4233.992163","volume":"6","author":"AN Esgiar","year":"2002","unstructured":"Esgiar AN, Naguib RN, Sharif BS, Bennett MK, Murray A (2002) Fractal analysis in the detection of colonic cancer images. IEEE Trans Inf Technol Biomed 6(1):54\u201358","journal-title":"IEEE Trans Inf Technol Biomed"},{"issue":"3","key":"9834_CR9","doi-asserted-by":"publisher","first-page":"036","DOI":"10.1103\/PhysRevE.84.036118","volume":"84","author":"S Furuya","year":"2011","unstructured":"Furuya S, Yakubo K (2011) Multifractality of complex networks. Phys Rev E 84(3):036\u2013118","journal-title":"Phys Rev E"},{"issue":"7","key":"9834_CR10","doi-asserted-by":"publisher","first-page":"1612","DOI":"10.1016\/j.engstruct.2006.09.016","volume":"29","author":"L Hadjileontiadis","year":"2007","unstructured":"Hadjileontiadis L, Douka E (2007) Crack detection in plates using fractal dimension. Eng Struct 29(7):1612\u20131625","journal-title":"Eng Struct"},{"key":"9834_CR11","doi-asserted-by":"crossref","unstructured":"Herrmann S, Ochoa G, Rothlauf F (2016) Communities of local optima as funnels in fitness landscapes. In: Proceedings of the 2016 on genetic and evolutionary computation conference, ACM, pp 325\u2013331","DOI":"10.1145\/2908812.2908818"},{"key":"9834_CR12","doi-asserted-by":"crossref","unstructured":"Hoos HH, Smyth K, St\u00fctzle T (2004) Search space features underlying the performance of stochastic local search algorithms for max-sat. In: International conference on parallel problem solving from nature, Springer, pp 51\u201360","DOI":"10.1007\/978-3-540-30217-9_6"},{"key":"9834_CR13","unstructured":"Hutter F, Hoos HH, St\u00fctzle T (2007) Automatic algorithm configuration based on local search. In: Proceedings of the 22nd national conference on artificial intelligence, vol 2, AAAI Press, AAAI\u201907, p 1152\u20131157"},{"issue":"4","key":"9834_CR14","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"EL Lawler","year":"1963","unstructured":"Lawler EL (1963) The quadratic assignment problem. Manag Sci 9(4):586\u2013599","journal-title":"Manag Sci"},{"issue":"2","key":"9834_CR15","doi-asserted-by":"publisher","first-page":"023","DOI":"10.1063\/1.4907557","volume":"25","author":"JL Liu","year":"2015","unstructured":"Liu JL, Yu ZG, Anh V (2015) Determination of multifractal dimensions of complex networks by means of the sandbox algorithm. Chaos Interdiscip J Nonlinear Sci 25(2):023\u2013103","journal-title":"Chaos Interdiscip J Nonlinear Sci"},{"issue":"1","key":"9834_CR16","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10589-005-4561-y","volume":"30","author":"M Locatelli","year":"2005","unstructured":"Locatelli M (2005) On the multilevel structure of global optimization problems. Comput Optim Appl 30(1):5\u201322","journal-title":"Comput Optim Appl"},{"key":"9834_CR17","doi-asserted-by":"crossref","unstructured":"Mandelbrot BB (1972) Possible refinement of the lognormal hypothesis concerning the distribution of energy dissipation in intermittent turbulence. In: Statistical models and turbulence, Springer, pp 333\u2013351","DOI":"10.1007\/3-540-05716-1_20"},{"issue":"10","key":"9834_CR18","doi-asserted-by":"publisher","first-page":"3825","DOI":"10.1073\/pnas.72.10.3825","volume":"72","author":"BB Mandelbrot","year":"1975","unstructured":"Mandelbrot BB (1975) Stochastic models for the earth\u2019s relief, the shape and the fractal dimension of the coastlines, and the number-area rule for islands. Proc Nat Acad Sci 72(10):3825\u20133828","journal-title":"Proc Nat Acad Sci"},{"key":"9834_CR19","unstructured":"Mandelbrot BB, Fisher AJ, Calvet LE (1997) A multifractal model of asset returns. Cowles Foundation discussion paper"},{"issue":"3","key":"9834_CR20","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1159\/000125551","volume":"119","author":"A Mashiah","year":"2008","unstructured":"Mashiah A, Wolach O, Sandbank J, Uziel O, Raanani P, Lahav M (2008) Lymphoma and leukemia cells possess fractal dimensions that correlate with their biological features. Acta Haematol 119(3):142\u2013150","journal-title":"Acta Haematol"},{"key":"9834_CR21","doi-asserted-by":"crossref","unstructured":"McMenemy P, Veerapen N, Ochoa G, (2018) How perturbation strength shapes the global structure of tsp fitness landscapes. In: Liefooghe A, L\u00f3pez-Ib\u00e1\u00f1ez M (eds) Evolutionary computation in combinatorial optimization. EvoCOP, (2018) Lecture Notes in Computer Science, vol 10782. Springer, Cham","DOI":"10.1007\/978-3-319-77449-7_3"},{"issue":"3","key":"9834_CR22","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1162\/1063656041774956","volume":"12","author":"P Merz","year":"2004","unstructured":"Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evol Comput 12(3):303\u2013325","journal-title":"Evol Comput"},{"issue":"4","key":"9834_CR23","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/4235.887234","volume":"4","author":"P Merz","year":"2000","unstructured":"Merz P, Freisleben B (2000) Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans Evol Comput 4(4):337\u2013352","journal-title":"IEEE Trans Evol Comput"},{"key":"9834_CR24","doi-asserted-by":"crossref","unstructured":"Ochoa G, Herrmann S (2018) Perturbation strength and the global structure of QAP fitness landscapes. In: International conference on parallel problem solving from nature, Springer, pp 245\u2013256","DOI":"10.1007\/978-3-319-99259-4_20"},{"key":"9834_CR25","first-page":"373","volume":"2016","author":"G Ochoa","year":"2016","unstructured":"Ochoa G, Veerapen N (2016) Additional dimensions to the study of funnels in combinatorial landscapes. Proc Genetic Evol Comput Conf 2016:373\u2013380","journal-title":"Proc Genetic Evol Comput Conf"},{"issue":"3","key":"9834_CR26","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s10732-017-9334-0","volume":"24","author":"G Ochoa","year":"2018","unstructured":"Ochoa G, Veerapen N (2018) Mapping the global structure of tsp fitness landscapes. J Heuristics 24(3):265\u2013294","journal-title":"J Heuristics"},{"key":"9834_CR27","doi-asserted-by":"crossref","unstructured":"Ochoa G, Tomassini M, V\u00e9rel S, Darabos C (2008) A study of nk landscapes\u2019 basins and local optima networks. In: Proceedings of the 10th annual conference on Genetic and evolutionary computation, ACM, pp 555\u2013562","DOI":"10.1145\/1389095.1389204"},{"key":"9834_CR28","doi-asserted-by":"crossref","unstructured":"Ochoa G, Veerapen N, Daolio F, Tomassini M, (2017) Understanding phase transitions with local optima networks: Number partitioning as a case study. In: Hu B, L\u00f3pez-Ib\u00e1\u00f1ez M (eds) Evolutionary computation in combinatorial optimization. EvoCOP 2017, Lecture notes in computer science, vol 10197. Springer, Cham","DOI":"10.1007\/978-3-319-55453-2_16"},{"key":"9834_CR29","doi-asserted-by":"crossref","unstructured":"Pitzer E, Affenzeller M (2012) A comprehensive survey on fitness landscape analysis. In: Recent advances in intelligent engineering systems, Springer, pp 161\u2013191","DOI":"10.1007\/978-3-642-23229-9_8"},{"issue":"5","key":"9834_CR30","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1080\/17445760.2017.1315721","volume":"33","author":"H Richter","year":"2018","unstructured":"Richter H (2018) Scale-invariance of ruggedness measures in fractal fitness landscapes. Int J Parallel Emergent Distrib Syst 33(5):460\u2013473","journal-title":"Int J Parallel Emergent Distrib Syst"},{"key":"9834_CR31","first-page":"93","volume":"1","author":"P Saeedi","year":"2009","unstructured":"Saeedi P, Sorensen S (2009) An algorithmic approach to generate after-disaster test fields for search and rescue agents. Proc World Congress Eng 1:93\u201398","journal-title":"Proc World Congress Eng"},{"issue":"7024","key":"9834_CR32","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1038\/nature03248","volume":"433","author":"C Song","year":"2005","unstructured":"Song C, Havlin S, Makse HA (2005) Self-similarity of complex networks. Nature 433(7024):392\u2013395","journal-title":"Nature"},{"issue":"4","key":"9834_CR33","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1038\/nphys266","volume":"2","author":"C Song","year":"2006","unstructured":"Song C, Havlin S, Makse HA (2006) Origins of fractality in the growth of complex networks. Nat Phys 2(4):275","journal-title":"Nat Phys"},{"key":"9834_CR34","doi-asserted-by":"publisher","first-page":"17628","DOI":"10.1038\/srep17628","volume":"5","author":"YQ Song","year":"2015","unstructured":"Song YQ, Liu JL, Yu ZG, Li BG (2015) Multifractal analysis of weighted networks by a modified sandbox algorithm. Sci Rep 5:17628","journal-title":"Sci Rep"},{"key":"9834_CR35","doi-asserted-by":"crossref","unstructured":"Stadler PF (2002) Fitness landscapes. Biological evolution and statistical physics lecture notes in physics 585:183\u2013204","DOI":"10.1007\/3-540-45692-9_10"},{"issue":"3","key":"9834_CR36","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1016\/j.ejor.2005.01.066","volume":"174","author":"T St\u00fctzle","year":"2006","unstructured":"St\u00fctzle T (2006) Iterated local search for the quadratic assignment problem. Eur J Oper Res 174(3):1519\u20131539","journal-title":"Eur J Oper Res"},{"issue":"4\u20135","key":"9834_CR37","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/S0167-8191(05)80147-4","volume":"17","author":"\u00c9 Taillard","year":"1991","unstructured":"Taillard \u00c9 (1991) Robust taboo search for the quadratic assignment problem. Parallel Comput 17(4\u20135):443\u2013455","journal-title":"Parallel Comput"},{"key":"9834_CR38","doi-asserted-by":"crossref","unstructured":"Thomson SL, Verel S, Ochoa G, Veerapen N, Cairns D (2018a) Multifractality and dimensional determinism in local optima networks. In: Proceedings of the genetic and evolutionary computation conference, pp 371\u2013378","DOI":"10.1145\/3205455.3205472"},{"key":"9834_CR39","doi-asserted-by":"crossref","unstructured":"Thomson SL, Verel S, Ochoa G, Veerapen N, McMenemy P, (2018b) On the fractal nature of local optima networks. In: Liefooghe A, L\u00f3pez-Ib\u00e1\u00f1ez M (eds) Evolutionary computation in combinatorial optimization. EvoCOP 2018, Lecture Notes in Computer Science, vol 10782. Springer, Cham","DOI":"10.1007\/978-3-319-77449-7_2"},{"issue":"1","key":"9834_CR40","first-page":"78","volume":"44","author":"LK Uahabi","year":"2017","unstructured":"Uahabi LK, Atounti M (2017) New approach to the calculation of fractal dimension of the lungs. Ann Univ Craiova-Math Comput Sci Ser 44(1):78\u201386","journal-title":"Ann Univ Craiova-Math Comput Sci Ser"},{"key":"9834_CR41","doi-asserted-by":"crossref","unstructured":"Verel S, Daolio F, Ochoa G, Tomassini M (2011) Local optima networks with escape edges. In: International conference on artificial evolution (Evolution Artificielle). Springer, pp 49\u201360","DOI":"10.1007\/978-3-642-35533-2_5"},{"key":"9834_CR42","doi-asserted-by":"crossref","unstructured":"Verel S, Daolio F, Ochoa G, Tomassini M (2018) Sampling local optima networks of large combinatorial search spaces: The qap case. In: International conference on parallel problem solving from nature. Springer, pp 257\u2013268","DOI":"10.1007\/978-3-319-99259-4_21"},{"issue":"2","key":"9834_CR43","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jtbi.1993.1120","volume":"163","author":"ED Weinberger","year":"1993","unstructured":"Weinberger ED, Stadler PF (1993) Why some fitness landscapes are fractal. J Theor Biol 163(2):255\u2013275","journal-title":"J Theor Biol"},{"issue":"1","key":"9834_CR44","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1109\/MAP.2003.1189650","volume":"45","author":"DH Werner","year":"2003","unstructured":"Werner DH, Ganguly S (2003) An overview of fractal antenna engineering research. IEEE Antennas Propag Mag 45(1):38\u201357","journal-title":"IEEE Antennas Propag Mag"},{"key":"9834_CR45","doi-asserted-by":"crossref","unstructured":"Zelinka I, Zmeskal O, Saloun P (2014) Fractal analysis of fitness landscapes. In: Recent advances in the theory and application of fitness landscapes, Springer, pp 427\u2013456","DOI":"10.1007\/978-3-642-41888-4_15"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-020-09834-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-020-09834-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-020-09834-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T13:45:22Z","timestamp":1654609522000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-020-09834-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,19]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["9834"],"URL":"https:\/\/doi.org\/10.1007\/s11047-020-09834-y","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2020,12,19]]},"assertion":[{"value":"3 December 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}