Complex network analysis of the energy landscape of the low autocorrelation binary sequences problem

Details

Serval ID
serval:BIB_C7E11819C37E
Type
Article: article from journal or magazin.
Collection
Publications
Institution
Title
Complex network analysis of the energy landscape of the low autocorrelation binary sequences problem
Journal
Physica A: Statistical mechanics and its applications
Author(s)
Tomassini Marco
Publication state
Published
Issued date
09/01/2021
Volume
577
Pages
126089
Language
english
Abstract
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.
Create date
21/06/2021 10:45
Last modification date
22/06/2021 6:37
Usage data