Aller au contenu


Information tutoriel

  • Ajouté le: mai 24 2011 08:26
  • Date Updated: mai 20 2016 09:38
  • Lectures: 18134
 


* * * * *
0 Notes

Réseaux de neurones & algorithme génétique d'apprentissage

Posté par Harry on mai 24 2011 08:26
Après de longs mois d'inactivité, je suis de retour avec ce petit tutoriel qui vous donnera - je l'espère - le goût du développement d'intelligence(s) artificielle(s). L'objectif de ce tutoriel est de vous expliquer le fonctionnement d'un "cerveau" pour que vous puissiez en développer un pour votre robot, de telle sorte qu'il apprenne de lui-même à éviter les obstacles... Vous avez bien lu : le robot que je vous propose d'étudier pourra éviter les obstacles après avoir appris à le faire, tout seul !

Bref, passons directement dans le vif du sujet !

Sommaire :

1. Constitution du robot
2. Établissement manuel du réseau de neurone
3. Algorithme génétique d'apprentissage

Constitution du robot

Partie "hardware"

Voici les principaux composants de notre robot
 
 
  •  
  • en vert : 2 moteurs à courant continu
  • en jaune, orange et rouge : 6 capteurs de distance
  • non représenté : un micro-rupteur (= interrupteur) qui se déclenche si le bord du robot touche un obstacle.

Image IPB

Je ne détaille pas l'alimentation, l'électronique employée, etc... l'objectif de ce tutoriel étant de comprendre le fonctionnement des réseaux de neurones : ce tutoriel sera donc applicable à n'importe quel robot ayant cette configuration et pouvant être programmé à vos souhaits.

Partie "software" : le réseau de neurone proprement dit

Un réseau de neurone relie les entrées d'un système à ses sorties.

Image IPBLes entrées et les sorties sont appelés des nœuds. Le "lien" qui relie deux nœuds est appelé un axiome. Ceci n'est donné qu'à titre informatif, il n'est pas indispensable de retenir ce vocabulaire pour comprendre ce tutoriel.

Voici un schéma détaillant la notation que l'on va utiliser pour repérer les capteurs et les moteurs :

Image IPB

J'en ai profité pour dessiner notre premier réseau de neurone. Pour simplifier la compréhension, on ne va s'intéresser qu'au moteur gauche de notre robot.

On distingue clairement sur ce schéma - grâce aux traits en gras - que toutes les entrées (les Ci) sont reliées au moteur (M1). Sur chaque lien, on peut voir d'autres notations : P11, P21, P31, P41, P51 et P61 (ou encore les Pik - P indice i indice k - avec i allant de 1 à 6, et k valant 1 puisqu'on n'étudie que le moteur gauche) C'est ce qu'on appelle les poids. Grâce à ces notations, voici l'équation du réseau de neurone que l'on vient de créer - pour le moteur gauche uniquement :

Image IPB

Les valeurs des capteurs sont données par les capteurs eux-même, en fonction de la distance qui les séparent d'un obstacle extérieur. Les valeurs des moteurs sont contrôlées par le logiciel qui est sur votre robot... ici, il sera contrôlé grâce au réseau de neurone, dont on a écrit l'équation juste au-dessus. Il nous manque donc plus qu'à connaître les valeurs des poids (Pik)... c'est justement ces poids que le robot doit apprendre à déterminer, de lui-même ! Pour comprendre comment lui faire faire cela, nous allons d'abord essayer de voir quelles valeurs pourraient fonctionner pour nos Pik, pour que notre robot puisse éviter les obstacles...

Établissement manuel du réseau de neurone

Comportement désiré

