.png){kind=icon}
返回
Explorative anytime local search for distributed constraint optimization
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2014.03.002.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Distributed Constraint Optimization Problems (DCOPs) are an elegant model for representing and solving many realistic combinatorial problems that are distributed by nature. DCOPs are NP-hard and therefore many recent studies consider incomplete algorithms for solving them. Distributed local search algorithms, in which agents in the system hold value assignments to their variables and iteratively make decisions on whether to replace them, can be used for solving DCOPs. However, because of the differences between the global evaluation of a system's state and the private evaluation of states by agents, agents are unaware of the global best state that is explored by the algorithm. Previous attempts to use local search algorithms for solving DCOPs reported the state held by the system at the termination of the algorithm, which was not necessarily the (global) best state explored. A general framework that enhances distributed local search algorithms for DCOPs with the anytime property is proposed. The proposed framework makes use of a BFS-tree in order to accumulate the costs of the system's state during the algorithm's iterative performance and to propagate the detection of a new best state when it is found. The proposed framework does not require additional network load. Agents are required to hold a small (linear) additional space (beside the requirements of the algorithm in use). We further propose a set of increased exploration heuristics that exploit the proposed anytime framework. These exploration methods implement different approaches towards exploration. Our empirical study considers various scenarios including random, realistic, and structured problems. It reveals the advantage of the use of the proposed heuristics in the anytime framework over state-of-the-art local search algorithms. (C) 2014 Elsevier B.V. All rights reserved.
Keyword:
Distributed constraint optimization
Incomplete search
Exploration heuristics
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.1K
被引数:
1.9W
机构
引用论文
Comparative analysis of fruit quality and nutritional components of four muscadine grape cultivars.png)
IF0
PREAI
分享收藏分享收藏
查看更多内容