Cours 7 - Algorithmes Génétiques (PDF) 2024-2025

Les algorithmes génétiques Survol ▪ Les algorithmes génétiques sont des algorithmes d'exploration fondés sur les mécanismes de la sélection naturelle et de la génétique. ▪ Ils sont basés sur les principes de survie de structures les mieux adaptées et les échanges d'information....

Les algorithmes génétiques Survol ▪ Les algorithmes génétiques sont des algorithmes d'exploration fondés sur les mécanismes de la sélection naturelle et de la génétique. ▪ Ils sont basés sur les principes de survie de structures les mieux adaptées et les échanges d'information. ▪ À chaque génération, un nouvel ensemble de créatures artificielles (codées sous forme de chaînes de caractères) est construit à partir des meilleurs éléments de la génération précédente. ▪ Bien que reposant fortement sur le hasard (et donc sur un générateur de nombres aléatoires) ces algorithmes ne sont pas purement aléatoires. 2 Un peu de génétique ▪ L'évolution dans la nature survient quand : ❑ des entités ont la capacité de se reproduire, ❑ qu'il existe une population de ces entités, ❑ qu'il existe une variété (diversité) à travers ces entités, ❑ que la survie des entités dépend des différences entre elles. ▪ Toute entité vivante possède un génotype et un phénotype. 3 Le génotype ▪ Le génotype est constitué de gènes situés sur des chromosomes stockés dans le noyau des cellules sous la forme d'une longue chaîne d'acide désoxyribonucléique (ADN). ▪ Dans la nature, l'ADN est un polymère constitué par l'enchaînement de quatre molécules, les nucléotides adénine (A), cytosine (C), guanine (G) et la thymine (T). ⇒ On peut donc décrire l'ADN par des chaînes de quatre caractères ACGT. ⇒ L'ADN constitue l'ensemble des chromosomes, ou le génome d'un individu: 4 Le phénotype ▪ Le phénotype est l'ensemble des protéines et des enzymes qui peuvent être fabriqués à partir de l'ADN. ▪ En fait, l'ADN est copiée par un messager (ARN) qui au niveau du ribosome, se traduit en chaînes d'acides aminés formant les protéines et les enzymes. ▪ En général, on compte une protéine (un enzyme) par gène. ▪ Ce sont les protéines et les enzymes qui dictent la structure et le comportement des cellules qui permettent à un individu de : ⇒ Réaliser des tâches dans son environnement, ⇒ survivre; ⇒ Reproduire à des taux différents. 5 La reproduction ▪ La reproduction se traduit par la transmission du génome aux individus de la progéniture ce qui permet de préserver les gènes menant à des performances supérieures. ▪ Occasionnellement, un processus naturel, la mutation génétique, introduit une variation dans les chromosomes. 6 Principes de survie et reproduction décrit par Charles Darwin «On the Origin of Species By Means of Natural Selection » en 1859 ▪ Les individus les mieux adaptés, c'est-à-dire capables de mieux effectuer les tâches nécessaires à leur survie, se reproduisent à des taux les plus élevés, alors que les individus les moins adaptés se reproduisent à des taux plus faibles. ⇒ Une population ayant une grande variété va, de génération en génération, contenir des individus dont le génotype se traduit par une meilleure adaptation, et ceci à cause de la contrainte de la sélection naturelle. 7 Introduction ▪ Les algorithmes génétiques sont des algorithmes d'optimisation s'appuyant sur des techniques dérivées de la génétique et des mécanismes d'évolution de la nature : croisements, mutations, sélections, etc... Ils appartiennent à la classe des algorithmes évolutionnaires.. 8 Historique ▪ 1859 ❑ Charles Darwin publie son livre intitulé L'origine des espèces au moyen de la sélection naturelle ou la lutte pour l'existence dans la nature. ❑ Dans ce livre, Darwin rejette l'existence «les systèmes naturels figés», déjà adaptés pour toujours à toutes les conditions extérieures, et expose sa théorie de l'évolution des espèces : sous l'influence des contraintes extérieurs, les êtres vivants se sont graduellement adaptés à leur milieu naturel au travers de processus de reproductions. 9 Historique ▪ 20ième siècle ❑ Mise en évidence de l'existence de mutations génétiques. Les problèmes de traitement de l'information sont résolus de manières figés : lors de sa phase de conception, le système reçoit toutes les caractéristiques nécessaires pour les conditions d'exploitations connues au moment de sa conception ce qui empêche une adaptation à des conditions d'environnement inconnues, variables ou évolutives. ⇒ Les chercheurs en informatique étudient donc des méthodes pour permettre aux systèmes d'évoluer spontanément en fonction de nouvelles conditions. 10 Historique ▪ 1966 ❑ Programmation évolutionnaire L. J. Fogel. ▪ 1973 ❑ Stratégie d'évolution I. Rechenberg. ▪ 1975 ❑ Dans les années 1960, John Holland étudient les systèmes évolutifs et, en 1975, il introduit le premier modèle formel des algorithmes génétiques (the canonical genetic algorithm AGC) dans son livre Adaptation in Natural and Artificial Systems. ⇒ Ce modèle servira de base aux recherches ultérieures. ▪ 1989 ❑ David Goldberg publie un ouvrage de vulgarisation des algorithmes génétiques. ▪ Années 1990 11 ❑ Programmation d'une panoplie d'algorithmes génétiques. Algorithmes génétiques ▪ Les AG sont des algorithmes inspirés des mécanismes de la sélection naturelle et de la génétique. ⇒ Ils utilisent à la fois les principes de la survie des individus les mieux adaptées et ceux de la propagation du patrimoine génétique. ▪ De façon très intuitive, on identifie le problème à un environnement donné et les solutions à des individus évoluant dans cet environnement. ❑ A chaque génération, on ne retient que les individus les mieux adaptés à cet environnement. ❑ Au bout d'un certain nombre de générations, les individus restants sont particulièrement adaptés à l'environnement donné. ⇒ On obtient donc des solutions très proches de la solution idéale du problème. 12 Vocabulaire ▪ Population ❑ Les algorithmes génétiques ne travaillent pas sur un individu, sur une donnée, mais au contraire sur une population de chaînes afin d'effectuer des opérations, des recherches sur un domaine de possibilités plus important. C'est une des grandes forces des AGs. Une population se compose de chaînes ou chromosomes ▪ Chromosome ou individu : ❑ Les chaînes des systèmes génétiques artificiels sont analogues aux chromosomes des systèmesbiologiques. Ils portent les informations génétiques d'un individu. Ainsi, un individu se compose de gènes. ▪ Gène : ❑ Les chromosomes se décomposent en gènes qui peuvent prendre des valeurs différentes que l'on appelle allèles. La position d'un gène dans un chromosome est identifiée par son locus. Un gène est une caractéristique génétique d’un individu. ❑ Dans les AGs, les gènes ont des valeurs appartenant à un alphabet qui dépend du problème à résoudre. On peut ainsi avoir des allèles binaires, décimaux, ou encore hexadécimaux. On peut imaginer d'autres sortes de codage. ▪ Génération : ❑ Une génération est une population à un instant t. Les AGs faisant évoluer les populations, on crée une nouvelle génération d'individus plus adaptés. Cette évolution13est effectuée par les opérateurs de reproduction, de croisement et de mutation. Analogie avec la nature Nature Algorithme génétique Chromosome Chaîne Gène Trait, caractéristique Allèle Valeur de la caractéristique Locus Position dans la chaîne Génotype Structure Phénotype Ensemble de paramètres, Une structure décodée 14 Fonctionnement simplifié ▪ Les mécanismes mis en jeu sont très simples : ❑ On dispose d'une population de chaînes de caractères sur un alphabet que nous supposerons binaire. ❑ À chaque individu est associé un score (fitness), on en profite pour calculer la somme de ces scores ainsi que les valeurs maximale, minimale et moyenne. ❑ Trois opérateurs vont être utilisés : Un opérateur de sélection (select) dont le rôle est de choisir les individus les plus adaptés (ceux possédant un score élevé), Un opérateur de croisement (cross-over ou hybridation), Un opérateur de mutation (mutation). 15 Fonctionnement simplifié ▪ L'algorithme génétique peut s'exprimer sous la forme suivante : T:= 0 P:= initPopulation Loop Evaluate(P,t) Exit when critere d'arrêt Q:= select(P,t) R:= cross-over(Q) P:= mutation(R) t:= t+1 EndLoop 16 Vocabulaire ▪ Avant de pouvoir utiliser un AG, il nous faut définir : ❑ un codage adapté au problème (les chromosomes), ❑ une fonction (fitness) qui va caractériser 'adéquation de la solution (représentée par son chromosome) au problème. 17 Chromosomes ▪ On suppose dans cette approche qu'une solution du problème peut être représentée par un ensemble de paramètres, ces paramètres sont regroupés sous la forme d'une chaîne de caractères. ❑ J. Holland a le premier montré pourquoi une représentation sous forme binaire était efficace (il existe cependant d'autres approches : décimale, hexadécimale, alphanumérique…). ❑ Rappel : En génétique, un ensemble de paramètres représentés par un chromosome particulier est appelé son génotype, le phénotype est quant à lui une instance particulière d'un génotype. La fonction d'évaluation dépend du phénotype. 18 Fitness ou fonction d'évaluation ▪ Cette fonction est déterminée en fonction du problème à résoudre et du codage choisi pour les chromosomes. À un chromosome particulier, elle attribue une valeur numérique, qui est supposée proportionnelle à l'intérêt de l'individu en tant que solution. ▪ L'évaluation d'un individu ne dépendant pas de celle des autres individus, le résultat fournit par la fonction d'évaluation va permettre de sélectionner ou de refuser un individu pour ne garder que les individus ayant le meilleur coût en fonction de la population courante : c'est le rôle de la fonction fitness. ▪ Cette méthode permet de s'assurer que les individus performants seront conservés, alors que les individus peu adaptés seront progressivement éliminés de la population. 19 Sélection ▪ Pour cette phase, nous supposons connu les individus de la population au temps t, la fonction d'évaluation. ▪ Il va falloir trouver une manière de choisir les individus répondant le mieux à notre problème. ⇒ Il s'agit donc de privilégier les individus ayant un score au- dessus de la moyenne, et de pénaliser ceux en dessous de cette moyenne. ⇒ Plusieurs approches sont possibles ! 20 21 22 23 24 25 26 27 28 29 30 31 32 33 Fonctionnement des AG 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48