# Recherche locale dichotomique pour la résolution des CSP continus

Vincent Barichard, Jin-Kao Hao

► To cite this version:

Vincent Barichard, Jin-Kao Hao. Recherche locale dichotomique pour la résolution des CSP continus. 13èmes Journées Francophones de Programmation Logique et programmation par Contraintes (JFPLC'04), Jun 2004, Angers, France. pp.253-258. hal-04031235

HAL Id: hal-04031235

https://univ-angers.hal.science/hal-04031235

Submitted on 15 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Recherche locale dichotomique pour la réso-
lution des CSP continus

Vincent Barichard — Jin-Kao Hao

Laboratoire d'Étude et de Recherche en Informatique d'Angers (LERIA)
Faculté des Sciences
2, Bd Lavoisier
F-49045 Angers Cedex 01
(Vincent.Barichard,Jin-Kao.Hao)@univ-angers.fr

RÉSUMÉ. Nous présentons un algorithme heuristique pour déterminer une solution d'un pro-
blème de satisfaction de contraintes continu. Cet algorithme, appelé Recherche Locale Dicho-
tomique (RLD), combine la recherche locale, la bissection et la contraction d'intervalle avec
la propagation de contraintes. Nous présentons des résultats expérimentaux et les comparons
avec un algorithme de recherche locale pure basé sur la stratégie d'évolution.

ABSTRACT. We present a heuristic algorithm for solving continuous constraint satisfaction prob-
lems. This algorithm, called Dichotomic Local Search (DLS), combines local search with tech-
niques such as bisection and interval constraint propagation. Experimental results are pre-
sented and compared with an Evolution Strategy algorithm.

MOTS-CLÉS: Heuristiques, recherche locale, bissection, propagation de contraintes, satisfaction de contraintes.

KEYWORDS: Heuristics, local search, bisection, constraint propagation, constraint satisfaction.
# 1. Introduction

Les problèmes de satisfaction de contraintes continus (CSPC) ou numériques, tout comme les CSP discrets, constituent un modèle très général et puissant permettant la formulation d'un grand nombre d'applications pratiques. Informellement, un CSP continu est défini par un ensemble de variables dont chacune est associée à un intervalle dans $\mathbb{R}$ (domaine) et un ensemble de contraintes. Une solution au problème est une affectation de valeurs, tirées des domaines des variables, telle que les contraintes du problème soient satisfaites simultanément. Étant donné un CSPC, il existe plusieurs problématiques liées :

1) Recherche d'une solution vérifiant toutes les contraintes;

2) Test de faisabilité (existe-il une solution ?);

3) Satisfaction maximale de contraintes (Max-CSP);

4) Détermination de l'espace des solutions ainsi que sa représentation.

Pour résoudre un CSP, en particulier pour trouver une solution, deux approches sont couramment utilisées : les approches complètes et les approches incomplètes.

Les approches complètes, représentées essentiellement par les algorithmes de bissection récursive ou de Branch-and-Bound [COC 01], permettent de calculer de manière exacte (à une certaine précision fixée) la première solution ou d'encadrer l'ensemble des solutions du CSPC. De par la nature même d'une recherche exacte, ces algorithmes ont en général une complexité exponentielle (en temps et en espace). Ainsi, le nombre de découpes (et de contractions) nécessaires à un algorithme de bissection récursive pour atteindre une solution peut devenir très vite prohibitif.

Il est assez curieux de constater que jusqu'à présent, peu de travaux existent dans la littérature concernant les méthodes incomplètes pour la résolution des CSPC. Notons néanmoins que les méthodes d'optimisation heuristiques comme les stratégies d'évolution [SCH 81] pourraient être directement adaptées aux CSPC. Ces méthodes utilisent des heuristiques pour tenter de trouver rapidement une solution faisable sans parcourir la totalité de l'espace de recherche. Même si les méthodes heuristiques n'ont pas la garantie de trouver une solution à chaque fois, elles représentent souvent une alternative indispensable et satisfaisante lorsque les méthodes complètes échouent.

Dans cet article, nous proposons un algorithme heuristique que nous appelons « Recherche Locale Dichotomique (RLD) ». Cet algorithme combine une recherche locale à la « stratégie d'évolution » avec les techniques classiques de contraction d'intervalles, de propagation de contraintes et de recherche dichotomique par bissection. L'idée fondamentale de la RLD est d'utiliser la contraction et la propagation de contraintes pour éliminer des parties non réalisables de l'espace de recherche, et d'employer la rechercher locale pour orienter la découpe et pour exploiter rapidement les zones délimitées par la découpe.

Pour évaluer la performance de notre algorithme, nous réalisons des expérimentations numériques sur des jeux de test couvrant des caractéristiques différentes et va-
riées et présentons des comparaisons entre *RLD* et un algorithme de recherche locale
à la « stratégie d'évolution ».

Notons que la recherche de solutions pour un CSP permet de tester partiellement
la faisabilité (point 2), et de par la nature même de l'approche proposée permet aussi
de résoudre le problème de satisfaction maximale de contraintes (point 3). Enfin, la re-
cherche de solutions est également indispensable pour l'optimisation sous contraintes
dont une des tâches les plus difficiles consiste à trouver des points faisables.

Le reste de l'article est organisé en trois sections. La section 2 présente l'algo-
rithme *RLD*, la section 3 est consacrée aux expérimentations et comparaisons. La
dernière section donne quelques conclusions et perspectives.

## 2. Recherche locale dichotomique (RLD)

### 2.1. Principe général

Comme les autres méthodes fondées sur le principe de bissection, l'algorithme
« Recherche Locale Dichotomique (RLD) », utilise une représentation de l'espace
de recherche par intervalles et manipule de manière itérative des boîtes, une boîte [x]
de $\mathbb{R}^n$ correspondant simplement au produit cartésien de n intervalles de $\mathbb{R}$. La dif-
férence fondamentale de la RLD par rapport aux méthodes de bissection existantes
réside dans l'introduction de la recherche locale comme un moyen puissant d'exploi-
tation de zones de recherche, mais aussi d'orientation pour les choix des découpes.

