2 Formalisation du problème d'optimisation

Marco Ballin et Giulio Barcaroli

Précédent | Suivant

Univers des diverses options de stratification

Nous définissons comme étant une base de sondage  $F$ un ensemble de $N$  enregistrements contenant de l'information (organisée en variables) en rapport avec $N$  individus de la population de référence. Certaines variables sont utiles pour l'identification des unités, tandis que d'autres peuvent être utilisées pour définir la stratégie d'échantillonnage. Les valeurs de ces dernières (appelées à partir d'ici variables auxiliaires) peuvent être observées au moyen d'un recensement ou d'autres sources de données telles que des registres administratifs.

Nous supposons qu'un ensemble de $M$  variables auxiliaires $X_m\left(m=1,\dots ,M\right)$ sont disponibles dans la base de sondage. Cet ensemble peut contenir différents types de variables (nominales, ordinales ou continues). Nous supposons également que les variables auxiliaires continues sont subdivisées en classes en appliquant des algorithmes de transformation appropriés.

Toutes ces variables peuvent potentiellement être utilisées pour stratifier les unités qui figurent dans la base de sondage.

Sous ces hypothèses, nous pouvons associer à chaque variable auxiliaire un vecteur $d_m=\left\{x_1,\dots ,x_{k_m}\right\}$ de valeurs entières contiguës, qui représentent chacune une valeur originale dans l'ensemble de domaines.

Alors, la stratification la plus détaillée de $F$ peut être considérée comme le résultat du produit cartésien $PC=X_1\times X_2\times \dots \times X_M.$

Le nombre maximal de strates sera $K={\displaystyle {\prod }_{m=1}^M{k}_m-I^{*}},$ où $I^{*}$ est le nombre de combinaisons impossibles ou absentes  de valeurs dans la base de sondage. Donc, la stratification la plus détaillée de la base de sondage est telle qu'elle contient $K$  strates, qui correspondent à toutes les combinaisons possibles des valeurs dans les $M$ variables auxiliaires. Nous appelons strates atomiques les strates qui appartiennent à cette stratification particulière. Chaque strate atomique est caractérisée par une combinaison unique de valeurs des $M$ variables auxiliaires. Nous pouvons attribuer une étiquette $l_k\left(k=1,\dots ,K\right)$ à chaque strate atomique.

Si nous considérons l'ensemble étiqueté de strates atomiques $L=\left\{l_1,l_2,\dots ,l_K\right\},$ nous pouvons définir l'ensemble de toutes les partitions possibles $P_1,P_2,\dots ,P_B,$ où $B$ peut être calculé en utilisant la formule de Bell :

$$B_K={\displaystyle \sum _{i=0}^{K-1}\left(\begin{array}{c}K-1\\ i\end{array}\right)}\cdot B_i\left(B_0=1\right)$$

Nous définissons l'ensemble $\left\{P_1,P_2,\dots ,P_B\right\}$ de partitions de $L$ comme étant l'univers (ou espace) des stratifications.

Évaluation d'une stratification donnée

Étant donné une partition $P_i$ de $L,$ caractérisée par $H$ strates, soit $N_h$ et $S_{h,g}^2,h=1,\dots ,H,$ $g=1,\dots ,G$ respectivement, le nombre d'unités et les variances dans la strate  $h$ des $G$  variables cibles de l'enquête $Y_1,\dots ,Y_G.$ En supposant un échantillonnage aléatoire simple de $n_h$ unités sans remise dans chaque strate, la variance de l'estimateur de Horvitz-Thompson du total de la $g^{\text{e}}$ variable cible $\left({\widehat{T}}_g\right)$ est

$$\text{Var}\left({\widehat{T}}_g\right)={\displaystyle \sum _{h=1}^H{N}_h^2\left(1-\frac{n_h}{N_h}\right)}\frac{S_{h,g}^2}{n_h}g=1,\dots ,G\left(2.1\right)$$

Considérons la fonction de coût suivante

$$C\left(n_1,\dots ,n_H\right)=C_0+{\displaystyle \sum _{h=1}^H{C}_h{n}_h}\left(2.2\right)$$

où $C_0$ indique un coût fixe (qui ne dépend pas de la taille de l'échantillon) et $C_h$ représente le coût moyen de l'observation d'une unité dans la strate $h.$

Sachant $V_g\left(g=1,\dots ,G\right),$ les limites supérieures des variances d'échantillonnage prévues de ${\widehat{T}}_1,\dots ,{\widehat{T}}_G,$ le problème de répartition multivariée optimale classique de l'échantillon (Bethel 1985) peut être défini comme la recherche de la solution du minimum (par rapport à $n_h$ ) de la fonction linéaire $C$ sous les contraintes convexes $\text{Var}\left({\widehat{T}}_g\right)\le V_{g}g=1,\dots ,G:$

$$\{\begin{array}{l}\min C\left(n_1,\dots ,n_H\right)=C_0+{\displaystyle \sum _{h=1}^H{C}_h{n}_h}\\ \text{Var}({\widehat{T}}_g)={\displaystyle \sum _{h=1}^H{N}_h^2\left(1-\frac{n_h}{N_h}\right)}\frac{S_{h,g}^2}{n_h}\le V_{g}g=\text{1,}\dots \text{,}G\end{array}\left(2.3\right)$$

Bethel (1989) a suggéré qu'il était plus facile de résoudre le problème en considérant la fonction suivante de $n_h:$

$$x_h=\{\begin{array}{l}1/n_h\text{ si }{n}_h\ge \text{1}\hfill \\ \infty \text{ autrement}\hfill \end{array}\left(2.4\right)$$

En utilisant $x_h$ , la fonction de coût peut s'écrire

$$C\left(x_1,\dots ,x_H\right)=C_0+{\displaystyle \sum _{h=1}^H\frac{C_h}{x_h}}\left(2.5\right)$$

et la variance,

$$\text{Var}\left({\widehat{T}}_g\right)={\displaystyle \sum _{h=1}^H{N}_h^2}\left(1-\frac{1}{x_h{N}_h}\right)S_{h,g}^2{x}_h={\displaystyle \sum _{h=1}^H{N}_h^2{S}_{h,g}^2{x}_h-N_h{S}_{h,g}^{2}g=1,\dots ,G}\left(2.6\right)$$

Par conséquent, le problème de répartition multivariée de l'échantillon peut être défini comme la recherche du minimum (par rapport à $x_h$ ) de la fonction convexe (2.5) sous un ensemble de contraintes linéaires

$${\displaystyle \sum _{h=1}^H{N}_h^2{S}_{h,g}^2{x}_h-N_h{S}_{h,g}^2}\le V_{g}g=1,\dots ,G\left(2.7\right)$$

Bethel a fourni un algorithme, dont il est prouvé qu'il converge vers la solution (si elle existe), en appliquant la méthode des multiplicateurs de Lagrange à ce problème (un algorithme plus facile avait été proposé antérieurement par Chromy (1987); comme l'a fait remarquer Bethel, l'algorithme de Chromy fonctionne dans la plupart des cas pratiques, mais il n'existe pas de preuve qu'il converge si une solution existe).

L'approche de l'optimisation illustrée ici donne une solution continue, qui doit être arrondie pour fournir des tailles entières d'échantillons de strates. Notre mise en œuvre de l'algorithme de Bethel fournit les valeurs de $n_h$ comme étant les valeurs $1/x_h$ arrondies à l'entier supérieur.

Il convient de souligner que la même approche peut être suivie pour traiter le problème des domaines multiples. Considérons la transformation habituelle pour le problème d'estimation par domaine :

$$Y_i^d=\{\begin{array}{l}{Y}_{\mathrm{i }}\text{si l'unité }i\text{ appartient au domaine }d\hfill \\ 0\text{ autrement}\hfill \end{array}$$

Si les quantités définies antérieurement pour décrire l'approche de Bethel sont calculées en utilisant les variables $Y^d\left(d=1,\dots ,D\right),$ la solution de la répartition multivariée est la solution pour le cas de plusieurs domaines.

Sélection de la meilleure stratification sur la base d'un dénombrement complet

Afin de choisir la meilleure stratification d'une base de sondage donnée, c.-à-d. celle qui garantit le coût minimal $C\left(n_1,\dots ,n_H\right)$ associé à un échantillon dont la taille totale et la répartition sont conformes aux contraintes de précision, il est possible de procéder comme il suit :

• générer la stratification la plus détaillée associée à $F,$ c'est-à-dire l'ensemble $L$ de strates atomiques;
• dénombrer toutes les partitions $P_i$ de $L;$
• pour chaque partition $P_i,$ résoudre le problème de répartition de l'échantillon correspondant, ce qui équivaut à déterminer le vecteur $\left(n_1,\dots ,n_H\right),$ et calculer la valeur $C_i\left(n_1,\dots ,n_H\right)$ associée à $P_i;$
• choisir la partition $P_i$ pour laquelle $C_i\left(n_1,\dots ,n_H\right)$ est minimisé.

Ce faisant, l'optimisation de la solution est obtenue en tenant compte de l'univers complet des stratifications.

Malheureusement, cette procédure ne s'applique qu'aux situations où la dimension $K$ de $L$ est faible : en fait, le nombre de partitions (donné par la formule de Bell) augmente très rapidement (p. ex., $B_4=$ 15, $B_{10}=$ 115 975 et $B_{100}\approx 4,76\times {10}^{115}$ ). Par conséquent, dans la plupart des cas, le dénombrement complet de l'espace des solutions n'est pas faisable. La présente proposition, fondée sur l'algorithme génétique, permet d'explorer l'univers des stratifications et de déterminer lesquelles ne devraient pas être éloignées de la stratification optimale.

L'algorithme génétique

L'algorithme génétique $\left(AG\right)$ est une technique de recherche utilisée en calcul pour trouver des solutions exactes ou approximatives aux problèmes d'optimisation et de recherche. Les algorithmes génétiques représentent une classe particulière d'algorithmes évolutionnaires qui font appel à des techniques inspirées de la biologie de l'évolution, telles que l'hérédité, la mutation, la sélection et le croisement (également appelé recombinaison) (Vose 1999) (Schmitt 2001 et 2004).

On implémente un $AG$ dans une simulation informatique itérative dans laquelle un ensemble initial d'individus, qui sont chacun une solution potentielle du problème courant (représentés par un vecteur appelé génome), évolue par hérédité, mutation, sélection et croisement, de manière à accroître la valeur d'adaptation (en anglais, fitness) moyenne des générations suivantes. Ici, la valeur d'adaptation correspond à la fonction objectif définie dans le problème d'optimisation de manière que l'évolution ait pour résultat la maximisation (ou la minimisation) de la fonction objectif.

L'ensemble d'individus traités à chaque itération de l'$AG$ est appelé génération. L'évolution est l'ensemble des changements qui ont lieu durant la production des générations consécutives par itération du processus.

À chaque itération de l'$AG$, après avoir évalué la valeur d'adaptation de chaque individu de la génération, un ensemble d'individus sont sélectionnés de manière stochastique (en privilégiant ceux ayant la valeur d'adaptation la plus élevée) et modifiés (recombinés et parfois soumis aléatoirement à des mutations) pour former une nouvelle génération. Cette nouvelle génération est alors évaluée durant l'itération suivante de l'algorithme. Puisque les individus ayant la meilleure valeur d'adaptation sont plus susceptibles que les autres d'être sélectionnés pour engendrer les individus de la génération suivante, l'$AG$ produit une augmentation de la valeur moyenne d'adaptation au cours de l'évolution.

Le paramètre taux de mutations est exprimé comme le taux de chromosomes (les éléments du génome) qui peuvent subir une mutation pour chaque individu au moment où sont générés les enfants destinés à former la génération suivante. Une valeur élevée garantit de grandes différences entre les générations successives. Il convient de souligner qu'un taux élevé de mutations rend l'$AG$ plus susceptible de ne pas stagner à des optima locaux, au prix d'une convergence plus lente vers la solution optimale, tandis qu'une valeur faible accélère la convergence, mais augmente le risque d'optima locaux.

Habituellement, l'algorithme s'arrête quand un nombre maximal d'itérations a été atteint ou que la poursuite des itérations n'améliore pas la solution courante. Dans les deux cas, la solution optimale peut ou non avoir été atteinte.

Précédent | Suivant