dc.contributor.convenor | Vietnam National University | |
dc.contributor.author | Thornton, John | |
dc.contributor.author | Pham, Nghia | |
dc.contributor.editor | Tu-Bao Ho and Zhi-Hua Zhou | |
dc.date.accessioned | 2017-05-03T12:54:34Z | |
dc.date.available | 2017-05-03T12:54:34Z | |
dc.date.issued | 2008 | |
dc.date.modified | 2009-07-03T06:57:47Z | |
dc.identifier.refuri | http://www.jaist.ac.jp/PRICAI-08/ | |
dc.identifier.doi | 10.1007/978-3-540-89197-0_38 | |
dc.identifier.uri | http://hdl.handle.net/10072/23559 | |
dc.description.abstract | Although clause weighting local search algorithms have produced some of the best results on a range of challenging satisfiability (SAT) benchmarks, this performance is dependent on the careful hand-tuning of sensitive parameters. When such hand-tuning is not possible, clause weighting algorithms are generally outperformed by self-tuning WalkSAT-based algorithms such as AdaptNovelty+ and AdaptG2WSAT. In this paper we investigate tuning the weight decay parameter of two clause weighting algorithms using the statistical properties of cost distributions that are dynamically accumulated as the search progresses. This method selects a parameter setting both according to the speed of descent in the cost space and according to the shape of the accumulated cost distribution, where we take the shape to be a predictor of future performance. In a wide ranging empirical study we show that this automated approach to parameter tuning can outperform the default settings for two state-of-the-art algorithms that employ clause weighting (PAWS and gNovelty+). We also show that these self-tuning algorithms are competitive with three of the best-known self-tuning SAT local search techniques: RSAPS, AdaptNovelty+ and AdaptG2WSAT. | |
dc.description.peerreviewed | Yes | |
dc.description.publicationstatus | Yes | |
dc.format.extent | 36011 bytes | |
dc.format.extent | 197915 bytes | |
dc.format.mimetype | text/plain | |
dc.format.mimetype | application/pdf | |
dc.language | English | |
dc.language.iso | eng | |
dc.publisher | Springer | |
dc.publisher.place | Heidelberg, Germany | |
dc.publisher.uri | http://www.jaist.ac.jp/PRICAI-08/ | |
dc.relation.ispartofstudentpublication | N | |
dc.relation.ispartofconferencename | 10th Pacific Rim International Conference on Artificial Intelligence | |
dc.relation.ispartofconferencetitle | PRICAI 2008: Trends in Artificial Intelligence | |
dc.relation.ispartofdatefrom | 2008-12-15 | |
dc.relation.ispartofdateto | 2008-12-19 | |
dc.relation.ispartoflocation | Hanoi, Vietnam | |
dc.rights.retention | Y | |
dc.subject.fieldofresearch | Artificial Intelligence and Image Processing not elsewhere classified | |
dc.subject.fieldofresearchcode | 080199 | |
dc.title | Using Cost Distributions to Guide Weight Decay in Local Search for SAT | |
dc.type | Conference output | |
dc.type.description | E1 - Conferences | |
dc.type.code | E - Conference Publications | |
gro.faculty | Griffith Sciences, School of Information and Communication Technology | |
gro.rights.copyright | © 2008 Springer. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. The original publication is available at www.springerlink.com | |
gro.date.issued | 2008 | |
gro.hasfulltext | Full Text | |
gro.griffith.author | Thornton, John R. | |
gro.griffith.author | Pham, Nghia N. | |