A study of NK landscapes' basins and local optima networks
A study of NK landscapes' basins and local optima networks
复制标题
DOI：
10.1145/1389095.1389204
复制
发表时间：
2008-07
期刊：
影响因子：
--
通讯作者：
G. Ochoa;M. Tomassini;S. Vérel;Christian Darabos
中科院分区：
文献类型：
--
作者：
G. Ochoa;M. Tomassini;S. Vérel;Christian Darabos
我们通过调整针对能量表面提出的固有网络的概念来提出组合适应性景观的网络表征（Doye，2002）。我们以$ NK $景观为例的著名家族为例。在我们的情况下，固有的网络是顶点是所有局部最大值的图形，边缘表示两个最大值之间的盆地邻近。我们在代表性的小型NK景观实例上详尽地提取了此类网络，并表明它们是“小世界”。但是，最大值不是随机的，因为它们的聚类系数比相应的随机图大得多。此外，学位分布接近指数级而不是泊松人。我们还描述了吸引力盆地的性质及其与局部最大值网络的关系。
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.