Conference Proceeding

A study of NK landscapes' basins and local optima networks



Ochoa G, Tomassini M, Verel S & Darabos C (2008) A study of NK landscapes' basins and local optima networks. In: GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008. GECCO '08 - 10th annual conference on Genetic and evolutionary computation, Atlanta, GA, USA, 12.07.2008-16.07.2008. New York, NY, USA: ACM, pp. 555-562.;

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces (Doye, 2002). We use the well-known family of $NK$ landscapes as an example. In our case the inherent network is the graph where the vertices are all the local maxima and edges mean basin adjacency between two maxima. We exhaustively extract such networks on representative small NK landscape instances, and show that they are 'small-worlds'. However, the maxima graphs are not random, since their clustering coefficients are much larger than those of corresponding random graphs. Furthermore, the degree distributions are close to exponential instead of Poissonian. We also describe the nature of the basins of attraction and their relationship with the local maxima network.

Nominated for best paper.

Publication date31/12/2008
Publication date online31/07/2008
Related URLs
Publisher URL
Place of publicationNew York, NY, USA
ConferenceGECCO '08 - 10th annual conference on Genetic and evolutionary computation
Conference locationAtlanta, GA, USA

People (1)


Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science