Algorithme génétique de regroupement pour la stratification et la répartition simultanée de l’échantillon dans les plans de sondage
Section 2. Algorithmes génétiques classiques et de regroupement

• Précédent
• Suivant

Dans cette section, il sera question d’AG « classiques » et d’AG de « regroupement ». Nous expliquerons en quoi les derniers conviennent mieux à notre problème.

2.1  Algorithmes génétiques classiques

Les AG forment une catégorie d’algorithmes d’optimisation inspirée par la nature et formée d’après la capacité des organismes à résoudre le problème complexe de l’adaptation à la vie sur Terre. Les variables d’un problème d’optimisation sont appelées gènes et leurs valeurs, allèles. Une solution possible est une liste d’allèles appelée chromosome. Un ensemble de chromosomes est ce qu’on appelle habituellement une population. Pour ne pas confondre cette population avec la population visée, nous parlerons de population de chromosomes à propos des AG. La fonction objectif (qui est à maximiser par convention) est celle de l’adaptation d’un chromosome. Dans la recherche de chromosomes adaptés (c’est-à-dire de solutions à haute valeur d’objectif), nous employons deux opérateurs génétiques, ceux de la mutation pour les légères variations aléatoires équivalant à de petits pas locaux dans un algorithme d’escalade, d’une part, et de la permutation pour de grandes variations avec recombinaison des gènes de deux chromosomes parents. Un opérateur de recombinaison bien connu est l’opérateur de permutation ponctuelle. Dans ce cas, nous choisissons deux chromosomes parents aux allèles

$$a_1\mathrm{,}\dots \mathrm{,}{a}_N{b}_1\mathrm{,}\dots \mathrm{,}{b}_N,$$

prenons un entier aléatoire $i$ (point de permutation) avec $1\le i\mathrm{<mo><</mo>}N$ et produisons deux nouveaux chromosomes de filiation

$$a_1\mathrm{,}\dots \mathrm{,}{a}_i\mathrm{,}{b}_{i+1}\mathrm{,}\dots \mathrm{,}{b}_N{b}_1\mathrm{,}\dots \mathrm{,}{b}_i\mathrm{,}{a}_{i+1}\mathrm{,}\dots \mathrm{,}{a}_N.$$

Les chromosomes fils pourraient alors être soumis à une mutation aléatoire où quelques allèles sont changés avant d’être reversés dans la population de chromosomes. Il existe diverses méthodes de sélection des parents et de remplacement des chromosomes. Dans les AG générationnels, toute la population de chromosomes se trouve remplacée par sa descendance et les parents sont souvent choisis au hasard, mais avec un biais en faveur des chromosomes mieux adaptés. Dans les AG stationnaires, une seule descendance naît à chaque itération de l’algorithme et le chromosome le moins adapté est habituellement remplacé dans la population de chromosomes. Les AG donnent dans bien des cas des résultats plus robustes que ceux des algorithmes de recherche à escalade grâce à leur recours à la recombinaison. Ils ont trouvé de nombreux usages depuis leur introduction en 1975 par John Holland.

L’AG représenté dans le paquet SamplingStrata en $R$ (R Core Team, 2015) (Barcaroli, 2014) est un AG générationnel élitiste où les strates atomiques $L$ sont considérées comme les éléments d’un ensemble (ou gènes) pour une stratégie type de permutation. À chaque itération, les meilleures solutions (élite) sont reportées à la génération qui suit. Chaque gène représente une variable du problème. C’est ce que nous appelons l’AG classique parce que l’on fait intervenir une représentation et des opérateurs génétiques classiques, comme nous allons le décrire.

