Not logged in.

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Evaluating adaptations of local iterative best-response algorithms for DCOPs using ranks
Organization Unit
  • Andreas Flückiger
  • Coralia-Mihaela Verman
  • English
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Number of Pages 34
Date April 2015
Abstract Text This thesis introduces two new algorithms that can be used to find approximate solutions to Distributed Constraint Optimization Problems (DCOPs). One of the new algorithms is based on Ranked DSA (RDSA), a modification of the classical Distributed Stochastic Algorithm (DSA). The other new algorithm is based on Distributed Simulated Annealing (DSAN). Both new algorithms performed well with graph colouring problems, surpassing all other tested algorithms in the longer term. However, RDSA and the new algorithms had problems with randomized DCOPs, which have more gradual constraints than graph colouring problems.
Zusammenfassung Diese Arbeit stellt zwei neue Algorithmen vor, die verwendet werden können, um Näherungslösungen zu DCOPs (Distributed Constraint Optimization Problems) zu finden. Einer der neuen Algorithmen baut auf RDSA (Ranked DSA) auf, einer Modifikation des klassischen DSA (Distributed Stochastic Algorithm). Der andere neue Algorithmus baut auf DSAN (Distributed Simulated Annealing) auf. Die beiden neuen Algorithmen zeigten gute Leistungen mit Knotenfärbungsproblemen und übertrafen alle anderen getesteten Algorithmen auf längere Sicht. Allerdings hatten RDSA und die neuen Algorithmen Probleme mit randomisierten DCOPs, welche graduellere Bedingungen als Knotenfärbungsprobleme haben.
PDF File Download
Export BibTeX