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

Dans un schéma d'exploration classique d'un arbre de recherche, lorsqu'on arrive à une feuille qui n'est pas une solution (c'est-à-dire lorsque des variables ont leur domaine vide ou lorsqu'un calcul de borne inférieure permet d'arrêter l'exploration), on effectue un Backtrack qui consiste à remettre en cause la dernière décision prise. On prend alors une nouvelle décision, si cela est possible. Dans le cas contraire, on remonte dans la liste des décisions prises. Un des gros inconvénients de cette méthode est d'oublier tout ce qui a été appris lors de l'exploration qui a mené à un échec, et ne garder en mémoire que le fait que les décisions n'étaient pas bonnes. En effet, lors d'un Backtrack, lorsqu'une valeur d'une variable a mené à un échec (ou à une solution dans le cas d'un problème d'optimisation combinatoire), on choisit la plupart du temps une autre valeur pour cette même variable. Or, parmi toutes les décisions prises qui mènent à des échecs, certaines ont pu être mauvaises et d'autres très mauvaises.

A travers la phase d'apprentissage, la méthode Dynamic Learning Search tente de tirer des enseignements des erreurs passées, afin de diriger la recherche vers un es-

pace qui soit le plus prometteur possible (voir la section 1.2.5 pour plus de détails sur d'autres techniques basées sur l'apprentissage). Les techniques existantes se basent en général sur les « NoGood ». Elles mémorisent ainsi les causes d'échec et tentent de ne plus commettre les mêmes échecs. La méthode DLS tente quant à elle de retenir les bonnes décisions et de les reproduire.

La phase d'apprentissage est donc une des phases les plus importantes de notre méthode. Durant cette phase, on va évaluer la qualité d'un sous-arbre, c'est-à-dire d'un es-pace de solution. De cette évaluation découlera une affectation de poids aux variables, ainsi qu'aux valeurs appartenant aux domaines des variables. Ces affectations permettront un ordonnancement parmi les variables non fixées sur lesquelles brancher, ainsi que l'ordre dans lequel leurs valeurs seront explorées.

La qualité d'un sous-arbre dépend de plusieurs paramètres. En particulier, on peut facilement se rendre compte que la fonction d'évaluation pour un problème de satisfaction de contraintes n'est pas la même que pour un problème d'optimisation combinatoire. Dans le cas d'un problème de satisfaction de contraintes, on cherche à obtenir une seule solution complète, c'est-à-dire que l'ensemble des variables du problème soient instanciées. On peut donc estimer que, plus le nombre de variables instanciées dans un espace de solution est important, plus les décisions prises correspondantes semblent prometteuses. La profondeur d'un sous-arbre (déterminée par le cardinal des variables instanciées) semble une fonction d`évaluation pertinente pour un problème de satisfaction de contraintes (voir la section 1.8.1 pour plus de détails). Dans le cas d'un problème d'optimisation combinatoire, la meilleure solution en terme d'objectif contenue dans le sous-arbre semble être une fonction d'évaluation judicieuse (voir la section 1.8.2 pour plus de détails). En effet, si dans un sous-arbre, il existe une solution de très bonne qualité, on peut supposer que la solution optimale sera proche en terme d'assignation valeur/variable de cette solution (on retrouve ce principe dans certains opérateurs de recherche locale). On peut aussi considérer comme des critères pertinents, des critères prenant en compte la diminution des domaines par les algorithmes de filtrage, ou encore le nombre de coupes effectuées dans un sous-arbre. En effet, on peut avoir intérêt à retenir les affections de valeurs à des variables qui ont permis de couper de manière importante l'arbre de recherche.

On peut remarquer néanmoins que ces critères sont des critères uniquement « positifs ». En effet, dans le cas d'un problème à satisfaction de contraintes, on peut obtenir deux sous-arbres dont les profondeurs maximales sont égales et pouvant pourtant présenter un intérêt différent. On peut imaginer qu'un des deux sous-arbres soit beaucoup moins large que l'autre (à cause par exemple des algorithmes de filtrage). Le temps passé à explorer ce sous-arbre aura donc été beaucoup plus court. On aura tout intérêt à mémoriser des critères « négatifs » afin de départager des éventuelles égalités entre deux sous-arbres.

Les fonctions d'évaluation proposées précédemment ne concernaient qu'un critère maximum (profondeur maximale, meilleure solution, ...). On pourra chercher aussi à mémoriser la qualité globale d'un sous-arbre en observant d'autres critères : moyenne du critère sur l'ensemble du sous-arbre, médiane, écart-type, etc. Le critère retenu ici

est un critère maximum.

Le besoin d'adapter la méthode à la spécificité du problème (problème de satisfaction de contraintes ou d'optimisation combinatoire) n'apparaît que dans la fonction d'évaluation. On peut néanmoins imaginer avoir un panel de fonctions d'évaluations à appliquer et ainsi pouvoir déterminer le type de problèmes en fonction de quelles évaluations ont été les plus efficaces. Par ce biais, il n'est plus indispensable de connaître dans quelle catégorie de problèmes la méthode est appliquée.

1.4.3 Prévision

L'apprentissage, par la fonction d'évaluation, permet de diriger la recherche vers des sous-espaces qui semblent prometteurs. Lorsqu'on branche sur une variable et sur une valeur, les pondérations associées à cette valeur et à cette variable nous donnent une prévision de la qualité espérée du sous-arbre qui va être parcouru.

L'apprentissage peut être un apprentissage supervisé. Un des moyens pour cela est de comparer la qualité d'un sous-arbre déterminée par la fonction d'évaluation et la qualité de ce même sous-arbre prévue par les pondérations lors de la phase d'apprentissage. Dans le cas où ces valeurs seraient trop éloignées, cela pourrait éventuellement indiquer que la fonction d'évaluation est inadaptée. Il peut être alors intéressant d'envisager une mise à jour des informations qui prenne en compte les différences entre ce qui était prévu et ce qui est avéré.

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








"Ceux qui vivent sont ceux qui luttent"   Victor Hugo