Diviser les strates atomiques en groupes disjoints est un exemple de problème de regroupement qui ressemble aux problèmes de découpe, de garnissage et de partition. Ce qui a motivé la présente recherche, c’est que nous savons que les AG classiques donnent de piètres résultats avec les problèmes de regroupement. La raison en est que la représentation chromosomique d’un regroupement comporte beaucoup de symétrie (ou de redondance): permuter entre groupes donne un regroupement équivalent, de sorte que chaque regroupement est à représentations multiples. La symétrie nuit aux AG, car recombiner dans un même regroupement parent pourrait donner un regroupement de filiation très différent, ce qui va à l’encontre du principe de base des algorithmes génétiques selon lequel les parents devraient généralement produire une descendance d’une même adaptation. Dans des cas extrêmes, un AG classique pourrait donner un résultat même pire que celui d’une recherche entièrement aléatoire. Nous éclairons ce problème par deux exemples.

Illustrons le problème de symétrie dans un premier exemple avec des parents représentant le même regroupement mais en des combinaisons différentes. Pour plus de lisibilité, nous employons les lettres A à F comme allèles au lieu de nombres entiers. Prenons les deux chromosomes suivants :

pour le regroupement $\left\{\left\{1\right\},\left\{2\right\},\left\{3\right\},\left\{4\right\},\left\{5\right\},\left\{6\right\}\right\}.$ Posons maintenant qu’une permutation ponctuelle permet d’obtenir de nouveaux chromosomes de filiation de ces parents. Si nous choisissons arbitrairement le centre des chromosomes comme point de permutation, nous obtenons la descendance suivante :

avec les deux, le regroupement est totalement autre $\left\{\left\{1;6\right\},\left\{2;5\right\},\left\{3;4\right\}\right\}:$ aucun groupe n’est reporté des parents à la descendance. Ainsi, l’adaptation de la descendance peut être sans lien aucun avec celle des parents et l’emploi de l’algorithme génétique se ramène à une recherche quasiment aléatoire. Voici un exemple avec les deux chromosomes classiques suivants :

avec les deux, le regroupement est hétérogène : $\left\{\left\{1\right\},\left\{3;6\right\},\left\{2;5\right\},\left\{4\right\}\right\}$ et $\left\{\left\{5;6\right\},\left\{1;4\right\},\left\{2;3\right\}\right\}.$ Par la même stratégie de permutation, nous obtenons la descendance suivante :

pour les regroupements $\left\{\left\{1;5;6\right\},\left\{3\right\},\left\{4\right\},\left\{2\right\}\right\}$ et $\left\{\left\{6\right\},\left\{1\right\},\left\{5\right\},\left\{2;3;4\right\}\right\}.$ À noter que les fils ont très peu en commun avec les parents, les seuls groupes préservés étant $\left\{1\right\}$ et $\left\{4\right\}.$

2.2  Algorithmes génétiques de regroupement

On peut s’attaquer au problème de symétrie en y allant de représentations d’opérateurs génétiques plus complexes (Galinier et Hao, 1999) ou en recourant aux techniques de classification automatique (Pelikan et Goldberg, 2000). Le risque avec ce mode de classification en grappes est que la diversité génétique se perde si les grappes en question sont trop étroites, d’où une éventuelle stagnation de la recherche (Prügel-Bennett, 2004). Il s’agit plutôt pour nous de poursuivre dans la voie déjà tracée en concevant un AGR (Falkenauer, 1998) dont on sait qu’il donne de bien meilleurs résultats que les AG classiques avec les problèmes de regroupement.

Les AGR sont expressément conçus pour résoudre de tels problèmes et ont trouvé de nombreux usages dans le déploiement de réseaux WiFi (Agustín-Blas, Salcedo-Sanz, Vidales, Urueta et Portilla-Figueras, 2011), la conception de réseaux sans fil (Brown et Vroblefski, 2004), le coupage de plaques d’acier (Hung, Sumichrast et Brown, 2003), l’aménagement d’ateliers de production (De Lit, Falkenauer et Delchambre, 2000) et l’analyse de réseaux sociaux (James, Brown et Ragsdale, 2010). L’heuristique peut être la même que pour les autres AG (sélection des parents, remplacement par filiation, etc.), mais le codage et les opérateurs génétiques diffèrent, c’est-à-dire la façon de traiter le tout comme des chromosomes et de procéder à la recombinaison et à la mutation. Nous allons illustrer les différences en reprenant nos exemples.

