Stalling in Space: Attractor Analysis for any Algorithm

Thomson, Sarah L.; Renau, Quentin; Vermetten, Diederick; Hart, Emma; van Stein, Niki; Kononova, Anna V.

Abstract

Network-based representations of fitness landscapes have grown in popularity in the past decade; this is probably because of growing interest in explainability for optimisation algorithms. Local optima networks (LONs) have been especially dominant in the literature and capture an approximation of local optima and their connectivity in the landscape. However, thus far, LONs have been constructed according to a strict definition of what a local optimum is: the result of local search. Many evolutionary approaches do not include this, however. Popular algorithms such as CMA-ES have therefore never been subject to LON analysis. Search trajectory networks (STNs) offer a possible alternative: nodes can be any search space location. However, STNs are not typically modelled in such a way that models temporal stalls: that is, a region in the search space where an algorithm fails to find a better solution over a defined period of time. In this work, we approach this by systematically analysing a special case of STN which we name attractor networks. These offer a coarse-grained view of algorithm behaviour with a singular focus on stall locations. We construct attractor networks for CMA-ES, differential evolution, and random search for 24 noiseless black-box opti-misation benchmark problems. The properties of attractor networks are systematically explored. They are also visualised and compared to traditional LONs and STN models. We find that attractor networks facilitate insights into algorithm behaviour which other models cannot, and we advocate for the consideration of attractor analysis even for algorithms which do not include local search.

Citation

Thomson, S. L., Renau, Q., Vermetten, D., Hart, E., van Stein, N., & Kononova, A. V. (2025, April). Stalling in Space: Attractor Analysis for any Algorithm. Paper presented at EvoStar 2025, Trieste, Italy

• Presentation Conference Type: Conference Paper (unpublished)
• Conference Name: EvoStar 2025
• Start Date: Apr 23, 2025
• End Date: Apr 25, 2025
• Acceptance Date: Jan 10, 2025
• Deposit Date: Feb 3, 2025
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Keywords: fitness landscape; local optima networks; search trajectory networks
• Public URL: http://researchrepository.napier.ac.uk/Output/4105662
• External URL: https://www.evostar.org/2025/