Première partie
Favoriser l'obtention rapide de
solutions dans les méthodes de
recherche arborescente
1 Dynamic Learning Search : une méthode par
apprentissage 19
1.1 Introduction 19
1.2 État de l'art des recherches arborescentes 20
1.2.1 Méthode de parcours de l'arbre de recherche 21
1.2.2 Méthode de structuration de l'arbre de recherche
22
1.2.3 Parcours réduit de l'arbre 22
1.2.4 Ordre dynamique 24
1.2.5 Apprentissage : look-back 26
1.2.6 Métaheuristiques combinées à la
recherche arborescente 27
1.3 Dynamic Learning Search : une méthode par
apprentissage 28
1.4 Learning : une méthode basée sur un
apprentissage 29
1.4.1 Sondage 29
1.4.2 Apprentissage 30
1.4.3 Prévision 32
1.4.4 Remise en question 32
1.5 Dynamic : un ordre dynamique de choix des variables et de
sélection des
valeurs 33
1.6 Search: un schéma de recherche adapté à
la méthode 34
1.7 Algorithme général de la méthode 34
1.8 Méthode Dynamic Learning Search : critères de
sélection 34
1.8.1 Problèmes de Satisfaction des Contraintes 35
1.8.2 Problèmes d'Optimisation Combinatoire 38
1.8.3 Méthode commune aux deux types de problèmes
39
1.9 Résultats expérimentaux 40
1.9.1 Application au problème du Voyageur de Commerce
40
1.9.2 Application au problème d'Emploi du Temps de Garde
d'Infirmières 41
1.9.3 Application à des problèmes de
Satisfaction de Contraintes aca-
démiques 43
1.10 Conclusion et perspectives 47
Chapitre 1
Dynamic Learning Search: une
méthode par apprentissage
1.1 Introduction
La plupart des méthodes de résolution exacte
utilisées en optimisation combinatoire s'appuient sur une
énumération intelligente des solutions (Branch & Bound,
Programmation par contraintes, Programmation dynamique ...). Cette
énumération consiste en règle générale en la
construction d'un arbre de recherche, au cours de laquelle la création
d'un fils pour un noeud correspond à une prise de décision:
typiquement fixer une valeur à une variable. L'exploration
complète d'un tel arbre peut s'avérer très coûteuse
en temps. Il est donc classique de fixer une limite de temps, rendant ainsi
l'exploration incomplète. Si cette limite de temps est atteinte avant la
fin de l'exploration complète de l'arbre de recherche, on retourne la
meilleure solution trouvée (dans le cas où une ou plusieurs
solutions ont été trouvées). Un défaut connu de
cette approche est que l'exploration peut se faire dans un premier temps sur un
sous-arbre qui ne contient pas ou peu de solution intéressante et ainsi
utiliser tout le temps alloué à n'explorer que ce sous-arbre.
Cette situation conduit à retourner une mauvaise solution (ou aucune
solution). On a donc tout intérêt à mettre en place des
techniques favorisant l'exploration en priorité de parties de l'espace
de recherche contenant de bonnes solutions. Il s'agit de gérer au mieux
la prise de décision à la fois en ce qui concerne la construction
de l'arbre et le parcours des noeuds créés, et ce dès le
début de l'arbre. La méthode que nous proposons, Dynamic
Learning Search a été conçue dans le but de diriger
l'exploration de l'arbre de recherche vers les parties de l'espace des
solutions contenant les meilleures solutions. Notre objectif est de proposer
une méthode générique, de manière à pouvoir
l'utiliser indépendamment du type de problème traité :
problèmes d'optimisation combinatoire ou problèmes de
satisfaction de contraintes. La méthode DLS 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 de l'ordre dans lequel les différentes valeurs pour chaque variable
sont explorées. Ces ordres sont déduits des
caractéristiques des sous-arbres obtenus jusqu'ici lors de branchements
concernant la même variable.
| 