Les AGR représentent un regroupement comme une liste ordonnée de sous-ensembles en écartant les ensembles vides. Les parents dans le second exemple à la section 2.1 peuvent ainsi être représentés :

$$\langle \left\{1\right\},\left\{3;6\right\},\left\{2;5\right\},\left\{4\right\}\rangle \langle \left\{5;6\right\},\left\{1;4\right\},\left\{2;3\right\}\rangle .$$

La mutation est simple avec l’AGR : un élément est déplacé d’un groupe à l’autre. Toutefois, l’opérateur de recombinaison est plus complexe. Nous choisissons une section de permutation dans chaque parent, soit $\langle \left\{1\right\},\left\{3;6\right\}\rangle$ pour le $1^{\text{er}}$ parent et $\langle \left\{1;4\right\}\rangle$ pour le second. Nous injectons la $1^{\text{re}}$ section de permutation dans le $2^{\text{e}}$ parent à un point aléatoire et vice versa :

$$\langle \left\{1\right\},\left\{3;6\right\},\underset{\_}{\left\{1;4\right\}},\left\{2;5\right\},\left\{4\right\}\rangle \langle \left\{5;6\right\},\left\{1;4\right\},\underset{\_}{\left\{1\right\}},\underset{\_}{\left\{3;6\right\}},\left\{2;3\right\}\rangle .$$

Nous retranchons ensuite tout objet répété se trouvant déjà dans le parent récepteur :

$$\langle \varnothing ,\left\{3;6\right\},\left\{1;4\right\},\left\{2;5\right\},\varnothing \rangle \langle \left\{5\right\},\left\{4\right\},\left\{1\right\},\left\{3;6\right\},\left\{2\right\}\rangle .$$

Enfin, nous retirons tout ensemble vide :

$$\langle \left\{3;6\right\},\left\{1;4\right\},\left\{2;5\right\}\rangle \langle \left\{5\right\},\left\{4\right\},\left\{1\right\},\left\{3;6\right\},\left\{2\right\}\rangle .$$

C’est là la descendance. Il est clair que les deux fils ont beaucoup en commun avec les deux parents, puisque 5 des 7 groupes des parents sont préservés chez les fils, à savoir : $\left\{1\right\},$ $\left\{4\right\},$ $\left\{1;4\right\},$ $\left\{2;5\right\}$ et $\left\{3;6\right\}.$ Dans le premier exemple à la section 2.1, nous pouvons facilement vérifier que les deux fils représentent le même regroupement que chez les parents, comme on pouvait s’y attendre. Cette propriété de la recombinaison à injection dans l’AGR rend bien plus probable la similitude d’adaptation entre la descendance et l’ascendance, ce qui aide à son tour l’AGR à améliorer itérativement la population de chromosomes.

On pourrait observer que la représentation AGR du problème comporte toujours de l’asymétrie : tout regroupement demeure à représentations multiples par permutation des sous-ensembles de la liste ordonnée, mais les opérateurs génétiques sont quasiment indépendants de cet ordre qui n’a presque plus rien à voir. Le seul effet de cet ordre est de limiter le jeu d’injections possibles : dans le second exemple à la section 2.1, il est impossible d’injecter une section de permutation inexistante comme $\langle \left\{1\right\},\left\{4\right\}\rangle$ du parent 1, parce que ces deux groupes ne sont pas adjacents. Nous pouvons supprimer cette limite à l’aide d’un opérateur génétique supplémentaire appelé inversion, lequel choisit une section du chromosome et l’inverse. Un exemple en est

$$\langle \left\{1\right\},\left\{2\right\},\underset{\_}{\left\{3;6\right\}},\underset{\_}{\left\{4\right\}},\underset{\_}{\left\{5\right\}}\rangle \to \langle \left\{1\right\},\left\{2\right\},\underset{\_}{\left\{5\right\}},\underset{\_}{\left\{4\right\}},\underset{\_}{\left\{3;6\right\}}\rangle .$$

