A Two-Phase Complete Algorithm for Multi-Objective Distributed Constraint Optimization

Access this Article

Search this Article

Author(s)

Abstract

<p>A Distributed Constraint Optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Many application problems in multi-agent systems can be formalized as DCOPs. However, many real world optimization problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Distributed Constraint Optimization Problem (MO-DCOP) is an extension of a mono-objective DCOP. Compared to DCOPs, there exists few works on MO-DCOPs. In this paper, we develop a novel complete algorithm for solving an MO-DCOP. This algorithm utilizes a widely used method called Pareto Local Search (PLS) to generate an approximation of the Pareto front. Then, the obtained information is used to guide the search thresholds in a Branch and Bound algorithm. In the evaluations, we evaluate the runtime of our algorithm and show empirically that using a Pareto front approximation obtained by a PLS algorithm allows to significantly speed-up the search in a Branch and Bound algorithm.</p>

Journal

  • Journal of Advanced Computational Intelligence and Intelligent Informatics

    Journal of Advanced Computational Intelligence and Intelligent Informatics 18(4), 573-580, 2014

    Fuji Technology Press Ltd.

Codes

  • NII Article ID (NAID)
    130007673206
  • Text Lang
    ENG
  • ISSN
    1343-0130
  • NDL Article ID
    025788431
  • NDL Call No.
    Z78-A599
  • Data Source
    NDL  J-STAGE 
Page Top