Not logged in.
Quick Search - Contribution
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 | |
Authors |
|
Supervisors |
|
Language |
|
Institution | University of Zurich |
Faculty | Faculty of Economics, Business Administration and Information Technology |
Number of Pages | 34 |
Date | 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 |
![]() |
Export |
![]() |