Retour-arrière basé sur les divergences pour l'optimisation distribuée - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

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

Jonathan Gaudreault
  • Fonction : Auteur
  • PersonId : 840396
Jean-Marc Frayet
  • Fonction : Auteur
  • PersonId : 840397
Gilles Pesant
  • Fonction : Auteur
  • PersonId : 840398

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.
Fichier principal
Vignette du fichier
53.pdf (108.74 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00151223 , version 1 (01-06-2007)

Identifiants

  • HAL Id : inria-00151223 , version 1

Citer

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. ⟨inria-00151223⟩

Collections

JFPC07
55 Consultations
64 Téléchargements

Partager

Gmail Facebook X LinkedIn More