Partant de la boîte $[x]$ de $\mathbb{R}^n$ définie par les domaines des variables (intervalles)<fnref n="1" /> du
CSPC initial, la RLD répète la séquence suivante d'actions : *Bissection* - *Contraction*
*et propagation* - *Recherche Locale* - *Remplacement de boîte*.

La *Bissection* coupe l'intervalle d'une variable en deux intervalles. Cette opération
nous conduit à l'obtention de deux nouvelles boîtes [a] et [b], qui sont ensuite réduites
grâce à une phrase de *contraction et propagation de contraintes* sur des intervalles
(ICP) (cf. Section 2.3). Cette phase de propagation de contraintes sur des intervalles
a pour but de réduire certains intervalles d'une boîte en retirant des valeurs inconsis-
tantes et, par conséquent, supprimer définitivement des zones de l'espace de recherche
n'ayant pas de solutions faisables.

Après l'application des algorithmes d'ICP, trois situations sont possibles :

1) Aucune des deux boîtes (réduites) n'est consistante (les applications d'ICP ont
conduit à l'obtention d'un intervalle vide). Dans ce cas l'algorithme s'arrête.

2) Seulement une des deux boîtes est consistante. Dans ce cas, nous abandonnons
la boîte inconsistante et continuons avec la boîte consistante.

<footnote n="1">1. Les domaines sont supposés être localement consistants. Si ce n'est pas le cas, une phase d'ICP (cf. Section 2.3) est appliquée au préalable pour les rendre consistants.</footnote>
3) Les deux boîtes sont consistantes. Dans ce cas, nous appliquons la recherche locale sur chacune des deux boîtes. Plus précisément, nous appliquons une phase de recherche locale pour tenter de trouver une solution dans chacune des boîtes. Si une solution est effectivement trouvée, alors le CSP est résolu. Si ce n'est pas le cas, nous continuons sur la phase de bissection avec la "meilleure" des deux boîtes selon la recherche locale, c'est-à-dire celle ayant un degré moindre de violation des contraintes obtenu par la recherche locale. La boîte qui n'a pas été sélectionnée est définitivement oubliée.

Notons que dans l'algorithm RLD, la phase de recherche locale joue un rôle fondamental et complémentaire par rapport au mécanisme de bissection. D'une part, elle permet de rechercher effectivement et efficacement une solution réalisable dans une boîte. D'autre part elle informe le mécanisme de bissection dans ses choix de boîte à conserver pour les découpes à venir. Cette caractéristique originale contribue grandement à la performance de l'algorithm RLD.

Notons également que l'algorithm RLD peut être considéré comme une heuristique d'exploration d'une seule branche de l'arbre de recherche. Cet algorithm s'arrête lorsqu'un domaine est réduit à vide par l'ICP, ou lorsqu'une solution réalisable a été trouvée.

Le pseudo-code de l'algorithm 1 montre le fonctionnement de l'algorithm de recherche locale dichotomique :

<table><caption>**Algorithm 1** Algorithme général de la recherche locale dichotomique</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Soit I la boîte initiale</td><td></td></tr><tr><td><strong>Répéter</strong></td><td></td></tr><tr><td>- Couper I pour obtenir I<sub>1</sub> et I<sub>2</sub></td><td></td></tr><tr><td>- Appliquer sur chaque I<sub>k</sub> une phase d'ICP, et conserver les I<sub>k</sub> localement consistant</td><td></td></tr><tr><td>- Si un seul I<sub>k</sub> est localement consistant <strong>Alors</strong></td><td></td></tr><tr><td>Remplacer I par le I<sub>k</sub> restant</td><td></td></tr><tr><td>- <strong>Sinon</strong></td><td></td></tr><tr><td>Appliquer sur chaque I<sub>k</sub> restant l'opérateur de <em>Recherche Locale continue</em></td><td></td></tr><tr><td>Remplacer I par le meilleur I<sub>k</sub> au sens de la fonction d'évaluation</td><td></td></tr><tr><td>- <strong>FinSi</strong></td><td></td></tr><tr><td><strong>Jusqu'à ce qu'un</strong> point réalisable soit trouvé, ou qu'aucun des I<sub>k</sub> ne soient localement consistant</td><td></td></tr></tbody></table>

Dans les sous-section suivantes, nous présentons les différents composants de l'algorithm RLD.
## 2.2. Représentation de l'espace de recherche

Dans la plupart des algorithmes fondés sur des heuristiques, une configuration correspond à un vecteur de décision, chaque variable étant instanciée par une valeur de $\mathbb{R}$. Avec cette représentation, chaque configuration correspond à un point particulier dans l'espace de recherche.

Dans notre approche, chaque configuration est aussi un vecteur, mais chaque variable est maintenant représentée par un *intervalle* au lieu d'une valeur simple. En conséquence, chaque configuration correspond maintenant à une *boîte* $[x]$ de $\mathbb{R}^n$ (n étant le nombre de variables du problème) dans l'espace de recherche.

La représentation de l'espace de recherche par des intervalles est nécessaire à l'utilisation des méthodes de bissection et de réduction. L'opérateur de recherche locale, qui nécessite un point particulier pour s'exécuter, choisira un point de la boîte (par exemple le centre) pour initialiser sa recherche. Pour rester cohérent avec notre représentation, cet opérateur n'aura accès qu'aux points contenus dans la boîte.

## 2.3. Analyse par intervalles et propagation des contraintes

