The Fractal Geometry of Fitness Landscapes at the Local Optima Level

Citation

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. https://doi.org/10.1007/s11047-020-09834-y

Abstract
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.

Keywords
Fitness landscapes; Fractal analysis; Local optima networks

Journal
Natural Computing: Volume 21, Issue 2

People

Professor Gabriela Ochoa

Professor, Computing Science