Conference Proceeding

Multifractality and Dimensional Determinism in Local Optima Networks



Thomson S, Verel S, Ochoa G, Veerapen N & Cairns D (2018) Multifractality and Dimensional Determinism in Local Optima Networks. In: Proceedings of the Genetic and Evolutionary Computation Conference 2018. 2018 Genetic and Evolutionary Computation Conference (GECCO 2018), Kyoto, Japan, 15.07.2018-19.07.2018. New York: ACM, pp. 371-378.;

We conduct a study of networks of local optimas 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 stochastic 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.

Fitness Landscapes; Quadratic Assignment Problem; Local Optima Networks; Fractal Dimension

Publication date31/12/2018
Publication date online31/07/2018
Publisher URL
Place of publicationNew York
Conference2018 Genetic and Evolutionary Computation Conference (GECCO 2018)
Conference locationKyoto, Japan

People (2)


Dr David Cairns

Dr David Cairns

Lecturer, Computing Science

Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science

Research centres/groups