Vélos névrotiques: Genesis

L'autre jour, Youtube a pensé que je trouverais intéressant de regarder une vidéo intitulée «AI apprend à jouer à Hill Climb Racing». C’est drôle, car quelques minutes auparavant, j’avais commis les prochaines modifications du projet, où mes collègues et moi, entre le travail et le travail, résolvons ce problème. Certes, il n'y avait pas d'IA dans cette vidéo - l'auteur a diverti le public avec indulgence avec Box2D et s'est calmé à ce sujet. Néanmoins, je propose de considérer ce fait comme une preuve convaincante de la pertinence du sujet et de démonter l'appareil de notre hochet.

Brièvement sur la tâche: le véhicule - dans notre cas, c'est Alien, ou la machine à coudre Singer sur roues, appelons-le simplement «agent» - doit parcourir le long des dunes avec le même nom le bruit du début à la fin. Voici à quoi ressemble l'agent dans son bac à sable:



Un agent qui touche l'arrière de la piste ou qui ne fait pas preuve de zèle en se déplaçant vers le but est retiré de la piste.

Nous allons résoudre le problème en utilisant des réseaux de neurones, mais optimisés par l'algorithme génétique (GA) - un tel processus est appelé neuroévolution . Nous avons utilisé la méthode NEAT (NeuroEvolution of Augmenting Topologies) inventée par Kenneth Stanley et Risto Miikkulainen au début du siècle [1] : d'une part, il a bien travaillé sur des problèmes importants pour l'économie nationale, et d'autre part, nous avons commencé à travailler sur le projet avait déjà son propre cadre de mise en œuvre de NEAT. Donc, franchement, nous n'avons pas choisi une méthode de solution - nous avons plutôt choisi une tâche où vous pouvez conduire ce qui est déjà prêt.

La figure montre un schéma approximatif d'algorithmes génétiques:



On peut voir que toute AG décente part de la population initiale (la population est un ensemble de solutions potentielles). Nous serons engagés dans sa création et en même temps nous familiariserons avec le premier principe de NEAT . Selon ce principe, tous les agents de la population de départ devraient avoir la topologie «minimale» la plus simple du réseau neuronal. Qu'est-ce que la topologie a à voir avec cela? Le fait est que dans NEAT avec l'optimisation des poids de connexion, l'architecture du réseau évolue également. Soit dit en passant, cela élimine le besoin de sa conception pour la tâche. Passer des architectures simples aux architectures complexes est non seulement logique, mais aussi pratique (il y a moins d'espace de recherche), vous devez donc commencer avec le minimum de topologies possibles - c'est ainsi que les auteurs de la méthode ont raisonné.

Pour notre cas et tous les cas similaires, cette topologie minimale est dérivée des considérations suivantes. Pour faire quelque chose de significatif, l'agent a besoin de:

• disposer d'informations sur l'environnement et son état,
• traiter ces informations
• interagissez avec votre monde.

Le premier rôle est joué par les capteurs - neurones de la couche d'entrée, auxquels nous fournirons des informations utiles à l'agent. Les neurones de la couche de sortie traiteront les données des capteurs. Les acteurs - dispositifs qui effectuent des actions mécaniques en réponse à un signal provenant de «leur» neurone de la couche de sortie - sont responsables de l'interaction avec l'environnement. Ainsi, le principe général de construction de la configuration initiale est le suivant: nous déterminons avec des capteurs et des actionneurs, démarrons un neurone par actionneur, nous connectons tous les capteurs et un autre neurone spécial - un neurone à déplacement ( biais , à ce sujet ci-dessous) avec des poids aléatoires pour tous les neurones couche de sortie. Quelque chose comme ça:



b - polarisation, s - capteurs, o - neurones de la couche de sortie, a - actionneurs, n - nombre de capteurs, k - nombre d'actionneurs

Et voici le NS minimum pour notre tâche:



Nous n'avons qu'un seul actionneur - c'est le moteur de notre création sur roues. Il ne sait pas encore tirer, sauter et jouer de la pipe. La valeur suivante est fournie au moteur à partir d'un seul neurone de la couche de sortie (c'est dommage de l'appeler une couche):


Ici w _b est la valeur du poids de la connexion allant du biais au neurone de sortie, multipliée par le fait que tout biais "produit", c'est-à-dire +1, s _i est la valeur normalisée dans la plage [0,1] sur le i-ème capteur, w _i est la valeur du poids de connexion du i-ème capteur au neurone de sortie, et f est la fonction d'activation.

En tant que fonction d'activation, nous utilisons ce fantasme de softsign:


- Elle a démontré les meilleures performances dans les tests d'un neuro-évolutionniste bien connu dans des cercles étroits [2] . Et cela n'a aucun sens de comparer la douceur des virages et la symétrie du graphique de cette fonction avec le Leaky ReLU à courbure angulaire:



Cette figure montre la réaction de l'agent à différentes valeurs de la fonction d'activation. À des valeurs proches de l'unité, le moteur fait tourner les roues dans le sens horaire, accélérant l'agent vers l'avant et inclinant fortement le boîtier vers l'arrière, de sorte que les faibles d'esprit, mais courageux, basculent rapidement sur le dos et meurent. Avec des valeurs proches de 0, l'inverse est vrai et avec une valeur de 0,5, le moteur d'agent ne fonctionne pas.

