Global Landscape Structure and the Random MAX-SAT Phase Transition

Détails

ID Serval
serval:BIB_161685FCC487
Type
Article: article d'un périodique ou d'un magazine.
Collection
Publications
Institution
Titre
Global Landscape Structure and the Random MAX-SAT Phase Transition
Périodique
PPSN 2020: Parallel Problem Solving from Nature – PPSN XVI
Auteur(s)
Ochoa Gabriela, Chicano Francisco, Tomassini Marco
Statut éditorial
Publié
Date de publication
02/09/2020
Peer-reviewed
Oui
Volume
12270
Pages
125-138
Langue
anglais
Résumé
We revisit the fitness landscape structure of random MAX-SAT instances, and address the question: what structural features change when we go from easy underconstrained instances to hard overconstrained ones? Some standard techniques such as autocorrelation analysis fail to explain what makes instances hard to solve for stochastic local search algorithms, indicating that deeper landscape features are required to explain the observed performance differences. We address this question by means of local optima network (LON) analysis and visualisation. Our results reveal that the number, size, and, most importantly, the connectivity pattern of local and global optima change significantly over the easy-hard transition. Our empirical results suggests that the landscape of hard MAX-SAT instances may feature sub-optimal funnels, that is, clusters of sub-optimal solutions where stochastic local search methods can get trapped.
Création de la notice
11/09/2020 11:04
Dernière modification de la notice
12/09/2020 5:20
Données d'usage