Skip to main content

Research Repository

Advanced Search

Multifractality and dimensional determinism in local optima networks

Thomson, Sarah L.; Verel, Sébastien; Ochoa, Gabriela; Veerapen, Nadarajen; Cairns, David

Authors

Sébastien Verel

Gabriela Ochoa

Nadarajen Veerapen

David Cairns



Abstract

We conduct a study of local optima networks (LONs) in a search space using fractal dimensions. The fractal dimension (FD) of these networks is a complexity index which assigns a non-integer dimension to an object. We propose a fine-grained approach to obtaining the FD of LONs, using the probabilistic search transitions encoded in LON edge weights. We then apply multi-fractal calculations to LONs for the first time, comparing with mono-fractal analysis. For complex systems such as LONs, the dimensionality may be different between two sub-systems and multi-fractal analysis is needed. Here we focus on the Quadratic Assignment Problem (QAP), conducting fractal analyses on sampled LONs of reasonable size for the first time. We also include fully enumerated LONs of smaller size. Our results show that local optima spaces can be multi-fractal and that valuable information regarding probabilistic self-similarity is encoded in the edge weights of local optima networks. Links are drawn between these phenomena and the performance of two competitive metaheuristic algorithms.

Presentation Conference Type Conference Paper (Published)
Conference Name GECCO '18: Genetic and Evolutionary Computation Conference
Start Date Jul 15, 2018
End Date Jul 19, 2018
Online Publication Date Jul 2, 2018
Publication Date 2018
Deposit Date Aug 16, 2023
Publisher Association for Computing Machinery (ACM)
Pages 371-378
Book Title GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference
ISBN 9781450356183
DOI https://doi.org/10.1145/3205455.3205472
Keywords fractal dimension, quadratic assignment problem, fitness landscapes, local optima networks