Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmes génétiques 1 Algorithmes génétiques Algorithmes génétiques Les sys

Algorithmes génétiques 1 Algorithmes génétiques Algorithmes génétiques Les systèmes évolutifs • Problèmes « non classiques » • Algorithmes basés sur les heuristiques • Algorithmes Génétiques (AG) Principe des algorithmes génétiques 2 Principe des algorithmes génétiques • Principes de base Fonctionnement des AG Champs d’application Les systèmes évolutifs Algorithmes évolutionnaires  Il s’agit des algorithmes évolutionnaires comptés parmi les méthodes de l’intelligence computationnelle 3 Les systèmes évolutifs Algorithmes évolutionnaires • sont une famille d'algorithmes dont le principe s'inspire de la théorie de l'évolution pour résoudre des problèmes divers. • L'idée est de faire évoluer un ensemble de solutions à un problème 4 • L'idée est de faire évoluer un ensemble de solutions à un problème donné, dans l'optique de trouver les meilleurs résultats. • Ce sont des algorithmes dits stochastiques, car ils utilisent itérativement des processus aléatoires. Principe de base Algorithmes génétiques  Algorithmes stochastiques itératifs qui opèrent sur des individus codés, à partir d’une population initiale.  Cette population évolue de la génération k à la génération k+1 à l’aide de trois opérateurs. trois opérateurs. Opérateur de sélection Opérateur de croisement Opérateur de mutation 5 Principe de base Algorithmes génétiques  Chaque individu est reproduit en fonction de son adaptation au problème (fitness).  On code les individus de manière à les faire évoluer grâce aux opérateurs.  On effectue: • Des croisements sur les individus destinés à être reproduits. • Des mutations aléatoires.  Génération de nouveaux individus. 6 Principe de base Les AGs utilisent un vocabulaire similaire à celui de la génétique.  Un AG recherche les extrêmes d’une fonction définie sur un espace de données appelé population. • Terminologie et éléments de base données appelé population.  Par analogie avec la génétique, - chaque individu de cette population est un chromosome - chaque caractéristique de l’individu est un gène. 7 Principe de base • Gène et génotype • Crossing over • Terminologie et éléments de base 8 Principe de base • Terminologie et éléments de base • Dans un cas simple : - un gène sera représenté par un bit (0 ou 1). - un chromosome par une chaîne de bits. - un chromosome par une chaîne de bits. • Chaque gène représente une partie élémentaire du problème, il peut être assimilé à une variable et peut prendre des valeurs différentes appelées allèles. 9 Principe de base • Terminologie et éléments de base La position du gène dans le chromosome se nomme locus. On parle également de génotype et de phénotype. Le génotype: représente l’ensemble des valeurs des gènes du chromosome le phénotype: représente la solution réelle après transformation du chromosome. Lors de la génération d’une nouvelle population, des opérateurs génétiques tels que la sélection, le croisement et la mutation sont nécessaires pour la manipulation des chromosomes. 10 Principe de base • Terminologie et éléments de base Le tableau suivante présente une récapitulation de la terminologie naturelle et celle utilisée par les AGs : 11 Principe de base Algorithmes génétiques  Les Algorithmes Évolutionnaires sont inspirés du concept de sélection naturelle élaboré par Charles Darwin.  · Les lois de variation (la théorie de l’hérédité), croisements et mutations, sont empruntées à Mendel et à la génétique moderne: sont empruntées à Mendel et à la génétique moderne: Evolution : résultat d’une altération progressive des êtres vivants au cours des générations Reproduction basée sur le caractère génétique qui subit au cours des générations des recombinaisons et des mutations Mécanisme de sélection naturelle 12 Principe de base • Individus différents • Sélection des mieux adaptés • Hérédité Un individu n’a pas été conçu pour réaliser des actions spécifiques, mais il peut évoluer Il détermine comment évoluer (génétiquement, en adaptant son corps et son esprit) Les individus les plus adaptés tendent à survivre plus longtemps et à se reproduire plus aisément. 13 Principe de base S’adapter c’est évoluer pour être au mieux en adéquation avec son environnement. Simuler cette évolution en 3 phases importantes (Opérateurs d’évolution) : 14 • Sélection (reproduction) • Croisement • Mutation Principe de base · Le vocabulaire est calqué sur celui de l’évolution et de la génétique • Individus (solutions potentielles), • Population, • Gènes (variables), • Chromosomes, 15 • Chromosomes, • Parents, • Croisement, • Mutations, • …. Principe de base Technique basée sur la Théorie de l'évolution de Darwin: A partir des données du problème, on crée (généralement aléatoirement) une "population" de solutions possibles. Les caractéristiques de chaque solution représentent ses gènes. Puis, on évalue chacune des solutions. On élimine une partie infime de 16 Puis, on évalue chacune des solutions. On élimine une partie infime de celles qui se sont montrées inutiles ou désastreuses, et on recombine les gènes des autres afin d'obtenir de nouveaux individus-solutions. Selon la théorie évolutionniste, cette nouvelle génération sera globalement plus adaptée au problème que la précédente. On itère alors le procédé jusqu'à la naissance d'une solution que l'on jugera satisfaisante. Principe de base Les AGs sont des algorithmes d’optimisation stochastique fondés sur les mécanismes de la sélection naturelle et de la génétique. Leur fonctionnement est extrêmement simple. On part avec une population de solutions potentielles (chromosomes) initiales arbitrairement choisies. On évalue leur performance (fitness) relative. Sur la base de ces performance 17 On évalue leur performance (fitness) relative. Sur la base de ces performance on crée une nouvelle population de solutions potentielles en utilisant des opérateurs évolutionnaires simples : - La sélection - Le croisement des parents -La mutation d’un enfant généré. On recommence ce cycle jusqu’à ce que l’on trouve une solution satisfaisante. Principe de base Le point clef est l’apparition, par hasard, de variations individuelles. Cela explique les phénomènes d’évolution et d’adaptation sans avoir recourt ni à une création, ni à une modification directe de l’hérédité recourt ni à une création, ni à une modification directe de l’hérédité par le milieu, ni même à une finalité. 18 Fonctionnement 1. Ingrédients: • Une fonction objectif (fonction fitness / fonction d’adaptation). • Une population initiale (ensemble de solutions / nœuds / 19 • Une population initiale (ensemble de solutions / nœuds / chromosomes). • Une méthode de codage. • Des opérateurs permettant de générer des enfants à partir de la population. • Un critère d’arrêt 2. Algorithme i : initialisation f(X) : évaluation ? : critère d'arrêt Fonctionnement 20 ? : critère d'arrêt Se : sélection Cr : croisement Mu : mutation Re : remplacement X* : optimum Fonctionnement • Génération - Création d’une population aléatoire • Evaluation 2. Algorithme • Evaluation - Comparaison des individus • Sélection - On ne garde que les meilleurs • Croisement/Mutation - On les fait se reproduire / Évoluer • Retour à l’évaluation 21 Fonctionnement 3. Explication de l’algorithme: 1/ Création de la population initiale. Si aucune idée de la solution du problème, génération aléatoire d ’une population. Sinon, création des individus qui représentent les solutions dont on dispose. Principal problème : Choix de la taille de la population : compromis à trouver - Besoin de suffisamment d’hétérogénéité. -Une population trop grande augmente le temps de calcul. 2/ Evaluation de l'adaptation. Mesure des performances de chaque individu par une fonction d'adaptation correspond au profit, à l'utilité de la solution par rapport au problème. 22 Fonctionnement 3. Explication de l’algorithme: 3/ Sélection des parents. - Pour que la génération suivante soit plus performante. - Accouplement des meilleurs individus. (chaque individu aura une chance proportionnelle à son adaptation de devenir parent). 4/ Recombinaison/ Croisement (crossover). - Pour donner naissance à un individu nouveau, prise aléatoire de quelques gênes de chacun des parents. 5/ Mutation. - Modifications aléatoires du génome. - Ne pas muter tous les gènes d'un individu, sinon détermination complète aléatoire, rôle secondaire par rapport à la recombinaison. 23 Fonctionnement 3. Explication de l’algorithme: 6. Sélection des survivants. - Ne garder que les solutions les plus intéressantes, tout en gardant une population assez grande et assez diversifiée. - En général, conservation de la taille de la population d'une génération à l'autre. (autant de "morts" que de "nouveaux-nés") - Parfois, garder uniquement des enfants Cela assure la diversité et l'évolution de la population. - Les enfants sont conservés en fonction de leur adaptation (fitness) déterminée par une fonction d’adaptation donnée F(n). 24 Fonctionnement 3. Explication de l’algorithme: 7. Critères d’arrêt (convergence d’un AG). - Le cycle de génération et de sélection de population est répété jusqu’à ce qu’un critère d’arrêt soit satisfait. Ce critère peut être notamment : - un nombre maximum de générations. - un temps maximal de calcul. - un temps maximal de calcul. - une valeur de fitness minimale/maximale. - ou/et une convergence vers une solution satisfaisante. - Les valeurs de tels paramètres dépendent fortement de la problématique étudiée. Faire tant que (il n'y a pas de solution satisfaisante) et (le temps est inférieur au temps limite) 25 Fonctionnement 4. Codage des solutions On crée des chromosomes (individus) à partir des solutions codées en : • Code binaire : - Le chromosome représente simplement une suite de 0 et de 1. - Le chromosome représente simplement une suite de 0 et uploads/Geographie/ chapitre-3-genetic-algorithm.pdf