Rapide survol des Algorithmes Génétiques

Les algorithmes génétiques appartiennent aux algorithmes basés sur la théorie de révolution nommés algorithmes ¿volutionnistes (EA). Parmi eux, on trouve à présent trois autres lignes de recherche: – La programmation évolutive (EP), proposée aux États Unis par L.J. Fogel, A.J. Owens and M.J.Walsh en [FOW66] et récemment affinée par D.B. Fogel en [Fog92]. – Les stratégies évolutives (ES) proposées en Allemagne par I. Rechenberg [Rec73] et H.P. Schwefel [SchSl]. — Le paradigme de la programmation génétique (GP) présenté aux Etats Unis par J.R.Koza [Koz89l. Chacune de ces quatre approches est basée sur le processus d’apprentissage collectif à partir d’une population d’individus, où chaque individu représente un point dans l’espace de recherche, La population initiale est générée d’une manière aléatoire. La population s’adapte à l’environnement en suivant un processus aléatoire de sélection, recombinaison et mutation. L’environnement évalue la qualité des individus et le processus de sélection préfère les individus de meilleure qualité. La recombinaison permet 29 Rapide survol des Algorithmes Génétiques 2. RAPIDE SURVOL DES ALGORITHMES GÉNÉTIQUES í’ócliaitge d’information entre les individus et ia mutation introduit une nouvelle int’onnar.ion dans la population. En général, la qualité de la population augmente et on espère arriver à trouver l’optimum. Pour construire un algorithme évolutionniste. nous avons besoin de: !. I ne population initiale de pré-solutions, 2. Une représentation génétique pour les pré-solutions. .’). Des opérateurs génétiques qui font les transformations. –!. Une fonction d’évaluation. •• »>. lu: algorithme de sélection, {>’. De> paramétres: taille de la population, probabilités pour les opérateurs génétiques. 

L’origine des algorithmes génétiques

En 1975. John Holland publie [Hol75j « Adaptation in Natural and Artificial Systems ». Son objectif était de mettre en évidence et d’expliquer rigoureusement les processus d’adaptation des systèmes naturels et de concevoir des systèmes artificiels (logiciels) qui utilisent ces mécanismes. Sa principale contribution était l’utilisation d’une chaîne de caractères binaires pour représenter des structures complexes et l’application de transformations pour les améliorer. L’algorithme génétique de Holland est une méthode pour évoluer depuis une population de « chromosomes » (chaîne de caractères de uns et zéros, ou bits) vers une nouvelle population en utilisant une sorte de « selection naturelle » et en appliquant ensuite les opérateurs inspirés de la génétique: croisement, mutation. Chaque chromosome est composé par des gènes (bits), chaque gène est une instantiation d’un allele (0 ou 1). Un chromosome ou individu représente une solution possible du problème à résoudre. Une population est formée par un ensemble d’individus généralement générés d’une façon aléatoire. Il s’agit d’un algorithme probabiliste qui maintient une population d’individus pour chaque génération. La façon d’évoluer est de sélectionner certains individus de la population « t » (les parents) et parmi eux d’en transformer quelques uns avec des opérateurs génétiques pour générer une nouvelle population « t+1 » (les enfants) qui, nous espérons, aura des meilleurs individus que la population de la génération précédente. Chaque individu est évalué par une fonction d’évaluation, laquelle va nous permettre de guider la sélection des bons individus et aussi de savoir quand nous trouvons une solution. La figure 2.2 montre schématiquement, d’une façon très simplifiée, l’évolution d’une génération à la suivante. Nous avons un ensemble initial de pré-solutions dénommé Population Initiale. Chaque pré-solution est évaluée pour connaître sa qualité vis-à-vis de la fonction à optimiser. Ensuite, l’algorithme de sélection choisit un sous-ensemble de cette population. Ces chromosomes participeront à la reproduction. En moyenne, produisent plus souvent et contribuent davantage aux populations futures. Une partie des membres du sous-ensemble seront donc transformés et ils feront partie de la nouvelle population. Le processus finira une fois qu’il aura, trouvé la solution au problème ou quand l’algorithme aura généré un nombre maximum de populations. Dans la même figure, nous montrons le processus de transformation standard. La transformation 1 prend une pré-solution sélectionnée et change aléatoirement quelques unes des valeurs des variables. Ce processus est. la « mutation ». La transformation 2 prend deux pré-solutions sélectionnées, et échange des sous-parties des deux chromosomes, comme une recombinaison biologique en choisissant un point de croisement d’une façon aléatoire. Ce processus est dénommé « croisement ». Ensuite, il faut évaluer la nouvelle population. Les algorithmes génétiques se sont révélés efficaces pour un grand ensemble de problèmes [Hol75!. De plus, ils n’étaient pas limités par des’Conditions analytiques sur l’espace de recherche telles que la continuité. Mais, Holland reconnaît que la non-linéarité ou la haute corrélation entre les variables représente un obstacle pour révolution. Pour faire une recherche efficace, il faut trouver un équilibre entre découvrir une nouvelle connaissance et exploiter ce que nous connaissons déjà. Cela peut s’exprimer avec. 2 concepts: