Bonjour à tous !

Ça faisait longtemps que je ne vous avais pas pondu un bon gros pavé de derrière les fagots pour accompagner un projet bien tordu comme j'en ai le secret, donc voici un résumé de mes nouvelles aventures sur Scratch !

TL;DR :

J'ai fait un projet où des créatures artificielles apprennent toutes seules à aller manger et à éviter les bords, grâce à un réseau de neurones artificiels et un algorithme génétique.

Il est ici : Emergence.

Cela faisait un certain temps que je voulais tâter de la simulation évolutionnaire mixant réseau de neurones artificiels (qu'à partir de maintenant je vais abréger en ANN pour Artificial Neural Network) et algorithme génétique (ou GA pour Genetic Algorithm). Je me suis donc fait une petite preuve de concept, qui fonctionne après de multiples péripéties (joie !). Ce projet ne devait au départ m'être personnel, pour faire mes tests, mais je me suis rendu compte qu'il pourrait être utile à d'autres personnes tentées par l'aventure, c'est pourquoi j'écris ce post que j'espère didactique.

I) Réseau de neurones artificiels (ANN) :

Si vous vous intéressez un tant soit peu à l'actualité informatique, notamment concernant l'intelligence artificielle, vous avez sûrement déjà entendu parler d'eux. Le concept est assez simple : pour simuler une intelligence, pourquoi ne pas simuler un cerveau ?

Alors, évidemment, il est illusoire d'espérer simuler un cerveau humain dans toute sa complexité… L'approche des ANN est donc une simplification massive de la réalité, mais qui apporte tout de même des résultats très impressionnants (par exemple, le premier logiciel à avoir battu un champion de go utilise un ANN).

En voici un schéma simple :


On constate ici qu'il y a 3 couches :

1. Input (entrées) :
   C'est ici que l'ANN va recevoir les informations qui lui sont accessibles et qui doivent lui permettre de “prendre une décision”. Par exemple, si l'on faisait un ANN qui jouait au morpion, les entrées donneraient les cases marquées d'un rond et celles marquées d'une croix.
   
   
2. Hidden (cachées) :
   En vérité, bien qu'il n'y ai qu'une couche hidden sur le schéma, il peut y en avoir bien plus que ça en pratique… Ou pas du tout ! Ces couches sont dites cachées parce qu'elles ne sont pas censées être en contact avec l'extérieur : elles ne reçoivent pas d'entrées directes, et ne donnent pas de sorties vers l'extérieur. Au lieu de ça, elles reçoivent des informations de la couche avant elles (input ou couche hidden précédente) et en envoient à la couche située derrière elles (output ou couche hidden suivante).
   
   
3. Output (sortie) :
   Cette couche renvoie les “décisions” de l'ANN. Il faut donc autant de neurones de sortie qu'il y a d'ordres que l'ANN doit donner.
   
   
4. Un cas particulier : le Bias (biais) :
   Sauf dans les ANN les plus simplistes, on trouve quasiment toujours un neurone très particulier, le bias. Il est à part, et sa valeur vaut toujours un. Le principal but de son existence est de définir un comportement quand toutes les entrées valent 0. Ce neurone est virtuel, c'est pourquoi on ne le représente en général pas sur les schémas, mais il faut quand même faire attention à ne pas l'oublier.
   

Voilà pour la représentation “humaine” d'un réseau de neurones. Toutefois, l'ordinateur ne le voit pas comme ça. Mais avant de parler de son implémentation, il va falloir préciser un peu comment il fonctionne.

Revenons sur les neurones d'entrées (Input) : il faut leur fournir des informations numériques, puisqu'un ordinateur ne saura pas vraiment quoi faire de “bleu” ou “Gertrude” sans le transformer en données numériques (= des chiffres). L'autre point auquel il faut faire attention est de donner des valeurs qui sont toutes dans le même ordre de grandeur : si ma première entrée va de -2 à 4 et la deuxième de 5 000 à 120 000, ça va être plus compliqué de régler correctement le réseau de neurones. C'est pourquoi en général on met tout entre 0 et 1 ou entre -1 et 1 (dans les deux cas, c'est mathématiquement assez simple à faire et ça assure aussi de ne pas perdre d'information (car il existe des bijections entre R et les segments (0,1) et (-1,1) )).

