A Study of NK Landscapes' Basins and Local Optima Networks

Abstract

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces (Doye, 2002). We use the well-known family of $NK$ landscapes as an example. In our case the inherent network is the graph where the vertices are all the local maxima and edges mean basin adjacency between two maxima. We exhaustively extract such networks on representative small NK landscape instances, and show that they are 'small-worlds'. However, the maxima graphs are not random, since their clustering coefficients are much larger than those of corresponding random graphs. Furthermore, the degree distributions are close to exponential instead of Poissonian. We also describe the nature of the basins of attraction and their relationship with the local maxima network.

best paper nomination

References in corpus (1)

• Characterizing the network topology of the energy landscapes of atomic clusters

Cited by in corpus (15)

• Complex-network analysis of combinatorial spaces: The NK landscape case
• Local optima networks and the performance of iterated local search
• The Connectivity of NK Landscapes' Basins: A Network Analysis
• Benchmarking optimization algorithms for auto-tuning GPU kernels
• Centric selection: a way to tune the exploration/exploitation trade-off
• Impacts of Single-objective Landscapes on Multi-objective Optimization
• Fitness Landscape Footprint: A Framework to Compare Neural Architecture Search Problems
• Problem Complexity in Parallel Problem Solving
• Subfunction Structure Matters: A New Perspective on Local Optima Networks
• First-improvement vs. Best-improvement Local Optima Networks of NK Landscapes
• What can we learn from slow self-avoiding adaptive walks by an infinite radius search algorithm?
• Local Optima Networks of NK Landscapes with Neutrality
• Analyzing the Landscape of the Indicator-based Subset Selection Problem
• Hilbert curves for efficient exploratory landscape analysis neighbourhood sampling
• NK landscapes difficulty and Negative Slope Coefficient: How Sampling Influences the Results