Dr Sarah L. Thomson S.Thomson4@napier.ac.uk
Lecturer
Günter Rudolph
Editor
Anna V. Kononova
Editor
Hernán Aguirre
Editor
Pascal Kerschke
Editor
Gabriela Ochoa
Editor
Tea Tušar
Editor
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.
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 |
The Easiest Hard Problem: Now Even Easier
(2024)
Presentation / Conference Contribution
Channel Configuration for Neural Architecture: Insights from the Search Space
(2023)
Presentation / Conference Contribution
From Fitness Landscapes to Explainable AI and Back
(2023)
Presentation / Conference Contribution
Randomness in Local Optima Network Sampling
(2023)
Presentation / Conference Contribution
Universally Hard Hamiltonian Cycle Problem Instances
(2022)
Presentation / Conference Contribution
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search