Parcours optimal de n-uplets
Bonjour
Voici un problème d'optimisation, qui revient dans différents cas pratiques (application : cf. plus bas). J'espère être dans le bon forum.
On se place dans l'ensemble des $n$-uplets de booléens (ou des sommets d'un hypercube à $n$ dimensions si vous préférez), notés $(a_i)_{i=1..n}$.
Soit $p < 2^n$. On souhaite choisir $p$ éléments de cet ensemble, de façon à optimiser $\sum_{i=1}^n c_i d_i$,
où $c_i$ est une suite décroissante de poids (réels positifs), et $d_i$ est la somme des nombres de valeurs différentes prises par chaque $i$-uplet de $a_j$ dans les $n$-uplets choisis.
Comment choisit-on les $n$-uplets ? Dans quelle mesure ce choix optimal dépend-il des $a_i$ ? Au cas où on ne connaît pas $p$ à l'avance, peut-on construire une suite de $n$-uplets qui soit constamment optimale, ou au moins "pas trop mauvaise" ?
Exemple avec $n = 3$ et $p = 4$ :
On choisit $(0,0,1), (1,0,0), (1,0,1), (1,1,0)$, ça donne
$d_1 = 6$ : $a_1$, $a_2$, $a_3$ prennent chacun les deux valeurs 0 et 1
$d_2 = 9$ : on a 9 couples de $a_i a_{j\neq i}$ sur les 12 possibles : $(0,0,-), (1,0,-), (1,1,-), (0,-,1), (1, -, 0), (1, -, 1), (-, 0,0), (-,0,1), (-,1,0)$.
$d_3 = p = 4$.
Application : on teste un logiciel. On suppose que le fonctionnement du logiciel dépend de $n$ booléens (configuration des modules optionnels, flags de compilation...). On peut effectuer $p$ tests. On souhaite les répartir de manière à maximiser la probabilité de détecter un bug. On suppose que le comportement du logiciel dépend principalement (coeff $a_1$) de chaque booléen, un peu moins de leurs combinaisons 2 à 2 (coeff $a_2$ inférieur à $a_1$), encore moins de leurs combinaisons 3 à 3 (coeff $a_3$ inférieur à $a_2$), etc.
J'ai aussi une autre application en tête, un peu longue à expliquer.
Je pourrai vous dire dans un prochain message comment je choisis les $n$-uplets, mais vous ne perdez rien, ça ne repose sur rien de rigoureux. :-)
Voici un problème d'optimisation, qui revient dans différents cas pratiques (application : cf. plus bas). J'espère être dans le bon forum.
On se place dans l'ensemble des $n$-uplets de booléens (ou des sommets d'un hypercube à $n$ dimensions si vous préférez), notés $(a_i)_{i=1..n}$.
Soit $p < 2^n$. On souhaite choisir $p$ éléments de cet ensemble, de façon à optimiser $\sum_{i=1}^n c_i d_i$,
où $c_i$ est une suite décroissante de poids (réels positifs), et $d_i$ est la somme des nombres de valeurs différentes prises par chaque $i$-uplet de $a_j$ dans les $n$-uplets choisis.
Comment choisit-on les $n$-uplets ? Dans quelle mesure ce choix optimal dépend-il des $a_i$ ? Au cas où on ne connaît pas $p$ à l'avance, peut-on construire une suite de $n$-uplets qui soit constamment optimale, ou au moins "pas trop mauvaise" ?
Exemple avec $n = 3$ et $p = 4$ :
On choisit $(0,0,1), (1,0,0), (1,0,1), (1,1,0)$, ça donne
$d_1 = 6$ : $a_1$, $a_2$, $a_3$ prennent chacun les deux valeurs 0 et 1
$d_2 = 9$ : on a 9 couples de $a_i a_{j\neq i}$ sur les 12 possibles : $(0,0,-), (1,0,-), (1,1,-), (0,-,1), (1, -, 0), (1, -, 1), (-, 0,0), (-,0,1), (-,1,0)$.
$d_3 = p = 4$.
Application : on teste un logiciel. On suppose que le fonctionnement du logiciel dépend de $n$ booléens (configuration des modules optionnels, flags de compilation...). On peut effectuer $p$ tests. On souhaite les répartir de manière à maximiser la probabilité de détecter un bug. On suppose que le comportement du logiciel dépend principalement (coeff $a_1$) de chaque booléen, un peu moins de leurs combinaisons 2 à 2 (coeff $a_2$ inférieur à $a_1$), encore moins de leurs combinaisons 3 à 3 (coeff $a_3$ inférieur à $a_2$), etc.
J'ai aussi une autre application en tête, un peu longue à expliquer.
Je pourrai vous dire dans un prochain message comment je choisis les $n$-uplets, mais vous ne perdez rien, ça ne repose sur rien de rigoureux. :-)
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
C'est le vaste domaine des "plans d'expérience" : https://fr.wikipedia.org/wiki/Plan_d'expériences
S'il n'y a pas d'interactions entre tes facteurs, tu peux penser aux matrices de Hadamard.
Je ne connaissais pas l'expression "plans d'expérience", et donc je ne trouvais pas de référence.
Avec l'article Wikipedia et tout ce vers quoi il pointe, j'ai de la lecture. Parfait !