The Fractal Geometry of Fitness Landscapes at the Local Optima Level



Thomson SL, Ochoa G & Verel S (2022) The Fractal Geometry of Fitness Landscapes at the Local Optima Level. Natural Computing, 21 (2), pp. 317-333.

A local optima network (LON) encodes local optima connectivity in the fitness landscape of a combinatorial optimisation problem. Recently, LONs have been studied for their fractal dimension. 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.

Fitness landscapes; Fractal analysis; Local optima networks

Natural Computing: Volume 21, Issue 2

Publication date30/06/2022
Publication date online19/12/2020
Date accepted by journal03/12/2020

People (2)


Professor Gabriela Ochoa
Professor Gabriela Ochoa

Professor, Computing Science

Dr Sarah Thomson
Dr Sarah Thomson

Lecturer in Computing Science, Computing Science and Mathematics - Division

Research centres/groups