Passions d’un développeur indépendant

Un nouveau blog sur Wefrag le blog de DraK.

Algorithme Génétique : Introduction et Exemple #1

Bonjour à tous !

Nous allons voir ensemble brièvement comment les algorithmes génétiques fonctionnent et quelles peuvent être leurs utilisations.
L’objectif de cet article n’est pas de montrer comment coder, développer ou mettre en place un algorithme génétique, il y a des tutoriels pour cela. Notre objectif ici est de vulgariser le principe afin de comprendre les possibilités qu’il offre.

Introduction

L’algorithme génétique est un algorithme qui permet de trouver des solutions à un problème donné. Il est basé en partie sur l’aléatoire et ne trouve que rarement la solution parfaite, mais s’approche plutôt d’une des solutions. Ce qui fait de lui un algorithme de recherche locale.

Le principe est inspiré de la génétique et de la théorie de l’évolution, ce qui lui vaut son nom.

Avantages

  • Il permet de trouver des compromis dans des problèmes complexes
  • Il permet de créer des IA pour contrôler des entités dans un jeu (un robot, une voiture, un monstre, etc…)

Inconvénients

  • Il faut beaucoup de temps pour obtenir un résultat correct dans la plupart des cas, il n’est donc pas fait pour être exécuter en temps réel dans un jeu mais exécuter pendant le développement du jeu (à moins de faire un jeu basé sur l’évolution évidemment)
  • Il ne fait bien souvent que se rapprocher d’une solution sans l’atteindre
  • Il faut passer du temps dans le paramétrage pour trouver le juste milieu entre diversité génétique et performance des ADN, et cela en fonction du type de problème, de la taille des ADN, etc…
  • Il est totalement dépassé par les algorithmes de recherche d’un chemin parmi des nœuds (A*, Dijkstra, etc…)
  • Le procédé étant basé en partie sur l’aléatoire, les résultats et le temps pour y parvenir sont différents à chaque exécution

Principe

L’algorithme génétique gère une population d’individus (le nombre est au choix) qui se renouvèle à chaque génération. Chaque individu a son ADN.

Un ADN est une liste d’informations qui constitue une possible solution que le développeur va tester dans son problème.

La structure d’information, le nombre et le type des informations est au choix du développeur, voici une liste non exhaustive :

  • Chaîne de caractères : “HHGBGGHD”
  • Une liste d’entier entre 1 et 8 : 13556482
  • Une formule mathématique : “(1+x)*2″
  • Une liste de paramètres pour une IA (taux d’agressivité, taux de fuite, etc…)
  • Les paramètres d’un réseau de neurone (article à venir)

Ces informations représentent pour le développeur quelque chose de précis :

On peut imaginer par exemple que la chaîne de caractère “HHGBGGHD” est en fait une série de touches à appuyer à la suite avec H = Haut, B = Bas, G = Gauche, D = Droite dans un jeu où le héros doit esquiver des monstres.

Revenons à notre population, à chaque génération, tous les individus vont voir leurs ADN évaluer par une fonction d’évaluation que le développeur aura créée. A la suite de cette évaluation, l’individu obtiendra un score qui définira combien sa “solution” est bonne dans ce problème. Ce score peut être le temps de survie du héros, ou bien le nombre de monstre qu’il a tué, ou encore la distance parcourue sur un terrain. En gros ce score doit refléter combien le développeur est satisfait de cet ADN.

Une fois l’évaluation terminée, on procède à une sélection des X% meilleurs individus (en fonction du score), et on leur permet de se reproduire entre eux, on supprime tous les anciens individus pour les remplacer par la génération suivante (les enfants).

Pour créer un enfant à partir des 2 parents, on lui donne une partie (la taille est aléatoire) de l’ADN d’un parent, et ce qu’il reste vient de l’autre parent, ça donne un tout nouvel ADN (à moins que les 2 parents aient le même ADN mais là on ferait dans le consanguin xD).

L’enfant donné a ensuite une chance de muter, c’est-à-dire voir une partie de son ADN changer aléatoirement, en général un ou plusieurs gènes. Dans notre cas, un gène serait par exemple un caractère de la chaîne de caractère “HHGBGGHD”.

Exemple de reproduction :

Parent A : “HHHHDDDD”

Parent B : “GGGBBBGG”

