|
Algorithmes génétiques
Ce type d'algorithme s'inspire de la théorie de l'évolution pour rechercher une ou plusieurs solutions optimales à un problème en faisant intervenir la notion de séléction naturelle. Ils manipulent une population d'individus décrits par un code génétique représentant une solution possible au problème. Les individus sont évalués et ceux offrant les moins bons résultats meurent alors que les autres sont reproduits par croisement de leur code génétique. Les enfants ainsi créés représentent chacun une variante de la solution qui a souri à leurs parents. ce cycle "évaluation - reproduction" est répété jusqu'à obtenir une population d'individus fortement adaptés, c'est à dire dont le code génétique représente une solution optimum au problème.  Génèse En premier lieu, on génère une population d'individus dont le code est établi avec des valeurs aléatoires. Ces individus constituent un ensemble de solutions de départ à évaluer. Selection Cette étape évalue la solution de chaque individu et divise la population en 2 : les plus adaptés et les autres. Ces derniers meurent alors que les meilleures solutions forment une population intermédiaire moitié plus petite que la population initiale. Reproduction Parmi les individus de cette population temporaire, des couples sont formés au hasard, ils produisent chacun 2 enfants par croisement de leur code génétique. Pour croiser deux codes génétiques, on détermine un point de croisement. Le premier enfant recoit les gènes du premier parent jusqu'au point de croisement et ceux du deuxième parent à partir de ce point. Le code du deuxième enfant contient les autres gènes. Mutation Cette étape permet de modifier légèrement les solutions enfants, variantes des solutions parents. Les codes génétiques des enfants mutent donc : un gène choisi au hasard reçoit une valeur aléatoire. On compte sur l'algorithme pour écarter les mauvaises nouvelles solutions et conserver les bonnes. Sans cette mutation, le réservoir génétique de la population n'évolue jamais : les individus ne "trouvent" jamais de nouvelles solutions.  Evolution de la population lors d'un cycle Boucle et fin Les enfants sont ajoutés à la population intermédiaire qui retrouve sa taille initiale. On recommence à partir de l'étape de sélection jusqu'à arriver à la génération voulue. Petite démo Ce script genere une population de 100 individus et effectue une selection sur 20 generations. Chaque individu represente un code couleur, on évalue leur score en fonction de leur nombre de bits communs avec le code solution; la couleur à trouver. Les 50 meilleurs individus croisent leur code genetique pour produire autant d'enfant. Chaque ligne represente les individus de la population pour une generation. Les individus sont des '|' dont la couleur represente le code genetique. Au fil des generations, on voit que de plus en plus d'individus se rapprochent du code couleur à trouver. |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| Code source Vous pouvez télécharger cette archive contenant quelque classes un peu plus élaborées. Vous pourrez adapter l'algo à un problème donné en modifiant le format du code génétique et la fonction de selection. Les fonctions liées au code génétique sont dans la classe Code, la fonction de selection est effectuée dans la classe Monde et la reproduction des individus est décrite dans la classe Population. Dans ces classes, on créé un Monde contenant des Environnements contenant eux-même des Populations d'Individus ayant un Code qui représente une solution possible au probleme. Cette structure, plus complexe que l'exemple décrit dans cette page, permet des selection en fonction de critères multiples : les individus doivent s'adapater à leur population (disons leur culture) ainsi qu'à leur environnement (disons leur climat). En l'etat, la selection est faite en fonction d'un code couleur, comme pour la démo ci-dessus. Cette méthode de recherche de solution peut trouver de nombreuses applications pratiques, par exemple pour determiner le meilleur coup à jouer sur un jeu de stratégie. Je m'en suis servi pour concevoir une I.A. pour jeu de Go : GnOm. |
scripts
dessin
plume
japonais
cinéma
parkour