Dans cette sous-section, nous présentons les concepts de base des mécanismes de contraction et de propagation sur des contraintes modélisées par des intervalles (*Interval Constraint Propagation*, ICP). Les algorithmes d'ICP combinent le calcul par intervalles [MOO 79] et la propagation des contraintes [MAC 77] pour résoudre des systèmes d'équations et d'inéquations non linéaires. Les premiers algorithmes d'ICP furent introduits par Cleary [CLE 87] et Davis [DAV 87]. Depuis ces travaux, d'autres algorithmes de contraction performants ont été implémentés, citons par exemple, les travaux présentés dans [LHO 93, SAM 96, Van 97, BEN 99].

### 2.3.1. Analyse par intervalles et contraction

Chaque variable du problème est représentée par un intervalle, et liée aux autres variables par une ou plusieurs contraintes. Il est clair que l'ensemble des affectations réalisables de variables reliées entre elles par une ou plusieurs contraintes est un sous-ensemble du produit cartésien des domaines de ces dites variables. Grâce aux techniques d'analyse par intervalles, il est possible, dans certains cas, de répercuter sur les domaines des variables certaines informations déduites des contraintes. Ces informations permettent de retirer du domaine des variables des valeurs ne participant à aucune solution, car violant au moins une contrainte.

Suite aux travaux de Moore [MOO 79], des opérateurs de réduction (ou contraction) ont été formalisés. En appliquant ces opérateurs sur une contrainte (ou fonction) il est possible de réduire le domaine d'une variable en contractant les bornes de l'intervalle. Cette contraction n'affecte en rien les solutions du problème. En effet, la contraction d'un intervalle par une fonction ou contrainte peut être calculée grâce à des opérateurs de réduction (ou contraction), et ceci sans perdre de solution.
De manière générale, pour chaque contrainte primitive<fnref n="2" /> (ou élémentaire), il existe un opérateur de réduction permettant de contracter chacun des domaines des variables. Pour une contrainte non primitive, formée à partir de plusieurs contraintes primitives, il est aussi possible de calculer un opérateur de réduction en composant les différents opérateurs de réduction de chaque contrainte primitive présente dans la contrainte non primitive. Pour plus d'informations sur ces opérateurs de contraction, le lecteur est invité à consulter le livre de L. Jaulin et al. [JAU 01].

### 2.3.2. Exemple de contraction avec la contrainte cubique

Considérons que les deux variables $x$ et $y$ appartiennent à des domaines dont toutes les valeurs sont à priori valides.

Considérons maintenant la contrainte : $y = x^3$ avec $x \in [x^{-}, x^{+}] = [-2, 2]$ et $y \in [y^{-}, y^{+}] = [-8, 9]$. Il résulte de cette définition que la contrainte cubique est un sous ensemble de $\mathbb{R}^2$ : cubique = $\{(x, y) \in \mathbb{R}^2 | y = x^3\}$

La contrainte cubique est une contrainte binaire puisqu'elle prend en compte deux variables $x$ et $y$. Dans notre exemple, la contrainte cubique peut être utilisée pour enlever des valeurs inconsistantes du domaine de $y$. En effet, nous observons que : $\forall x \in [-2, 2], x^3 \le 8$. Donc, toutes les valeurs du domaine de $y$ plus grandes que 8 peuvent être retirées, car elles ne participent à aucune solution. De manière plus formelle, la contrainte cubique permet de réduire le domaine de $x$ et de $y$ grâce à l'opérateur de contraction suivant :

$$ 
\left\{ 
\begin{array}{lcl}
[x^{-}, x^{+}] & \leftarrow & [x^{-}, x^{+}] \cap (\sqrt[3]{[y^{-}, y^{+}]}) \\
[y^{-}, y^{+}] & \leftarrow & [y^{-}, y^{+}] \cap ([x^{-}, x^{+}]^3) \\[1em]
où & & \sqrt[3]{[y^{-}, y^{+}]} = [\sqrt[3]{y^{-}}, \sqrt[3]{y^{+}}] \\
et & & [x^{-}, x^{+}]^3 = [(x^{-})^3, (x^{+})^3]
\end{array}
\right. 
$$

Cet opérateur de réduction (ou contraction) peut ensuite être ré-appliqué à chaque modification du domaine d'une des deux variables. En effet, un autre opérateur de contraction peut, en utilisant une autre contrainte du problème, être amené à réduire un domaine d'une de nos deux variables.

### 2.3.3. Atteindre un point fixe

Pour un ensemble de contraintes, l'application itérative de procédures de contraction (issues du calcul par intervalles) sur les contraintes conduit à l'obtention d'un état où plus aucun domaine de variables ne peut être réduit. Cet état est le point fixe de cet ensemble de contraintes. Notons que ce point fixe ne constitue pas une solution car les variables ne sont pas encore instanciées. Pour obtenir une solution, il est nécessaire d'utiliser en plus des méthodes d'exploration de l'espace de recherche. Dans *RLD*, nous utilisons conjointement la bissection et la recherche locale.

<footnote n="2">2. Une contrainte primitive n'est formée que d'un seul opérateur arithmétique ou trigonométrique.</footnote>
### 2.3.4. La bisection

Un algorithme d'ICP est une procédure polynomiale qui réduit (contracte) le domaine des variables du problème. Cette famille d'algorithmes réduit l'espace de recherche en retirant des valeurs inconsistantes du domaine des variables par rapport à chaque contrainte du problème. À aucun moment, une solution du problème n'est enlevée. Cependant, l'application d'un algorithme d'ICP conduit seulement à l'obtention d'une approximation de la solution. Pour augmenter la précision de cette approximation, il est nécessaire de découper le domaine des variables et d'appliquer des algorithmes d'ICP sur les différentes alternatives obtenues. En itérant ce procédé, nous augmentons la précision, mais nous tendons vers un nombre exponentiel de découpes, et donc un très long temps de calcul. En pratique, cette approche n'est pas applicable aux problèmes ayant un grand nombre de variables.

Dans notre algorithme *RLD*, nous effectuons plusieurs bissections pour augmenter la précision de la boîte courante. Toutefois, pour ne pas trop augmenter la complexité de l'algorithme, nous limitons le nombre de ces bissections (cf. Algorithme 1). La stratégie utilisée pour couper chaque boîte consiste à choisir la variable ayant *le plus grand intervalle* et à le couper en deux de manière à obtenir deux boîtes distincts. Notons que le but de *RLD* est de trouver le plus rapidement possible une solution réalisable et que le "plus grand domaine" à *a priori* plus de chances de contenir de telles solutions.

## 2.4. L'opérateur de recherche locale continue (RLC)

Rappelons qu'une boîte $[x]$ de longueur $n$ est définie à partir de $n$ intervalles. Donnons-nous une telle boîte, un opérateur de recherche locale continue (*RLC*) recherche un point réalisable $x \in [x]$. Le concept de *RLC* ressemble beaucoup à la stratégie d'évolution (1+1), une méthode heuristique d'optimisation très réputée [SCH 81]. Parmi le grand nombre de méthodes heuristiques existantes pour l'optimisation, nous avons choisi une méthode à la stratégie d'évolution car il est facile d'en décliner une version simple nécessitant peu de paramètres (ici un seul). Nous décrivons maintenant son principe de fonctionnement.

Démarrant avec un point $x^0$ tiré dans la boîte $[x]$, *RLC* génère de manière itérative une série de points voisins de meilleure qualité (violant moins de contraintes) $x^0, x^1, \dots, x^i, x^{i+1}, \dots$. Dans notre algorithme, le point initial $x^0$ est généré en as signant à chaque variable le milieu de son intervalle de définition. Plus concrètement, l'algorithme *RLC* est défini par trois éléments centraux : 1) une *fonction d'évaluation* pour mesurer la qualité des points, 2) une *fonction de voisinage* pour générer les points voisins et 3) une *stratégie de mouvement* décidant de l'acceptation ou du rejet d'un point voisin.

