| 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.
|
