Randomness in Local Optima Network Sampling

Thomson, Sarah L.; Veerapen, Nadarajen; Ochoa, Gabriela; van den Berg, Daan

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.

Citation

Thomson, S. L., Veerapen, N., Ochoa, G., & van den Berg, D. (2023, July). Randomness in Local Optima Network Sampling. Presented at GECCO '23, Lisbon, Portugal

• Presentation Conference Type: Conference Paper (published)
• Conference Name: GECCO '23
• Start Date: Jul 15, 2023
• End Date: Jul 19, 2023
• Acceptance Date: May 1, 2023
• Online Publication Date: Jul 24, 2023
• Publication Date: 2023-07
• Deposit Date: Aug 16, 2023
• Publicly Available Date: Aug 17, 2023
• Publisher: Association for Computing Machinery (ACM)
• Pages: 2099-2107
• Book Title: GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation
• ISBN: 9798400701207
• DOI: https://doi.org/10.1145/3583133.3596309