Maintenant, intéressons-nous aux autres neurones (hidden et output) : ils fonctionnent tous de la même façon : ils reçoivent des données de tous les neurones de la couche avant eux, ainsi que du bias, et renvoie une valeur. Du coup, ce qui nous intéresse, c'est comment calculer cette valeur : chaque neurone va avoir un tableau qui lui est propre et qui contient ce que l'on appelle des poids. Chaque poids est associé à un neurone de la couche précédente, plus le dernier qui est associé au bias. Ainsi, pour calculer la valeur qu'il va renvoyer, chaque neurone va multiplier, pour chacun des neurones qui lui envoie une valeur, ladite valeur par le poids associé au neurone émetteur. Ensuite, il va faire la somme de tout ça.

Exemple :

Un neurone N possède les poids suivants : 0.2 pour le neurone 1, 0.75 pour le neurone 2 et -0.5 pour le bias.
Le neurone 1 envoie une valeur de 0.6. Le neurone 2 envoie une valeur de 0.8. Le bias envoie une valeur de 1 (toujours, vu que c'est le bias).
Ainsi, mon neurone N va envoyer : 0.2 x 0.6 + 0.75 x 0.8 + (-0.5) x (1) = 0.12 + 0.6 - 0.5 = 0.22.

On constate donc que les poids sont essentiels pour faire fonctionner l'ANN. En fait, du point de vue de l'ordinateur, c'est tout ce qui l'intéresse, et on peut très bien représenter un ANN juste comme une liste de poids.

Il reste juste une dernière étape, optionnelle : ce que renvoie un neurone n'est plus limité à un intervalle compris entre 0 et 1 ou -1 et 1. Parfois, ça ne dérange pas, et parfois (notamment s'il s'agit de neurones hidden), il vaut mieux les recadrer à nouveau. On utilise alors une fonction d'activation : c'est une fonction que l'on connaît, qui a des propriétés mathématiques qui nous plaisent (espace d'arrivée limité, dérivabilité, monotonie, etc.) et que l'on va appliquer à la somme obtenue précédemment. Une des plus utilisées est la fonction sigmoïde x -> 1 / (1 + e^(-x) ).
Dans notre exemple précédent, la sortie du neurone ne serait donc plus 0.22 mais 1 / ( 1 + e^(-0.22) = 0.5547792 environ.


Voilà en très gros le fonctionnement d'un ANN (s'il y a besoin de détails supplémentaires, je vous invite à vous renseigner sur le net, on trouve plein de bonnes choses, et à me poser des questions dans les réponses à ce topic). Toutefois, si vous êtes observateur, vous devriez remarquer que j'ai dit qu'un ANN n'était en fait qu'une liste de poids, mais je n'ai absolument pas dit comment on les trouvait, ces poids ! Et c'est là en fait tout le problème : un ANN ne sait résoudre un problème que si ces poids sont adaptés pour le problème…

Pour trouver les bons poids, il y a plusieurs méthodes : l'apprentissage supervisé, qui consiste à utiliser des valeurs d'entrées pour lesquelles on connaît les valeurs de sortie que l'on voudrait que l'ANN renvoie, puis à lui faire apprendre comment renvoyer les bonnes valeurs (par backtracking, mais ça je vous laisse chercher) ; il y a également l'apprentissage non supervisé, qui est un peu compliqué à décrire…

Et puis, on peut utiliser un algorithme génétique.

II) Algorithmes génétiques (GA) :

Si le but d'un ANN est de résoudre un problème en simulant un cerveau, celui d'un GA est de résoudre un problème en simulant l'évolution au sens darwinien du terme !

On utilise un algorithme génétique quand on a un ensemble de valeurs et qu'on veut maximiser un (des) propriété(s) de cet ensemble.

Chaque valeur correspond alors à un gène, et l'ensemble des valeurs - ou gènes - constitue un individu.
La population est un ensemble suffisamment grand d'individus.

Le principe est le suivant : on génère aléatoirement des gènes de manière à former une population, constituée d'individus. Puis on mesure, à l'aide d'une fonction dit de fitness (aptitude) la “qualité” de chacun de ces individus.

En fonction des qualités mesurées, les individus ont des chances de se reproduire : évidemment, ceux qui sont les mieux adaptés ont plus de chances de se reproduire.

Pour la reproduction, on choisit deux parents au hasard (en donnant à chaque individu d'autant plus de chance d'être choisi qu'il est apte), puis pour chaque gène on copie celui du premier parent ou du second (au hasard).
Pour un meilleur brassage génétique, il est souvent intéressant de s'inspirer un peu plus de la biologie et d'avoir une probabilité de crossover plutôt que de copie du gène : le gène est alors un “mélange” du gène des deux parents.
Pour un brassage encore meilleur, il faut aussi une (petite) probabilité de mutation : le gène est alors modifié aléatoirement.

Enfin, on a parfois besoin d'élitisme : un pourcentage des meilleurs individus sont gardés tels quels.

Une fois que tout ça est fait, on a une nouvelle population : la génération suivante. On mesure le fitness de chacun des individus et on recommence.

III) Tout ça pour quoi ? :

Pour les impatients : le projet.

Détails :
J'ai voulu simuler de petites créatures qui se déplacent dans un plan (en deux dimensions), mangent des cercles rouges et doivent aussi éviter les bords.

Pour cela, elles ont un réseau de neurones constitué de 3 entrée, 3 hidden et 2 outputs (et le bias) :
En entrée : l'inverse de leur distance à la nourriture (comme ça, c'est compris entre 0 et 1, vu que si elles sont à moins de 1 de la nourriture, elles l'ont mangé) ; l'angle entre leur direction et la nourriture et enfin l plus petite distance entre elle et un bord.
En sortie : de combien elle avancent et de combien elles tournent.

Tous les neurones ont une fonction d'activation sigmoïde, à part la sortie rotation, car je voulais qu'elle puisse aussi être négative (tourner dans l'autre sens, c'est faisable).

Les poids sont tirés au hasard au début, puis je fais vivre une génération de 30 individus pendant 500 ticks : elles gagnent des poits si elles mangent la nourriture ou si elles s'en approchent, et en perdent si elles s'en éloignent ou touchent un bord. De plus, afin de minimiser les dépenses inutiles d'énergie, elles perdent aussi des points de manière proportionnelle à leur vitesse : il faut aller vite vers la nourriture, mais éviter les déplacement inutiles.

L'algorithme génétique tourne donc sur les poids de ces individus, avec un élitisme de 5 (les 5 meilleurs individus sont gardés d'une génération sur la suivante), une probabilité de crossover de 70% et une probabilité de mutation de 0.5%.

