Trap escape for local search by backtracking and conflict reverse
Paper
Paper/Presentation Title | Trap escape for local search by backtracking and conflict reverse |
---|---|
Presentation Type | Paper |
Authors | Duong, Huu-Phuoc (Author), Duong, Thach-Thao (Author), Pham, Duc Nghia (Author), Sattar, Abdul (Author) and Duong, Anh Duc (Author) |
Editors | Jaeger, Manfred, Nielsen, Thomas Dyhre and Viappiani, Paolo |
Journal or Proceedings Title | Frontiers in Artificial Intelligence and Applications |
ERA Conference ID | 44019 |
Journal Citation | 257, pp. 85-94 |
Number of Pages | 10 |
Year | 2013 |
Place of Publication | Amsterdam |
ISSN | 0922-6389 |
1879-8314 | |
ISBN | 9781614993292 |
9781614993308 | |
Digital Object Identifier (DOI) | https://doi.org/10.3233/978-1-61499-330-8-85 |
Web Address (URL) of Paper | https://ebooks.iospress.nl/publication/35449 |
Conference/Event | 12th Scandinavian Conference on Artificial Intelligence (SCAI 2013) |
Scandinavian Conference on Artificial Intelligence | |
Event Details | Scandinavian Conference on Artificial Intelligence SCAI Rank B B B B B B B |
Event Details | 12th Scandinavian Conference on Artificial Intelligence (SCAI 2013) Event Date 20 to end of 22 Nov 2013 Event Location Aalborg, Denmark |
Abstract | This paper presents an efficient trap escape strategy in stochastic local search for Satisfiability. The proposed method aims to enhance local search by providing an alternative local minima escaping strategy. Our variable selection scheme provides a novel local minima escaping mechanism to explore new solution areas. Conflict variables are hypothesized as variables recently selected near local minima. Hence, a list of backtracked conflict variables is retrieved from local minima. The new strategy selects variables in the backtracked variable list based on the clause-weight scoring function and stagnation weights and variable weights as tiebreak criteria. This method is an alternative to the conventional method of selecting variables in a randomized unsatisfied clause. The proposed tiebreak method favors high stagnation weights and low variable weights during trap escape phases. The new strategies are examined on verification benchmark and SAT Competition 2011 and 2012 application and crafted instances. Our experiments show that proposed strategy has comparable performance with state-of-the-art local search solvers for SAT. |
Keywords | local search; SAT; Stagnation; Trap escape |
ANZSRC Field of Research 2020 | 460210. Satisfiability and optimisation |
Byline Affiliations | Vietnam National University, Vietnam |
Griffith University | |
University of Information Technology, Vietnam | |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q7112/trap-escape-for-local-search-by-backtracking-and-conflict-reverse
69
total views3
total downloads0
views this month0
downloads this month