Global Landscape Structure and the Random MAX-SAT Phase Transition

Details

Serval ID
serval:BIB_161685FCC487
Type
Article: article from journal or magazin.
Collection
Publications
Institution
Title
Global Landscape Structure and the Random MAX-SAT Phase Transition
Journal
PPSN 2020: Parallel Problem Solving from Nature – PPSN XVI
Author(s)
Ochoa Gabriela, Chicano Francisco, Tomassini Marco
Publication state
Published
Issued date
02/09/2020
Peer-reviewed
Oui
Volume
12270
Pages
125-138
Language
english
Abstract
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.
Create date
11/09/2020 11:04
Last modification date
12/09/2020 5:20
Usage data