TítuloDeciMaxSum: Décimer pour résoudre des DCOP cycliques plus efficacement
Publication TypeConference Paper
Year of Publication2018
AuthorsCerquides J, Emonet R, Picard G, Rodríguez-Aguilar JA
Conference Name26emes Journées Francophones sur les Systèmes Multi-Agents (JSFMA 2018)
Date Published2018
Resumen

Dans le cadre de la résolution des pro-
blèmes d’optimisation des contraintes distribués
(DCOP), les algorithmes approchés de pro-
pagation de croyances (BP) comme Max-Sum
sont des candidats de choix. Cependant, lorsque
le modèle graphique sous-jacent est très cy-
clique, ces méthodes de résolution souffrent de
mauvaises performances, en raison de la non-
convergence et des trop nombreux messages
échangés. Afin d’améliorer les performances de
Max-Sum sur de tels DCOPs, nous proposons
de s’inspirer de la décimation guidée par BP
pour résoudre des problème k-SAT. Nous pro-
posons la nouvelle méthode DeciMaxSum, pa-
ramétrable par des critères de déclenchement
de décimation, de choix de variables à décimer
et de valeurs pour ces variables. Sur la base
d’une évaluation expérimentale sur le modèle
d’Ising, certaines de ces combinaisons de cri-
tères présentent de meilleures performances que
les algorithmes concurrents.