4 Un exemple fondé sur le jeu de données Fleurs d'iris

Marco Ballin et Giulio Barcaroli

Afin d'illustrer comment appliquer l'algorithme pour trouver la stratification optimale, nous pouvons nous servir du jeu de données Fleurs d'iris bien connu. Ce jeu de données comprend un total de 150 observations, réparties de manière égale entre les trois espèces de fleurs d'iris (setosa, virginica et versicolor). Quatre caractéristiques sont mesurées pour chaque observation (c.-à-d. la longueur et la largeur du sépale et du pétale, en centimètres).

Nous considérerons ce jeu de données comme une base de sondage possible de laquelle nous pouvons tirer un échantillon, sous un plan stratifié, afin d'estimer deux variables cibles :

$Y_{1}$ : Pétale.longueur;
$Y_{2}$ : Pétale.largeur.

Pour simplifier, nous supposons que deux variables auxiliaires seulement sont disponibles dans la base de sondage :

$X_{1}$ : Sépale.longueur;
$X_{2}$ : Espèce.

Alors que la deuxième variable auxiliaire est catégorique, la première est continue et doit être transformée en une variable catégorique ordonnée. Pour cela, nous utilisons la méthode de classification automatique univariée à $k $ moyennes (Hartigan et Wong 1979), et obtenons les intervalles suivants : [4,3; 5,5], (5,5; 6,5], (6,5; 7,9].

Le produit cartésien des deux variables auxiliaires devrait produire $3 \times 3 = 9$ strates distinctes. En réalité, celle correspondant à Espèce $=$ « setosa » et Sépale.longueur $\in$ (6,5; 7,9] ne contient aucune unité. Donc, les strates présentées au tableau 4.1 seront considérées comme représentant la stratification atomique initiale.

Tableau 4.1
Information sur les strates atomiques
Sommaire du tableau
Le tableau montre de l'information sur les strates atomiques. Les données sont présentées selon strate, X ₁ = Sépale.longueur, X ₂ = Espèce, N, Y ₁ = Pétale.longueur, Y ₁ = Pétale.largeur, Coût (figurant comme en-tête de colonne).
strate	X ₁ = Sépale.longueur	X ₂ = Espèce	N	Y ₁ = Pétale.longueur		Y ₁ = Pétale.largeur		Coût
strate	X ₁ = Sépale.longueur	X ₂ = Espèce	N	Moyenne	Écart-type	Moyenne	Écart-type	Coût
1	[4,3; 5,5] (1)	Setosa (1)	45	1,47	0,17	0,24	0,11	1
2	[4,3; 5,5] (1)	Versicora (2)	6	3,58	0,49	1,17	0,21	1
3	[4,3; 5,5] (1)	Virginica (3)	1	4,50	0,00	1,70	0,00	1
4	[5,5; 6,5] (2)	Setosa (1)	5	1,42	0,17	0,26	0,08	1
5	[5,5; 6,5] (2)	Versicora (2)	35	4,27	0,37	1,32	0,19	1
6	[5,5; 6,5] (2)	Virginica (3)	23	5,23	0,32	1,95	0,29	1
7	[6,5; 7,9] (3)	Versicora (2)	9	4,68	0,19	1,46	0,11	1
8	[6,5; 7,9] (3)	Virginica (3)	26	5,88	0,49	2,11	0,23	1

Pour simplifier, nous supposons que le coût fixe $C_{0}$ est nul et que la valeur de tous les $C_{h}$ est fixée à 1 : de la sorte, le coût d'une solution coïncide avec la somme des unités d'échantillonnage affectées aux strates, c.-à-d. avec la taille totale d'échantillon $(C = n = \sum_{h = 1}^{H} n_{h}) .$

Nous imposons comme contraintes de précision sur les estimations des deux variables cibles une borne supérieure de 0,05 (5 %) de leur coefficient de variation prévu.

Enfin, nous fixons le nombre minimal d'unités qui doit être sélectionné dans chaque strate à 2 (le minimum requis pour calculer la variance d'échantillonnage).

Sous ces hypothèses, et en utilisant la stratification atomique, l'algorithme de Bethel résout le problème de répartition optimale de l'échantillon en définissant une taille minimale d'échantillon de 17 unités, avec un vecteur de répartition $a = (2, 2, 1, 2, 3, 3, 2, 2) .$

Si nous procédons à la partition de l'ensemble de strates atomiques, le nombre total résultant de stratifications possibles (donné par la formule de Bell) est $B_{8} =$ 4 140. Ce nombre est tel qu'il est possible de dénombrer toutes les partitions des strates atomiques et, pour chacune d'elles, de calculer la taille minimale d'échantillon en appliquant l'algorithme de Bethel (pour dénombrer toutes les partitions dans cet exemple, nous avons utilisé la fonction setparts(), contenue dans le module R partitions (Hankin 2011)).

