A Study of NK Landscapes' Basins and Local Optima Networks

Details A Study of NK Landscapes' Basins and Local Optima Networks A Study of NK Landscapes' Basins and Local Optima Networks

2008-10-20

arxiv.org/abs/0810.3484v1

Genetic And Evolutionary Computation Conference, Atlanta : \'Etats-Unis d'Am\'erique (2008)

Computer Science

Neural and Evolutionary Computing

best paper nomination

Scientific paper

10.1145/1389095.1389204

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.

Affiliated with

Also associated with

No associations

Rating

A Study of NK Landscapes' Basins and Local Optima Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Study of NK Landscapes' Basins and Local Optima Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Study of NK Landscapes' Basins and Local Optima Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-265310