Local Optima Networks of NK Landscapes with and without Neutrality

Description

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. In further work, we extended this formalism to neutral fitness landscapes, which are extremely common in difficult combinatorial search spaces. By using two known neutral variants of the NK family (i.e.NK_p and NK_q) in which the amount of neutrality can be tuned by a parameter, we show that our new definitions of the optima networks and the associated basins are coherent with the previous definitions for the non-neutral case. Moreover, our empirical study and statistical analysis show that the features of neutral landscapes interpolate smoothly between landscapes with maximum neutrality and non-neutral ones. We found some unknown structural differences between the two studied families of neutral landscapes. But overall, the network features studied confirmed that neutrality in a landscape may enhance heuristic search. The methodologies introduced here should be useful in the future to design new search heuristics or modifications to existing ones such that the configuration space can be searched more effectively.

Additional details