Un algorithme d’optimisation appliqué au problème de stratification unidimensionnelle
Section 5. Résultats du calcul

• Précédent
• Suivant

Dans cette section, nous présentons les résultats de l’application de six méthodes au problème de stratification (Dalenius et Hodges (DH), méthode géométrique (GH), Kozak (KO), algorithme génétique de Keskintürk et Er (KE), GRASP (GR) et nouvelle méthode BRKGA décrite à la section 4 (BR)). Nous avons effectué toute cette expérience avec la version 3.3.1 de R. On peut trouver les méthodes DH, GH et KO dans le package stratification en R de Baillargeon et Rivest (2014) (version 2.2-5). Nous employons dans ce cas la méthode de répartition d’échantillon de Neyman. La méthode KE figure dans le package en R GA4Stratification de Er, Keskintürk et Daly (2010) (version 1.0). Avec cette méthode, le maximum d’itérations considérées était de 10 000 et les valeurs des autres paramètres requis étaient celles qu’indiquent Keskintürk et Er (2007), à savoir $p=35$ solutions candidates dans chaque population, un taux de mutation de 15 % et une répartition d’échantillon aussi fondée sur l’algorithme génétique. Les auteurs ont appliqué les méthodes GR et BR en R et le code en question figure dans le package stratbr de de Moura Brito et coll. (2017a) (version 1.2) disponible par le réseau CRAN.

Dans le cas de la méthode BR, nous avons examiné $p=100$ solutions candidates à chaque itération avec 20 % de solutions retenues $\left(p_e=20\right)$ et 30 % de mutations $\left(p_m=30\right).$ La probabilité de copier un gène du vecteur retenu était fixée à $r_c=\text{0,6}$ et le nombre total d’itérations, à 1 500. Aux fins de la répartition d’échantillon, nous avons combiné les méthodes BR et GR à la formulation proposée par de Moura Brito et coll. (2015) qui figure dans le package MultAlloc en R et qui est aussi disponible par le réseau CRAN.

Dans une comparaison d’efficacité relative, nous avons appliqué ces méthodes à 27 populations. Certaines de celles-ci figurent dans les packages stratification et GA4Stratification en R; elles ont auparavant servi à certaines études comparatives comme celles de Keskintürk et Er (2007), Er (2011) et de Moura Brito et coll. (2017b). On trouvera à l’annexe A une brève description de toutes ces populations avec des précisions sur les variables considérées comme la « variable $x»$ dans chaque population. Le tableau 5.1 présente certaines descriptions sommaires des populations en question.

Les 27 populations traitées forment ici un ensemble très hétérogène et leur taille totale varie de quelques centaines d’éléments (ME84 et P75 avec $N=\text{18}\text{570}$ sont les plus petites tailles) à plusieurs milliers (Coffee avec $N=\text{18}\text{570}$ est la taille la plus grande). On constate aussi une forte variation (de $K=51$ pour Kozak1 à $K=\text{5}\text{453}$ pour Kozak3) du nombre $K$ de valeurs distinctes de la variable de stratification, qui est la mesure de taille la plus importante pour l’efficacité de notre algorithme d’optimisation. Notons enfin une ample variation de l’asymétrie des distributions de la variable $x$ entre des valeurs modestes en sens négatif (-0,70 pour Beta103) et une valeur appréciable (40,04 pour CensoCO).

Nous avons fait tous les calculs du volet computationnel de notre expérience en R avec un ordinateur de 24 Go de mémoire vive et 8 processeurs de 3,40 GHz (I7). Tirant parti de l’architecture multicœur des ordinateurs modernes, nous avons employé le package snowfall en R pour un traitement parallèle de l’algorithme BRKGA. Précisons que, à chaque itération, la procédure de décodage produit un jeu de solutions pour les bornes. Ces bornes sont ensuite transmises au package MultAlloc pour une répartition optimale permettant d’obtenir les tailles d’échantillon des diverses strates, puis de calculer la fonction objective de variance. Comme la formulation de cet exercice d’optimisation globale influe directement sur le temps de calcul à cette étape, nous avons mis la répartition et le calcul de la fonction objective en traitement parallèle.