L'intervalle de tailles d'échantillon va d'un minimum de 11 à un maximum de 78 (cette dernière valeur correspond à la solution « pas de stratification ») (voir figure 4.1).

Description de la figure 4.1

Figure 4.1 Espace des partitions

Nous constatons que la valeur minimale $(n = 11)$ trouvée est considérablement plus faible que la valeur calculée correspondant à la stratification atomique $(n = 17) .$ Cette valeur minimale caractérise 8 partitions seulement sur 4 140.

Maintenant, nous appliquons l'algorithme génétique pour évaluer sa capacité à trouver la solution optimale (ou du moins une solution qui ne s'en écarte pas trop), sans être obligés d'explorer toutes les solutions, mais uniquement un sous-ensemble strict de celles-ci.

Étape 0 : Création de la première génération

Pour commencer, nous posons que $U = 8$ (nous pouvons accepter un nombre de strates final qui est égal au nombre de strates atomiques, de sorte que $U = K$ ). Le paramètre pop de taille de génération est fixé à 10. Donc, un premier ensemble contenant dix individus (stratifications) distincts est généré. Chacun d'eux est représenté par un vecteur de huit éléments, c.-à-d. le nombre de strates atomiques différentes. Un individu $v = (1, 2, 3, 4, 5, 6, 7, 8)$ ou, de façon équivalente, $v = (3, 6, 4, 2, 1, 8, 7, 5)$ correspond à la stratification la plus détaillée (car chacune des strates porte une étiquette différente), tandis que $v = (1, 1, 1, 1, 1, 1, 1, 1)$ ou de façon équivalente $v = (4, 4, 4, 4, 4, 4, 4, 4)$ correspond à la « stratification nulle » (car les strates atomiques portent des étiquettes identiques).

Étape 1 : Évaluation de l'adaptation de chaque individu de la génération

Nous appliquons l'algorithme de Bethel à chacun des dix individus de la génération courante afin de trouver le coût de l'échantillon requis pour satisfaire les contraintes de précision fixes.

Pour cela, nous commençons par calculer les strates et l'information pour chaque individu. Par exemple, pour un individu généré $v = (4, 1, 1, 4, 8, 7, 8, 1)$ , l'information est obtenue au moyen de l'une des strates atomiques disponibles, en appliquant (3.1) et (3.2) (voir le tableau 4.2).

Tableau 4.2
Information sur les strates agrégées générées
Sommaire du tableau
Le tableau montre l'information sur les strates agrégées générées. Les données sont présentées selon Strate agrégée, Strates atomiques originales, ( X ₁, X ₂), N, Y ₁, Y ₂ (figurant comme en-tête de colonne).
Strate agrégée	Strates atomiques originales	( X ₁, X ₂)	N	Y ₁		Y ₂
Strate agrégée	Strates atomiques originales	( X ₁, X ₂)	N	Moyenne	Écart-type	Moyenne	Écart-type
1	2,3,8	(1,2) ou (1,3) ou (3,3)	33	5,41	1,01	1,92	0,44
2	1,4	(1,1) ou (2,1)	50	1,46	0,17	0,25	0,10
3	6	(2,3)	23	5,23	0,31	1,95	0,28
4	5,7	(2,2) ou (3,2)	44	4,35	0,37	1,35	0,18

La valeur d'adaptation de cet individu est mesurée par la taille d'échantillon requise correspondante, qui s'avère être 14, avec un vecteur de répartition $a = (6, 2, 3, 3) .$

Tous les individus sont triés en fonction de leur performance : l'individu en première position est celui qui requiert la taille d'échantillon minimale, et en 10^e position, celui nécessitant la taille d'échantillon maximale.

Étape 2 : Production d'une nouvelle génération

Si nous fixons la valeur du paramètre élitisme à 20 % (une valeur par défaut fréquente), nous prenons systématiquement les deux meilleurs individus de la génération courante et nous les transférons directement à la génération suivante, sans aucune modification de leur génome.

Puis, nous procédons à la génération de nouveaux individus de la façon suivante :

nous sélectionnons des couples d'individus de la génération courante avec une probabilité proportionnelle à leur valeur d'adaptation : par exemple, supposons que nous sélectionnions $v_{k} = (1, 1, 3, 4, 3, 2, 2, 2)$ et $v_{j} = (2, 2, 2, 2, 2, 1, 1, 1);$
un point de croisement est généré aléatoirement, c.-à-d. un nombre entier à l'intérieur de l'intervalle $[1, 8] :$ supposons qu'il est égal à 3;
le croisement est exécuté en attribuant à l'enfant les trois premiers éléments du parent $v_{k}$ et les cinq derniers éléments du parent $v_{j},$ pour obtenir de cette façon $v_{new} = (1, 1, 3, 2, 2, 1, 1, 1);$
en ayant fixé la valeur du paramètre de taux de mutations à 0,05, pour chaque élément de l'enfant, un nombre aléatoire est généré dans l'intervalle $[0, 1] :$ si ce nombre est inférieur à 0,05, la valeur de l'élément est modifiée (en générant une nouvelle valeur comprise entre 1 et 9), sinon elle n'est pas modifiée.

