Discussion :

[A. D.]

Bonjour à tous,

Je vous expose mon problème : je cherche à programmer la génération de plans d'expériences (matrices) dans un cas bien particulier.
Je vais me baser sur un exemple concret pour vous présenter ma problématique :

Je dispose de 3 variables (par exemple : X, Y et Z) pouvant prendre respectivement : 3, 4 et 5 modalités.
Une combinaison des modalités de ces 3 variables est appelée produit, par exemple ( X=1 , Y=4 , Z=1 ), ou encore : ( X=2 , Y=2 , Z=4 ).
Une planche est un ensemble de k produits. Prenons par exemple : k=3. On aura alors par exemple comme planche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
X  Y  Z
2  2  5
1  3  2
2  2  4

On a ensuite N individus (prenons par exemple N=10) et à chaque individu est associé un nombre g de planches (par exemple g=4).
Ainsi, on aura au final comme matrice/plan d'expériences quelque chose de la forme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Individu  Planche  Produit     |     X  Y  Z
1         1        1           |     2  4  1
1         1        2           |     3  2  4
1         1        3           |     1  2  5
1         2        1           |     2  1  3
1         2        2           |     1  4  1
1         2        3           |     1  2  1
1         3        1           |     3  3  2
...
...
...
10         3        3          |     1  2  3
10         4        1          |     3  1  5
10         4        2          |     2  4  1
10         4        3          |     1  1  5

Voilà, j'espère que jusqu'ici je suis assez claire...


Maintenant, il y a également des conditions à appliquer.
Tout d'abord, aucune planche ne peut être composée de 2 mêmes produits. Ensuite, aucune planche sur l'ensemble des individus ne peut exister en double.
Enfin, il faut que chaque individu voit un même nombre de fois (approximativement bien sûr) toutes les paires possibles de modalités de deux variables.

Et c'est ce dernier point qui me pose le plus de problèmes à programmer. Pour l'instant j'ai commencé par générer tous les produits possibles (stockés dans une matrice P0), et je pioche des produits un par un dans cette matrice P0 en "comptant" les apparitions des couples de modalités pour faire en sorte de maintenir l'équilibre. Sauf qu'il arrive que je tombe sur un cas impossible (!) où quel que soit le produit qu'on ajoutera, cela "cassera" l'équilibre. Dans un tel cas j'avais pensé à "recommencer" toute la sélection de produits pour l'individu concerné, mais alors mon algorithme met énormément de temps (sachant qu'il peut y avoir 1000 individus).

Donc voilà, si quelqu'un à des pistes intéressantes sur le sujet ou des astuces de programmation pour ce genre de problème, cela m'intéresse grandement
De plus, si vous souhaitez que je donne plus d'explications, n'hésitez pas à me le faire savoir.

Merci d'avance


Cordialement,

A.D.

[Nemerle]

Je reformule pour être sur de bien comprendre la condition en gras.

1) un produit est un triplet d'entiers positifs (x,y,z) où x<=3,y<=4 et z<=5. On note PR cet ensemble.Pour un tel produit p on note p_1,p_2 et p_3 les valeurs x,y, et z.
2) un planche est un élément pl=(pl(1),pl(2),pl(3)) de PR^k tel que pl(i)<>pl(j) si i<>j. On note PL cet ensemble.
3) un individu est un élément ind=(ind(1),...,ind(g)) de PL^g tel que ind(i)<>ind(j) si i<>j. On note IND cet ensemble

On utilise la notation de composition X_Y

Pour tout ind de IND et tout x<=3,y<=4 et z<=5, on pose
IND_XY={(i,j): ind(i)_p(j)_1=x, ind(i)_p(j)_2=y},
IND_XZ={(i,j): ind(i)_p(j)_1=x, ind(i)_p(j)_3=z},
IND_YZ={(i,j): ind(i)_p(j)_2=y, ind(i)_p(j)_3=z}.

Les cardinaux du plus petit et plus grand ensemble ci-dessus sont notés ind_min et ind_max.

On recherche les ind qui minimisent ind_max-ind_min (en fait un algo qui génère de tels individus).

J'ai bon??

[A. D.]

Bonjour,

Tout d'abord, merci beaucoup pour votre réponse !

1) un produit est un triplet d'entiers positifs (x,y,z) où x<=3,y<=4 et z<=5. On note PR cet ensemble.Pour un tel produit p on note p_1,p_2 et p_3 les valeurs x,y, et z.
2) un planche est un élément pl=(pl(1),pl(2),pl(3)) de PR^k tel que pl(i)<>pl(j) si i<>j. On note PL cet ensemble.
3) un individu est un élément ind=(ind(1),...,ind(g)) de PL^g tel que ind(i)<>ind(j) si i<>j. On note IND cet ensemble

Ca me paraît ok.
Perso, j'aurais noté comme suit :

pl=(pr(1),pr(2),...pr(k)) car pl = planche et une planche = un ensemble de k produits.
ind=(pl(1),pl(2),...pl(g)) car un individu voit un ensemble de g planches.

