___ ___ ____ ___ __ _______ __ __ ______ | | | | | ; | | | |___ | |___ | | | .------. | | .- ---' , '-----'------'-----'--- ----'------- - -- - - - - ' _|________|__ ¦ | mkd.10 Mendel et ses bytes : aka 'les algorythmes genetiques' ' _ ___ __ ____ : | | '-----.------- .-----.------.-----| |----- - ------- - - - ---- - - - ____| |____ |______| ____| |____ | | | | |___ _ ________ ___|___ ____|_________ _______ | I. Introduction Il existe des problèmes pour lesquels on ne peut pas trouver de solution optimale parcequ'il n'existe pas d'algorithme pour la trouver ou parceque les algos existants sont trop coûteux. Mais comme vous vous en doutez, on ne veut pas lacher l'affaire, il nous FAUT la solution ou le truc qui s'en rapproche le plus. C'est à ça que servent les algorithmes génétiques dont nous allons parler dans cet article... (comment vous aviez deviné ?) si vous n'aimez pas la théorie, que vous avez mal à la tête ou que vous devez nourrir votre lémurien dans 2mn : goto end; On va prendre un exemple de cas qui arrive souvent : on a une "boite noire" (f) à qui on passe une valeur (x) et qui nous retourne une autre valeur en échange (y). Mais on ne connait pas f pour une raison quelconque (vous n'avez pas les sources de f, f est quelque part sur le réseau sur une machine sécurisé, ... [complétez les pointillés comme vous le sentez]). Notre problème c'est qu'on veut trouver la valeur de x qui donne un certain y sans rien savoir sur f... La première solution barbare c'est de passer toutes les valeurs de x possibles à f et éspérer obtenir en retour le y qu'on veut... évidemment cette solution ne marche pas dès que le nombre de x possible est grand ou que f est difficilement calculable. On parlait pas d'algos génétiques par hasard ? I. Bases On va commencer par initialiser quelques solutions possibles aléatoirement. On commence donc avec x1, x2, ..., xN qui sont des x possibles parmi les solutions mais pris totalement au hasard. On demande à f les y qui correspondent à ces x... On se retrouve donc avec f(x1), f(x2), ... f(xN). La deuxième chose essentielle c'est qu'on doit avoir une fonction "g" qui nous donne la qualité d'une solution. Par exemple plus une solution est proche de ce qu'on cherche, plus g(xI) va retourner une petite valeur.C'est ce qu'on appelle la fonction d'évaluation. Si vous ne pouvez pas en trouver une pour votre problème ===> goto end; Cette fonction sert à classer les solutions qu'on a sous la main de la meilleure à la moins bonne. bon ça fait pas mal de blabla tout ça, je vous saoule ? ok. on va prendre un petit exemple concret : on va se prendre un f tout bête pour l'exemple f(x) = 2*x (je vous rappelle que nous on NE CONNAIT PAS f sinon aucun interêt) On veut trouver le x pour lequel f(x) = 100 il nous faut la fonction d'évaluation g(x) qui dit si x est une bonne solution... dans ce cas ci c'est simple une solution est bonne si elle est proche de 100 donc on regarde la distance entre 100 et f(xI) : g(xI) = | 100 - f(xI) | Plus on va se rapprocher de ce qu'on cherche (100), plus g va retourner une petite valeur donc c'est ok. On initialise aléatoirement quelques x : 2, 5, 10, 7, 24, 38 avec notre g, on évalue leur qualité et on les classe : 1. 38 2. 24 3. 10 4. 7 5. 5 6. 2 (ok ok j'avoue mon exemple est débile mais c'est juste pour expliquer hein) Quel interêt ? vous trouvez ça idiot ? bah maintenant on va faire se reproduire nos solutions ! (non je n'écris pas sous l'emprise de substances psychotropes ;o) II. Main Une fois qu'on a le classement de nos solutions de la meilleure à la moins bonne, on va sélectionner les meilleures solutions pour qu'elles deviennent les parents des solutions suivantes... (obscur ? read_next();) D'après ce qu'on vient de dire, on va donc se prendre quelques solutions parmi les meilleures : 38, 24, 10 Ce sont les parents de nos solutions suivantes. On va maintenant voir comment leur faire faire des enfants : Comme le titre de l'article est "les algorithmes génétiques", il va bien falloir les placer quelques part les gènes : read_next(); ! On va considérer les solutions qu'on a sélectionnées comme des chromosomes...dans ce cas ce sont des nombres qui ont une représentation binaire, donc on peut les voir comme : 38 : 0 1 0 0 1 1 0 24 : 0 0 1 1 0 0 0 10 : 0 0 0 1 0 1 0 c'est marrant ça ressemble à un chromosome comme ça non ? si vous avez suivi 2 3 cours de biologie vous vous rappellez peut être de comment se combinent 2 chromosomes... On tire au sort 2 parents : on va dire 38 et 24 on veut un truc qui fasse 1 0 0 1 1 0 + 0 1 1 0 0 0 = deux enfants... bah il suffit de prendre un indice dans le papa : 0 1 0 0 1 1 0 ^ ça nous fait 2 bouts de chromosomes : 1 0 0 et 1 1 0 on fait pareil avec la maman de manière à pouvoir faire des enfants de la même taille que les parents : 0 0 1 1 0 0 0 ^ maintenant il suffit de recombiner 1 morceau du papa avec 1 morceau de la maman * 2 et on obtient 2 enfants : 0 1 0 0 + 0 0 0 = 0 1 0 0 0 0 0 0 0 1 1 + 1 1 0 = 0 0 1 1 1 1 0 on repasse dans la représentation compréhensible (phénotype pour les fans de biologie) : 1 0 0 0 0 0 = 32 0 1 1 1 1 0 = 30 bon c'est pas encore super mais on peut voir que on va vers une amélioration des solutions...On recommence l'opération plusieurs fois jusqu'à ce qu'on ait assez d'enfants. Par contre on a oublié un truc qui se passe dans la nature (cf cours de biologie toujours [héhé comme quoi ya des trucs qui servent là où on l'attend pas]). pendant les reproductions, il arrive que par magie, un élément d'un gène change spontanément... on appelle ça la mutation. dans notre algorithme génétique, on va donc fixer une probabilité qu'un enfant soit victime d'une mutation (yen a sur #mindkind.org qui ont du muter plus d'une fois d'ailleurs... anyway : read_next();) par exemple, on avait fait un enfant 0 1 0 0 0 0 0 on tire un indice au hasard (par exemple 3) => l'enfant mute et devient 0 1 1 0 0 0 0 ! Il faut cependant que la probabilité que ça arrive ne soit pas trop importante, sinon nos reproductions ne vont rien améliorer du tout... souvent on prend p(mutation) = 0.05 ou 0.1 à la rigueur... au dessus c'est que vous habitez tchernobyl et vous aurez des enfants loupés :/ On rajoute tous les enfants qu'on a obtenu avec les parents. on refait un classement et on sélectionne les N meilleurs (ici 6 puisqu'on a commencé avec 6 solutions au début) et on recommence tout ça depuis le début ! On s'arrête quand on a trouvé ce qu'on cherchait... pour certains problèmes très difficiles pour lesquels une solution approchée suffit, on s'arrête au bout d'un temps fixé ou quand la meilleure solution trouvée est assez proche de celle cherchée. III. Résumé Comme tout ça n'est pas très clair un petit pseudo code ne fait pas de mal : population = initialisation_aleatoire(); while(bonne solution pas dans population) { faire un classement de population avec la fonction d'évaluation; parents = meilleurs de population; enfants = résultat de la reproduction des parents; // ne pas oublier // de faire quelques // mutations population_intermediaire = parents + enfants; faire un classement de population_intermediaire avec la fonction d'évaluation; new_population = meilleurs de population_intermediaire; population = new_population; } Il existe pas mal de variantes de cet algorithme de base... notamment au niveau des méthodes de sélection des parents ou de la nouvelle population. On n'est pas obligé de toujours choisir les meilleurs : on peut tirer au sort des chromosomes en fonction de leur place au classement (du genre : 1er a 30% de chances d'être tiré au sort, le 2ème 20%, ...) A vous de voir comment vous pouvez faire varier des paramètres, la façon de sélectionner des individus, leur méthodes de reproductions... IV. Conclusion merci à ceux qui ont lu jusqu'ici... j'éspère que j'ai pas été trop obscur ! Si j'ai attisé votre curiosité c'est déjà ça :o] Pour ceux qui sont pas trop bêtes, vous remarquerez que les algorithmes génétiques sont applicables à pleins de trucs : imaginez que vous cherchez une chaine de caractères (password ou autre), il suffit de remplacer les 0 et les 1 par des caractères et ça revient au même (par contre la fonction d'évaluation "g" peut être plus difficile à trouver) Les algos génétiques ne sont pas magiques non plus... il n'y a aucune assurance de trouver la bonne solution ! votre algo peut tourner 10^32 années sans jamais trouver la solution. mais dans la plupart des cas du style de celui du dessus, avec un poil de chance, il s'arrête vite et donne des résultats pas trop mauvais. si ça vous a plu, faites le savoir et peut être que je coderai un petit truc en C pour le prochain zine qui illustre tout ça de manière pratique. .----------------------------------------------- - - --- - --- | TheTurtle [theturtle at email2me dot net] www.mindkind.org '------ -- ----------- -- - - ---------- - - -- - - -- ----- - - - - -