Directed plateau search for MAX-k-SAT

Andrew M. Sutton, Adele E. Howe, L. Darrell Whitley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

Local search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using aWalsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space. This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks. We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.

Original languageEnglish (US)
Title of host publicationProceedings of the 3rd Annual Symposium on Combinatorial Search, SoCS 2010
Pages90-97
Number of pages8
StatePublished - Dec 1 2010
Event3rd International Symposium on Combinatorial Search, SoCS 2010 - Atlanta, GA, United States
Duration: Jul 8 2010Jul 10 2010

Other

Other3rd International Symposium on Combinatorial Search, SoCS 2010
CountryUnited States
CityAtlanta, GA
Period7/8/107/10/10

Cite this