Improving the efficiency of the distributed stochastic algorithm
Melanie Smith, Roger Mailler · Adaptive Agents and Multi-Agents Systems · 2010
The Distributed Stochastic Algorithm (DSA) is a distributed hill-climbing technique for solving large Distributed Constraint Optimization Problems (DCOPs) such as distributed scheduling, resource allocation, and distributed route planning. The best known version of DSA, DSA-B, works by having agents change their assignments with probability p when making that change will improve their solution (a hill-climbing move). To escape local minima, DSA-B performs a lateral escape move by switching to another equally good value with the same probability p. It is unclear why hill climbing and escape moves are chosen with the same probability. We investigate the performance effects of making these moves with different probabilities, pH and pL. Through empirical evaluation, we discover that the efficiency of DSA can not only be considerably improved, but can be more specifically tuned to a particular domain or user's needs when these two move types are considered separately. Our work also shows that DSA can outperform both DBA and DPP when it is properly tuned.