Skip to main content

Research Repository

Advanced Search

Fractal Dimension and Perturbation Strength: A Local Optima Networks View

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

Authors

Gabriela Ochoa

Sébastien Verel



Contributors

Günter Rudolph
Editor

Anna V. Kononova
Editor

Hernán Aguirre
Editor

Pascal Kerschke
Editor

Gabriela Ochoa
Editor

Tea Tušar
Editor

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 combinatorial 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.

Citation

Thomson, S. L., Ochoa, G., & Verel, S. (2022, September). Fractal Dimension and Perturbation Strength: A Local Optima Networks View

Presentation Conference Type Conference Paper (published)
Start Date Sep 10, 2022
End Date Sep 14, 2022
Acceptance Date Jun 15, 2022
Online Publication Date Aug 13, 2022
Publication Date 2022
Deposit Date Aug 16, 2023
Publisher Springer
Pages 562-574
Series Title Lecture Notes in Computer Science
Series Number 13398
Book Title Parallel Problem Solving from Nature – PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part I
ISBN 9783031147135
DOI https://doi.org/10.1007/978-3-031-14714-2_39
Keywords Local Optima Network, Fractal dimension, Quadratic Assignment Problem, QAP, Iterated local , Perturbation strength, Fitness landscapes
Public URL http://researchrepository.napier.ac.uk/Output/3169631



You might also like



Downloadable Citations