Conference Proceeding

On the Fractal Nature of Local Optima Networks


Thomson SL, Verel S, Ochoa G, Veerapen N & McMenemy P (2018) On the Fractal Nature of Local Optima Networks. In: Liefooghe A & López-Ibáñez M (eds.) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2018.. Lecture Notes in Computer Science, 10782. EvoCOP 2018 - The 18th European Conference on Evolutionary Computation in Combinatorial Optimisation, Parma, Italy, 04.04.2018-06.04.2018. Cham, Switzerland: Springer, pp. 18-33.

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.

Combinatorial Fitness Landscapes; Local Optima Networks; Fractal Analysis; NK Landscapes

FundersThe Leverhulme Trust and Engineering and Physical Sciences Research Council
Title of seriesLecture Notes in Computer Science
Number in series10782
Publication date31/12/2018
Publication date online03/03/2018
Place of publicationCham, Switzerland
ISSN of series0302-9743
ConferenceEvoCOP 2018 - The 18th European Conference on Evolutionary Computation in Combinatorial Optimisation
Conference locationParma, Italy

Research centres/groups