1.3 Dynamic Learning Search: une méthode par
apprentissage
La plupart des méthodes de résolution exactes
utilisées en optimisation combinatoire s'appuient sur une
énumération intelligente des solutions (Branch and Bound,
Programmation par contraintes, Programmation dynamique, ...). Cette
énumération revient généralement à
construire un arbre de recherche, pour lequel un certain nombre de
décisions sont prises à chaque noeud.
La construction d'un arbre dépend de trois niveaux de
décisions:
Le schéma d'exploration : ce
schéma détermine la manière dont va se dérouler
l'exploration de l'arbre (on peut citer par exemple Depth First
Search, Breadth First Search, Back Jumping, ...). Ces
schémas ne modifient pas la structure principale de l'arbre. Par contre,
par des mécanismes de coupes (Branch & Bound, Branch & Cut)
et/ou de calculs de bornes, l'exploration de certaines parties de l'arbre peut
être tronquée, ces parties étant différentes selon
les schémas d'exploration retenus.
Le schéma de recherche: L'arbre est
structuré par les schémas de recherche. Cette structure est
déterminée par la politique de choix des variables, ainsi que par
la politique de séparation du domaine des variables (arbre binaire, un
noeud-fils par valeur possible, equal-split, ...). Ces schémas de
structure ont un impact important sur les performances du parcours de l'arbre
de recherche (en terme de rapidité de temps de calcul et d'occupation
mémoire). Les schémas les plus connus pour les politiques de
choix de variables sont l'ordre lexicographique, MinDom, ou encore
Dom/DDeg.
Le schéma de complétude :
à partir de ce schéma, on détermine la
complétude de l'algorithme, c'est-à-dire le fait de choisir entre
une exploration complète (et donc une résolution exacte) et une
exploration tronquée (et une résolution approchée). Dans
le cas où l'on souhaite une résolution approchée, on peut
par exemple choisir de ne pas tester toutes les valeurs d'une variable, les
valeurs à tester pouvant être déterminées par des
heuristiques (politique de type Limited Discrepancy Search).
La méthode Dynamic Learning Search
détermine un schéma structurel de l'arbre de recherche, mais
aussi un schéma d'exploration de cet arbre. De plus, cette
méthode est facilement adaptable dans le cas où l'on voudrait une
méthode exacte ou heuristique.
La méthode Dynamic Learning Search (DLS) est
conçue dans l'objectif de diriger la recherche vers les parties de
l'espace des solutions contenant les meilleures solutions. Cette méthode
se veut générique, de manière à pouvoir être
utilisée indépendamment du problème traité. La
méthode DLS se greffe sur un parcours en profondeur et définit de
manière dynamique à chaque noeud de l'arbre des règles de
priorité pour la sélection de la variable sur laquelle brancher
et pour l'ordre dans lequel les différentes valeurs possibles pour
chaque variable sont explorées. Ces ordres sont déduits des
caractéristiques des sous-arbres obtenus jusque là lors de
branchements concernant la même variable. Ainsi, lors de l'exploration,
à chaque fermeture de sous-arbre (c'est-à-dire lorsque la branche
issue de la dernière valeur d'une variable vient d'être
explorée), le poids associé à la variable et l'ordre des
valeurs à instancier pour cette variable sont mis à jour. Ces
mises à jour peuvent dépendre de différents
critères : qualité de la meilleure solution trouvée dans
le sous-arbre considéré, nombre de coupes effectuées (dans
le cas d'un Branch and Bound), moyenne des solutions... En pratique, les
critères retenus dépendent principalement de la nature du
problème : optimisation combinatoire ou satisfaction de contraintes.
Le fonctionnement d'une recherche arborescente semble le
même que ce soit pour un problème d'optimisation combinatoire ou
pour un problème de satisfaction de contraintes. A chaque noeud de
l'arbre de recherche, des décisions sont prises. Ces décisions
concernent la plupart du temps la diminution du domaine d'une variable. La
méthode DLS est donc conçue dans l'optique de pouvoir s'appliquer
assez aisément sur ces deux types de problèmes, avec toutefois
une adaptation de la fonction d'évaluation qui permet de
déterminer les règles de priorité pour la sélection
des variables et l'ordre dans lequel les différentes valeurs possibles
pour la variable sont explorées.
Les sections suivantes vont détailler les trois aspects
de la méthode DLS : Dynamic, Learning et Search.
| 
