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

Détails

ID Serval
serval:BIB_C7E11819C37E
Type
Article: article d'un périodique ou d'un magazine.
Collection
Publications
Institution
Titre
Complex network analysis of the energy landscape of the low autocorrelation binary sequences problem
Périodique
Physica A: Statistical mechanics and its applications
Auteur⸱e⸱s
Tomassini Marco
Statut éditorial
Publié
Date de publication
09/01/2021
Volume
577
Pages
126089
Langue
anglais
Résumé
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.
Création de la notice
21/06/2021 10:45
Dernière modification de la notice
22/06/2021 6:37
Données d'usage