Cela ne change pas le regroupement représenté par le chromosome, mais si on réordonne les groupes de ce chromosome, toutes les injections sont possibles.

L’injection, la mutation et l’inversion sont les opérateurs courants des AGR, mais il n’existe pas d’algorithme canonique. Les AGR tendent plutôt à s’ajuster à leurs usages particuliers et, en principe, tout AG peut s’adapter à un problème de regroupement par le choix des opérateurs. À la section 2.3, nous concevons un AGR en adaptation à notre problème.

2.2.1  À propos de la mise en œuvre

Pour plus de clarté, nous omettons les détails de mise en œuvre dans les descriptions de la section 2.2 et oublions, par exemple, que les chromosomes AGR se traitent habituellement en deux parties (et parfois plus). Il y a représentation classique comme plus haut, d’une part, puis liste des groupes non vides en permutation, d’autre part. L’injection intervient en seconde partie sur les chromosomes parents et une certaine réidentification des groupes est nécessaire.

En temps normal, nous décidons d’avance du nombre d’itérations dans l’exécution de l’algorithme. Leur nombre doit être tel que l’AGR puisse converger vers la solution optimale après application des probabilités de mutation et d’inversion. Si la solution optimale est connue d’avance, nous pouvons régler l’algorithme pour qu’il s’arrête à ce point d’optimalité.

Nous déterminons ordinairement le nombre d’itérations par l’expérience acquise dans l’application de l’AGR à des variables cibles et auxiliaires semblables pour les mêmes ensembles de données ou avec l’ensemble de données et les variables cibles et auxiliaires propres au problème à résoudre. Nous pouvons avoir à expérimenter avec l’AGR (ou l’AG) avant de pouvoir estimer le nombre d’itérations nécessaires pour que la convergence s’opère. En fait, il est possible que l’AGR ou l’AG paraisse converger après un nombre donné d’itérations, mais que l’algorithme soit plutôt coincé dans un minimum local. Il serait bon que l’on hausse le nombre d’itérations et essaie diverses probabilités de mutation pour être sûr de converger vers un minimum global.

Cela implique qu’un certain nombre d’essais aient lieu avant le choix définitif des paramètres d’exécution de l’algorithme. Ainsi, que l’on sache que l’AGR convergera plus rapidement que l’AG s’ajoutera probablement comme facteur complexe dans l’amélioration de la durée totale du traitement. Dans les expériences que nous allons décrire, nous allons garder petit le nombre d’itérations, car nous voulons démontrer la convergence possible de l’AGR vers une solution dans ce nombre donné d’itérations.

Nous prenons alors les paramètres de mutation des exemples cités par Ballin et Barcaroli (2013) ou les paramètres par défaut dans Barcaroli (2014). Nous appliquons les opérateurs génétiques de regroupement avec inversion à l’AG conçu par Ballin et Barcaroli (2013) : ce sont là les opérateurs génétiques de regroupement d’un AGR. Nous comparons dans ce cas en rendement les différents opérateurs génétiques AG et AGR plutôt que d’expérimenter le paramétrage en variant le nombre d’itérations, la taille de la population de chromosomes, la probabilité de mutation ou le taux d’élitisme.

L’utilisateur peut choisir d’avance la probabilité de mutation. En temps normal, celle-ci devrait être telle qu’elle accroisse les chances que l’AGR décolle d’un minimum local sans dérégler l’évolution naturelle des chromosomes d’une génération à l’autre. Par ailleurs, nous avons arrêté la probabilité d’inversion à 0,01, parce que cela suffit au maintien de la diversité.

