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