论文标题
低自相关二进制序列问题的能量格局的复杂网络分析
Complex Networks Analysis of the Energy Landscape of the Low Autocorrelation Binary Sequences Problem
论文作者
论文摘要
我们提供了低自相关二进制序列问题的能源景观结构的最新视图，这是$ NP $ -HARD类的典型代表。为了研究感兴趣的景观特征，我们通过详尽地提取最高$ 24 $的问题大小的优化图来使用本地Optima网络方法。几个指标用于表征网络：Optima的数量和类型，Optima盆地结构，程度和强度分布，最短的全局最佳路径以及Optima的随机步行中心性。综上所述，这些指标为低自相关二进制序列问题的难度提供了定量和连贯的解释，并提供了可以通过对此问题的优化启发式方法来利用的信息，以及对于具有类似配置空间结构的许多其他问题。
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.