Étape 3 : Critères d'itération et d'arrêt

Le nombre d'itérations a été fixé à 25. Donc, les étapes 1 et 2 sont répétées 25 fois. L'individu qui, de toutes les générations, possède la meilleure valeur d'adaptation est retenu comme étant la meilleure solution.

Le graphique de la figure 4.2, obtenu durant l'exécution du programme, montre la convergence de l'algorithme. Deux courbes différentes sont présentées : la courbe inférieure est reliée à la meilleure solution trouvée jusqu'à la $k^{e}$ itération (comme la meilleure solution est mémorisée, la courbe ne peut que diminuer à mesure que l'exécution de l'algorithme se poursuit); la courbe supérieure donne la moyenne des 10 solutions évaluées à chaque itération.

Description de la figure 4.2

Figure 4.2 Meilleure valeur et valeur moyenne d'évaluation durant l'exécution de l'AG

La meilleure solution résultante est $v = (4, 1, 3, 4, 1, 3, 3, 2) .$ Elle correspond à la stratification présentée dans le tableau 4.3, avec un vecteur de répartition $a = (3, 2, 4, 2) .$

Tableau 4.3
Information sur les strates finales
Sommaire du tableau
Le tableau montre de l'information sur les strates finales. Les données sont présentées selon Strate agrégée, Strates atomiques originales, ( X ₁, X ₂), N, Y ₁, Y ₂ (figurant comme en-tête de colonne).
Strate agrégée	Strates atomiques originales	( X ₁, X ₂)	N	Y ₁		Y ₂
Strate agrégée	Strates atomiques originales	( X ₁, X ₂)	N	Moyenne	Écart-type	Moyenne	Écart-type
1	2,5	(1,2) ou (2,2)	41	4,16	0,45	1,30	0,19
2	8	(3,3)	26	5,88	0,49	2,10	0,22
3	3,6,7	(1,3) ou (2,3) ou (3,2)	33	5,06	0,38	1,80	0,33
4	1,4	(1,1) ou (2,1)	50	1,46	0,17	0,25	0,10

Brièvement, en appliquant l'algorithme génétique, nous réussissons à trouver la solution optimale en n'explorant que $25 \times 10 = 250$ stratifications différentes au lieu des 4 140 appartenant à l'univers des partitions.

Afin de confirmer que ce résultat n'est pas dû à un « coup de chance », nous effectuons différentes exécutions de l'algorithme : chaque exécution comporte 10 répétitions de l'application de l'algorithme génétique, en faisant varier les valeurs du paramètre « nombre d'itérations ». Les résultats sont présentés au tableau 4.4.

Tableau 4.4
Capacité de l'AG à trouver la solution optimale
Sommaire du tableau
Le tableau montre la capacité de l'AG à trouver la solution optimale. Les données sont présentées selon Exécution de l'AG (10 répétitions chacune), Valeur du paramètre « nombre d'itérations » dans l'AG, Solutions avec n = 11 (optimale), Solutions avec n = 12, Solutions avec n = 14 (figurant comme en-tête de colonne).
Exécution de l'AG (10 répétitions chacune)	Valeur du paramètre « nombre d'itérations » dans l'AG	Solutions avec n = 11 (optimale)	Solutions avec n = 12	Solutions avec n = 14
(a)	25	5	4	1
(b)	50	7	3	-
(c)	100	9	1	-
(d)	200	10	-	-

Dans l'exécution (a), nous découvrons que, avec 25 itérations seulement, arriver à trouver la solution optimale est effectivement un « coup de chance », car dans la moitié des essais, la solution trouvée est plus grande que la solution optimale. Toutefois, si l'on fait augmenter le nombre d'itérations jusqu'à 200 (exécution (d)), l'algorithme génétique s'avère fiable en ce qui a trait à sa capacité d'atteindre l'optimalité, car dans tous les essais, la solution optimale est trouvée.

En ce qui concerne le nombre de strates correspondant à la solution optimale trouvée, en moyenne, il est de 4, avec un intervalle de $[3, 5] .$

Enfin, nous voulons aussi vérifier que les solutions trouvées sont conformes aux contraintes de précision (CV maximal égal à 5 % pour les deux variables cibles). Donc, dans l'exécution (d) (itérations $= 200$ ), pour chacune des 10 solutions produites, nous procédons au tirage de 1 000 échantillons dans la base de sondage et nous calculons les CV associés. Les résultats correspondants sont présentés à la figure 4.3 : la moyenne des CV pour la première variable cible (pétale.longueur) est de l'ordre de 3 %, tandis que pour la deuxième, elle est de l'ordre de 5 %. Donc, nous pouvons dire qu'en moyenne, les contraintes de précision n'ont pas été violées.