Pour que tout le monde suive, on va mettre à plat le comportement du robot. Le robot doit toujours avancer, sauf dans les cas suivant :

  •  
  • si un obstacle se présente sur la gauche, le robot doit tourner à droite (c'est à dire que le moteur gauche doit "avancer" - tandis que le moteur droit doit "reculer")
  • si un obstacle se présente sur la droite, le robot doit tourner à gauche (c'est à dire que le moteur gauche doit "reculer" - tandis que le moteur droit doit "avancer")
Et si un obstacle se présente au centre ? Ceci est un faux problème car les capteurs ne donneront jamais constamment la même valeur à droite et à gauche : on rentrera donc systématiquement dans un des deux cas précédents. Si vraiment cela devait arriver, je suis sûr que vous saurez palier à ce problème une fois que vous aurez compris comment faire un réseau de neurone. Mais pour l'instant, on va simplifier les choses : aucun obstacle ne se présentera pic poil au milieu, et le robot ne PEUT PAS se planter (admettez-le, ou remettez ce problème à plus tard... ne restez pas bloqué à cause de ce cas).

Nous allons donc traiter ces deux cas, l'un après l'autre, ce qui nous permettra de donner des valeurs fonctionnelles pour P11, P21 et P31 d'une part, puis P41, P51 et P61 d'autre part.

Si un obstacle se présente sur la gauche...

... dans ce cas, les capteurs de gauche, C1, C2 et C3 auront une valeur importante (les capteurs de distance renvoie une valeur d'autant plus importante que l'obstacle est proche). Or, on voulait que si un obstacle se présente à gauche, le moteur gauche devait avancer... pour cela, on doit lui envoyer une valeur positive. Je rappelle notre équation du RdN (réseau de neurone) :

Image IPB

Vu ce que l'on cherche à faire, le plus simple pour répondre à cette demande serait - en premier lieu - d'imposer P11 = 1, P21 = 1 et P31 = 1 (ce sont des valeurs possibles). Notre équation devient donc :

Image IPB

Image IPBOui, mais attends, tu en fais quoi des valeurs des 3 autres poids ?

Je ne les ai pas oublié, soyez patients !

Si un obstacle se présente sur la droite...

... alors là, à l'inverse, ce sont les capteurs C4, C5 et C6 qui auront une valeur importante. Or, on voulait que si un obstacle se présente à droite, notre robot doit tourner à gauche, et pour cela, le moteur gauche doit "reculer"... pour cela, il faut lui envoyer une valeur négative. Vous l'aurez compris, on va imposer P41 = -1, P51 = -1 et P61 = -1. Ainsi :

Image IPB

Pour ceux qui auraient des doutes...

Image IPBAttends c'est n'importe quoi ce que tu fais là ! Tu détermines les valeurs de la moitié des poids pour un cas, et l'autre moitié avec un autre cas ! Ca ne pourra jamais marcher... !!!

Je conviens que la méthode employée n'est pas très catholique : cependant, cela fonctionne ! Vérifiez par vous-même... si un obstacle arrive à gauche, C1, C2 et C3 auront une valeur importante, et C4, C5 et C6 auront une valeur faible... d'autant plus faible que l'objet est loin, voire nulle si l'objet est à l'infini... on peut donc considérer que dans le cas où un obstacle arrive sur la gauche, seules les valeurs de C1, C2 et C3 sont pris en compte... et regardez l'équation dans ce cas là :

Image IPB !!! notre moteur gauche va donc "avancer" !

Et ça marche aussi si un obstacle arrive à droite : C1, C2 et C3 sont faibles cette fois-ci, voire négligeable... alors que C4, C5 et C6 auront une valeur importante, et dans ce cas, l'équation devient :

Image IPB !!! notre moteur gauche va donc "reculer" !

Et le moteur droit alors ?

Cela pourrait faire un très bon exercice... je vous laisse chercher (il suffit de suivre exactement le même schéma que précédemment), mais voici la réponse :

Image IPB

Algorithme génétique d'apprentissage

Introduction

Nous avons créé un réseau de neurone, et nous avons trouvé des valeurs possibles pour les poids de ce réseau. Je vous avais pourtant dit au début que votre robot allait apprendre à le faire de lui-même ! Vous aurais-je menti ? Non, mais je voulais que vous ayez bien compris la constitution d'un réseau de neurone et son fonctionnement. Maintenant que cela est fait, nous allons imaginer que nous ne connaissons pas les valeurs de ces poids, et nous allons faire faire ce dur labeur à notre robot.

Image IPBAttends, c'est complètement idiot de faire ça ! On connaît des valeurs qui marchent, pourquoi ne pas lui donner directement les valeurs et tester ?

Vous avez raison : vous pouvez tester ces valeurs sur votre propre robot. Et ça marchera. Très bien même. Et puis vous aurez deux possibilités :
 
  •  
  • vous êtes content de ce que vous avez appris et cela vous suffit : dans ce cas, merci d'avoir lu ce tutoriel et au revoir ! Bonne journée !
  • vous avez envie d'en apprendre plus, en particulier sur l'algorithme génétique d'apprentissage, et vous avez même envie que l'apprentissage se fasse le plus simplement possible : dans ce cas, je vous invite à lire la suite
Et pour ceux qui trouvent que c'est dommage de rester sur le même exemple - déjà résolu qui plus est - pour apprendre le fonctionnement de l'algorithme génétique d'apprentissage, je répondrai ceci : c'est un choix que j'ai fait en toute connaissance de cause. En effet, si on reste sur un exemple déjà bien connu, les termes que je vais employer auront un aspect "concret", tandis que si je pars sur un autre exemple, ce sera un peu plus subjectifs, et certains risquent de ne pas suivre.

Je vous invite donc à rentrer dans le vif du sujet de cette grosse bête qui paraît si méchante... et qui ne l'est pas du tout en fait o_O

Algorithme d'apprentissage simple

Le principe de l'apprentissage simple est le suivant : on choisit des valeurs aléatoires pour les poids, puis le robot le teste de lui-même. Pour qu'il puisse les tester, on va lui dire d'utiliser un capteur qu'on n'a pas encore utilisé, mais que j'ai indiqué au tout départ, souvenez vous :
Citation de : Harry
Citation

Voici les principaux composants de notre robot
  •  
  • en vert : 2 moteurs à courant continu
  • en jaune, orange et rouge : 6 capteurs de distance
  • non représenté : un micro-rupteur (= interrupteur) qui se déclenche si le bord du robot touche un obstacle.
Nous allons donc demander à notre robot d'utiliser ce micro-rupteur : si celui-ci se déclenche, cela voulait donc dire que les valeurs de nos poids (choisis aléatoirement) étaient "mauvais". Il faut donc faire un autre "jet" (c'est à dire qu'on va choisir d'autres valeurs aléatoires pour les poids). Et ainsi de suite... jusqu'à ce que le robot évite tous les obstacles !

Image IPBAttends... mais ça peut prendre un temps fou ça !

Oui, mais observez un bébé qui apprend à attraper un verre : un coup, sa main passe au dessus, le coup d'après sa main se cogne contre la table ("ouille" :mort: "ouinnnn" Image IPB ), le coup d'après il envoie le verre sur la lune (là, c'est le papa qui n'est pas content :colere: -> fessée)... puis après en avoir cassé plusieurs, il arrive enfin à l'attraper ! Tout cela prend du temps ! Si vous voulez, vous pouvez créer un "simulateur de robot" qui pourra vous permettre de tester votre algorithme pour obtenir la valeur des poids plus rapidement ^^

Algorithme génétique d'apprentissage

On a failli oublié la partie "génétique" dans tout ça dites donc... meuh non, ne vous inquiétez pas ! Image IPB

Cependant, la partie "génétique" est tellement simple que j'ai honte de la détailler... faisons le tout de même. Dans la partie précédente, on a effectué une série de jets sur les poids.

Ce que l'on va faire maintenant, c'est d'enregistrer une dizaine de jet, et, pour chaque jet, lancer notre robot dans une arène pendant disons une dizaine de minute. Puis on regarde les résultats obtenus pour le nombre de fois où le robot s'est cogné pour chaque jet. La "sélection génétique" de cette "génération" va consister à sélectionner le jet qui aura obtenu le meilleur score, c'est à dire le jet pour lequel le robot s'est cogné le moins souvent.

Puis on passe à la génération suivante : cette génération est issu du jet "sélectionné". Je veux dire par là qu'au lieu de faire des choix aléatoires pour tous les poids à chaque nouveau jet, on va en conserver 1 (d'une manière aléatoire, mais on en conserve au moins 1 du jet "parent" pour chaque nouveau jet). Puis on re-fait nos tests, et on refait une sélection du meilleur.

A la génération suivante, on va conserver cette fois-ci 2 valeurs de poids...

A la génération suivante, on va en conserver 3...

et ainsi de suite...

Petit à petit, vous verrez que les enfants issus des "meilleures" sélections auront les mêmes comportements que ceux de leurs parents, mais améliorés (les parents ont transmis leur "savoir" à leurs enfants qui à leur tours font leur vie et enseignent ce qu'ils ont appris à leurs enfants).

Je trouve ce concept passionnant et pourtant d'une facilité déconcertante une fois qu'on a compris de quoi il s'agissait, n'est-ce pas ?

N'hésitez pas à poser vos questions sur le forum !