Local optima networks and the performance of iterated local search
  Local Optima Networks (LONs) have been recently proposed as an alternative
model of combinatorial fitness landscapes. The model compresses the information
given by the whole search space into a smaller mathematical object that is the
graph having as vertices the local optima and as edges the possible weighted
transitions between them. A new set of metrics can be derived from this model
that capture the distribution and connectivity of the local optima in the
underlying configuration space. This paper departs from the descriptive
analysis of local optima networks, and actively studies the correlation between
network features and the performance of a local search heuristic. The NK family
of landscapes and the Iterated Local Search metaheuristic are considered. With
a statistically-sound approach based on multiple linear regression, it is shown
that some LONs' features strongly influence and can even partly predict the
performance of a heuristic search algorithm. This study validates the
expressive power of LONs as a model of combinatorial fitness landscapes.
