标题： 低自相关二元序列问题的能量景观的复杂网络分析 显示英文标题

标题： Complex Networks Analysis of the Energy Landscape of the Low Autocorrelation Binary Sequences Problem

摘要： 我们提供了低自相关二元序列问题能量景观结构的最新视图，这是$NP$-hard 类的一个典型代表。 为了研究感兴趣的景观特征，我们通过对于问题规模达到$24$的最优图的完全提取，使用局部最优网络方法。 用于描述网络的多个指标包括：最优解的数量和类型、最优解盆地结构、度数和强度分布、到达全局最优解的最短路径以及基于随机游走的最优解中心性。 这些指标综合起来，为低自相关二元序列问题的难度提供了定量且一致的解释，并提供了可以被优化启发式算法利用的信息，这对于该问题以及具有类似配置空间结构的其他一些问题都有帮助。 显示英文摘要

摘要： We provide an up-to-date view of the structure of the energy landscape of the low autocorrelation binary sequences problem, a typical representative of the $NP$-hard class. To study the landscape features of interest we use the local optima network methodology through exhaustive extraction of the optima graphs for problem sizes up to $24$. Several metrics are used to characterize the networks: number and type of optima, optima basins structure, degree and strength distributions, shortests paths to the global optima, and random walk-based centrality of optima. Taken together, these metrics provide a quantitative and coherent explanation for the difficulty of the low autocorrelation binary sequences problem and provide information that could be exploited by optimization heuristics for this problem, as well as for a number of other problems having a similar configuration space structure.