Trap Avoidance in Local Search Using Pseudo-Conflict Learning
Paper
Paper/Presentation Title | Trap Avoidance in Local Search Using Pseudo-Conflict Learning |
---|---|
Presentation Type | Paper |
Authors | Pham, Duc Nghia (Author), Duong, Thach-Thao (Author) and Sattar, Abdul (Author) |
Journal or Proceedings Title | Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012) |
ERA Conference ID | 43933 |
Journal Citation | 242, pp. 542-548 |
Number of Pages | 7 |
Year | 2012 |
Place of Publication | United States |
ISBN | 9781577355687 |
Web Address (URL) of Paper | https://dl.acm.org/doi/abs/10.5555/2900728.2900806 |
Conference/Event | 26th AAAI Conference on Artificial Intelligence (AAAI 2012) |
AAAI Conference on Artificial Intelligence | |
Event Details | AAAI Conference on Artificial Intelligence AAAI Rank A A A A A |
Event Details | 26th AAAI Conference on Artificial Intelligence (AAAI 2012) Event Date 22 to end of 26 Jul 2012 Event Location Toronto, Canada |
Abstract | A key challenge in developing efficient local search solvers is to effectively minimise search stagnation (i.e. avoiding traps or local minima). A majority of the state-of-the-art local search solvers perform random and/or Novelty-based walks to overcome search stagnation. Although such strategies are effective in diversifying a search from its current local minimum, they do not actively prevent the search from visiting previously encountered local minima. In this paper, we propose a new preventative strategy to effectively minimise search stagnation using pseudo-conflict learning. We define a pseudo-conflict as a derived path from the search trajectory that leads to a local minimum. We then introduce a new variable selection scheme that penalises variables causing those pseudo-conflicts. Our experimental results show that the new preventative approach significantly improves the performance of local search solvers on a wide range of structured and random benchmarks. |
Keywords | Local minimums; Local search; Trap avoidances; Variable selection |
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/q711z/trap-avoidance-in-local-search-using-pseudo-conflict-learning
50
total views2
total downloads3
views this month0
downloads this month