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.2 Méthode de structuration de l'arbre de recherche

Lorsqu'on construit un arbre de recherche, la structure proprement dite de celui-ci sera en grande partie déterminée par les choix concernant les politiques de séparation. Une fois que la variable sur laquelle on veut brancher a été déterminée, on doit choisir la politique en ce qui concerne la séparation du domaine de cette variable. Classiquement, on choisit de créer un noeud par valeur possible du domaine de la variable. Cela conduit à des arbres de recherche dont la structure est assez large. On peut aussi appliquer une politique de séparation binaire : on crée d'un côté un noeud pour lequel la variable est fixée à une valeur, de l'autre côté, un noeud pour lequel la variable est différente de cette valeur. Éxcepté pour le cas des problèmes à variables binaires, le problème d'une telle politique réside dans la création d'un arbre fortement déséquilibré (l'affectation d'une variable à une valeur a beaucoup plus de conséquences que l'interdiction de cette valeur). La stratégie equal split consiste quant à elle à séparer les domaines des variables en deux sous-domaines de taille égale. L'intérêt de cette méthode est principalement de créer un arbre équilibré. Quelle que soit la politique de séparation du domaine des variables, une fois les noeuds créés, la politique de choix de l'ordre de traitement des noeuds ainsi créés reste elle-aussi à déterminer.

1.2.3 Parcours réduit de l'arbre

Dans le cadre de la résolution d'un problème d'optimisation combinatoire par une méthode exacte, on peut chercher à obtenir rapidement de bonnes solutions dans un temps limité. Un des moyens pour y arriver est de transformer la méthode exacte en une méthode heuristique. Cela passe la plupart du temps par une exploration incomplète de l'arbre de recherche. Un des moyens les plus simples est de ne pas traiter l'ensemble des noeuds en attente. Un ordre de priorité pour le traitement des noeuds en attente est appliqué et on choisit de ne traiter qu'un certain nombre de noeuds parmi l'ensemble des noeuds. On restreint donc la recherche à un sous-espace de l'espace original, par exemple en ne choisissant que les valeurs les plus prometteuses pour chaque variable lors de l'exploration. Fondamentalement, dans ces méthodes, on peut considérer que les noeuds non traités sont des noeuds restant en attente en fin de résolution. Idéalement, on pourrait donc conserver l'exactitude de la méthode en continuant le traitement des noeuds jusqu'au bout (au prix de temps de résolution beaucoup plus important).

Beam Search (Ow et Morton, 1988) est sûrement l'alternative la plus connue pour tronquer une exploration. Cette approche est basée sur une exploration en largeur de l'arbre de recherche. On utilise une fonction heuristique pour estimer l'intérêt de chaque noeud examiné. A chaque niveau de l'arbre, on garde seulement les w noeuds les plus prometteurs dans l'ensemble des noeuds ouverts, qui est l'ensemble de noeuds à

partir desquels la recherche peut continuer. Le terme w est appelé la profondeur Beam. On voit facilement que plus w est grand, plus le nombre de noeuds explorés sera important. Ainsi, lorsqu'on augmente w, on s'approche de la solution qui aurait été trouvée par une exploration exacte. En règle générale, l'efficacité de cette approche dépend de la qualité des bornes inférieures et supérieures. De plus, tant que w est petit, cette méthode n'est pas complète.

Limited Discrepancy Search ou LDS , méthode proposée par Harvey et Ginsberg (1995), dérive d'une recherche en profondeur classique, mais peut être combinée avec des règles de sélection de variables et de valeurs. L'idée principale de cette méthode est de limiter la recherche aux branches qui ont au plus z déviations (discrepancies). Une déviation est définie comme une décision contraire par rapport à une heuristique qui indique le meilleur noeud fils pour chaque noeud. Une déviation apparaît à chaque fois que le noeud fils choisi dans une branche n'est pas le meilleur noeud. Par exemple, si l'on considère les branches avec z = 0 déviation, l'arbre ne comportera qu'une seule branche : à chaque étape, la recherche doit suivre la branche qui mène au meilleur noeud. Plus on augmente z, plus la méthode s'approche d'une résolution exacte. Néanmoins, cette méthode est par définition assez dépendante de la qualité de l'heuristique choisie, qui détermine à chaque noeud la direction à prendre.

La méthode Branch & Greed a été présentée par Sourd et Chretienne (1999) (voir par exemple (Néron et al., 2008) pour un article récent sur cette méthode). Cette méthode consiste à guider un arbre de recherche incomplet à l'aide d'un algorithme glouton. Comme pour Beam Search ou pour LDS, on peut paramétrer l'algorithme grâce à une valeur, notée ici k, afin que plus ou moins de feuilles soient visitées. L'algorithme parcourt alors l'arbre de recherche en partant du noeud racine et suit une branche jusqu'à trouver une feuille. Considérons une itération de l'algorithme. A l'étape l, la profondeur du noeud courant noté N, est égale à l. Pour déterminer le noeud fils de la prochaine étape, l'algorithme considère l'ensemble des noeuds fils de N dont la profondeur est égale à l + k. Chacun de ces noeuds correspond à une solution partielle et, pour chaque solution partielle, on construit une solution réalisable en utilisant l'algorithme glouton suivant : on choisit le meilleur noeud fils jusqu'à ce qu'on arrive à une feuille. Cet algorithme glouton correspond à suivre la branche qui ne comporte aucune déviation. Notons Nbest la meilleure solution trouvée durant cette étape. Le noeud successeur de N dans l'algorithme de Branch & Greed est le noeud qui permet d'atteindre le noeud Nbest. La profondeur de ce noeud est donc l + 1 et la procédure de Branch and Greed continue avec ce noeud. La qualité de l'algorithme glouton et l'heuristique choisie pour mesurer les déviations déterminent en grande partie l'efficacité de la méthode.

Les méthodes décrites ci-dessus présentent toutes l'intérêt de dépendre d'un seul paramètre, qui détermine le niveau de complétude de la résolution. En effet, si ce paramètre est fixé à une grande valeur, les résolutions seront de type exactes. Ces méthodes, bien que pouvant s'avérer très efficaces, présentent néanmoins un défaut principal : leur réussite est fortement dépendante de l'efficacité des heuristiques retenues. Dans le cas d'une heuristique peu efficace, les déviations ne sont pas significatives. On remarque donc que ces méthodes doivent être adaptées au problème traité, pour se montrer le plus efficace possible.

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








"Qui vit sans folie n'est pas si sage qu'il croit."   La Rochefoucault