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.