An Iterative Refined Max-sum_AD Algorithm via Single-side Value Propagation and Local Search
Ziyu Chen, Yanchen Deng, Tengfei Wu · Adaptive Agents and Multi-Agents Systems · 2017
Max-sum_ADVP is a message-passing algorithm for solving Distributed Constraint Optimization Problems (DCOPs) able to obtain a convergent solution in a cyclic factor graph. Nevertheless, the solution quality is closely related to the timing for starting value propagation in Max-sum_ADVP. In other words, low-quality initial assignments will lead to a poor result. In this paper, we illustrate that value propagation can eliminate the inconsistent contexts in Max-sum_AD and break ties among utilities, but it also restricts the exploration brought by Max-sum. For balancing between the exploration and the accuracy, we propose a new iterative refined Max-sum_AD algorithm with single-side value propagation, called Max-sum_ADSSVP. It performs two phases in every two convergences, one phase which enables the exploration to find high-quality initial assignments and the other phase which enables value propagation to guarantee solution quality. Max-sum_ADSSVP tackles the timing selection problem by iteratively refining initial assignments in every exploration phase. Besides, local search is introduced after the value propagation phase to speed up the convergence process. Our empirical evaluation indicates that our methods are independent of initial assignments and less likely to get stuck in local optima.