Distributed Guided Local Search for Solving Binary DisCSPs

Muhammed Basharu, Ines Arana, and Hatem Ahriz, Robert Gordon University

We introduce the Distributed Guided Local Search (Dist-GLS) algorithm for solving Distributed Constraint Satisfaction Problems. Our algorithm is based on the centralised Guided Local Search algorithm, which is extended with additional heuristics in order to enhance its efficiency in distributed scenarios. We discuss the strategies we use for dealing with local optima in the search for solutions and compare performance of Dist-GLS with that of Distributed Breakout (DBA). In addition, we provide the results of our experiments with distributed versions of random binary constraint satisfaction and graph colouring problems.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.