Sinon pour les conditions, c'est ça.

(Après, les valeurs données aux paramètres (le fait qu'il n'y ait que 3 "variables" x, y et z, les nombres de produits k, de planches g, etc...) ont été fixés pour l'exemple mais sont variables dans la pratique).

Pour tout ind de IND et tout x<=3,y<=4 et z<=5, on pose
IND_XY={(i,j): ind(i)_p(j)_1=x, ind(i)_p(j)_2=y},
IND_XZ={(i,j): ind(i)_p(j)_1=x, ind(i)_p(j)_3=z},
IND_YZ={(i,j): ind(i)_p(j)_2=y, ind(i)_p(j)_3=z}.

Les cardinaux du plus petit et plus grand ensemble ci-dessus sont notés ind_min et ind_max.

Je ne suis pas sûre de bien comprendre ici la manière dont vous définissez ces ensembles? Par exemple, l'ensemble "IND_XY" va contenir tous les couples de valeurs prises par les variables x et y pour un individu, c'est bien cela?
Du coup, je ne comprends pas à quoi correspondent les "cardinaux du plus petit et plus grand ensemble"?

On recherche les ind qui minimisent ind_max-ind_min (en fait un algo qui génère de tels individus).

Ca m'intéresserait d'en savoir plus mais comme le point précédent n'est pas très clair pour moi...


En tout cas merci d'essayer de m'aider et désolée d'avoir un peu de mal quant à la formulation "théorique" de mon problème


Bien cordialement,

A.D.

[Nemerle]

Ok pour vos remarques, j'ai rédigé trop vite
En pariculier sur les IND_??, il manque un niveau :

Pour tout individu IND et tout x<=3,y<=4 et z<=5,en notant Gamma l'ensemble produit [1,g]x[1,k]x[1,3], on pose

IND_(X=x,Y=y) = {(i,j,l) dans Gamma: IND(i)_pl(j)_pr(l)_1=x, IND(i)_p(j)_pr(l)_2=y},
IND_(X=x,Z=z) = {(i,j,l) dans Gamma : IND(i)_pl(j)_pr(l)_1=x, IND(i)_p(j)_pr(l)_3=z},
IND_(Y=y,Z=z) = {(i,j,l) dans Gamma : IND(i)_pl(j)_pr()_2=y, IND(i)_p(j)_pr(l)_3=z}.

Le cardinal de IND_(X=2,Y=4) par exemple donne le nombre de paires (X=2,Y=4) présentes dans tous les produits des planches associées à IND.

Donc avoir le même nombre de fois "approximativement" revient à minimiser la valeur IND_max - IND_min, soit la différence des cardinaux du plus grand et du plus petit ensembles IND_??.

C'est plus clair?

[A. D.]

Re-bonjour,

Ok pour vos remarques, j'ai rédigé trop vite

Pas de soucis, au contraire, je vous remercie d'essayer de m'aider

Le cardinal de IND_(X=2,Y=4) par exemple donne le nombre de paires (X=2,Y=4) présentes dans tous les produits des planches associées à IND.

Donc avoir le même nombre de fois "approximativement" revient à minimiser la valeur IND_max - IND_min, soit la différence des cardinaux du plus grand et du plus petit ensembles IND_??

Je n'arrive pas bien à comprendre le "revient à minimiser la valeur de IND_max - IND_min"...
Si ce que vous voulez calculer ici est le nombre minimal de fois où chaque combinaison/couple de 2 variables doit apparaître, alors il peut se calculer (il me semble) comme etant le reste entier de la division euclidienne du nombre de produits vu en tout par un individu (soit g*k) par [ le nombre de niveaux de la variable i fois le nombre de niveaux de la variable j ].

Dans mon exemple : g = 9, k = 3, [ nombre de niveaux de X ] = 3, [ nombre de niveaux de Z ] = 5. Alors, chaque couple de deux niveaux/modalités de X et de Z doit apparaîte au moins : (3*9) // (3*5) = 1 fois.

Je ne sais pas si c'est très clair...


Encore merci d'essayer de m'aider


Bien cordialement,

A.D.

[Nemerle]

si, c'est clair, et je suis ok avec votre rq

Quand vous dites "chaque individu voit un même nombre de fois (approximativement bien sûr) toutes les paires possibles de modalités de deux variables.",

moi je le traduis par "IND_max -IND_min doit être minimal. IND_max représente le nombre d'occurence du couple de produits étant le plus vu par les individus, et IND_min l'inverse.

Donc minimiser la différence, c'est "votre" phrase! Si cette différence vaut zéro, tous les couple de produits ont le même nombre d'occurences chez tous les individus. Si elle vaut 2, le nombre d'occurences d'un couple est le même à 2 près...

Donc on se comprend, je vais réfléchir à la suite.

[A. D.]

Ok, j'ai compris aussi votre manière de poser le problème.

Merci pour votre attention concernant mon "problème".
Si vous avez d'eventuelles idées pour poursuivre, je suis toute ouïe


Bien cordialement,

A.D.