Local Optima Networks of the Quadratic Assignment Problem
  Using a recently proposed model for combinatorial landscapes, Local Optima
Networks (LON), we conduct a thorough analysis of two types of instances of the
Quadratic Assignment Problem (QAP). This network model is a reduction of the
landscape in which the nodes correspond to the local optima, and the edges
account for the notion of adjacency between their basins of attraction. The
model was inspired by the notion of 'inherent network' of potential energy
surfaces proposed in physical-chemistry. The local optima networks extracted
from the so called uniform and real-like QAP instances, show features clearly
distinguishing these two types of instances. Apart from a clear confirmation
that the search difficulty increases with the problem dimension, the analysis
provides new confirming evidence explaining why the real-like instances are
easier to solve exactly using heuristic search, while the uniform instances are
easier to solve approximately. Although the local optima network model is still
under development, we argue that it provides a novel view of combinatorial
landscapes, opening up the possibilities for new analytical tools and
understanding of problem difficulty in combinatorial optimization.