Enfant avant mutation : “HHGBBBGG”

Enfant après mutation “HHGBDBGG”

Dans cet exemple, les ADN font tous 8 gènes, mais il est possible de faire reproduire des ADN de tailles différentes.

Une fois la nouvelle génération conçue, on est partis pour un nouveau tour d’évaluation. Ce procédé est répétable à l’infini, on ne s’arrête que lorsque l’on a une solution que l’on juge convenable. Au fil des générations, les ADN devrait se rapprocher de la solution. Si je dis “devrait”, c’est parce qu’il est possible de perdre des bons ADN si le paramétrage n’est pas correct (trop de mutation ou trop de diversité génétique). Le nombre de générations à faire avant d’avoir un résultat satisfaisant dépend du problème initial et de la chance, et ça peut monter à 100, 1.000, 10.000 ou même 100.000 générations !

Notons que les ADN de la 1ère génération sont totalement aléatoires et donc chaotiques (bien qu’il soit possible de reprendre des ADN sauvegardés afin de les améliorer).

Exemple #1 : Dessiner une image avec des ellipses

On prend une image qui va nous servir de modèle pour dessiner (je me suis limité à 400px de large).

En définissant l’ADN comme étant 5000 gènes, chacun contient des informations pour dessiner une ellipse (position horizontale, position verticale, largeur, hauteur, couleur).

Les positions horizontales et verticales sont comprises entre 0 et la taille de l’image. La largeur et la hauteur de l’ellipse sont comprises entre 3 et 16 pixels. Les couleurs possibles sont limitées à la palette de couleur de l’image modèle. Sans ces conditions préalables, il serait trop compliqué d’obtenir un résultat correct.

