I. Introduction
In a series of papers we introduced a novel representation for combinatorial landscapes that we called local optima network [1], [2], [3]. This is a view of landscapes derived from a previously proposed one for continuous energy landscapes by Doye [4], [5] but it has been modified and adapted to work for discrete combinatorial spaces. It is based on the idea of compressing the information given by the whole problem configuration space into a smaller mathematical object which is the graph having as vertices the optima configurations of the problem and as edges the possible weighted transitions between these optima. The methodology is intended to be a descriptive one in the first place; for example, some measures on the optima networks have been found to be related with problem difficulty. In the longer term, the methodology is expected to be useful for suggesting improvements in local search heuristics and perhaps even for suggesting new ones. In recent work we have studied by this method the family of Kauffman's -landscapes [6], for which we have shown that some optima network statistics can be related to the tunable difficulty of these landscapes. Moreover, since to obtain the local optima of the configuration space we need to explore the corresponding basins, the above graph is also a description of the basins and of their connectivity. In this way we have been able to find previously known properties of these basins, as well as new ones [2], [3]. However, although useful for classification purposes, the family of landscapes is a highly artificial one. For this reason, in the present paper we study the more realistic problem called the quadratic assignment problem (QAP). The quadratic assignment problem, as introduced by Koopmans and Beckmann [7] in 1957, is a combinatorial optimization problem which is known to be NP-hard [8]. This paper presents preliminary results of an exhaustive analysis of small instances' fitness landscapes by means of extracting the networks of local optima and evaluating their statistics.