L'algorithme NEAT (de l'anglais Neuroevolution of augmenting topologies) est un algorithme génétique utilisé pour la génération de réseaux de neurones artificiels développé par Ken Stanley en 2002 lorsqu'il était à l'Université du Texas à Austin. L'algorithme consiste à modifier à la fois les paramètres de pondération et les structures des réseaux de neurones afin d'essayer de trouver un équilibre entre la performance des solutions obtenues et leur diversité. Il est basé sur trois techniques principales : suivre les modifications réalisées sur chaque gêne afin de permettre des croisements entre les différentes topologies, appliquer des mutations (l'évolution des espèces) pour conserver les innovations et développer les topologies pas-à-pas à partir de structures initiales simples ("complexification").
Performance
Sur de simples tâches de contrôle, l'algorithme NEAT arrive souvent à des réseaux efficaces plus rapidement que d'autres techniques de neuro-évolution récentes et méthodes d'apprentissage par renforcement.
Algorithme
Traditionnellement, la topologie du réseau de neurones est choisie expérimentalement par un humain et des valeurs efficaces des poids des connexions sont apprises grâce une procédure d'entrainement. Ceci entraîne une situation où un processus d'essai et d'erreur peut être nécessaire afin de déterminer une topologie appropriée. L'algorithme NEAT est un exemple d'une topologie et réseau de neurones à poids évolutifs qui essaie simultanément d'apprendre sur les valeurs des poids et d'une topologie appropriée pour un réseau de neurones.
Afin d'encoder le réseau dans un phénotype pour l'algorithme génétique, NEAT utilise un schéma d'encodage direct, ce qui signifie que chaque connexion et neurone est représenté explicitement. Cela est à mettre en contraste avec les schémas d'encodage indirect qui donnent les règles qui autorisent la construction du réseau, sans pour autant représenter explicitement chaque connexion et neurone, autorisant à une représentation plus compacte.
L'approche de NEAT commence de façon semblable à un perceptron avec un réseau de neurones à propagation avant qui ne comporte que des neurones d'entrée et de sortie. Comme l'évolution progresse par étapes, la complexité de la topologie du réseau peut évoluer soit en insérant un nouveau neurone sur le chemin de connexion ou en créant une nouvelle connexion entre des neurones (qui n'étaient pas précédemment connectés).
Conventions concurrentes
Le problème des conventions concurrentes apparaît lorsqu'il y a plus d'une façon de représenter l'information dans un phénotype. Par exemple, si un génome contient des neurones A, B et C qui sont représentés par [A B C], et si ce génome est croisé avec un génome identique (en termes de fonctionnalités) mais représenté par [C B A], le croisement peut donner un enfant avec des fonctionnalités manquantes, comme [A B A] ou [C B C]. L'algorithme NEAT résout ce problème en suivant l'historique des gênes par l'utilisation d'un nombre global d'innovation qui augmente à chaque fois que de nouveaux gênes sont ajoutés. Ainsi, quand un nouveau gêne est ajouté, le nombre d'innovation global est incrémenté et est assigné à ce nouveau gêne. Un nombre élevé assigné à un gêne signifie que celui-ci a été ajouté récemment. Pour une génération particulière, si deux mutations identiques ont lieu dans plus qu'une génome, elles obtiennent toutes deux le même nombre, mais au-delà le nombre de mutation restera inchangé indéfiniment.
Ces nombres d'innovation permettent à l'algorithme NEAT de faire correspondre les gênes qui peuvent être croisés entre eux.
Implémentation
L’implémentation originale de Ken Stanley a été publiée sous GPL. L’implémentation est basée sur Guile, un interpréteur GNU basé sur Scheme. Cette implémentation de NEAT est un point de départ conventionnel des implémentations de l'algorithme NEAT.
Extensions
rtNEAT
En 2003, Stanley a conçu une extension de NEAT qui permet à l'évolution de se produire en temps réel plutôt que par l'itération de générations comme le font la plupart des algorithmes génétiques. L'idée de base est de soumettre la population à une évaluation constante à l'aide d'un compteur de "durée de vie" pour chaque individu de la population. Lorsque la minuterie d'un réseau expire, sa mesure d'aptitude actuelle est examinée pour voir si elle se situe près du bas de la population, et si c'est le cas, elle est éliminée et remplacée par un nouveau réseau issu de deux parents très aptes. Une minuterie est fixée pour le nouveau réseau et il est placé dans la population pour participer aux évaluations en cours.
La première application de rtNEAT est un jeu vidéo appelé Neuro-Evolving Robotic Operatives. Dans la première phase du jeu, les joueurs déploient chacun de leur côté des robots dans un "bac à sable" et ils les forment à une certaine doctrine tactique souhaitée. Une fois qu'une collection de robots a été entraînée, une deuxième phase du jeu permet aux joueurs d'opposer leurs robots à des robots entraînés par les autres joueurs, afin de voir si leurs régimes d'entraînement ont bien préparé leurs robots au combat.
Élagage progressif
Une extension du NEAT de Ken Stanley, développée par Colin Green, ajoute un élagage périodique des topologies de réseau des solutions candidates pendant le processus d'évolution. Cet ajout répond à la crainte qu'une croissance automatisée illimitée ne génère une structure inutile.
HyperNEAT
HyperNEAT est spécialisé dans l'évolution des structures à grande échelle. Il était à l'origine basé sur la théorie des réseaux de production de motifs compositionnels et constitue un domaine de recherche actif.
cgNEAT
cgNEAT permet de faire évoluer le contenu de jeux vidéo en fonction des préférences de l'utilisateurs. Le premier jeu vidéo à mettre en œuvre cgNEAT est Galactic Arm Race (en), un jeu de tir spatial dans lequel les particules des armes évoluent de façon unique en fonction des statistiques d'utilisation du joueur.
odNEAT
odNEAT est une version en ligne et décentralisée de NEAT conçue pour les systèmes multi-robots. odNEAT est exécuté à bord des robots eux-mêmes pendant l'exécution de la tâche afin d'optimiser en permanence les paramètres et la topologie des contrôleurs à base de réseaux de neurones artificiels. De cette façon, les robots exécutant odNEAT ont la possibilité de s'adapter à des conditions changeantes et d'apprendre de nouveaux comportements pendant l'exécution de leurs tâches. Le processus d'évolution en ligne est mis en œuvre selon un modèle d'îlot physiquement distribué. Chaque robot optimise une population interne de solutions candidates (variation intra-île), et deux robots ou plus échangent des solutions candidates lorsqu'ils se rencontrent (migration inter-île). De cette façon, chaque robot est potentiellement autosuffisant et le processus évolutif capitalise sur l'échange de contrôleurs entre plusieurs robots pour une synthèse plus rapide de contrôleurs efficaces.