Exemple d’un ADN : (30, 55, 12, 7, #FF0000), (201, 138, 9, 16, #AB3765), … 5000 fois

Notre fonction d’évaluation crée une image toute noire aux dimensions du modèle, puis dessine les 5000 ellipses de l’ADN. La fonction compare alors chaque pixel de l’image résultante avec le pixel correspondant sur l’image modèle et donne un pourcentage global de similarité entre les 2 images. Ce pourcentage sera alors le score de l’individu.

Lors du procédé, j’ai généré une capture d’écran du meilleur individu toutes les 10 générations, et j’ai laissé tourner ça 2 heures (avec 1 processeur à 100%) pour obtenir finalement cette vidéo :

YouTube Preview Image

Il est mimi le gros chat ! Bon, l’image restera toujours grossière avec seulement 5000 ellipses quand on sait que l’image originale est composée de 131600 pixels et de 29303 couleurs différentes ! Mais la ressemblance est flagrante quand on s’éloigne de l’écran, non ?

Ce qui est pratique, c’est que ça fonctionne pour toutes les images, il suffit juste de remplacer l’image modèle pour obtenir une nouvelle vidéo :

YouTube Preview Image

Ha ! La flemme légendaire des développeurs…

Le prochain exemple sera un peu plus intéressant qu’une bouillie de pixels dégueulasse…

Tags: , , ,

7 commentaires pour “Algorithme Génétique : Introduction et Exemple #1”

  1. divide dit :

    Intéressant, mais ça reste une intro, curieux de voir la suite du développement!

  2. drloser dit :

    Intéressant.

  3. SanD dit :

    Intéressant, j’attends la suite.

  4. DrKant dit :

    Pour complement, ce type d’algo genetique est lie aux filtres particulaires (particle filter). Les algo genetiques sont plutot utilises pour rechercher un optimum global plutot que local, contrairement aux methodes de type Newton (comme utilisee par Carmack https://en.wikipedia.org/wiki/Fast_inverse_square_root). On les utilise surtout quand la fonction a minimiser est fortement non-lineaire, non-convexe et que l’espace des solutions admissibles a une geometrie degeulasse. Les methodes de types “colonies de fourmis” sont aussi tres simples a coder et permettent de simplement jouer sur le type de comportement que tu donnes aux populations, c’est a dire exploratif (tendance a chercher un optimum loin des optima connus) ou bien exploitant (tendance a chercher un optimum parmis les meilleurs individus).

    Exemple:
    Exploratif pour les algo a bases de mutation, ca correspond a croiser des individus tres differents tandis que exploitant ca consiste a ne garder que les meilleurs individus a l’interieur d’un meme groupe.

    Exploratif pour les algo a bases de fourmis, ca correspond a forcer les individus a aller voir des terres inconnues
    tandis que exploitant ca consiste a se concentrer sur seulement quelques filons.

    En general, on cherche a etre exploratif au debut afin de trouver un maximum de pistes, et au fur et a mesure on force les populations a exploiter les solutions precedemment trouver plutot que d’aller en chercher d’autres.

  5. skaven dit :

    Le principe est simple, mais c’est souvent la fonction de score qui est dure à déterminer.
    Par ex, pour un projet, je voulais construire une composition de boites pour avoir un beau panorama. Genre sky line. L’itération est simple: J’ai mon lot de boites et un point de vue et je change la position/orientation de quelques boites.
    Je n’ai pas trouvé de fonction pour savoir si ce que je voyais était plus beau qu’une autre itération.

  6. Beber dit :

    Une fois l’évaluation terminée, on procède à une sélection des X% meilleurs individus

    Il me semble que la sélection est plus complexe que ça. J’avais utilisé la “roulette wheel selection” (https://en.wikipedia.org/wiki/Fitness_proportionate_selection, une sorte de roulette de casino où la tailles des cases est proportionnelle au fitness des individus) qui était bien plus adaptée que la simple sélection des meilleurs (qui peut s’apparenter à une forme d’eugénisme et qui, de mémoire, me sortait plutôt des maximums locaux que globaux). J’avais utilisé ce genre d’algorithme pour faire du “min-maxing” dans un MMO, ça marchait du tonnerre.

    Et un exemple vaguement interactif avec des voitures dont la forme évolue pour aller le plus loin possible dans le parcours : http://rednuht.org/genetic_cars_2/

  7. DraK dit :

    @divide, @drloser, @SanD
    Merci pour votre intérêt, le prochain article devrait sortir Vendredi et concernera le jeu vidéo ;)

    @DrKant
    Merci pour ces informations complémentaires, je ne connaissais pas les filtres particulaires.
    Pour la différence entre exploratif et exploitant, je fais les paramètres à la main et les change en cours pour finalement exploiter les meilleurs comme tu le dis (ou alors revenir en exploration si je suis allé trop vite). Il faudrait que je code une stratégie qui fait ça toute seule, mais bon, la stratégie dépend aussi du problème : pour mon 1er exemple avec les images, ça ne sert à rien d’explorer car le problème a une seule dimension (si le score est plus élevé, c’est forcément plus proche du but, ce qui n’est pas forcément le cas dans des plus grandes géométries), il vaut mieux exploiter pour améliorer à chaque génération.
    D’ailleurs pour les mutations, les tutoriels disent de faire un % de chance par gène, ce que j’ai fait, mais je me rends compte que je dois modifier ce pourcentage en fonction du nombre de gène que j’ai. J’ai l’impression que les résultats sont meilleurs quand un seul gène mute à la fois, trop de mutation casse tout. Mais d’un coté, il y a desfois des plafonds à depasser qui nécessitent des gros changements. Il faut vraiment que je code une stratégie :p

    @skaven
    Effectivement, pour les critères de beauté, faudrait faire soi-même le juge pour chaque itération, mais c’est peut être pas une bonne idée ! xD
    Pour ce cas (ville donc architecture avec une logique), il vaut mieux passer par une génération procédurale adaptée, je crois que c’est ce que t’as fait en voyant les anciens articles de ton blog :)

    @Beber
    Oui, tu as raison, il vaut mieux mettre une pondération sur les individus en fonction du score.
    Je ne l’ai pas préciser dans mon article mais c’est ce que je fais, je garde X% meilleurs de la population, et ensuite je fais la pondération avec les restants pour tirer au sort les ADN pour la reproduction. C’est donc différent car je garde les meilleurs sans aléatoire, je n’utilise qu’ensuite la pondération. J’imagine qu’il doit y avoir une différence dans les résultats, il faudrait que je teste.
    Ha les genetic cars ^^. Je les avais vu dans la vidéo de Pause Process : https://www.youtube.com/watch?v=FOv1mN7D9TA

Laisser un commentaire

Vous devez être connecté avec votre compte Wefrag pour publier un commentaire.