On constate qu'on commence à voir des créatures qui se dirigent correctement vers la nourriture en une dizaine de générations en général, ensuite c'est de l'amélioration de comportement.

Pour info, les créatures foncées sont les élites de la génération précédente, les verts clairs sont les mutants et la rouge et la dernière à avoir réussi à manger la nourriture.

Enfin, les barres gris qui apparaissent en bas de l'écran représentent le fitness total des 15 meilleurs individus de chaque génération : normalement, ça a tendance à augmenter (en moyenne, on peut avoir des pics plus bas).

Voilà, j'espère que mon gros pavé vous aura été utile ou au moins vous aura intéressé, et j'espère que vous vous amuserez autant que moi à voir émerger l'intelligence artificielle toute seule !

J'ai oublié de le préciser, mais évidemment maintenant que j'ai réussi à faire tourner mon proof of concept, le but c'est de faire bien plus compliqué pour simuler de mieux en mieux des formes de vie

Juste (la flemme de tout lire, je suis en vacances quand même), ça t'a pris combien de temps d'écrire ce (très) gros pavé ?

Une bonne heure, je pense.

SBissay wrote:

Une bonne heure, je pense.

Dis donc, tu es courageux pour un truc tellement long que presque personne va lire tellement c'est long.

Bouboufez wrote:

SBissay wrote:

Une bonne heure, je pense.

Dis donc, tu es courageux pour un truc tellement long que presque personne va lire tellement c'est long.

Peut-être, mais j'avais vraiment envie d'expliquer le cheminement derrière ce projet. Et puis je préfère voir le verre à moitié plein en me disant que ce post sera peut-être utile à quelqu'un, plutôt que de penser que personne ne va le lire

