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