VLSs: A Local Search Algorithm for Distributed Constraint Optimization Problems

Fukui LI, Jingyuan HE*, Mingliang ZHOU, Bin FANG

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

2 Citations (Scopus)

Abstract

Local search algorithms are widely applied in solving large-scale distributed constraint optimization problem (DCOP). Distributed stochastic algorithm (DSA) is a typical local search algorithm to solve DCOP. However, DSA has some drawbacks including easily falling into local optima and the unfairness of assignment choice. This paper presents a novel local search algorithm named VLSs to solve the issues. In VLSs, sampling according to the probability corresponding to assignment is introduced to enable each agent to choose other promising values. Besides, each agent alternately performs a greedy choice among multiple parallel solutions to reduce the chance of falling into local optima and a variance adjustment mechanism to guide the search into a relatively good initial solution in a periodic manner. We give the proof of variance adjustment mechanism rationality and theoretical explanation of impact of greed among multiple parallel solutions. The experimental results show the superiority of VLSs over state-of-the-art DCOP algorithms.

Original languageEnglish
Article number2259006
JournalInternational Journal of Pattern Recognition and Artificial Intelligence
Volume36
Issue number3
Early online date12 Jan 2022
DOIs
Publication statusPublished - 15 Mar 2022
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2022 World Scientific Publishing Company.

Keywords

  • distributed constraint optimization problem
  • incomplete algorithm
  • local search algorithm
  • Multi-agent system

Fingerprint

Dive into the research topics of 'VLSs: A Local Search Algorithm for Distributed Constraint Optimization Problems'. Together they form a unique fingerprint.

Cite this