On peut décider par tâtonnement de la taille de la population de chromosomes. Il est souhaitable de s’attacher à la durée d’évaluation de chaque chromosome lorsqu’on établit cette taille : si les chromosomes sont trop nombreux dans l’ensemble, le laps de temps pourrait être démesuré lorsqu’on passe d’une itération à l’autre. Nous avons constaté que l’algorithme bethel.r (algorithme d’évaluation de Bethel-Chromy dans Barcaroli (2014)) prend plusieurs secondes à évaluer fût-ce un seul chromosome dans les ensembles de données plus abondants que nous allons employer (pour plus de détails, voir la section 4).

Nous renvoyons le lecteur à des études comme celle de Falkenauer (1998) pour un complément d’information sur la mise en œuvre des AGR (taux d’élitisme, par exemple).

2.3  Application au problème de stratification et de répartition de l’échantillon en combinaison

Comme nous l’avons mentionné, notre AGR est tiré de l’AG décrit dans Ballin et Barcaroli (2013) et représenté en $R$ dans le paquet SamplingStrata (Barcaroli, 2014), mais avec des chromosomes et des opérateurs de regroupement au lieu des versions classiques. Ce changement est la seule nouveauté dans notre algorithme (sauf pour l’optimisation décrite à la section 4), mais son effet sur le rendement est marqué. Nous avons inséré cet AGR dans une version modifiée de la fonction appelée rbga.r dans le paquet genalg en R (Willighagen, 2005). Il est conçu pour s’agencer avec les autres fonctions dans SamplingStrata et s’appliquer au problème d’optimisation de stratification et de taille d’échantillon en combinaison. Il est résumé à la figure 2.1.

Suivant l’énoncé du problème dans Ballin et Barcaroli (2013), nous récapitulons ainsi la fonction de coût :

$$C\left(n_1\mathrm{,}\dots \mathrm{,}{n}_H\right)\mathrm{<mo>=</mo>}{C}_0+{\displaystyle \sum _{h\mathrm{<mo>=</mo>\; 1}}^H{C}_h{n}_h},$$

où $C_0$ est le coût fixe et $C_h$ le coût moyen de l’interview d’une unité dans la strate $h$ et où $n_h$ est le nombre d’unités ou l’échantillon attribué à la strate $h.$ Dans notre analyse, $C_0$ est fixé à 0 et $C_h$ à 1. L’espérance de l’estimateur du $«g^{\text{e}}»$ total de population est :

$$E\left({\widehat{T}}_g\right)\mathrm{<mo>=</mo>}{\displaystyle \sum _{h\mathrm{<mo>=</mo>\; 1}}^H{N}_h{\overline{Y}}_{h\mathrm{,}g}}\left(g\mathrm{<mo>=</mo>\; 1,}\dots \mathrm{,}G\right),$$

où ${\overline{Y}}_{h\mathrm{,}g}$ est la moyenne des $G$ variables cibles $Y$ dans chaque strate $h.$ La variance de l’estimateur est :

$$\text{VAR}\left({\widehat{T}}_g\right)\mathrm{<mo>=</mo>}{\displaystyle \sum _{h\mathrm{<mo>=</mo>\; 1}}^H{N}_h^2}\left(1-\frac{n_h}{N_h}\right)\frac{S_{h\mathrm{,}g}^2}{n_h}\left(g\mathrm{<mo>=</mo>\; 1,}\dots \mathrm{,}G\right).(2.1)$$

La limite supérieure de variance ou de précision $U_g$ s’exprime comme coefficient de variation (CV) pour chaque ${\widehat{T}}_g:$

$$\text{CV}\left({\widehat{T}}_g\right)\mathrm{<mo>=</mo>}\frac{\sqrt{\text{VAR}\left({\widehat{T}}_g\right)}}{E\left({\widehat{T}}_g\right)}\le U_g.(2.2)$$

Le problème se résume ainsi :

$$\begin{array}{ll}\min n\hfill & ={\displaystyle \sum _{h\mathrm{<mo>=</mo>\; 1}}^H{n}_h}\hfill \\ \text{CV}\left({\widehat{T}}_g\right)\hfill & \le U_g.\hfill \end{array}$$

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