Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/77078
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Sutton, Andrew M. | en |
dc.contributor.author | Howe, Adele E. | en |
dc.contributor.author | Whitley, L. Darrell | en |
dc.date.issued | 2010 | en |
dc.identifier.citation | Proceedings of the Third Annual Symposium on Combinatorial Search, held in Atlanta, Georgia, 8-10 July, 2010: pp.90-97 | en |
dc.identifier.uri | http://hdl.handle.net/2440/77078 | - |
dc.description.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. | en |
dc.description.statementofresponsibility | Andrew M. Sutton, Adele E. Howe and L. Darrell Whitley | en |
dc.language.iso | en | en |
dc.publisher | AAAI Press | en |
dc.rights | © 2010, Association for the Advancement of Artificial Intelligence. All rights reserved. | en |
dc.source.uri | http://www.aaai.org/ocs/index.php/SOCS/SOCS10/paper/view/2091 | en |
dc.title | Directed plateau search for MAX-k-SAT | en |
dc.type | Conference paper | en |
dc.contributor.school | School of Computer Science | en |
dc.contributor.conference | Annual Symposium on Combinatorial Search (3rd : 2010 : Atlanta, Georgia USA) | en |
dc.contributor.conference | SOCS-10 | en |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.