WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Techniques hybrides de recherche exacte et approchée: application à  des problèmes de transport

( Télécharger le fichier original )
par Boris BONTOUX
Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

1.2.5 Apprentissage : look-back

Dans le cadre des problèmes de satisfaction de contraintes classiques, le Backtracking (voir la section 1.2.1 pour une définition) souffre fréquemment d'un phénomène de « trashing >>, qui se traduit par le fait de redécouvrir de manière répétitive les mêmes échecs et les mêmes instanciations partielles durant la recherche.

Les procédures dynamiques d'amélioration de parcours de l'arbre sont les schémas du type « look-ahead>> (sélection de variables et de valeurs) et « look-back>> (Backjumping, apprentissage, Nogood Recording). Le raisonnement du Backtrack conclut au rejet d'un certain nombre de choix combinatoires; le Nogood Recording (Schiex et Verfaillie, 1994) consiste à mémoriser ces choix afin de ne plus les reproduire. Ainsi, plusieurs techniques d'apprentissage des échecs ont été proposées.

Le Backjumping a été proposé par Gaschnig (1979). Supposons qu'un échec est rencontré sur la variable xi. La technique de Backtrack classique revient sur la dernière variable instanciée xi_1. Si une autre valeur est possible pour xi_1 mais qu'aucune contrainte ne porte sur les variables xi et xi_1, alors la variable xi_1 ne peut être la source de l'échec rencontré sur xi. Ainsi, on retrouve nécessairement un échec sur la variable xi pour chaque valeur instanciée de xi_1. Gaschnig (1979) propose d'améliorer ce processus en identifiant la variable coupable de l'échec et en effectuant le retour dans l'arbre sur cette variable. L'identification est basée sur la notion d'ensemble en conflit. Un ensemble en conflit est une instanciation d'un sous-ensemble de variables ne laissant aucune possibilité pour une certaine variable non encore instanciée. Une instanciation partielle qui n'apparaît dans aucune solution est un « NoGood >> (Doyle, 1979).

Ginsberg (1993) a proposé un nouvel algorithme pour résoudre les problèmes de satisfaction de contraintes. Cet algorithme, appelé Dynamic Backtracking peut être vu comme une amélioration du principe de Backjumping, de Graph Based Backjumping (Dechter, 1990) et de la méthode Conflict Directed Backjumping algorithms (Prosser, 1993) . La méthode Conflict Directed Backjumping enregistre à chaque étape de la recherche et pour chaque variable xi, l'ensemble des variables assignées qui a conduit à une réduction de domaine de xi. De tels ensembles sont appelés des ensembles de conflits. Dynamic Backtracking enregistre le même type d'informations, mais à un niveau plus fin. À chaque étape de la recherche, pour chaque variable xi et pour chaque valeur j qui a été supprimée du domaine courant de xi, l'algorithme enregistre l'ensemble des variables assignées précédemment qui sont responsables de cette élimination. Ces ensembles sont appelés des explications d'élimination. L'ensemble en conflit d'une variable est alors défini comme l'union des explications d'élimination des valeurs de cette variable.

Chvátal (1997) a présenté une méthode exhaustive pour la résolution de problèmes linéaires en variables binaires, Resolution Search. Cette méthode se démarque des procédures arborescentes classiques par une exploration originale de l'espace de recherche, censée permettre de rendre la résolution du problème moins largement dépendante de

la stratégie de branchement invoquée. Celle-ci, à l'instar des procédés de backtracking intelligents, est basée sur le principe d'apprentissage qui consiste à identifier et mémoriser les raisons des échecs qui surviennent tout au long de la recherche. Lorsqu'un échec est détecté au cours de l'exploration de l'espace de recherche, l'ensemble des variables, dont l'instanciation est responsable de l'échec, est déterminé à partir de la configuration partielle courante. Interdire pour la suite de la recherche cette instanciation partielle revient à générer une contrainte additionnelle au problème, appelée Nogood, afin de couper la recherche en amont du noeud considéré. Resolution Search propose un schéma original de gestion de ces nogoods. Celui-ci permet de limiter l'espace mémoire et le temps de traitement des nogoods. De plus, il permet d'indiquer rapidement comment poursuivre la recherche à la suite d'un échec, tout en assurant la convergence de l'algorithme. Demassey (2003) a appliqué cette méthode sur le problème d'Ordonnancement de Projet à Contraintes de Ressources (RCPSP). Palpant (2005) a proposé une utilisation de cette approche pour la résolution du problème des Queens_n2.

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Nous voulons explorer la bonté contrée énorme où tout se tait"   Appolinaire