1.2.4 Ordre dynamique
Plusieurs travaux ont déjà
développé l'idée d'utiliser un ordre dynamique dans le
choix des variables ou des valeurs. La plupart de ces méthodes
intègrent un processus de mémorisation, appelé look
back.
Frost et Dechter (1994) ont présenté une
nouvelle heuristique d'ordre de choix de valeurs pour les variables,
appelée sticking value. L'idée principale est de garder
en mémoire la valeur assignée à une variable durant la
phase de remontée dans l'arbre, et de sélectionner cette valeur,
si elle est consistante, la prochaine fois que cette variable devra être
instanciée durant une phase de remontée. Leur intuition est que
si cette valeur a été un succès à un moment
donné, cela peut être utile de la choisir plus tard dans la
recherche, afin d'accélérer la résolution. Les
résultats obtenus montrent que cet algorithme offre de bonnes
améliorations des performances, en réduisant de manière
significative les temps d'utilisation du CPU, surtout lorsque les domaines des
variables sont de tailles réduites.
YIELDS (A yet improved limited discrepancy
search) (Karoui et al., 2007) est une méthode exact qui
résout des problèmes de satisfaction de contraintes. YIELDS
est une version améliorée de Limited Discrepancy Search
qui intègre de la propagation de contraintes et de l'apprentissage
d'ordre de variables. Le schéma d'apprentissage, qui est la contribution
principale de cette méthode, est basé sur les échecs
rencontrés durant la recherche, dans le but d'augmenter
l'efficacité de l'heuristique de sélection des variables. Un des
objectifs de YIELDS est de trouver une amélioration au
principal défaut de LDS, celui d'être un algorithme redondant,
c'est-à-dire que des mêmes parcours peuvent être faits un
nombre important de fois. Avec la méthode LDS, l'ordre de
traitement des variables n'est déterminé que par une heuristique
et n'est pas modifié par la méthode. Cela signifie que lorsque
LDS est relancé en augmentant le nombre de déviations
autorisées, on doit instancier plusieurs fois la même variable
initiale. Or, si on suppose que cette variable est la cause d'échecs, il
n'est pas nécessaire de développer sa branche à nouveau.
Pour éviter ce genre de situation, un poids est associé à
chaque variable. Ce poids est fixé initialement à 0. Durant la
résolution de l'algorithme, le poids associé à la variable
est incrémenté à chaque fois que la variable en question
est en échec à cause de la limite sur le nombre de
déviations autorisées : même si le domaine de cette
variable est non vide, on ne peut choisir aucune de ses valeurs sans augmenter
le nombre de déviations. Dans les itérations suivantes, cette
variable sera privilégiée et placée en priorité
dans la branche. Cette technique permet d'éviter la situation
d'inconsistances causées par cette variable. En introduisant la notion
de poids, le but est de corriger l'heuristique de choix dans les variables afin
de guider ce choix vers les variables très contraintes. En effet, ce
sont ces variables en particulier qui influent sur la qualité de la
recherche de solutions. Afin d'accélérer le processus, les
sous-problèmes difficiles et/ou inconsistants sont placés en haut
de l'arbre de recherche. Cette méthode s'applique surtout aux
problèmes de satisfaction de contraintes.
Refalo (2004) a proposé une stratégie de
recherche générale appliquée à de la programmation
par contraintes, basée sur les impacts. L'impact de l'affection de la
variable xi à la valeur a est défini de la
manière suivante : I(xi = a) = 1 -
Paprès/Pavant où P
est défini comme une estimation de la taille de l'arbre
de recherche. L'estimation retenue dans l'article est le produit
cartésien des domaines de l'ensemble des variables. Plusieurs
stratégies de choix de variables sont proposées. Afin de
réduire l'arbre de recherche, la variable ayant l'impact le plus
important est choisie en premier. Le branchement se fera alors sur la valeur de
la variable ayant le plus petit impact. Afin que les décisions prises au
début de l'arbre de recherche soient les plus judicieuses possibles, la
méthode propose une initialisation des impacts en calculant une
approximation des impacts. Celle-ci sera remplacée par la suite par les
impacts effectifs. Des stratégies de redémarrage sont ensuite
appliquées en cours de résolution, lorsque les impacts deviennent
de plus en plus précis.
Levasseur etal. (2007) proposent une extension de
cette méthode pour les problèmes de Weighted Contraint
Satisfaction. L'impact est alors défini comme étant une
estimation de la capacité de l'affectation de la variable a
à la valeur i à être présente dans des
solutions optimales. Des méthodes de descentes gloutonnes permettent
d'augmenter le nombre de solutions rapidement, afin de rendre les impacts plus
précis. La sélection des variables est dans un premier temps
basée sur une heuristique qui choisit la variable ayant le plus petit
rapport de la taille du domaine sur le degré futur, celui-ci
étant défini comme le nombre de contraintes portant sur la
variable qui ont au moins une variable non affectée.
Zanarini et Pesant (2007) proposent une heuristique
centrée sur les contraintes qui guide l'exploration de l'espace de
recherche vers les sous-espaces qui semblent contenir un grand nombre de
solutions. Ils proposent de nouvelles heuristiques de recherche basées
sur le dénombrement de solutions pour chaque contrainte. De plus, ils
proposent des algorithmes pour évaluer le nombre de solutions pour deux
familles de contraintes : les contraintes de dénombrement d'occurrence
et les contraintes d'ordonnancement. Leur intuition est qu'une contrainte avec
peu de solutions correspond à un sous-espace critique du
problème.
Boussemart et al. (2004) présentent une
heuristique d'ordre dynamique sur les variables, appelée
dom/wdeg, qui guide la recherche vers des espaces inconsistants des
problèmes de Satisfaction de Contraintes. Cette heuristique
générique exploite les informations sur des états
précédents de la recherche. Un poids est associé à
chaque contrainte. Ce poids est incrémenté dès que la
contrainte associée est violée durant la recherche.
Récemment, Balafoutis et Stergiou (2008) ont
proposé une méthode qui utilise l'information des poids des
contraintes pour d'une part, établir un ordre de traitement sur les
variables, et d'autre part, trier efficacement la liste de révision des
méthodes basées sur l'arc-consistance. Ils montrent que les
heuristiques proposées, quand elles sont utilisées en même
temps qu'une heuristique de sélection de variable qui suit la politique
«first fail », se montrent très efficaces en réduisant
la taille de l'arbre de recherche par une recherche centrée sur les
variables les plus significatives.
Les méthodes existantes peuvent soulever certaines
difficultés. Certaines sont plus génériques que d'autres
et nécessitent une adaptation au problème pour se montrer les
plus efficaces. Elles sont pour la plupart dépendantes de la nature du
problème; elles sont soit adaptées à des problèmes
d'optimisation combinatoire, soit à des problèmes
de satisfaction de contraintes.
| 
