Passions d’un développeur indépendant

Un nouveau blog sur Wefrag le blog de DraK.

Algorithme Génétique : Exemple #2 : Voiture 2D et réseau de neurones

Bonjour à tous,

Si vous n’avez pas vu le 1er article, vous risquez de ne pas tout saisir.

Aujourd’hui, nous allons voir une application des algorithmes génétiques qui permet d’obtenir une IA de voiture sur un circuit en 2D. Pour ce faire, nous allons intégrer un réseau de neurones à notre algorithme.

Introduction baclée très rapide aux réseaux de neurones

Neurone

Un neurone a plusieurs entrées (autant que voulu) et une seule sortie. Les valeurs des entrées passent dans une fonction mathématique et le résultat donne la valeur de sortie du neurone. Cette fonction est paramétrable pour chaque neurone.

Généralement, cette fonction est une somme des entrées E pondérée par des poids P et à laquelle on soustrait un seuil S. Le résultat étant borné entre 0 et 1 par une fonction F.

Ce qui nous donne en formule : pour n entrées : F(E1 * P1 + … + En * Pn - S)

Nous choisissons d’utiliser cette fonction, les paramètres de chaque neurone seront donc tous les poids P ainsi que le seuil S.

Fonctionnement d'un neurone

Réseau de neurones

La version la plus simple consiste à faire des couches de neurones, en sachant que chaque couche reçoit en entrée de ses neurones les sorties des neurones de la couche précédente.

De plus, les neurones de la 1ère couche vont recevoir en entrée les informations concernant notre problème. Les neurones de la dernière couche nous donneront le résultat en sortie.

Fonctionnement d'un réseau de neurones

Exemple #2 : Voiture de course 2D

Voiture et neurones

La voiture possède 4 capteurs de route positionnés sur les roues permettant au programme d’éliminer la voiture si 2 de ses roues sont en dehors du circuit. Elle possède également 8 capteurs lasers qui donnent la distance avant la sortie de chaussée. Pour contrôler la voiture, nous disposons de 2 commandes : le moteur et le volant.

Capteurs de la voiture

Du coup, nous allons utiliser une seule couche de 2 neurones, un neurone pour contrôler le moteur (accélérer, freiner, voire marche arrière) et un autre pour contrôler le volant.

Chacun de nos 2 neurones va recevoir 9 valeurs en entrée : la vitesse actuelle de la voiture, car il y a de l’inertie dans la commande du moteur (accélération), et les 8 capteurs lasers.

Et là, vous vous posez une question : où est passé l’algorithme génétique ?

Algorithme génétique

L’ADN de l’algorithme génétique va correspondre dans notre cas au paramétrage du réseau de neurones.

L’ADN de chaque voiture sera donc une liste de 20 nombres réels ((9 poids + 1 seuil) * 2 neurones).

Nous allons ensuite voir la fonction d’évaluation !

Ce sera un championnat composé de 4 circuits différents. Chaque circuit est complété en faisant un seul tour.

Si la voiture sort du circuit (2 roues dehors), nous lui donnerons un nombre de points équivalant au pourcentage du circuit complété (exemple : 50 points pour 50% du circuit). Si la voiture boucle le circuit, nous lui donnerons 200 points + un bonus en fonction du temps (exemple : 100 points pour 30 secondes, 300 points pour 10 secondes, etc…). Pour ne pas attendre indéfiniment, nous imposons un temps maximum pour chaque circuit. Toutes les voitures encore sur le circuit à la fin du temps imparti seront considérées comme sortant de la piste.

Pour évaluer les individus à chaque génération, les 4 circuits se succéderont, le score d’une voiture sera la somme de ses scores sur les 4 circuits.

Les principes de l’algorithme génétique sont toujours présents : l’évaluation, la sélection, la reproduction et la mutation seront utilisées.

Le résultat est une IA qui apprend à conduire la voiture grâce aux capteurs. L’IA est encouragée à boucler le circuit rapidement, mais la sortie de route reste très punitive (elle passe de 300/400 points à moins de 100…). L’IA n’apprend pas le circuit, elle n’a d’ailleurs aucune mémoire de suite de virage ou quoi que ce soit. Elle apprend simplement à négocier les virages. Ou plutôt, elle apprend à négocier les combinaisons de valeurs que ses capteurs lui donnent.