### 2.4.1. Fonction d'évaluation

Soit $C$ l'ensemble de contraintes du CSPC initial et $x$ un point de $\mathbb{R}^n$, la fonction d'évaluation est simplement définie comme suit :
$$ eval(\mathbf{x}, C) = \sum \{deg(c, \mathbf{x}) \mid c \in C, c \text{n'est pas satisfait par } \mathbf{x}\} $$

où deg(c, x) est la fonction évaluant le niveau de violation de la contrainte c en fonction de la configuration x. Ainsi, cette fonction calcule la distance entre l'évaluation de la contrainte violée et son domaine de faisabilité. Plus la valeur de l'évaluation de la contrainte est éloignée du domaine de faisabilité, plus le niveau de violation sera élevé. Évidemment, la valeur minimale de la fonction eval(x, C) est 0, correspondant à un point satisfaisant toutes les contraintes de C. Dans la suite, nous utiliserons eval(x) en remplacement de eval(x, C).

Prenons comme exemple, le calcul de deg(c, x) quand c correspond à la contrainte $x + y \le 3$ et quand x correspond à la configuration (3, 4). Alors, $x + y = 3 + 4 = 7$, et le degré de violation de la contrainte est égal à $7 - 3 = 4$. D'où, deg(c, x) = 4 dans notre exemple.

### 2.4.2. Fonction de voisinage

Soit un point x, un point voisin x' est construit en ajoutant des nombres aléatoires à x. Dans la suite, $x_i$ désigne la $i^{\text{ème}}$ composante du vecteur x. La fonction de voisinage est définie formellement de la manière suivante :

$$ \text{voisin}(x_i) = \begin{cases} \text{Soit } x_i' = x_i + (x_i^{(U)} - x_i^{(L)}) \times \mathbf{N}_0(\delta, \sigma_i) \\ \text{Si } x_i' > x_i^{(U)} \text{ alors renvoyer } x_i^{(U)} \\ \text{Sinon } x_i' < x_i^{(L)} \text{ alors renvoyer } x_i^{(L)} \\ \text{Sinon renvoyer } x_i' \end{cases} $$

où $x_i^{(U)}$ et $x_i^{(L)}$ correspondent respectivement à la borne supérieure et inférieure de la $i^{\text{ème}}$ composante, $\mathbf{N}_0$ désigne un vecteur de nombres aléatoires indépendants de moyenne 0, $\delta$ une fonction stochastique basée sur une loi de probabilité et $\sigma_i \in \{1, \dots, n\}$ l'écart type (ou facteur de perturbation).

Pour obtenir une fonction de voisinage complète, nous devons implémenter deux composants : la fonction $\delta$ et le vecteur $\sigma$.

Le vecteur $\mathbf{N}_0$ est calculé grâce aux fonctions $\delta$ et $\sigma$. De plus, comme $\mathbf{N}_0$ est un vecteur de nombres aléatoires indépendants, une valeur aléatoire, nécessaire à $\delta$, est calculée au préalable. Chaque élément de $\mathbf{N}_0$ peut être calculé de la manière suivante :

$$ \mathbf{N}_0(\delta, \sigma) = (\delta(r_0, \sigma_0), \dots, \delta(r_n, \sigma_n)) \text{ où } r_i \text{ est une valeur aléatoire} $$

Il est clair que $\mathbf{N}_0$ dépend fortement de la fonction $\delta$. Dans cette étude, nous utilisons plusieurs fonctions $\delta$ basées sur des lois de probabilité différentes. Nous décrivons maintenant les deux meilleures retenues après nos expérimentations.
La première ($\delta_G$), qui est aussi la plus classique, est basée sur une distribution de probabilité gaussienne $P_G$ (Laplace-Gauss) de la forme suivante :

$$P_G(\delta_G, \sigma_i) = \frac{1}{\sigma_i \sqrt{2\pi}} \times \exp\left(-\frac{\delta_G^2}{2\sigma_i^2}\right)$$

À partir de cette formule, nous pouvons déduire une expression de $\delta_G$ qui calcule la variation à appliquer à la composante $x_i$ de notre point courant :

$$\delta_G = \begin{cases} -\sqrt{-2\sigma_i^2 \log(-r_i\sigma_i\sqrt{2\pi})}, & \text{if } r_i < 0 \\ \sqrt{-2\sigma_i^2 \log(r_i\sigma_i\sqrt{2\pi})}, & \text{if } r_i \ge 0 \end{cases} \\ r_i \in \left[ \frac{1}{\sigma_i\sqrt{2\pi}} \cdots \frac{1}{\sigma_i\sqrt{2\pi}} \right]$$

La seconde ($\delta_P$) est fondée sur une distribution de probabilité polynomiale $P_P$ formulée comme suit :

$$P_P(\delta_P, \sigma_i) = \frac{1}{2} \times (1 - |\delta_P|)^{(\sigma_i+1)}$$

À partir de cette formule, nous pouvons déduire une expression de $\delta_P$ qui calcule la variation à appliquer à la composante $x_i$ de notre point courant :

$$\delta_P = \begin{cases} (2r_i)^{\frac{1}{\sigma_i+1}} - 1, & \text{if } r_i < 0.5 \\ 1 - [2(1 - r_i)]^{\frac{1}{\sigma_i+1}}, & \text{if } r_i \ge 0.5 \end{cases} \\ r_i \in [0 \cdots 1]$$

Cette fonction, présentée dans [DEB 96], a été utilisée pour implémenter des opérateurs de mutation dans des algorithmes génétiques, ceux-ci ont obtenu des résultats expérimentaux très intéressants.

Le vecteur de perturbation $\sigma$ doit aussi être défini. Dans cet article, nous utilisons des valeurs initiales déjà testées par d'autres chercheurs (cf. tableau 1). L'algorithme *RLC* utilise des lois de probabilité pour ajouter des quantités aléatoires aux variables. Notre algorithme étant très similaire aux algorithmes (1+1) ES, il est clair que les atouts de ces algorithmes sont exploités dans notre algorithme *RLC*.

Comme de nombreux choix sont possibles pour ces fonctions, nous ne pouvons pas étudier toutes les combinaisons. Nous avons donc décidé de garder quelques alternatives représentatives utilisées pour les expérimentations dans cet article (cf. Section 3). Le tableau 1 récapitule les trois meilleures combinaisons (appelées $RLC_G$, $RLC_E$ et $RLC_P$ dans la suite) gardées pour nos expérimentations (cf. Section 3).
<table><caption>**Tableau 1. Opérateurs de recherche locale continue**</caption><thead><tr><th></th><th>RLC<sub>G</sub></th><th>RLC<sub>E</sub></th><th>RLC<sub>P</sub></th></tr></thead><tbody><tr><td>Loi de probabilité : δ</td><td>Laplace-Gauss : δ<sub>G</sub></td><td>Laplace-Gauss : δ<sub>G</sub></td><td>Polynomiale : δ<sub>P</sub></td></tr><tr><td>Vecteur de perturbation : σ</td><td>(<sup>1.22</sup>&frasl;<sub>n</sub>, ..., <sup>1.22</sup>&frasl;<sub>n</sub>)</td><td>(<sup>1.22 &times; |x<sub>i</sub>|</sup>&frasl;<sub>n</sub>, ..., <sup>1.22 &times; |x<sub>n</sub>|</sup>&frasl;<sub>n</sub>)</td><td>(20, ..., 20)</td></tr></tbody></table>

### 2.4.3. Stratégie de mouvement

Soient un point $\mathbf{x}$ et un point $\mathbf{x}'$ issu de son voisinage. Une stratégie de mouvement définit les règles utilisées pour décider ou non du mouvement du point courant vers le point voisin. Dans cet article, nous utilisons une règle à la manière des méthodes de descente qui n'acceptent que les voisins améliorant le point courant.

### 2.4.4. Critère d'arrêt

Les algorithmes RLC étant des processus itératifs stochastiques, il est nécessaire de définir un critère d'arrêt pour assurer la terminaison de l'algorithme. Dans notre cas, l'algorithme s'arrête lorsque un solution réalisable est trouvée ou lorsqu'un nombre d'itérations fixé au préalable est atteint par l'algorithme.

## 2.5. Discussion

Notre algorithme RLD est formé de plusieurs composants tels que l'analyse par intervalles, la propagation de contraintes, la bissection et la recherche locale continue. De ces différents composants, c'est le dernier qui nécessite le plus d'attention. En effet, une recherche locale continue est définie par plusieurs éléments, dont certains comme la fonction de voisinage, sont difficiles à régler. Ainsi, comme nous l'avons vu dans les sections précédentes, nous avons définis plusieurs variantes de la recherche locale continue (RLC<sub>G</sub>, RLC<sub>E</sub> et RLC<sub>P</sub>) en nous basant sur plusieurs fonctions de voisinages différentes. Ainsi nous avons définis plusieurs variantes de la recherche locale dichotomique (RLD<sub>G</sub>, RLD<sub>E</sub> et RLD<sub>P</sub>), chacune étant fondée sur un algorithme RLC différent.

## 3. Expérimentations

Dans cette section, nous évaluons les algorithmes présentés à la section précédente sur quelques problèmes test issus de différentes communautés de recherche. Rappe-lons que, pour ces algorithmes, nous cherchons à trouver le premier point réalisable et non pas à déterminer toutes les solutions du problème.

Ces expérimentations sont regroupées en deux séries : la première série regroupe les résultats des comparaisons des algorithmes de recherche locale (RLC<sub>G</sub>, RLC<sub>E</sub>
et RLC<sub>P</sub>) seuls (comme présenté à la section 2.4). Ces algorithmes, fondés sur la stratégie d'évolution (1+1)-ES, nous serviront de référence lors de la deuxième série d'expérimentations. La deuxième série d'expérimentations regroupe les résultats obtenus par nos algorithmes de recherche locale dichotomique (RLD<sub>G</sub>, RLD<sub>E</sub> et RLD<sub>P</sub>).

**3.1. Les problèmes test**

Pour ces expérimentations, nous utilisons quatre jeux de problèmes comprenant dix instances. Tous ces problèmes sont définis à partir d'un ensemble de contraintes linéaires et non linéaires.

Le premier jeu est constitué d'une seul instance (TNK) présentée par Tanaka [TAN 95]. Initialement, TNK est un problème d'optimisation sous contraintes, seules les contraintes ont été conservées pour définir un CSP. Le deuxième jeu est constitué de trois instances (BRANIN, H77 et HS111) dont la description est donnée sur le site COCONUT Benchmark<fnref n="3" />. Le troisième jeu est basé sur les instances G4, G6 et G11 présentées dans [MIC 96]. Ces problèmes sont à l'origine des problèmes d'optimisation globale. Nous les avons réutilisés en transformant la fonction objectif en une contrainte à satisfaire de la manière suivante : $f \le f^* + eps$, où $f$ est la fonction objectif du problème, $f^*$ est l'évaluation d'une solution globale connue du problème et $eps$ est un paramètre permettant de régler la difficulté de la contrainte. Le paramètre $eps$ est choisi en fonction de l'instance. Ainsi, pour G4 et G6, $eps$ est fixé à 100, et pour G11, $eps$ est fixé à 0.1. Le dernier jeu de problèmes, constitué des instances RBT<sub>1</sub>, RBT<sub>2</sub> et RBT<sub>3</sub> est issu d'une application réelle du domaine de la robotique [JAU 01]. Le tableau 3.1 indique le nombre de variables ainsi que le nombre de contraintes pour chaque instance utilisée dans nos expérimentations.

**3.2. Résultats expérimentaux**

Notons que les algorithmes que nous avons présentés ne nécessitent qu’un seul paramètre : le nombre d’itérations maximum de recherche locale. Ainsi, les résultats présentés dans cette section ont été obtenus en paramétrant les différents algorithmes de la manière suivante : tous les algorithmes *RLC* effectuent au maximum 10000 itérations, et tous les algorithmes *RLD* effectue au plus 500 itérations de recherche locale à chaque fois que celle-ci est appelée. Remarquons que si l’opérateur de recherche locale est appelée à plusieurs reprises dans l’algorithme, le nombre total d’itérations comptabilisé pour *RLD* peut dépasser le chiffre 10000.

Pour ces expérimentations, nous mémorisons le nombre d'itérations, le temps de calcul, et le nombre de découpes (bissections) éventuelles nécessaires à chaque algorithme pour calculer un point réalisable (satisfaisant toutes les contraintes du pro-

<footnote n="3">3. http://www.mat.univie.ac.at/~neum/glopt/coconut/benchmark/Library3.html</footnote>
<table><caption>**Tableau 2. Caractéristiques des problèmes test.**</caption><thead><tr><th></th><th>Nombre de variables</th><th>Nombre de contraintes</th></tr></thead><tbody><tr><td>TNK</td><td>2</td><td>2</td></tr><tr><td>BRANIN</td><td>2</td><td>4</td></tr><tr><td>H77</td><td>5</td><td>13</td></tr><tr><td>HS111</td><td>10</td><td>23</td></tr><tr><td>G4</td><td>5</td><td>14</td></tr><tr><td>G6</td><td>2</td><td>7</td></tr><tr><td>G11</td><td>2</td><td>6</td></tr><tr><td>RBT<sub>1</sub></td><td>5</td><td>3</td></tr><tr><td>RBT<sub>2</sub></td><td>8</td><td>6</td></tr><tr><td>RBT<sub>3</sub></td><td>20</td><td>18</td></tr></tbody></table>

Le tableau 3 donne les moyennes de ces valeurs calculées sur le nombre d'exécutions ayant menées à la découverte d'une solution réalisable sur un total de 100 exécutions indépendantes<fnref n="4" />. Lorsque le nombre d'échecs est égale au nombre d'exécutions (ici 100) nous ne calculons pas ces moyennes et mettons les symboles ?? en guise d'indication.

Le tableau 3 récapitule les résultats obtenus pour les opérateurs de recherche locale continue présentés au tableau 1. Comme nous le constatons dans le tableau 3, les trois opérateurs permettent d'obtenir des résultats comparables sur le problème facile TNK. Pour les instances suivantes, plus difficiles à résoudre, les deux algorithmes $RLC_G$ et $RLC_E$ échouent dans la majorité des cas. L'algorithme $RLC_P$ quant à lui trouve des solutions sur un plus grand nombre d'instances, mais échoue systématiquement sur les problèmes HS111, RBT₂ et RBT₃. Remarquons que les temps de calcul de chaque algorithme sont très compétitifs, ne dépassant pas 1 s en moyenne quelque soit le problème traité ici.

Le tableau 4 récapitule les résultats obtenus par les opérateurs de recherche locale continue combinés avec notre processus de découpes dichotomiques. Nous obtenons donc plusieurs algorithmes de recherche locale dichotomique (RLD). Remarquons que dans cette deuxième série d'expérimentations, la cause de l'échec n'est plus exactement la même que lors de la première série. En effet, un algorithme RLC échoue lorsque le nombre maximum d'itérations est atteint, alors qu'un algorithme RLD échoue lorsqu'un domaine vide est trouvé après contraction de la boîte courante.

Nous observons sur les résultats obtenus, que $RLD_G$ et $RLD_P$ trouvent des solutions pour chaque problème sur au moins une exécution. $RLD_E$ quant à lui échoue systématiquement sur le dernier problème RBT₃. Nous observons également que

<footnote n="4">4. Les algorithmes sont exécutés sur une station Quadri Processeurs Ultra Sparc III à 750 Mhz.</footnote>
<table><caption>**Tableau 3.** Résultats de la recherche locale continue (RLC).</caption><thead><tr><th rowspan="2"></th><th colspan="3">RLC<sub>G</sub></th><th colspan="3">RLC<sub>E</sub></th><th colspan="3">RLC<sub>P</sub></th></tr><tr><th>Itérations</th><th>Échecs</th><th>Temps</th><th>Itérations</th><th>Échecs</th><th>Temps</th><th>Itérations</th><th>Échecs</th><th>Temps</th></tr></thead><tbody><tr><td>TNK</td><td>7</td><td>0</td><td>0.001s</td><td>5</td><td>0</td><td>0.001s</td><td>24</td><td>0</td><td>0.001s</td></tr><tr><td>BRANIN</td><td>595</td><td>0</td><td>0.012s</td><td>??</td><td>100</td><td>??</td><td>41</td><td>0</td><td>0.002s</td></tr><tr><td>H77</td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td><td>6549</td><td>92</td><td>0.169s</td></tr><tr><td>HS111</td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td></tr><tr><td>G4</td><td>5082</td><td>95</td><td>0.160s</td><td>??</td><td>100</td><td>??</td><td>3510</td><td>20</td><td>0.091s</td></tr><tr><td>G6</td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td><td>6596</td><td>92</td><td>0.11s</td></tr><tr><td>G11</td><td>3869</td><td>98</td><td>0.04s</td><td>997</td><td>99</td><td>0.01s</td><td>2054</td><td>0</td><td>0.022s</td></tr><tr><td>RBT<sub>1</sub></td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td><td>4400</td><td>51</td><td>0.108s</td></tr><tr><td>RBT</td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td></tr><tr><td>RBT<sub>3</sub></td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td><td>??</td><td>100</td><td>??</td></tr></tbody></table>

sur la majorité des problèmes, $RLD_G$ échoue plus rarement que $RLD_P$ et nécessite moins d'itérations de recherche locale ainsi que moins de découpes pour calculer une solution. Il apparaît que $RLD_G$ est plus robuste et plus performant que $RLD_E$ et $RLD_P$, et donc que la combinaison $RLC_G$ et coupes dichotomiques est la plus adaptée sur les problèmes testés ici.

Il est très intéressant de noter que, même s'il est difficile de comparer les résultats obtenus par $RLD$ et un algorithme $RLC$ pur, $RLD$ est toujours plus performants que l'algorithme de recherche locale continue seul, et ceci pour tous les problèmes testés dans cet article. Pour s'en convaincre, il suffit de comparer le nombre d'échecs obtenus par chaque méthode pour l'ensemble des problèmes traités. Le mécanisme de coupes dichotomiques guide la recherche locale vers des zones plus prometteuses lui évitant ainsi de rester confinée à des zones sans solution. Remarquons que la coopération entre ces deux opérateurs est réciproque. En effet, la recherche locale est guidée par le processus de coupes dichotomiques, mais celle-ci permet après réalisation d'une bissection de sélectionner la boîte qui sera conservée dans la prochaine itération de l'algorithme. La recherche locale est donc elle aussi un élément important pour guider le processus de bissection. Finalement, nous observons que $RLD$ est plus robuste car il échoue plus rarement pour découvrir une solution sur ces problèmes.

## 4. Conclusion

Dans cet article, nous avons introduit la « Recherche locale dichotomique », un algorithme heuristique pour la résolution des CSP continus. L'originalité de cet algorithme réside dans l'hybridation de la recherche locale avec les techniques classiques de bissection, contraction et propagation de contraintes. Les expérimentations que nous avons réalisées montrent clairement une dominance de $RLD$ par rapport à un algorithme de recherche locale à la « stratégie d'évolution ». Néanmoins, plusieurs
<table><thead><tr><th rowspan="2"></th><th colspan="4">RLD<sub>G</sub></th><th colspan="4">RLD<sub>E</sub></th></tr><tr><th>Itérations</th><th>Coupes</th><th>Échecs</th><th>Temps</th><th>Itérations</th><th>Coupes</th><th>Échecs</th><th>Temps</th></tr></thead><tbody><tr><td>TNK</td><td>1</td><td>1</td><td>0</td><td>0.005s</td><td>1</td><td>1</td><td>0</td><td>0.005s</td></tr><tr><td>BRANIN</td><td>485</td><td>1</td><td>0</td><td>0.015s</td><td>1597</td><td>2</td><td>0</td><td>0.036s</td></tr><tr><td>H77</td><td>3521</td><td>5</td><td>2</td><td>0.172s</td><td>6635</td><td>9</td><td>15</td><td>0.296s</td></tr><tr><td>HS111</td><td>1294</td><td>2</td><td>12</td><td>0.448s</td><td>638</td><td>2</td><td>0</td><td>0.248s</td></tr><tr><td>G4</td><td>1484</td><td>3</td><td>2</td><td>0.116s</td><td>1547</td><td>3</td><td>71</td><td>0.118s</td></tr><tr><td>G6</td><td>1</td><td>1</td><td>0</td><td>0.054s</td><td>1</td><td>1</td><td>0</td><td>0.054s</td></tr><tr><td>G11</td><td>4</td><td>1</td><td>0</td><td>0.019s</td><td>31</td><td>1</td><td>0</td><td>0.019s</td></tr><tr><td>RBT<sub>1</sub></td><td>706</td><td>8</td><td>0</td><td>0.049s</td><td>793</td><td>9</td><td>0</td><td>0.055s</td></tr><tr><td>RBT<sub>2</sub></td><td>1915</td><td>8</td><td>0</td><td>0.119s</td><td>2523</td><td>10</td><td>24</td><td>0.159s</td></tr><tr><td>RBT<sub>3</sub></td><td>28587</td><td>94</td><td>82</td><td>4.3s</td><td>??</td><td>??</td><td>100</td><td>??</td></tr></tbody></table>

<table><caption>**Tableau 4.** Résultats de la recherche locale dichotomique (RLD).</caption><thead><tr><th rowspan="2"></th><th colspan="4">RLD<sub>P</sub></th></tr><tr><th>Itérations</th><th>Coupes</th><th>Échecs</th><th>Temps</th></tr></thead><tbody><tr><td>TNK</td><td>1</td><td>1</td><td>0</td><td>0.004s</td></tr><tr><td>BRANIN</td><td>17</td><td>1</td><td>0</td><td>0.008s</td></tr><tr><td>H77</td><td>11750</td><td>13</td><td>0</td><td>0.52s</td></tr><tr><td>HS111</td><td>8167</td><td>9</td><td>43</td><td>2.474s</td></tr><tr><td>G4</td><td>5102</td><td>10</td><td>27</td><td>0.295s</td></tr><tr><td>G6</td><td>1</td><td>1</td><td>0</td><td>0.055s</td></tr><tr><td>G11</td><td>382</td><td>1</td><td>0</td><td>0.023s</td></tr><tr><td>RBT<sub>1</sub></td><td>5270</td><td>9</td><td>0</td><td>0.169s</td></tr><tr><td>RBT<sub>2</sub></td><td>17411</td><td>27</td><td>1</td><td>0.897s</td></tr><tr><td>RBT<sub>3</sub></td><td>26470</td><td>90</td><td>91</td><td>3.209s</td></tr></tbody></table>

pistes d'amélioration sont envisageables. Premièrement, l'incorporation d'autres méthodes de consistances locales plus fortes augmenterait la puissance de contraction et diminuerait la taille de l'espace de recherche dans lequel évolue la méthode de recherche locale. Ceci augmenterait donc les probabilités de succès de l'algorithme. Deuxièmement, l'étude d'autres méthodes de recherche locale ou d'opérateurs sto-chastiques de recherche de solution permettrait de calculer une information la plus pertinente possible lorsque l'algorithme doit faire le choix, pour sa prochaine itération, d'une boîte parmi deux boîtes localement consistantes.

Enfin, au-delà de la recherche d'une solution pour un CSP continu donné, l'algorithme *RLD* peut être utilisé pour déterminer des points faisables d'un problème d'optimisation sous contraintes. Plus généralement, il est tout à fait possible d'adapter notre algorithme pour l'optimisation non linéaire sous contraintes dans laquelle l'optimisation et la recherche de points faisables seront traitées simultanément. Ce dernier point constitue un des travaux que nous sommes en train de développer.
Remerciements

Ce travail a été partiellement financé par le projet CPER « COM », Pôle Informa-
tique Régional (Pays de la Loire), Programme de Recherche No 18013 (2000-2006).
Nous remercions les rapporteurs pour leurs remarques et critiques qui nous ont permis
d'améliorer le fond et la forme de notre article.

5. Bibliographie

[BEN 99] BENHAMOU F., GOUALARD F., GRANVILLIERS L., PUGET J., « Revising hull and box consistency », *Proc. of the Int. Conference on Logic Programming*, 1999, p. 230–244.

[CLE 87] CLEARY J., « Logical arithmetic », *Future Computing Systems*, vol. 2, n° 2, 1987, p. 125–149.

[COC 01] COCONUT, « Algorithms for Solving Nonlinear Constrained and Optimization Problems : The State of The Art », rapport, 2001.

[DAV 87] DAVIS E., « Constraint propagation with interval labels », *Artificial Intelligence*, vol. 32, n° 3, 1987, p. 281–331.

[DEB 96] DEB K., GOYAL M., « A combined genetic adaptive search (GeneAS) for enginee- ring design », *Computer Science and Informatics*, vol. 26, n° 4, 1996, p. 30–45.

[JAU 01] JAULIN L., KIEFFER M., DIDRIT O., WALTER E., *Applied Interval Analysis, with Examples in Parameter and State Estimation, Robust Control and Robotics*, Springer-Verlag, London, 2001.

[LHO 93] LHOMME O., « Consistency techniques for numeric CSPs », *Proc. of the 13th Int. Joint Conference on Artificial Intelligence (IJCAI'93)*, 1993, p. 232–238.

[MAC 77] MACKWORTH A., « Consistency in networks of relations », *Artificial Intelligence*, vol. 8, 1977, p. 99–118.

[MIC 96] MICHALEWICZ Z., SCHOENAUER M., « Evolutionary algorithms for constrained parameter optimization problems », *Evolutionary Computation*, vol. 4, n° 1, 1996, p. 1–32.

[MOH 86] MOHR R., HENDERSON T., « Arc and path consistency revisited », *Artificial Intelligence*, vol. 28, 1986, p. 225–233.

[MOO 79] MOORE R., « Methods and applications of interval analysis », *SIAM, Philadelphia, PA*, 1979.

[SAM 96] SAM-HAROUD D., FALTINGS B., « Consistency Techniques for Continuous Constraints », *Constraints*, vol. 1(1&2), 1996, p. 85–118.

[SCH 81] SCHWEFEL H.-P., *Numerical optimization of computer models*, Wiley, Chichester, 1981.

[TAN 95] TANAKA M., « GA-based decision support system for multi-criteria optimization », *Proc. of the Int. Conference on Systems, Man and Cybernetics-2*, 1995, p. 1556–1561.

[Van 97] VAN HENTENRYCK P., MICHEL L., BENHAMOU F., « Newton : Constraint Programming over Non-linear Constraints », *Scientific Programming*, vol. 30, n° 1-2, 1997, p. 83–118.