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.5 Dynamic : un ordre dynamique de choix des variables et de sélection des valeurs

La phase d'apprentissage permet de déterminer la qualité d'un sous-arbre : une fonction d'évaluation renvoie une valeur (ou plusieurs valeurs) quant a la qualité estimée de ce sous-arbre. Ainsi, une pondération va être associée a chaque décision qui correspond a l'obtention de ce sous-arbre. La mise a jour des pondérations se passe de la manière suivante : lorsqu'un sous-arbre est complété, on regarde toutes les décisions qui ont été prises pour amener a ce sous-arbre et la pondération associée a ce sousarbre va remplacer les pondérations précédentes, dans le cas où elle est de meilleure qualité. Prenons un exemple concret : lors de l'exploration de l'arbre de recherche, une pondération de valeur n avait été associée a la variable xi. Si par la suite, la fonction d'évaluation renvoie une pondération égale a m (avec m < n), alors la pondération associée a la variable xi sera dorénavant m. D'autres choix de mises a jour sont envisageables, tels que la moyenne de l'ancienne pondération et de la nouvelle, ou encore la somme.

Ces pondérations permettent d'ordonner le choix de sélection des variables. Lors de l'exploration, quand le choix concernant la prochaine variable se pose, la méthode DLS choisit la variable non-instanciée possédant la plus faible pondération. Puis, la valeur sur laquelle brancher est ensuite choisie en fonction des pondérations de l'ensemble des valeurs du domaine de la variable. La phase d'apprentissage a indiqué que cette valeur pour cette variable semblait conduire vers des espaces de recherches intéressants. Donc, la recherche est intensifiée dans les sous-arbres correspondant a ce couple variablevaleur.

Une fois que le sous-arbre a été exploré et que les algorithmes de filtrage ont été appliqués, les pondérations sont de nouveau mises a jour a l'aide de la fonction d'évaluation.

Les fonctions d'évaluation présentées proposent une pondération pour un couple valeur-variable. A partir de ces pondérations, il faut déterminer une pondération associée a une variable. Pour cela, il est possible de faire la moyenne des pondérations associées aux valeurs du domaine de la variable. On branchera sur la variable ayant la plus petite moyenne en priorité, afin de limiter la taille de l'arbre de recherche. D'autres pondérations sont néanmoins envisageables.

La phase d'apprentissage permet de déterminer des pondérations qui servent a déterminer un ordre pour les variables, ainsi que pour chaque variable, l'ordre dans lequel ses valeurs vont être sélectionnées. Une question importante est de savoir quand a lieu la mise a jour des pondérations.

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








"Piètre disciple, qui ne surpasse pas son maitre !"   Léonard de Vinci