Utilisateur:Léna/Configuration

En informatique théorique, et plus particulièrement en intelligence artificielle, la configuration est un paradigme pouvant aussi bien représenter de la configuration industrielle, telle que la configuration d'un ordinateur ou celle d'une voiture, mais aussi, de manière plus abstraite, des problématiques de bioinformatique ou de design. Configurer un produit, c'est composer un modèle du produit correspondant à des exigences données.

Modélisation

Trois niveaux de modélisation co-existent en configuration : celui le plus bas, c'est-à-dire le niveau de l'instanciation, correspond à la description d'un produit en particulier; le second niveau permet de décrire la gamme à laquelle le produit appartient; enfin, le dernier niveau se rapporte aux concepts utilisés pour contruire une gamme de produits.

Programmation par contraintes

La programmation par contraintes, en raison de sa capacité à exprimer des contraintes complexes (telles que la compatibilité entre des valeurs de variables données) et à assurer un certain niveau de cohérence, à l'aide par exemple de la cohérence d'arc, est très utile pour modéliser les problèmes de configuration. Toutefois, les algorithmes associés à la programmation par contrainte cherchent surtout à déterminer l'existence d'une solution et/ou d'un construire une ; le cadre naturel est celui de problèmes fortement contraints (huit dames) alors que, dans le cadre de la configuration, de très nombreuses solutions existent ($10^{21}$ possibilités pour un Renault Trafic) et les requêtes associées sont très différentes (détermination du nombre de solutions, recherche de l'origine d'une incohérence).

Logiques de description

Les logiques de description sont bien adaptées à la description d'un système devant être configuré

Formes compilées

La forme compilée d'un problème de configuration est une structure de donnée représentant toutes les solutions du problème de manière compact.

Diagrammes de décision binaires

Il est possible de représenter un problème de configuration sous forme de diagramme de décision binaire : chaque variable $v_{i}$ sera représentée par un noeud, chaque valeur d'une variable $v_{i}$ par une arête du noeud $i$ au noeud $i+1$ et chaque chemin de la racine au noeud terminal $1$ (respectivement noeud terminal $0$) correspond à une affectation valide (respectivement non valide) des variables. Pour respecter la propriété de binarité, c'est-à-dire le fait que chaque noeud ait deux fils, on décompose le domaine $D_{i}$ d'une variable en $k_{i}=log_{2}(D_{i})$ variables booléennes.

Diagrammes de décision multi-valués

Un diagramme de décision multi-valué est un tuple $(V,r,E,{\hbox{var}})$ où $V$ est un ensemble de noeuds contenant le noeud terminal $1$ ainsi que la racine $r\in V$ et où $E\in VXV$ est un ensemble d'arêtes tel que $(V,E)$ soit un graphe orienté sans cycle d'origine $r$ et de puit des chemins maximaux $1$. De plus, on définit $var:V\rightarrow [|1;n+1|]$ fonction de labellisation des nœuds telle que que ${\hbox{var}}(r)=n+1$; chaque arête $e\in E$ est caractérisée par le triplet $(u,u',v)$ où $u$ est son nœud de départ, $u'$ son nœud d'arrivée et $v$ une valeur.

Un diagramme de décision multi-valué associé à un problème de configuration est tel que $n$ correspond au nombre de variables du problème, où chaque nœud $u$ de niveau $i$ correspond à la même variable $x_{i}$ et où pour toute arrête $(u,u',v)$, $v$ soit dans le domaine de $x_{i}$.

Résolution

Programmation par contraintes

Composite CSP

Un CSP composite est un CSP où l’activation de variables est conditionné à l'affectation particulière d'autres variables. Plus formellement,

Définition — Un problème de satisfaction de contraintes composite sur des domaines finis (ou DCSP) est défini par un quintuplet $({\mathcal {X}},{\mathcal {D}},{\mathcal {X_{I}}},{\mathcal {C_{C}}},{\mathcal {C_{A}}})$ où:

• ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ est l'ensemble de variables du problème;
• ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ est l'ensemble des domaines des variables, c'est-à-dire que pour tout $k\in [1;n]$ on a $x_{k}\in {\mathcal {D}}_{k}$;
• ${\mathcal {X_{I}}}\subset {\mathcal {X}}$ l'ensemble des variables initialement activées;
• ${\mathcal {C_{C}}}=\{C_{C_{1}},\dots ,C_{C_{m}}\}$ est l'ensemble des contraintes de compatibilité. Une contrainte $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ est définie par l'ensemble ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ des variables sur lequel elle porte et la relation ${\mathcal {R}}_{i}\subset {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ qui définie l'ensemble des valeurs que peuvent prendre simultéanément les variables de ${\mathcal {X}}_{i}$;
• ${\mathcal {C_{A}}}$ est l'ensemble des contraintes d'activation. Une contrainte d'activation ${\mathcal {C_{A}}}_{j}=({\mathcal {X}}_{j},{\mathcal {R}}_{j},x_{j})$ est définie par l'exemple des tuples ${\mathcal {R}}_{j}$ des variables ${\mathcal {X}}_{j}=\{x_{j_{1}},\dots ,x_{j_{k}}\}$ qui induisent l'activation de la variable $x_{j}$.

On remarquera que, pour les contraintes d'activité, il est possible que $x_{j}\in {\mathcal {X}}_{j}$.

Toutefois, Soininen, Gelle et Niemela font remarquer que les CSP composites ne permettent pas d'exprimer l'idée « qu'il puisse y avoir soit un condensateur, soit un refroidisseur », le condensateur et le refroidisseur étant eux-même des variables.

Configurateurs

Le rôle d'un configurateur est de rechercher le ou les produits dans la gamme correspondant aux exigences spécifiées par l'utilisateur ; dans le cas où plusieurs solutions existent, le configurateur doit proposer la meilleure (suivant un critère donné, tel que le coût).

Configuration interactive

Lorsque l'utilisateur d'un configurateur « voit en direct les conséquences de ses choix », on parle alors de configuration interactive. Elle s'oppose à la configuration automatique où l'ensemble des possibilités restantes n'est calculé qu'une fois que l'utilisateur a spécifié tous ses choix.

Voir aussi

Liens externes

• (en) Base de données de configurateurs