Retour-arrière basé sur les divergences pour l'optimisation distribuée

Jonathan Gaudreault 1 Jean-Marc Frayet 1 Gilles Pesant 1
1 Département de génie informatique
Résumé : Les approches dites DCOP (Distributed Constraint Optimization Problems) sont de plus en plus utilisées pour formaliser des situations oùp lusieurs agents doivent coopérer pour résoudre un problème d'optimisation.Parfois, les agents constituent une organisation fortement hétérogène. Un réseau de compagnies en est un bon exemple. Dans ce contexte, la structure du réseau et les règles d'affaires régissent les échanges qui sont possibles pendant la résolution du problème. L'espace de recherche d'une solutions apparente alors à un arbre de recherche classique pour un problème d'optimisation combinatoire centralisé. Or, pour les problèmes centralisés,les stratégies de recherche exploitant un retour-arrière basé sur les divergences (LDS, par exemple) donnent généralement de bons résultats. Nousp roposons donc un nouvel algorithme qui permet aux agents de réaliser de manière distribuée une recherche basée sur les divergences. La méthode proposée permet le travail concurrent des agents et elle est tolérante aux délais aléatoires de communication. Elle est complète, mais elle vise d'abord à obtenir de bonnes solutions en un temps très court. L'approche a été évaluée sur des problèmes industriels réels pour lesquels elle a montré de bonnes performances.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00151223
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:19:42
Dernière modification le : lundi 19 mars 2018 - 22:38:02
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:44:36

Fichier

53.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151223, version 1

Collections

JFPC07

Citation

Jonathan Gaudreault, Jean-Marc Frayet, Gilles Pesant. Retour-arrière basé sur les divergences pour l'optimisation distribuée. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151223〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

103

Contact


archive-ouverte@inria.fr