Tomassini Marco, Vérel Sébastien, Ochoa Gabriela
Information Systems Institute, HEC, University of Lausanne, Switzerland.
Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Dec;78(6 Pt 2):066114. doi: 10.1103/PhysRevE.78.066114. Epub 2008 Dec 24.
We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces. We use the well-known family of NK landscapes as an example. In our case the inherent network is the graph whose vertices represent the local maxima in the landscape, and the edges account for the transition probabilities between their corresponding basins of attraction. We exhaustively extracted such networks on representative NK landscape instances, and performed a statistical characterization of their properties. We found that most of these network properties are related to the search difficulty on the underlying NK landscapes with varying values of K .
我们通过改编用于能量表面的固有网络概念，提出了一种组合适应度景观的网络表征方法。我们以著名的NK景观族为例。在我们的案例中，固有网络是这样一个图，其顶点代表景观中的局部最大值，边表示其相应吸引盆之间的转移概率。我们在具有代表性的NK景观实例上详尽地提取了此类网络，并对其属性进行了统计表征。我们发现，这些网络的大多数属性都与具有不同K值的基础NK景观上的搜索难度相关。
