Conference Proceeding

Global Landscape Structure and the Random MAX-SAT Phase Transition


Ochoa G, Chicano F & Tomassini M (2020) Global Landscape Structure and the Random MAX-SAT Phase Transition. In: Bäck T, Preuss M, Deutz A, Wang H, Doerr C, Emmerich M & Trautmann H (eds.) Parallel Problem Solving from Nature. Lecture Notes in Computer Science. PPSN 2020: Conference on Parallel Problem Solving from Nature, Leiden, The Netherlands, 05.09.2020-09.09.2020. Cham, Switzerland: Springer International Publishing, pp. 125-138.

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.

Title of seriesLecture Notes in Computer Science
Publication date31/12/2020
Publication date online02/09/2020
PublisherSpringer International Publishing
Place of publicationCham, Switzerland
ISSN of series0302-9743
ConferencePPSN 2020: Conference on Parallel Problem Solving from Nature
Conference locationLeiden, The Netherlands