Subfunction Structure Matters: A New Perspective on Local Optima Networks

Thomson, Sarah L.; Przewozniczek, Michal W.

Abstract

Local optima networks (LONs) capture fitness landscape information. They are typically constructed in a black-box manner; information about the problem structure is not utilised. This also applies to the analysis of LONs: knowledge about the problem, such as interaction between variables, is not considered. We challenge this status-quo with an alternative approach: we consider how LON analysis can be improved by incorporating subfunction-based information this can either be known a-priori or learned during search. To this end, LONs are constructed for several benchmark pseudo-boolean problems using three approaches: firstly, the standard algorithm ; a second algorithm which uses deterministic grey-box crossover; and a third algorithm which selects perturbations based on learned information about variable interactions. Metrics related to subfunction changes in a LON are proposed and compared with metrics from previous literature which capture other aspects of a LON. Incorporating problem structure in LON construction and analysing it can bring enriched insight into optimisation dynamics. Such information may be crucial to understanding the difficulty of solving a given problem with state-of-the-art linkage learning optimisers. In light of the results, we suggest incorporation of problem structure as an alternative paradigm in landscape analysis for problems with known or suspected subfunction structure.

Citation

Thomson, S. L., & Przewozniczek, M. W. (2025, July). Subfunction Structure Matters: A New Perspective on Local Optima Networks. Presented at Genetic and Evolutionary Computation Conference (GECCO 2025), Málaga, Spain

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Genetic and Evolutionary Computation Conference (GECCO 2025)
• Start Date: Jul 14, 2025
• End Date: Jul 18, 2025
• Acceptance Date: Mar 19, 2025
• Deposit Date: Apr 11, 2025
• Peer Reviewed: Peer Reviewed
• Keywords: fitness landscape analysis; local optima networks; combinatorial optimization; visualization
• Public URL: http://researchrepository.napier.ac.uk/Output/4237989
• Publisher URL: https://dl.acm.org/conference/gecco
• External URL: http://gecco-2025.sigevo.org/HomePage