Complex-network analysis of combinatorial spaces: The $NK$ landscape case

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces. We use the well-known family of $NK$ landscapes as an example. In our case the inherent network is the graph whose vertices represent the local maxima in the landscape, and the edges account for the transition probabilities between their corresponding basins of attraction. We exhaustively extracted such networks on representative $NK$ landscape instances, and performed a statistical characterization of their properties. We found that most of these network properties are related to the search difficulty on the underlying $NK$ landscapes with varying values of $K$.

Figure 1

HillClimbing algorithm.

Figure 2

Average with standard deviation of the distance (shortest path) between nodes (top), and of the path length to the optimum from all the other basins (bottom).

Figure 3

Cumulative probability distribution of the network weights $w_{ij}$ for outgoing edges with $j\ne i$ in log-log scale, for $N=16$ (top) and $N=18$ (bottom). Averages of 30 instances for each $N$ and $K$ are reported.

Figure 4

Average disparity, $Y_2$, of nodes with a given degree $K$, for $N=16$ (top) and $N=18$ (bottom). Average of 30 independent instances for each $N$ and $K$ are reported. The curve $1∕k$ is also reported to compare to a random case.

Figure 5

Average weight $w_{ii}$ according to the parameters $N$ and $K$.

Figure 6

Average with standard deviation (on 30 independent landscapes for each $N$ and $K$) of the mean sizes of the basins interiors.

Figure 7

Average value of the weights of incoming transitions into maxima nodes for $N=14$, 16, 18 and for whole $K$ interval.

Figure 8

Scatter plots of the sum of weights into basins vs the basin size in log-log scale for $N=18$ and four values of $K$: (a) $K=2$, (b) $K=2$, (c) $K=6$, (d) $K=12$. The regression line of each scatter plot is shown. The theoretical curves, under the hypothesis that the weights are proportional, to the size of basin are also given.

Figure 9

Average with standard deviation of the normalized size of the basin corresponding to the global maximum for each $K$ over 30 independent landscapes. The normalization is done with respect to the total size of the search space.

Figure 10

Cumulative distribution of the number of basins of a given size with regression line. A representative landscape with $N=18$ and $K=4$ is visualized. A lin-log scale is used.

Figure 11

Correlation coefficient $\overline{\rho }$ (bottom), and linear regression (top) for $N=18$ of the relationship between the basin size of optima and the cumulative number of nodes of a given (basin) size (in logarithmic scale: $\ln \left[p\left(s\right)\right]=\alpha +\beta s+ϵ$). The average and standard deviation values over 30 instances, are shown.

Figure 12

Correlation between the fitness of local optima and their corresponding basin sizes, for two representative instances with $N=18$, $K=4$ (top) and $K=8$ (bottom).