Scalable Local Optima Networks for Continuous Search Spaces

Abstract

Local optima networks (LONs) are a compact graph-based visualisation and characterisation approach to represent the fitness land scape of an optimisation problem. LONs are most frequently generated for combinatorial problems, where neighbourhoods can be crisply defined. A few approaches exist for continuous spaces, notably using derivatives-based local search approaches and basin-hopping, or by discretising the continuous space via gridding. Here we propose a new approach. Using a set of quasi-random samples from the search space, neighbourhoods are defined as balls around these locations, with basins and local optima identified by greedily traversing these sampled neighbourhoods, rather than calculating/approximating derivatives. One interpretation of such a formulation is that it approximates the LON induced by a (1 + λ)–Evolution Strategy (ES) with mutation from a ball. The proposed approach also allows the generation of LONs for problems with non-linear constraints, and discontinuous functions. We detail generation approaches and illustrate the effective landscapes for some different objective functions using both the proposed methodology and derivatives-based alternatives. We discuss computationally efficient implementation, and the computational budget gains observed using this approach for LON construction in continuous spaces — notably with regards to basin size estimation accuracy, and number of optima.