La même figure montre le rôle du neurone de polarisation - le poids de la liaison allant de celui-ci au neurone de la couche de sortie est responsable, comme suit de (1), de l'amplitude et de la direction du biais f (x) le long de l'abscisse. La ligne pointillée de la figure montre un graphique de la fonction d'activation à w _b = -1. Il s'avère que même en l'absence de signal sur les capteurs, un agent avec une telle connexion va assez vite revenir en arrière: f (x) = f (-1 + 0) ≈0.083 <0.5. En général, le décalage horizontal des valeurs de la fonction permet à la connexion de polarisation d'ajuster subtilement (bien ou en épaisseur, selon le poids) la réaction du moteur à toutes les valeurs de capteur et au poids de leurs connexions à la fois. Il semble qu'une nouvelle dimension ait été ajoutée à l'espace de recherche (la valeur «correcte» de w _b devra être recherchée), mais les avantages sous la forme d'un degré de liberté supplémentaire l'emportent sur la possibilité de tels déplacements.

Eh bien, nous avons présenté les réseaux neuronaux d'agents de la future population initiale. Mais NEAT est un algorithme génétique, et il fonctionne avec les génotypes - les structures à partir desquelles les réseaux sont formés ou, plus généralement, les phénotypes dans le processus de décodage. Depuis que nous avons commencé avec le phénotype, nous allons tout faire à l'envers: essayer de coder le réseau présenté ci-dessus dans le génotype. Ici, vous ne pouvez pas vous passer du deuxième principe NEAT , dont l'essence principale est la suivante: dans le génotype, en plus de la structure du réseau neuronal et du poids de ses connexions, des informations sont stockées sur l'historique de l'origine de tous ses éléments. À l'exception de cet aspect historique, le phénotype est codé dans le génotype presque «un à un», par conséquent, nous allons maintenant illustrer le deuxième principe avec des fragments de réseaux de neurones.

La valeur de ce principe est difficile à surestimer - il offre aux agents la possibilité de se reproduire sexuellement. Le sujet est assez délicat, nous allons donc d'abord considérer la reproduction asexuée . Cela se passe comme ceci: une copie de tous les gènes de l'agent est faite, l'un des nombreux types de changements est effectué sur eux - des mutations . Dans notre version de NEAT, les mutations suivantes sont possibles:

• changement de poids de connexion
• dissocier
• ajouter un lien
• insertion de neurones.

Les trois premiers types de mutations sont simples et compréhensibles sans autre explication. L'insertion d'un neurone est illustrée dans la figure ci-dessous, elle a toujours lieu à la place de la connexion existante, la connexion est supprimée et deux nouvelles apparaissent à sa place:



Ici h est un neurone caché .

Deux agents sont impliqués dans la reproduction sexuelle ou le croisement - les parents, et en conséquence un troisième apparaît - un enfant. Dans le processus de formation du génotype de l’enfant, un échange se produit, disons, de gènes ou de groupes de gènes de parents de signification identique. Le deuxième principe est exactement ce dont vous avez besoin pour rechercher des gènes ayant la même signification.

Imaginez que nous voulons croiser des agents avec des génotypes qui ont subi différentes séries de mutations de la liste ci-dessus:



Il semble logique de rechercher certains fragments qui sont communs en termes de topologie chez les deux parents et de prendre un morceau de ces fragments pour le génotype de l'enfant à naître. Ce sera difficile à faire, même NP est difficile dans le cas général, mais supposons que nous ayons réussi. Dans ce cas, nous constatons que dans le parent de droite, il y a deux sous-graphiques isomorphes au graphique du parent de gauche. Dans la figure ci-dessous, les arcs de ces sous-graphiques sont mis en évidence dans différentes couleurs:



Lequel choisir pour la recombinaison avec les gènes parent gauche?

Passons à l'histoire de l'émergence de ces génotypes:



Les deux ancêtres des agents parents ont commencé, comme prévu, avec une NS minimale (T ₀ ). Leurs génomes y ont en quelque sorte muté, et au moment du temps T ₁ , le neurone caché a été inséré dans la connexion s ₁ -> o chez l'ancêtre du parent gauche. A ce moment dramatique, les gènes codant pour les liaisons s ₁ -> h et h -> o trouvent leur signification dans l'ancêtre du parent gauche: substitution du lien s ₁ -> o .
Les gènes s ₁ -> h ₁ et h ₁ -> o dans le génotype du bon parent au temps T ₂ ont exactement la même signification. Le sort de nos ancêtres ne nous intéresse pas particulièrement - nous savons déjà avec quoi nous mélanger:



Comment écrire correctement l'histoire génétique, il sera possible de distinguer la prochaine fois, d'autant plus que nous avons quelques petites trouvailles dans ce domaine, elles sont associées à l'adaptation de la technique originale à un schéma de reproduction stable.

Il est temps d'arrêter. L'article a commencé avec Youtube - et nous le compléterons. Dans une version antérieure du simulateur, un collègue qui a écrit le code pour générer la piste l'a terminé avec rien, un abîme sans fond. La réaction d'un réseau de neurones qui a évolué depuis longtemps en présence d'un firmament terrestre sous roues à une telle conception de son petit univers peut peut-être s'appeler une «rupture de gabarit»:


Une vaste collection d'autres histoires anecdotiques de la vie des cybernaturalistes peut être trouvée dans [3] .

Les sources

[1] KO Stanley et R .. Miikkulainen, Evolving Neural Networks through Augmenting Topologies Evolutionary Computation, vol. 10, non. 2, pp. 99-127, 2002.
[2] C. Green, «A Review of Activation Functions in SharpNEAT», 19 juin 2017.
[3] J. Lehman et al, «The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities», arXiv: Neural and Evolutionary Computing, 2018.