1.4 Learning : une méthode basée sur un
apprentissage
La phase de Learning se décompose en plusieurs
sous-parties : le sondage, l'apprentissage, la prévision et la remise en
question.
1.4.1 Sondage
Le sondage représente la phase de démarrage de
notre méthode. On sait que les décisions prises au sommet de
l'arbre de recherche sont primordiales pour l'efficacité de la
résolution. Il existe donc des méthodes génériques
afin de choisir le plus judicieusement possible les variables. Ces
méthodes sont basées sur l'idée que les variables les plus
intéressantes à choisir au début de la résolution
sont les variables les plus contraintes et les plus contraignantes. On peut
donc choisir les variables ayant le plus petit domaine, le plus fort
degré de connexité ou une combinaison des deux
précédents critères. Mais, il existe des
problèmes oü ces critères ne suffisent pas à
déterminer quelles variables choisir, par exemple, lorsque toutes les
variables ont le même domaine. Un choix pertinent de variables est alors
complexe.
Dans un souci de généricité, notre
méthode se base sur une phase de sondage. Le sondage permet de prendre
connaissance rapidement de l'arbre de recherche, il consiste en un
apprentissage rapide et non exhaustif. Le sondage peut être totalement
aléatoire ou dirigé vers un espace de recherche précis,
notamment en fixant certaines variables à des valeurs. Une des
principales difficultés est de déterminer le temps à
passer dans cette phase. En effet, le fait de passer beaucoup de temps dans la
phase de sondage comporte deux risques principaux. Premièrement, si le
problème est facilement résoluble, la phase de sondage peut
s'avérer plus longue que la résolution proprement dite.
Deuxièmement, on peut risquer d'accorder une confiance trop importante
au sondage et de ne pas remettre en question par la suite les informations
apportées lors du sondage. Le temps accordé à la phase de
sondage est donc un paramètre important. Une fois la phase de sondage
terminée, les fonctions d'évaluation permettent d'attribuer des
poids initiaux aux variables, ainsi qu'aux valeurs appartenant aux domaines des
variables. Ces poids serviront dans la suite de la résolution afin de
déterminer des ordres de branchement.
Un cas pratique de sondage est le suivant. Pour un
problème de satisfaction de contraintes, une variable est choisie
aléatoirement, puis une valeur du domaine de cette variable est choisie
aléatoirement. Un algorithme de filtrage est appliqué. On
réitère ce procédé jusqu'à obtenir un
conflit (une variable dont le domaine a été réduit au
domaine nul). On évalue alors les sous-arbres fermés et on
relance la résolution. Dans le cas d'un sondage dirigé, lorsque
la fonction d'évaluation semble nous indiquer qu'un espace de l'arbre de
recherche est intéressant, on peut alors intensifier le sondage aux
abords de cet espace de l'arbre de recherche.
| 