Une fois que l’on a obtenu une IA qui gère bien les 4 circuits, nous arrêtons l’algorithme et nous sauvegardons l’ADN de notre champion pour pouvoir l’utiliser plus tard.

Mais nous n’en avons pas fini avec elle, nous allons lui soumettre un test particulier… Notre IA va devoir compléter un 5ème circuit inconnu et du 1er coup ! Plus besoin d’algorithme génétique, plus d’évolution possible ! Il nous suffit de charger notre ADN dans le réseau de neurones et de poser la voiture sur le nouveau circuit.

Va-t-elle réussir le test ?

Résultat

Vidéo de l’apprentissage au fil des générations + Bonus test sur le 5ème circuit :

YouTube Preview Image

Et voilà ! Nous venons de prouver qu’il est possible de conduire une voiture avec seulement 2 neurones :D

Nous avons obtenu une IA qui est capable de finir des circuits simples avec des virages assez serrés, mais elle sera surement perdue si elle rencontre une situation jamais vue (croisement de route, virage encore plus serré, route plus étroite, grande étendue, etc…).

Il est donc possible de créer une IA pour son propre jeu relativement facilement. Il suffit de créer quelques capteurs d’environnement (position de l’ennemi le plus proche, distance avant le prochain mur en face, etc…). De plus, si vous codez l’algorithme génétique et le réseau de neurones de manière générique, vous pouvez l’utiliser facilement partout.

Bonne fin de semaine à vous :)

Tags: , , , , , ,

