Trap avoidance in local search using pseudo-conflict learning

Duc Nghia Pham, Thach Thao Duong, Abdul Sattar

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationAAAI-12 / IAAI-12 - Proceedings of the 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference
Place of PublicationPalo Alto, California
PublisherAAAI press
Pages542-548
Number of pages7
ISBN (Print)9781577355687
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12 - Toronto, ON, Canada
Duration: 22 Jul 201226 Jul 2012

Publication series

NameProceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
PublisherAssociation for the Advancement of Artificial Intelligence
Number1
Volume26
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

Conference26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12
Country/TerritoryCanada
CityToronto, ON
Period22/07/1226/07/12

Fingerprint

Dive into the research topics of 'Trap avoidance in local search using pseudo-conflict learning'. Together they form a unique fingerprint.

Cite this