Skip to main content

Research Repository

Advanced Search

On the Fractal Nature of Local Optima Networks

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


Sébastien Verel

Gabriela Ochoa

Nadarajen Veerapen

Paul McMenemy


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
Keywords Combinatorial fitness landscapes, Local optima networks, Fractal analysis, NK Landscapes
Additional Information An erratum to this publication is available online at