The fractal geometry of fitness landscapes at the local optima level

Thomson, Sarah L.; Ochoa, Gabriela; Verel, Sébastien

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.

Citation

Thomson, S. L., Ochoa, G., & Verel, S. (2022). The fractal geometry of fitness landscapes at the local optima level. Natural Computing, 21(2), 317-333. https://doi.org/10.1007/s11047-020-09834-y

• Journal Article Type: Article
• Acceptance Date: Dec 3, 2020
• Online Publication Date: Dec 19, 2020
• Publication Date: 2022-06
• Deposit Date: Aug 16, 2023
• Publicly Available Date: Aug 17, 2023
• Journal: Natural Computing
• Print ISSN: 1567-7818
• Electronic ISSN: 1572-9796
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 21
• Issue: 2
• Pages: 317-333
• DOI: https://doi.org/10.1007/s11047-020-09834-y
• Keywords: Fitness landscapes, Fractal analysis, Local optima networks
• Public URL: http://researchrepository.napier.ac.uk/Output/3169642