Directed plateau search for MAX-k-SAT

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

Directed plateau search for MAX-k-SAT

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

Computer Science (Duluth)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

14 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 language	English (US)
Title of host publication	Proceedings of the 3rd Annual Symposium on Combinatorial Search, SoCS 2010
Pages	90-97
Number of pages	8
State	Published - 2010
Event	3rd International Symposium on Combinatorial Search, SoCS 2010 - Atlanta, GA, United States Duration: Jul 8 2010 → Jul 10 2010

Publication series

Name	Proceedings of the 3rd Annual Symposium on Combinatorial Search, SoCS 2010

Other

Other	3rd International Symposium on Combinatorial Search, SoCS 2010
Country/Territory	United States
City	Atlanta, GA
Period	7/8/10 → 7/10/10

Find It

Find It at U of M Libraries

Cite this

@inproceedings{d760ec26294d4691a1cab9de996eb6e1,

title = "Directed plateau search for MAX-k-SAT",

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.",

author = "Sutton, {Andrew M.} and Howe, {Adele E.} and Whitley, {L. Darrell}",

year = "2010",

language = "English (US)",

isbn = "9781577354819",

series = "Proceedings of the 3rd Annual Symposium on Combinatorial Search, SoCS 2010",

pages = "90--97",

booktitle = "Proceedings of the 3rd Annual Symposium on Combinatorial Search, SoCS 2010",

note = "3rd International Symposium on Combinatorial Search, SoCS 2010 ; Conference date: 08-07-2010 Through 10-07-2010",

}

TY - GEN

T1 - Directed plateau search for MAX-k-SAT

AU - Sutton, Andrew M.

AU - Howe, Adele E.

AU - Whitley, L. Darrell

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84865749563&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865749563&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84865749563

SN - 9781577354819

T3 - Proceedings of the 3rd Annual Symposium on Combinatorial Search, SoCS 2010

SP - 90

EP - 97

BT - Proceedings of the 3rd Annual Symposium on Combinatorial Search, SoCS 2010

T2 - 3rd International Symposium on Combinatorial Search, SoCS 2010

Y2 - 8 July 2010 through 10 July 2010

ER -

Directed plateau search for MAX-k-SAT

Abstract

Publication series

Other

Find It

Other files and links

Fingerprint

Cite this