C'est souvent la même rouge qui mange ^^. tu devrais pour plus d'interaction nous laisser poser la nourriture en cliquant un peu comme on veut avec la souris ^^

Sinon j'ai également tout lu ^^ allez Sbissay, c'est le moment de nous dire ton métier dans la vie ^^

remarque: je n'ai pas l'impression que les bestioles choisissent la meilleure façon de tourner, je ne les vois jamais tourner dans le sens anti horaire alors que j'ai cru comprendre que tu as dit que c"était possible , même si la nouriture se trouve sur leur gauche, elles vont faire un tour complet vers la droite avant d'y aller.

Itharius wrote:

C'est souvent la même rouge qui mange ^^

Ça arrive souvent dans les premières générations, quand il y a un individu bien mieux adapté que les autres. Au fil du temps, ça s'estompe (et d'ailleurs, vu que mon fitness “global” n'est en fait calculé que sur les 15 premiers, j'avais eu la surprise de le voir drastiquement chuter après une bonne centaine de générations, pour comprendre ensuite que c'était parce que la nourriture se répartissait du coup sur plus de 15 individus.

Itharius wrote:

tu devrais pour plus d'interaction nous laisser poser la nourriture en cliquant un peu comme on veut avec la souris ^^

Ça c'est une bonne idée, tiens ! Je ne pensais pas y toucher plus, parce que je voulais me concentrer une une version bien plus complète, mais j'avoue que l'idée de pouvoir placer la nourriture là où ça fera bien travailler les créatures est tentante. Mais après courte réflexion, je n'ai qu'à rendre le jeton nourriture déplaçable via scratch, vu que ses coordonnées sont utilisées directement pour les calculs (et ce à chaque tick). Je tente ça, puis je vois si ça nécessite plus.

Itharius wrote:

remarque: je n'ai pas l'impression que les bestioles choisissent la meilleure façon de tourner, je ne les vois jamais tourner dans le sens anti horaire alors que j'ai cru comprendre que tu as dit que c"était possible , même si la nouriture se trouve sur leur gauche, elles vont faire un tour complet vers la droite avant d'y aller.

Oui, j'ai remarqué qu'elles finissent assez souvent par décider de ne tourner que dans un sens. Toutefois, j'ai vu les 2 sens se développer, donc ça ne vient pas de l'implémentation. Enfin, après quelques dizaines (centaines ^^°) de générations, elles comprennent que tourner dans les 2 sens est plus rentable… En général ! Mais on touche à un point critique des algos génétiques : les optima locaux…

Itharius wrote:

Sinon j'ai également tout lu ^^ allez Sbissay, c'est le moment de nous dire ton métier dans la vie ^^

Merci d'avoir tout lu ! J'espère que c'était compréhensible, digeste mais surtout intéressant !
Quant à mon métier, il me semblait l'avoir déjà donné… Pour le moment, c'est pas très sexy : j'ai repris mes études, en fac de mathématiques.

(Mais si tu veux un CV complet : j'ai un bac S, une prépa MP*, 2 ans d'école d'ingénieur en informatique (pas finie pour raisons de santé), 1 an et demi de webmaster dans une boîte de e-commerce, 2 ans de concepteur web et logiciel à mon compte, 4 ans d'AED (faut bien manger quand sa boîte coule ^^) et 1 an de formateur en mathématiques, physique-chimie et informatique en CFA à mon actif).

je propose aussi que l'utilisateur puisse rajouter des obstacles (des murs) à contourner comme ça on visualise bien comment les bestioles s'adaptent pour survivre ^^

el15617 wrote:

je propose aussi que l'utilisateur puisse rajouter des obstacles (des murs) à contourner comme ça on visualise bien comment les bestioles s'adaptent pour survivre ^^

Alors ça fait partie des améliorations que je veux apporter : à l'heure actuelle, la seule perception de l'environnement qu'ont les créatures est celle concernant la nourriture et les bords de la zone. Donc si l'on créait des obstacles, comme elles n'auraient aucun moyen de les percevoir, elles se jetteraient dedans sans s'en rendre compte… Ça peut être amusant un court moment à regarder, mais ça ne va pas nous mener bien loin.