Les six méthodes de l’expérience numérique ont été appliquées à chacune des 27 populations; le nombre $H$ de strates était de 3, 4, 5 et 6. Nous avons employé ces valeurs puisqu’elles revenaient souvent dans les applications et dans des études comparatives semblables de la documentation spécialisée comme celles de Er (2011) et de Gunning et Horgan (2004). Nous avons négligé les valeurs supérieures de $H,$ car le gain d’efficacité serait modeste avec $H>6.$ Nous avons pris comme taille d’échantillon $n=100$ (à coût fixe) comme dans les expériences numériques de Er (2011) et Kozak et Verma (2006).

Pour évaluer l’efficacité des méthodes, nous avons calculé les CV de l’estimateur du total de la variable de stratification $x$ pour chaque population et chaque nombre de strates, ce qui a donné $27\times 4=$ 108 scénarios pour chaque méthode. Nous avons obtenu les CV à l’équation (2.7) et multiplié ces valeurs par 100 pour les mettre sous forme de pourcentage. Le tableau 5.2 présente les CV des six méthodes. Les cases ombrées correspondent aux méthodes représentant la meilleure solution (CV minimal) dans chacun des 108 scénarios. Les « sans objet » dans ces tableaux sont les cas où nous ne pouvions obtenir de solutions à cause de problèmes avec la méthode de stratification ou la répartition correspondante.

Si nous analysons les résultats au tableau 5.2 et, en particulier, les cases ombrées, il ressort que BR est d’un excellent rendement si on compare cette méthode aux cinq rivales. Cette perception est renforcée par les courbes de la figure 5.1 où la méthode BR est comparée à toutes ses rivales. Les points au-dessus de la droite représentent les scénarios où la méthode mise en comparaison est d’un moindre rendement que la méthode BR. À considérer ces courbes, il est clair que les trois méthodes les plus performantes sont GR, KO et BR.

Le tableau 5.3 indique en pourcentage le nombre de fois que chaque méthode produit la meilleure solution sur les 108 scénarios. Les deux méthodes BR et KO sont d’un rendement supérieur aux autres méthodes et se retrouvent à égalité à plusieurs reprises pour la meilleure solution. La méthode DH a produit la meilleure solution dans seulement 3 des 108 scénarios et la méthode GH ne le fait jamais.

Ajoutons que la méthode géométrique GH donne non seulement des CV élevés, mais souvent aussi des solutions impossibles où les bornes de strate mènent à des répartitions où les tailles d’échantillon sont supérieures aux tailles de population correspondantes. Cette méthode a quelquefois pour effet de répartir la population en laissant très peu d’éléments dans certaines strates. D’après Gunning et Horgan (2004) et comme le signalent Keskintürk et Er (2007), comme l’étendue des intervalles s’accroît géométriquement, la méthode GH ne donne pas de bons résultats avec de faibles valeurs de la variable de stratification, puisque certaines strates sont alors étroites. Cette méthode est inapplicable de surcroît lorsque la valeur la plus basse de la variable de stratification est zéro.

Pour la plupart des populations, la méthode KE a produit des CV proches de ceux des méthodes KO, GR et BR, qui sont les plus efficaces en temps de calcul. Nous avons observé une forte variation des temps de calcul entre les méthodes. La méthode KE était la pire à ce critère avec des temps bien supérieurs à ceux des méthodes rivales. Par ailleurs, la méthode KO avait les calculs les plus rapides et offrait fréquemment la meilleure précision possible (CV les plus bas). La méthode BR présentait un temps de calcul intermédiaire entre ceux des méthodes KO et KE.

Le graphique à la figure 5.2 présente en pourcentage les fois que chacune des méthodes BR, KO, KE et GR produit la meilleure solution selon le nombre de strates. On y voit un net avantage pour la méthode BR comparativement aux méthodes KE et GR. Comparée à la KO, la BR a un meilleur rendement avec $H=3$ et $H=6,$ la KO l’emporte cependant sur le BR avec $H=4$ et $H=5.$ La GR était aussi bonne que la KO avec $H=3$ et $H=6,$ mais l’était moins que la BR et KO avec $H=4$ et $H=5.$ La KE était clairement la perdante dans cette analyse pour tout nombre $H$ de strates.

Nous avons en outre étudié les associations entre le rendement et d’autres facteurs possibles comme l’asymétrie ou la taille $(N$ ou $K)$ des populations, mais sans en arriver à des associations significatives dans notre ensemble limité de populations.

• Précédent
• Page principale de l'article
• Suivant