On the Fractal Nature of Local Optima Networks

Thomson, Sarah L.; Verel, Sébastien; Ochoa, Gabriela; Veerapen, Nadarajen; McMenemy, Paul

Abstract

A Local Optima Network represents fitness landscape connectivity within the space of local optima as a mathematical graph. In certain other complex networks or graphs there have been recent observations made about inherent self-similarity. An object is said to be self-similar if it shows the same patterns when measured at different scales; another word used to convey self-similarity is fractal. The fractal dimension of an object captures how the detail observed changes with the scale at which it is measured, with a high fractal dimension being associated with complexity. We conduct a detailed study on the fractal nature of the local optima networks of a benchmark combinatorial optimisation problem (NK Landscapes). The results draw connections between fractal characteristics and performance by three prominent metaheuristics: Iterated Local Search, Simulated Annealing, and Tabu Search.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: 18th European Conference: EvoCOP 2018
• Start Date: Apr 4, 2018
• End Date: Apr 6, 2018
• Online Publication Date: Mar 3, 2018
• Publication Date: 2018
• Deposit Date: Aug 16, 2023
• Publisher: Springer
• Pages: 18-33
• Series Title: Lecture Notes in Computer Science
• Series Number: 10782
• Book Title: Evolutionary Computation in Combinatorial Optimization. EvoCOP 2018
• ISBN: 978-3-319-77448-0
• DOI: https://doi.org/10.1007/978-3-319-77449-7_2
• Keywords: Combinatorial fitness landscapes, Local optima networks, Fractal analysis, NK Landscapes
• Additional Information: An erratum to this publication is available online at https://doi.org/10.1007/978-3-319-77449-7_13