Randomness in Local Optima Network Sampling

Citation

Thomson S, Veerapen N, Ochoa G & van den Berg D (2023) Randomness in Local Optima Network Sampling. In: GECCO ’23 Companion: Genetic and Evolutionary Computation Conference Companion. GECCO '23, Lisbon (hybrid), 15.07.2023-19.07.2023. New York: ACM. https://doi.org/10.1145/3583133.3596309

Abstract
We consider statistical randomness in the construction of local optima networks (LONs) and conduct a preliminary and exploratory study into this. LONs capture a fitness landscape into network format: the nodes are local optima, and edges are heuristic search transitions between them. Problem instances from the benchmark quadratic assignment problem library are used in the analysis. LONs are constructed using an iterated local search (ILS) and several different random seeds. Metrics are computed from the networks and visualised to assess the effect of randomness. Algorithm performance models for ILS runtime are built using metrics of LONs constructed using different seeds and the results compared. The results show that some LON metrics seem consistent across seeds, while others vary substantially. Additionally, the quality of algorithm performance models using LON metrics as predictors can differ depending on randomness. Finally, LON metrics associated with separate seeds can lead to different algorithm configuration recommendations for the same instance.

Keywords
Fitness Landscapes; Quadratic Assignment Problem; Local Optima Networks; Iterated Local Search

Notes
Output Status: Forthcoming

People

Professor Gabriela Ochoa

Professor, Computing Science