5 commentaires pour “Algorithme Génétique : Exemple #2 : Voiture 2D et réseau de neurones”

  1. divide dit :

    Bravo, c’était très clair, et la vidéo est fascinante. Je suis vraiment très étonné que seul 2 neurones arrivent à ce niveau d’analyse et d’anticipation !
    Est-ce qu’il y a un nombre de couches et de neurones par couche optimum en fonction de chaque problème, ou est-ce que plus de couches et plus de neurones par couche donne toujours un meilleur résultat (plus de subtilité)?
    J’imagine que plus le réseau est complexe plus il faut d’iterations pour voir des avancées significatives ?
    A ta connaissance, puisque tu as choisi cet exemple, est-ce que certaines voitures autonomes utilisent ce genre de principe (au moins partiellement, et dans des versions plus élaborées j’entend).

  2. skaven dit :

    Top! On pourrait avoir des bouts de code pour voir à quoi ca ressemble?
    Vidéo un peu longue, il faudrait tout mixer en 1min30 max.

  3. khelben dit :

    Original ! J’avais jamais vu un réseau entraîné par algorithme génétique. Ca apporte quelque chose de plus par rapport à l’apprentissage par rétro-propagation ? Ca aurait demandé plusieurs couches de neurones mais pourquoi pas ?
    C’est dommage tu n’expliques pas ici ta méthode de reproduction. As tu testé la méthode par “arène” ? Je la trouve plus efficace quand tu as des clusters de données comme ça.

  4. DraK dit :

    @divide Merci !
    D’après mes tests, il y a des réseaux de neurones qui marchent mieux que d’autres en fonction du problème. Il n’y a aucune limite dans la forme du réseau, les couches, les neurones, ni dans les connexions entre les neurones (tout peut se choisir de manière arbitraire).
    D’un coté, on est plus ou moins obligé d’avoir 2 neurones de sortie pour piloter nos 2 commandes. De plus, il vaut mieux utiliser toutes les informations en entrée (tous les capteurs).
    En fait, chaque couche supplémentaire correspond à une abstraction (il faut déjà avoir en tête une idée de l’abstraction).
    Voici un réseau de neurone que j’aurais pu faire : 2 couches : 3 et 2 neurones, 3 neurones qui vont correspondre à l’abstraction suivante : Le 1er neurone me dit si il y a quelque chose en face, le 2eme si quelque chose à droite, et le 3ème si quelque chose à gauche. Du coup je ne donne pas toutes les informations à tous les neurones en entrée, mais seulement les 2 capteurs de devant pour le 1er neurone, les 3 de droite pour le 2ème neurone et les 3 de gauche pour le 3ème neurone. Du coup, la 2ème couche reçoit des informations qui sont déjà pré-mâchées (je viens de tester sur un seul circuit pour aller plus vite, l’IA vient juste de completer le circuit après 148 générations…).
    Tu as vu juste : plus le réseau est complexe, plus il est long à apprendre (normal, quand un neurone de la 1ère couche change de paramétrage, les neurones qui sont derrières lui vont devoir changer leur interprétation, il faut donc beaucoup de chance sur les modifications génétiques pour tomber sur un truc cohérent).
    En gros, je pense que le réseau le plus simple est le mieux, mais certains problèmes demandent des abstractions (exemple : la reconnaissance d’image, souvent on regroupe par carrés de pixels ou par formes, donc plusieurs couches).

    Pour les voitures autonomes, j’ai regardé un peu, il a effectivement l’air d’y avoir du réseau de neurones derrière tout ça, mais je ne pense pas qu’ils utilisent un algo génétique pour lui apprendre (trop long et chaotique). De plus, il y a surement pleins d’autres types d’IA combinés pour être sûr de l’interprétation (et ne pas écraser un gosse).

    @skaven Merci !
    Tout mon code est en Java et est très découpé car assez générique. Du coup, je t’ai fait un zip contenant les fichiers concernant l’algorithme génétique, le réseau de neurones et les voitures, j’ai seulement mis le code non instancié. Ca ne peut pas être exécuté comme tel car il manque des fonctions de mon framework, mais les fichiers des 2 concepts peuvent être réutilisés facilement si on remplace les fonctions manquantes. Je t’ai fait un petit fichier d’exemple d’instanciation simplifiée à coup de copier-coller (donc surement avec des erreurs) de mon simulateur de course 2D.
    Fichier zip : http://files.drakou.net/dev/SourceNeuralNetwork.zip

    Pour la vidéo, effectivement, c’est long, la prochaine fois je couperai le milieu ^^

    @khelben
    Je n’ai pas encore codé l’auto-apprentissage des réseaux de neurones sans algorithme génétique, donc j’en ai aucune idée :D
    En regardant les cours dessus, j’ai cru qu’il fallait déjà avoir des “modèles” que le réseau allait copier, mais je me trompe surement. Mais c’est pour ça que j’ai pas encore testé. En fait, ça fait environ 1 mois que j’ai découvert les algorithmes génétiques, et 3 semaines les réseaux de neurones, du coup, je dois encore passer à coté de pas mal de trucs. Mais bon, je suis là sans prétention, je cherche juste le partage de ce que je trouve sympa et utile :p

    Concernant la méthode de reproduction, c’est la même que pour le 1er article, mais je la change en cours de l’exécution. Au début, je suis parti en mode exploration (Tous les ADN peuvent se reproduire, avec une pondération allant de 1 à 2.5 en fonction du score, avec 33% des enfants qui mutent 20% de leurs gènes) pour finir sur un mode exploitant (Seuls les 10% meilleurs peuvent se reproduire, toujours avec pondération, mais 100% des enfants mutent 20% de leur gènes).
    A cela s’ajoute un système de “lignées” que j’ai inventé pour ne pas perdre en qualité d’une génération sur l’autre : Les lignées sont mes meilleurs ADN et se retrouvent dans chaque génération sans mutation. De cette manière, je ne risque pas de perdre mes champions du moment à cause d’un surplus de mutation. Pour qu’un ADN devienne une lignée, il doit avoir un score minimum (exemple : au moins 50% du score du meilleur ADN) et des gènes différents à X% de toutes les autres lignées. Une lignée disparait si son score n’est plus suffisant. Je peux évidemment paramétrer tout ça avec mon code, y compris le nombre maximum de lignées.
    Pendant l’exploration, j’ai 10 lignées, mais pendant l’exploitation, je limite à une seule lignée. A ce niveau là, ce n’est plus vraiment de la reproduction mais plutôt des copies du champion qui mutent tous (il faudrait que je code un moyen de virer la reproduction pour cette stratégie), c’est très efficace quand on les fait muter très peu (l’idéal que j’ai trouvé serait de muter un seul gène à chaque fois, ça aussi faudrait que je le code), ça optimise vite l’ADN !

    Je ne connais pas la méthode arène, mais le nom me fait penser au fait de faire une sélection sur un tournoi d’ADN en 1 contre 1. Si c’est ça, je n’ai jamais testé.

  5. neFAST dit :

    Ca aurait été intéressant de partager les pondérations de la meilleure voiture. Est-ce que certains “lasers” sont totalement ignorés (par exemple les plus latéraux ont surement des pondérations extra faible.), si tu simplifies en retirant ces paramètres, est-ce que tu peux converger beaucoup plus vite ?

Laisser un commentaire

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