Source-linked AI summary
A Study of NK Landscapes' Basins and Local Optima Networks
Gabriela Ochoa, Marco Tomassini, Sébastien Verel, Christian Darabos
TL;DR
The paper asks how local optima and their attraction basins are structurally organized in combinatorial fitness landscapes. It adapts inherent-network analysis to NK landscapes and exhaustively studies small instances. The resulting maxima networks are small-world but nonrandom, with exponential-like degree distributions and systematic basin relationships.
Problem
The paper seeks structural insights into local-optimum connectivity and basin characteristics in combinatorial landscapes, features relevant to heuristic-search effectiveness.
Method
The study maps NK configurations to local optima using exhaustive best-improvement search, defines attraction basins, and connects optima whose basins are adjacent.
Results
The maxima networks are small-world but nonrandom, with clustering coefficients above corresponding random graphs and degree distributions close to exponential rather than Poissonian.
Takeaways & Limitations
Basin sizes are approximately exponentially distributed, shrink for the global maximum as K increases, and strongly correlate with maxima degree.
Takeaways & Limitations
The findings require confirmation on larger NK instances and do not yet cover landscapes containing neutrality.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
The paper adapts inherent-network analysis to study local-optimum organization and basin connectivity in combinatorial landscapes, using exhaustive small NK instances. It aims to provide structural insights relevant to heuristic-search effectiveness and reports this as an initial network-analysis treatment of fitness landscapes.
- Motivation: Heuristic-search effectiveness depends partly on landscape features, especially the number and distribution of local optima.Understanding these features may help predict performance and improve meta-heuristic design.
- Motivation: Local optima often cluster near the global optimum and near one another, forming a central massif or big-valley structure.This globally convex organization has been observed in NK landscapes and several combinatorial optimization problems.
- Approach: The study maps NK landscapes onto networks and analyzes complete networks for representative small instances.The approach is inspired by Doye’s energy-landscape networks and complex-network analysis.
- Contribution: The paper presents its network characterization as the first use, to the authors’ knowledge, of network-analysis techniques for combinatorial fitness landscapes and problem difficulty.The work focuses particularly on local-optimum connectivity and basin characteristics.
2. COMPLEX NETWORKS
Complex-network analysis characterizes systems through local connectivity, global separation, and degree distributions. Small-world networks combine high clustering with short paths, while heavy-tailed degree distributions indicate hubs.
- Network measures: The clustering coefficient C measures local density, while average shortest path length l measures global separation.These statistics quantify complementary aspects of network structure.
- Small-world networks: Small-world topology combines high node clustering with short path lengths.Such networks are neither completely ordered nor completely random.
- Degree distributions: Heavy-tailed degree distributions place most nodes below average degree while a small fraction of hubs have many connections.Power-law behavior gives an asymptotic form p(k) ∼ k^-α.
3. LANDSCAPES AS NETWORKS
The paper converts discrete NK landscapes into local-optima networks by assigning configurations to basins through best-improvement search and linking adjacent basins. This operationalizes an inherent-network view for combinatorial landscapes.
- Inherent networks: Doye’s inherent-structure mapping assigns each configuration to the minimum reached by steepest descent, partitioning the landscape into attraction basins.The paper adapts this energy-landscape abstraction to combinatorial fitness landscapes.
- Landscape mapping: In the NK adaptation, vertices are local maxima found by exhaustive best-improvement search from every configuration.The landscapes are discrete and finite rather than continuous physical energy surfaces.
- NK representation: NK landscapes use binary strings of length N with 1-bit-flip neighborhoods of size N and no neutrality between neighboring solutions.The search space therefore contains 2^N configurations.
- Definitions and algorithms: A local optimum is a solution whose every neighboring solution has lower fitness.The LocalSearch procedure repeats improving moves until reaching such a solution.
- Basins of attraction: A basin of attraction contains all configurations that LocalSearch maps to the same local optimum.Its size is the cardinality of that configuration set.
- Local optima network: The local optima network connects two optima when at least one pair of 1-bit-apart configurations lies in their respective basins.Thus, network edges encode basin adjacency rather than direct movement between optima.
4.1 Experimental Setting
The study examines adjacent-neighborhood NK landscapes across increasing interaction strengths using exhaustive networks from small instances. Network statistics average results over 30 independent instances for each parameter pair.
- Experimental Setting: NK landscapes vary from smooth to rugged as K increases from 0 to N −1.N is the binary genotype length, while K counts genes influencing a particular gene.
- Experimental Setting: The experiments use the adjacent-neighborhood model and leave the random-neighborhood model for future analysis.Prior work found no significant differences between the models in selected global landscape properties.
- Experimental Setting: 30 independent instances are explored for each N and K pair, with N = 16, 18 and K = 2, 4, 6, ..., N −2, N −1.These are the largest values of N the authors could analyze exhaustively with reasonable computational resources.
4.2 General Network Statistics
Across the examined NK landscapes, maxima networks combine short global separation with strong local clustering, while their size and connectivity vary systematically with K.
- 30 random landscapes were averaged for N = 16, 18 and even K values, with K = N −1 also reported.The table summarizes mean vertices, mean edges, clustering, random-graph clustering, path length, degree, and assortativity.
- The number of local optima, and therefore search difficulty, increases with K.
- O(log nv) growth in mean shortest path length identifies the maxima networks as small worlds for all examined K values.
- Clustering coefficients remain well above equivalent random graphs, indicating local structure in the maxima networks.
- Mean degree first increases with K and then decreases for K > 8, while assortativity remains very small.The low assortativity indicates almost no degree correlation between neighboring nodes.
4.3 Degree Distributions
The maxima networks’ degree distributions are not power-law or Poissonian; across NK instances they are approximately exponential, with deviations near finite-size cutoffs and stronger fluctuations in small, easy landscapes.
- The degree distribution p(k) gives the probability that a randomly chosen node has degree k, while random graphs have Poissonian p(k).
- Power-law degree distributions are ruled out because the log-log plots are not straight over a sizable degree range.
- Most curves are approximately straight on linear-log plots, supporting exponential fits of the form p(k) = (1/z)e^-k/z, where z is the mean degree.The fit worsens near the finite degree cutoff.
- N = 16, K = 4 instances show larger fluctuations and tails that decay faster than exponentially, indicating finite-size and parameter-dependent deviations.
- The exponential pattern persists as NK difficulty increases smoothly with K, unlike the power-law distributions reported for inherent energy-landscape networks.
4.4 Basins of Attraction
The study exhaustively characterizes attraction basins in small NK landscapes and relates their sizes to optimum fitness and local-optimum network degree. Basin-size distributions are approximately exponential, while higher-fitness and higher-degree maxima tend to have larger basins.
- Basin characterization: The authors exhaustively computed the size and number of all attraction basins for N = 16 and N = 18 across the studied K values.The analysis used representative NK landscape instances and connects basin properties to network features.
- Global optimum basin size vs. K: The global-optimum basin shrinks very quickly as K increases, making it harder for stochastic search to locate.This trend was observed for N = 16 and N = 18 across all studied K values.
- Number of basins of a given size: Basin-size distributions decay exponentially or faster for lower K and become closer to exponential for higher K.The distributions were estimated from cumulative basin counts for representative landscapes and regression fits.
- Fitness of local optima vs. basin sizes: Higher-fitness local maxima tend to have wider attraction basins, producing a clear positive correlation between optimum fitness and basin size.The relationship was evaluated across the studied N = 16 and N = 18 landscapes using correlation and regression analyses.
- Network degree and basin size: Maxima with higher network degree tend to have larger basins, linking basin accessibility to connectivity in the local-optima network.The reported correlation suggests that lower-K landscapes offer configurations with more neighbors in the same large basin.
5. CONCLUSIONS
The paper characterizes NK landscapes through networks whose nodes are local maxima and whose edges represent adjacency between their attraction basins. Exhaustive analyses of small instances find small-world, nonrandom maxima networks and systematic basin-size relationships, while larger and other landscape types remain for future study.
- Maxima networks: The maxima networks are small-worlds, with short average path lengths that scale logarithmically with graph size.The networks were exhaustively obtained for N = 16 and N = 18 across the specified K values.
- Maxima networks: The maxima networks are nonrandom: clustering coefficients exceed corresponding random-graph values, and degree distributions are closer to exponential than Poissonian.These structural properties distinguish the observed networks from random graphs.
- Attraction basins: Global-optimum basins become smaller as K increases, while basin-size distributions are approximately exponential across N and K.Larger basins at low K provide an indirect indication of increasing landscape randomness and difficulty at larger K.
- Attraction basins: Basin size is strongly positively correlated with maxima degree, supporting the maxima graph as a useful synthetic representation of the landscape.The conclusion connects network connectivity with the independently characterized attraction basins.
- Future work and scope: The findings require confirmation on larger NK instances and examination of other landscape types, including landscapes with neutrality.Exhaustive sampling becomes impractical for larger instances, motivating sampling or theoretical approaches.