Fractal Dimension and Perturbation Strength: A Local Optima Networks View

Citation

Thomson SL, Ochoa G & Verel S (2022) Fractal Dimension and Perturbation Strength: A Local Optima Networks View. In: Rudolph G, Kononova AV, Aguirre H, Kerschke P, Ochoa G & Tušar T (eds.) Parallel Problem Solving from Nature. Lecture Notes in Computer Science, 13398. Parallel Problem Solving from Nature – PPSN XVII 17th International Conference, PPSN 2022, Dortmund, Germany, 10.09.2022-14.09.2022. Cham, Switzerland: Springer, pp. 562-574. https://doi.org/10.1007/978-3-031-14714-2_39

Abstract
We study the effect of varying perturbation strength on the fractal dimensions of Quadratic Assignment Problem (QAP) fitness landscapes induced by iterated local search (ILS). Fitness landscapes are represented as Local Optima Networks (LONs), which are graphs mapping algorithm search connectivity in a landscape. LONs are constructed for QAP instances and fractal dimension measurements taken from the networks. Thereafter, the interplay between perturbation strength, LON fractal dimension, and algorithm difficulty on the underlying combina-torial problems is analysed. The results show that higher-perturbation LONs also have higher fractal dimensions. ILS algorithm performance prediction using fractal dimension features may benefit more from LONs formed using a high perturbation strength; this model configuration enjoyed excellent performance. Around half of variance in Robust Taboo Search performance on the data-set used could be explained with the aid of fractal dimension features.

Keywords
Local Optima Network; Fractal Dimension; Quadratic Assignment Problem; QAP; Iterated Local Search; Perturbation Strength; Fitness Land- scapes

People

Professor Gabriela Ochoa

Professor, Computing Science