Article

The Fractal Geometry of Fitness Landscapes at the Local Optima Level

Citation

Thomson SL, Ochoa G & Verel S (2020) The Fractal Geometry of Fitness Landscapes at the Local Optima Level. Natural Computing. 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

Notes
Output Status: Forthcoming/Available Online

Journal
Natural Computing

StatusIn Press
Publication date online19/12/2020
Date accepted by journal03/12/2020
URLhttp://hdl.handle.net/1893/32149
ISSN1567-7818
eISSN1572-9796

Research centres/groups