C'est pourquoi j'espère améliorer leur perception, afin de pouvoir :

1. Mettre plusieurs sources de nourriture (ou d'autres “récompenses” potentielles),
   
2. Gérer des interactions entre créatures (combat ? reproduction ?),
   
3. Avoir des obstacles,
   
4. Avoir d'autres dangers potentiels.
   

Le truc, c'est que ça nécessite un ANN plus grand, car il y aura plus d'entrées (Inputs). Ce n'est pas un problème en soi, par contre il faudra sûrement plus de générations avant de voir apparaître des comportements intéressants.

En fait, là où le bât blesse, c'est sur le mode de perception à proprement parler : au départ, je pensais faire un truc calqué sur la vision, mais ça nécessite du raycasting, et Scratch est beaucoup trop lent pour faire ce genre de choses à une échelle aussi grande (si on a un angle de vision de 120°, ça nécessite au moins 120 raycasting par créature par ticks, donc 3600 raycastings par tick, et là c'est LAG PARTY). Du coup, je réfléchis à un truc un peu plus limité : chaque créature pourrait avoir un “senseur” à une distance fixée d'elle-même, donc l'angle avec la créature serait décidée par la créature elle-même, et qui renverrait des infos sur ce qu'il rencontre, un peu à la manière de la canne blanche d'un malvoyant…

Mais il faut que je teste pour voir ce que cela donne. A suivre, donc…

c'est très intéressant d'apprendre ce genre de truc, même si elle est virtuelle c'est vraiment super de pouvoir faire ta rencontre Sbissay ! j'ai hâte de pouvoir poser la nourriture pour faire comme si c'était un aquarium moi je n'ai tester que 35 générations, les bestioles n'ont jamais tourné dans l'autre sens, je réessayerai plus tard dans le week end une centaine de générations, si ça se met vraiment à tourner dans l'autre sens ce sera vraiment surprenant parce que ça montrera vraiment l'apprentissage et ce serait vraiment un truc assez impressionnant à voir sur scratch !

Héhé, je suis moi aussi ravi d'avoir fait ta connaissance !

Pour la bouffe, elle est déplaçable à la souris, c'est déjà un début.

J'ai fait un autre test : plutôt que de normaliser l'angle entre 0 et 1 (avec 0.5 signifiant que la nourriture est en face de la créature), je l'ai normalisé entre -1 et 1 (0 étant en face) : ça a l'air de donner de meilleurs résultats concernant la rotation dans des sens différents, par contre ça met plus de temps à trouver une solution viable…

c'est trop compliqué de pouvoir rajouter plusieurs points de nourriture en même temps ?

Il y a des générations qui n'ont pas le temps d'arriver au point nourriture.

ça y est il y a des choix de rotations dans les 2 sens très rapidement ( en moins de 10 générations ^^)
En effet , il tourne dans différents sens par contre il ne font plus tous une ligne droite vers la nourriture dès que c'est possible

Bon, j'ai pas encore compris le truc des mutations

+1 pour le tl;dr

ça veut dire quoi tl;dr ?

J'ai remarqué que les “mutants” ne sont pas forcément les plus malins pour aller bouffer, on dirait qu'il y a des mutations qui ne sont franchement pas bénéfique à l'individu

too long, did not read

en français, trop long, j'ai pas lu

Disons que comme il y a une (grosse) part d'aléatoire, ça peut converger vers une solution très vite, très lentement ou même pas du tout (s'ils trouvent un optimum local qui leur plaît bien ^^).

Pour avoir plusieurs points de nourriture en même temps : avec le système actuel, c'est difficile : en effet, les créatures reçoivent leur position par rapport à la nourriture sur 2 inputs : l'inverse de la distance et l'angle entre leur direction et la nourriture. Si je venais à mettre un second point de nourriture, ça voudrait dire rajouter 2 inputs supplémentaires, et donc complexifier le réseau de neurones, et donc a priori augmenter le temps moyen de convergence…
Et le souci, c'est qu'avoir un nombre arbitraire de points de nourriture oblige à avoir un ANN de taille arbitraire aussi, ce qui se fait relativement facilement en programmation orientée objet, mais bine plus difficilement sous scratch.
Une solution possible serait de ne leur donner des infos que sur le point de nourriture le plus proche, mais je trouve ça assez peu réaliste : on ne perçoit pas que l'objet le plus proche de nous, a priori… D'où mes investigations pour des méthodes de perception différentes, celle-ci étant très limitée (mais elle a bien rempli son rôle pour mes premiers tests).

