Algorithmes Génétiques (Chapitre 4) - Cours PDF

1  Depuis le début de la vie l'être humain cherche la perfection dans sont travail, pour ce la les scientifiques invente les méthodes d’optimisation pour obtenir les bons résultats dans tout les domaines. Ces méthodes en pour objectif de donner les optimums parmi l’ens...

1  Depuis le début de la vie l'être humain cherche la perfection dans sont travail, pour ce la les scientifiques invente les méthodes d’optimisation pour obtenir les bons résultats dans tout les domaines. Ces méthodes en pour objectif de donner les optimums parmi l’ensemble de solution possible.  Les algorithmes génétiques font parti de ces méthodes. 2  Les algorithmes génétiques (AG) sont des méthodes utilisées dans les problèmes d’optimisation. Les AG tirent leur nom de l’évolution biologique des êtres vivants dans le monde réel  Les algorithmes génétiques fournissent des solutions aux problèmes n'ayant pas de solutions calculables en temps raisonnable de façon analytique ou algorithmique. Selon cette méthode, des milliers de solutions (génotypes) plus ou moins bonnes sont crées au hasard puis sont soumises à un procédé d'évaluation de la pertinence de la solution mimant l'évolution des espèces : les plus "adaptés", c'est-à-dire les solutions au problème qui sont les plus optimales. Les algorithmes génétiques sont basés sur trois éléments principaux : la sélection, le croisement et la mutation. Dans la littérature on parle alors d’opérateurs de reproduction. 3  Les AG cherchent une représentation codée dans l’espace des solutions et non pas directement dans le domaine original.  Les AG utilisent un espace de recherche plus vaste, limité par la taille de la population.  Les AG utilisent des règles de transition probabiliste et non déterministes (pseudo aléatoires).  Les AG n’utilisent que les valeurs de la fonction à optimiser, pas sa dérivée ou une autre connaissance auxiliaire. 4 5  1860 >Charles Darwin et l’origine des espèces.  19 ème siècle > Mise en évidence de l'existence. de mutations génétiques.  1966 >Programmation évolutionnaire (Fogel).  1975 >1er modèle formel de AG (J.Holland).  Années 90 >Création de GAlib. Librairie en C++contenant des outils pour les problèmes d’optimisation à base d’AG. 6  a- INITIALISATION : Générer une population initiale Po de N individus.  b- ÉVALUATION : Évaluer la "force" de tout individu de la population.  c- SÉLECTION : Sélectionner N/2 couples d'individus dans la population.  d- CROISEMENT : tout couple d'individus est - avec la probabilité pc remplacé par un nouveau couple d'individus obtenu en lui appliquant un opérateur génétique de croisement,  e- MUTATION :tout individu - avec la probabilité pm subit une mutation, f- ARRÊT : on reprend en b- jusqu'à avoir effectué un nombre donné d'itérations (variantes possible : autre condition d'arrêt, voir plus loin).  g- RESULTAT : Un des chromosomes qui a la meilleure force. 7 Organigramme d’un Population de Base algorithme génétique. Evaluation Sélection Non Terminé Croisement et ? Mutation Oui => Résultat atteint 8 L’idée fondamentale est la suivante : le pool génétique d’une population donnée contient potentiellement la solution, ou plutôt une meilleure solution, à un problème adaptatif donné. Cette solution n’est pas exprimée car la combinaison génétique sur laquelle elle repose est dispersée chez plusieurs individus. Ce n’est que par l’association de ces combinaisons génétiques au cours des croisements entre individus que la solution pourra s’exprimer. Les individus générés aléatoirement représentent donc chacun un chromosome, chacun composé de gènes codés en binaire. Les croisements entre chromosomes permettent d’échanger les gènes et donc de créer des individus nouveaux. Ces croisements se font de manière aléatoire, mais de façon à permettre la convergence vers une solution optimale. 9  Cette étape consiste à générer une population constituée de « n » individus, chaque Individu représente une ou une partie de la solution. La représentation de chaque individu suit un codage particulier, le plus communément utilisé est le codage binaire. Les individus sont aussi appelés chromosomes et leur représentation est un ensemble de gènes. Représentation génétique 10 Les éléments d'une population sont appelés des individus ou des chromosomes ou des génotypes Représentation génétique Le processus de l’optimisation par AG commence par choisir aléatoirement dans l’espace de recherche un nombre fini d’individus qui vont constituer la population initiale. 11 a- Le codage Le codage des variables est une étape importante dans l'optimisation des algorithmes génétiques. A chaque paramètre, on doit faire correspondre à un gène. 1/Le codage binaire: Le gène est codé par un caractère binaire, 0 ou 1. C’est le plus courant. 2/Le codage réel: cela peut-être utile notamment dans le cas où l'on recherche le maximum d'une fonction réelle. 3/Codage Gray: En codage binaire deux éléments voisin (en distance de Hamming) ne codent pas toujours deux solutions proche. En codage gray, on évite cet inconvénient. La distance de Hamming entre deux éléments n et n + 1 (voisins dans l’espace de recherche) est 1. Un opérateur d'évaluation, qui mesure l'adaptation des individus aux conditions imposées, et qui dépend donc du problème à traiter; normalement, cette évaluation est faite à l'aide d'une fonction d'adaptation (fitness) qui mesure la qualité de l'individu comme solution au problème; oFonction de fitness (évaluation) : Fonction qui détermine la qualité d’un individu notée f Pour n individus : avec i de 1 à n. F = ∑ f(xi) On appelle force ou fitness une valeur calculée associée à chaque chromosome. 13  La sélection est chargée de définir quels seront les individus de population P qui vont être dupliqués dans la nouvelle population P' et vont servir de parents (application de l'opérateur de croisement).. En règle générale, la probabilité de survie d’un individu sera directement reliée à son efficacité relative au sein de la population.  Il y’ a plusieurs méthodes de sélection, citons quelques- unes :  La sélection par roulette,  La sélection universelle stochastique (sélection par rang),  La sélection par tournois,  La sélection Elitiste. 14  C’est la sélection naturelle la plus employée pour l’AG binaire. Chaque chromosome occupe un secteur de roulette dont l’angle est proportionnel à son indice de qualité. Un chromosome est considéré comme bon aura un indice de qualité élevé, un large secteur de roulette et alors il aura plus de chance d’être sélectionné.  chaque individu a une chance d'être sélectionné proportionnelle à sa performance. 15 Cette méthode de sélection est divisée en deux étapes. Tout d’abord, il faut ranger les individus par ordre croissant(ou décroissant) de performance. Ensuite, une procédure de sélection permet d’attribuer une probabilité de sélection en fonction du rang, Pour désigner quels individus seront choisis, cette méthode utilise 𝑵sel pointeur simultanément, où Nsel correspond au nombre de sélection requise. Ces pointeurs se positionnent aléatoirement dans l’intervalle C/ La méthode par tournoi :  Choisir aléatoirement deux individus et on compare leur fonction d’adaptation (combattre) et on accepte la plus adapte pour accéder à la génération intermédiaire, et on répète cette opération jusqu'à remplir la génération intermédiaire (N/2 composants). Les individus qui gagnent à chaque fois on peut les copier plusieurs fois ce qui favorisera la continuité de leurs gènes.  Elle consiste à copier un ou plusieurs des meilleurs chromosomes dans la nouvelle génération. Ensuite, on génère le reste de la population selon l'algorithme de reproduction usuel.  Cette méthode améliore considérablement les algorithmes génétiques, car elle permet de ne pas perdre les meilleures solutions. 17  à partir de deux chromosomes le croisement produit deux nouveaux chromosomes incorporant chacun du matériel génétique pris dans le patrimoine initial.  Il y a plusieurs méthodes de sélection, citons quelques-unes : Les deux chaînes initiales vont être divisées en deux. La première partie de la première chaîne sera associée à la seconde partie de la seconde chaîne et inversement, deux nouveaux individus sont ainsi obtenus résultant d’un croisement entre les deux chaînes initiales. 18 Le principe est assez proche de croisement simple point, à cette différence qu’il y a deux points de séparation des chaînes, la chaîne initiale est divisée en 3 parties et la combinaison de ces 3parties permet d’obtenir deux nouvelles chaîne 4.3/Les croisements uniformes : Cet opérateur combine deux chromosomes selon une chaîne binaire aléatoire. A chaque position, les bits correspondants des parents sont échangés si la chaîne aléatoire contient un « l » à cette position. Si le bit aléatoire est « 0 », il n’y a pas d’échange. 19 20 opérateur d'importance secondaire, mais qui permet d'éviter une convergence prématurée vers un maximum local, en maintenant une diversité de solution. Pour l'appliquer, choisir au hasard un bit du chromosome et modifier sa valeur. Les probabilités de l'ordre de 0,01 à 0,03 sont généralement choisies. 21  Après ces diverses opérations génétiques, un nouvel ensemble de variables est obtenu. A ces nouveaux individus, la fonction d’adaptation F est appliquée pour déterminer le maximum. L’AG travaille par générations successives jusqu’à ce qu’un critère d’arrêt soit vérifié. Ce critère d’arrêt peut être de nature diverse :  la nième génération est atteinte ;  le meilleur élément de la dernière génération a atteint un seuil de qualité fixé au départ ;  aucune évolution du meilleur individu n’est perceptible après un nombre donné de générations. 22  en robotique: où l'on s'intéresse aux MOBOTS (MObile roBOTS) qui doivent pouvoir se mouvoir et agir dans des environnements inconnus, variables (programmation génétique, systèmes de classeurs) ;  en physique et en ingénierie : en tant que méthode d'optimisation pour les problèmes réels complexes (pour l'optimisation de structures par exemple) ;  en économie : pour la modélisation de comportements d'agents par exemple; en traitement d'images, du signal, pour détecter des formes caractéristiques, problème que l'on peut soit comprendre comme une optimisation, soit comme une application de règles de décision (SC);  en théorie des graphes et théorie des jeux : le problème du voyageur de commerce, notamment a beaucoup intéressé les chercheurs. 23  Nécessite beaucoup de temps de calcul.  Ils sont le plus souvent difficiles à mettre en œuvre.  Impossible d'être assuré que la solution trouvée est la meilleure.  Problème de convergence vers un optimum local, si celui si est le plus majoritaire.