# Subfunction Structure Matters: A New Perspective on Local Optima Networks

arXiv: https://arxiv.org/abs/2504.17799 · HTML: https://mlsanity.com/paper/2504.17799/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 44 references that are in the map.
- First posted on arXiv 17 Apr 2025.

## Builds on (most cited first, 1 of 1)

- [Generalizing and Unifying Gray-box Combinatorial Optimization Operators](https://mlsanity.com/paper/2407.06742/) (2024)

## Abstract (arXiv)

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.