1.6 Search: un schéma de recherche adapté
à la méthode
La méthode DLS se base sur une recherche en profondeur.
Une fois qu'une variable a été choisie, on choisit une valeur
(selon les règles déterminées par les
pondérations), puis on applique des algorithmes de filtrage (propagation
de contraintes ou calcul de bornes inférieures). S'il reste des
variables non instanciées, on réitère le processus.
Lorsque l'exploration d'un sous-arbre est complète,
c'est-à-dire que toutes les valeurs d'une variable ont été
instanciées, la fonction d'évaluation est appelée, afin
d'obtenir des pondérations pour les valeurs instanciées, ainsi
que pour la variable instanciée. Le fait de mettre les
pondérations à jour uniquement lorsque le sous-arbre est
complété permet d'assurer d'une part la complétude de la
méthode, d'autre part la non-répétition de solutions.
Néanmoins, on peut imaginer ne pas visiter le
sous-arbre dans son intégralité. Une phase de sondage pour chaque
sous-arbre avec des informations de plus en plus complètes au fur et
à mesure de la descente dans l'arbre de recherche permettrait
d'envisager une méthode efficace applicable dans des temps
limités.
De même, on peut appliquer une méthode de type
Limited Discrepancy Search afin de limiter le nombre de valeurs
instanciées pour chaque variable.
Enfin, lorsqu'il faut choisir la prochaine variable à
instancier, on peut limiter le choix aux variables appartenant au voisinage des
variables déjà instanciées (le voisinage d'une variable
xi étant défini comme l'ensemble des variables qui
partagent une contrainte avec xi). Cela permet une certaine
continuité dans le parcours de l'arbre de recherche.
1.7 Algorithme général de la
méthode
Par la suite, nous utiliserons les notations suivantes : Soit
la variable i pour i allant de 1 à n. On note
Di le domaine de la variable i. Soit
pi,j la valeur de la pondération
associée à la jeme valeur de la variable
i, mini (respectivement maxi) la valeur minimum
(respectivement maximum) des pondérations des valeurs de la variable
i.
L'algorithme de la méthode DLS est le suivant :
1.8 Méthode Dynamic Learning Search:
critères de sélection
La plupart des méthodes existantes consistent à
définir des priorités de branchement sur les variables ou sur les
valeurs. La méthode que nous proposons consiste, quant à elle,
à définir dynamiquement des politiques de priorités de
branchement sur les variables, ainsi que sur les valeurs que peuvent prendre
les variables. N'étant pas basée sur des critères
heuristiques, cette méthode se veut surtout générique. En
effet, dans
Algorithme 1 : Algorithme général
de DLS
1 Phase Sondage;
2 tant que critère d'arrêt non
atteint faire
Construction d'arbres aléatoires : choix aléatoire
d'une variable, choix aléatoire d'une valeur dans son domaine;
4 Mises à jour des pondérations en
fonction des arbres aléatoires obtenus par le biais de la fonction
d'évaluation;
5 tant que critère d'arrêt non
atteint faire
6 Sélectionner la variable k
selon les pondérations;
7
8
9
10
Trier les valeurs j avec j ? Dk selon
les pondérations;
Branchement et propagation des contraintes et/ou calcul d'une
borne inférieure;
Mise à jour des pondérations sur les valeurs et sur
les variables au cours de la recherche dès qu'un sous-arbre est
complété (ou une partie du sous-arbre visitée dans le cas
d'une méthode non complète);
Phase d'évaporation;
un premier temps, sa seule dépendance au problème
est la nécessité de différencier les problèmes
d'optimisation combinatoires aux problèmes de satisfaction de
contraintes.
En s'inspirant des principes énoncés
précédemment, notre méthode propose des politiques de
branchement pour les valeurs et pour les variables.
1.8.1 Problèmes de Satisfaction des Contraintes
Dans le cadre de l'application de la méthode DLS aux
problèmes de Satisfaction de Contraintes, plusieurs possibilités
se sont présentées à nous pour les choix des valeurs,
ainsi que pour le choix des variables.
Choix de sélection des valeurs
Dans un problème de Satisfaction de Contraintes, la
réponse classique au problème est de type « oui >> ou
« non >> (existence ou non d'une solution). Le cas où on
recherche l'ensemble des solutions n'est pas abordé ici. La
qualité des solutions trouvées ne peut donc pas être un
critère pour le calcul des pondérations liées aux valeurs
ou aux variables.
Lorsque l'on cherche à résoudre un
problème de satisfaction de contraintes, une solution correspond
à l'instanciation de l'ensemble des variables. La feuille dans l'arbre
de recherche qui correspond à cette solution a donc une profondeur
égale au nombre de variables du problème. On comprend alors que
lorsqu'une solution existe, la feuille correspondante se situera dans un
sous-arbre de profondeur importante. On va donc
chercher à se diriger dans de tels sous-arbres. Le
critère de pondérations pour la politique de branchement sur les
valeurs est donc le suivant : pour chaque valeur de chaque variable, on garde
en mémoire le maximum des profondeurs maximales des sous-arbres
engendrés. La profondeur correspond dans notre cas au nombre de
variables instanciées. On ne différenciera pas le cas des
variables instanciées lors de la phase de propagation des contraintes,
des variables instanciées lors de la séparation. La
pondération associée au choix de cette valeur est donc mise
à jour chaque fois que le choix de cette valeur engendre un sous-arbre
d'une profondeur plus importante que tous les sous-arbres engendrés
précédemment dans l'arbre par cette valeur.
Comme on cherche à se diriger vers les sous-arbres de
plus grande profondeur, on va donc choisir pour chaque variable la valeur ayant
la pondération la plus importante.
La moyenne de la profondeur du sous-arbre engendré ne
nous a pas semblé être un bon critère de sélection.
En effet, une valeur qui amènerait à un sous-arbre ayant un
chemin de grande profondeur et un grand nombre de chemins de petites
profondeurs aurait une moyenne de profondeur de sous-arbre assez faible et
serait donc pénalisée alors que cette valeur peut s'avérer
très intéressante, puisqu'elle a amené à un chemin
de grande profondeur.
Choix de sélection des variables
On a vu que le choix des variables était primordial
pour la taille de l'arbre de recherche. Plusieurs choix sur l'ordre de
sélection des variables sont possibles, certains tirent parti des
pondérations calculées pour le choix des valeurs, d'autres sont
plus génériques et utilisés de façon assez
répandue. Les choix suivants sont des choix classiques de la
littérature.
- Première variable non instanciée : on choisit
parmi les variables non instanciées la première variable dans un
ordre lexicographique.
- Plus petit domaine : on choisit en priorité parmi les
variables non instanciées la variable qui possède le plus petit
domaine. Ce domaine peut être calculé en phase initiale de la
résolution du problème ou de manière dynamique à
chaque noeud.
- Plus petit regret minimum : ce choix renvoie la variable
avec la plus petite différence entre la plus petite valeur possible et
la prochaine plus petite valeur possible. Ce choix est basé sur le
principe de regret. Le regret est défini comme la différence
entre ce qu'aurait été la meilleure décision possible dans
un scénario et la décision actuelle. Dans un problème des
satisfaction de contraintes, on peut définir le regret minimum comme la
différence entre les deux plus petites valeurs du domaine d'une
variable.
- Plus petit regret maximum: ce choix renvoie la variable avec
la plus petite différence entre la plus grande valeur possible et la
prochaine plus grande valeur possible.
- Plus fort degré : on choisit la variable ayant le
degré futur le plus important, le degré étant
défini pour une variable comme le nombre de contraintes portant sur
celle-ci et ayant au moins une variable non affectée.
- Plus petit domaine divisé par le plus fort
degré (MinDom/Deg) : on choisit la variable ayant le plus petit rapport
entre la taille de son domaine et le degré de cette variable.
Pour les choix des variables qui utilisent les
pondérations sur les variables, nous avons proposé les ordres
suivants :
- Profondeur maximale : on choisit parmi les variables non
instanciées la variable qui a parmi ses valeurs celle qui a amené
au sous-arbre le plus profond. Ce choix ne nous semble pas cohérent. En
effet, lors de la fermeture d'un sous-arbre de profondeur n (où
n est maximal), toutes les variables instanciées ont une de
leurs valeurs qui a une pondération égale à n.
Selon le critère « Profondeur maximale » pour le choix de la
variable, toutes les variables auraient la même pondération et il
faudrait donc choisir parmi toutes ces variables. Ce choix pourrait alors se
faire de manière aléatoire ou lexicographique, mais ne
profiterait pas des informations apportées par les pondérations
sur les valeurs.
- Moyenne maximale : ce critère propose de choisir la
variable ayant la moyenne de pondération de ses valeurs la plus
importante. Par ce principe, on cherche à brancher en priorité
sur les variables qui ont amené à des sous-arbres de taille
importante. Ce critère est en opposition avec certains principes
proposés auparavant (Haralick et Elliot, 1980).
- Moyenne minimale : ce critère propose de choisir la
variable ayant la moyenne de pondération de ses valeurs la moins
importante. On dirige donc la recherche vers les variables les plus
contraintes. Ce critère est proche de la philosophie de la
méthode First Fail.
- Plus petit écart aux extrêmes : ce
critère part du principe que les variables les plus intéressantes
sont les variables dont les valeurs ont amené à des sous-arbres
soit de toute petite profondeur (ces variables réduisent la taille de
l'arbre de recherche) soit de grande profondeur. On cherche donc à
choisir en priorité les variables dont les pondérations sur les
valeurs sont le plus proches possibles des extrêmes. On branchera donc
sur la variable qui minimise l'équation (1.1).
1
|Di| ? minimum(n -
pi,j, pi,j) (1.1)
j?Di
où n représente le nombre de variables (et
donc une borne supérieure de la profondeur maximale de l'arbre de
recherche).
Pour ne pas privilégier les variables dont le domaine
initial est restreint, cette somme est divisée par le nombre de valeurs
du domaine (|Di|).
On peut remarquer que si l'on enlève le premier terme du
minimum, on cherche alors la variable qui minimise
1
|Di| ? (n - pi,j) (1.2)
j?Di
ce qui est équivalent à rechercher la variable qui
maximise
1
|Di| ? (pi,j) (1.3)
j?Di
Ce critère correspond alors à une constante
prêt au critère de choix de Moyenne maximale. De manière
équivalente, si l'on enlève le deuxième terme, on cherche
alors la variable qui minimise
1
|Di| ? (pi,j) (1.4)
j?Di
ce qui correspond au critère de choix de Moyenne
minimale.
Les critères de pondérations retenus pour les
choix des valeurs (et donc certains des critères de choix des variables
qui dépendent des pondérations) ne sont pas adaptés pour
les problèmes d'optimisation combinatoire.
| 
