Weight-Enhanced Diversification in Stochastic Local Search for Satisfiability
Paper
Paper/Presentation Title | Weight-Enhanced Diversification in Stochastic Local Search for Satisfiability |
---|---|
Presentation Type | Paper |
Authors | Duong, Thach-Thao (Author), Pham, Duc Nghia (Author), Sattar, Abdul (Author) and Newton, M. A. Hakim (Author) |
Editors | Rossi, Francesca |
Journal or Proceedings Title | Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013) |
ERA Conference ID | 43623 |
Number of Pages | 7 |
Year | 2013 |
ISBN | 9781577356332 |
Web Address (URL) of Paper | https://www.iospress.com/catalog/books/twelfth-scandinavian-conference-on-artificial-intelligence |
Conference/Event | 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013) |
International Joint Conference on Artificial Intelligence | |
Event Details | International Joint Conference on Artificial Intelligence IJCAI Rank A A A A A |
Event Details | 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013) Event Date 03 to end of 09 Aug 2013 Event Location Beijing, China |
Abstract | Intensification and diversification are the key factors that control the performance of stochastic local search in satisfiability (SAT). Recently, Novelty Walk has become a popular method for improving diversification of the search and so has been integrated in many well-known SAT solvers such as TNM and gNovelty+. In this paper, we introduce new heuristics to improve the effectiveness of Novelty Walk in terms of reducing search stagnation. In particular, we use weights (based on statistical information collected during the search) to focus the diversification phase onto specific areas of interest. With a given probability, we select the most frequently unsatisfied clause instead of a totally random one as Novelty Walk does. Amongst all the variables appearing in the selected clause, we then select the least flipped variable for the next move. Our experimental results show that the new weight-enhanced diversification method significantly improves the performance of gNovelty+ and thus outperforms other local search SAT solvers on a wide range of structured and random satisfiability benchmarks. |
Keywords | Artificial intelligence; Benchmarking; Stochastic systems |
ANZSRC Field of Research 2020 | 460210. Satisfiability and optimisation |
Byline Affiliations | Griffith University |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q7115/weight-enhanced-diversification-in-stochastic-local-search-for-satisfiability
55
total views2
total downloads0
views this month0
downloads this month