Concernant les mutations, ça fonctionne comme en biologie : les créatures ont une reproduction sexuée : à chaque changement de générations, 25 nouvelles créatures sont créées (pour remplacer les 25 moins bien notées qui … meurent ). Pour les créer, voici la marche que je suis :

1. Je sélectionne 2 parents distincts, parmi les 15 les mieux notés : le mieux noté a plus de chances d'être sélectionné que le second, et ainsi de suite.
   
2. Pour chacun des gènes constituant le génome d'une créature, on teste les choses suivantes :
   

• Est-ce qu'il y a crossover ? (ici, probabilité de 70% que ça arrive)
  Si oui, alors le nouveau gène sera un mélange des deux gènes des parents. Dans la nature, ça se traduit par des coupures de l'ADN qui se recolle pour former un nouveau brin. Dans un encodage en binaire, disons par exemple sur 8 bits, ça revient à couper les gènes à un bit précis et à recoller des morceaux de parents différents pour en créer un nouveau. Exemple : si le parent 1 a le gène 01101100 et le parent 2 a le gène 11100010, alors on tire au hasard un endroit où couper (disons après le 3ème bit) et quel parent fournit la première partie (disons le parent 1). Le nouveau gène sera donc les 3 premiers bit du parent 1 suivant des 5 derniers du parent 2, ici : 01100010. En binaire, on peut donc bien copier la nature. Le souci, c'est qu'ici on travaille avec des réels (flottants), donc c'est mal adapté. Une solution consiste alors à prendre une moyenne pondérée des deux flottants : ici on tire un nombre a entre 0 et 1 et le nouveau gène devient (a x gène du parent 1 + (1 - a) x gène du parent 2).
  S'il n'y a pas crossover, alors on tire un des deux parents au hasard et on copie le gène du parent choisi, sans modification.
  
• Après ça, il y a une petite chance de mutation lors de la copie d'un gène, comme dans la nature. Ici, c'est 0.5%.
  Dans ce cas, le gène n'est pas copié à l'identique, il subit une modification. Dans la nature, c'est généralement un A qui devient un T, C ou G ou une autre permutation dans le genre. En binaire, il suffit en général de changer un 1 en 0 ou l'inverse. Encore une fois, en flottant ça ne fonctionne pas aussi bien. La solution la plus simple consiste alors à modifier le gène en lui ajoutant un nombre aléatoire, en général pas trop grand (ici, c'est entre -1.5 et 1.5). Du coup le gène est “nouveau”, et permet d'explorer un peu plus l'espace des solutions. Souvent, les “mutants” sont assez inutiles parce que la mutation a détruit un gène nécessaire à la survie, mais parfois ça donne une amélioration notable : ils deviennent alors parmi les mieux adaptés de leur génération et transmettent cette mutation à leur descendance, d'où l'intégration de cette mutation par la population sur le long terme.
  

smrman wrote:

+1 pour le tl;dr

Fainéant

Il y a des bestioles qui ont beaucoup de mal à se dégager du bord quand elles l'ont touché , j'avais pas constaté ça lors de la version précédente.

je suis loin d'avoir tout compris mais j'ai remarqué qu“il y a des bestioles qui captent que même si elles sont derrière le troupeau, il faut mettre un coup de boost pour passer devant tout le monde pour arriver à la nourriture, il doit donc y avoir un neurone qui décide de la vitesse de déplacement ^^

Il faut que tu rajoute un tag IA Sbissay !!!

2eme remarque: génération 51, les bestioles sont ”évolués" c'est à dire rapide; il peut arriver que le point de nourriture est au centre d'un cercle qu'elles forment toutes autour et on dirait qu'elles n'arrivent pas à réduire leur vitesse ou leur angle pour choper le point de nourriture qui est juste à côté (elles forment toutes un magnifique cercle resséré autour du point de nourriture en tournant tout autour)