# Neuroevolució de les topologies augmentants

NeuroEvolution of Augmenting Topologies (NEAT) és un algorisme genètic (GA) per a la generació de xarxes neuronals artificials en evolució (una tècnica de neuroevolució) desenvolupat per Kenneth Stanley i Risto Miikkulainen l'any 2002 mentre estava a la Universitat de Texas a Austin. Altera tant els paràmetres de ponderació com les estructures de les xarxes, intentant trobar un equilibri entre l'adequació de les solucions evolucionades i la seva diversitat. Es basa en l'aplicació de tres tècniques clau: el seguiment de gens amb marcadors històrics per permetre l'encreuament entre topologies, l'aplicació de l'especiació (l'evolució de les espècies) per preservar les innovacions i el desenvolupament de topologies de manera incremental a partir d'estructures inicials simples ("complexificant").

## Rendiment

En tasques de control senzilles, l'algoritme NEAT sovint arriba a xarxes efectives més ràpidament que altres tècniques contemporànies i mètodes d'aprenentatge de reforç neuroevolutius.

## Algorisme

Tradicionalment, un experimentador humà tria una topologia de xarxa neuronal i els valors de pes de connexió efectius s'aprenen mitjançant un procediment d'entrenament. Això produeix una situació en la qual pot ser necessari un procés d'assaig i error per determinar una topologia adequada. NEAT és un exemple de xarxa neuronal artificial en evolució de topologia i pes (TWEANN) que intenta aprendre simultàniament valors de pes i una topologia adequada per a una xarxa neuronal.
Per codificar la xarxa en un fenotip per a GA, NEAT utilitza un esquema de codificació directa que significa que cada connexió i neurona està representada explícitament. Això contrasta amb els esquemes de codificació indirecta que defineixen regles que permeten construir la xarxa sense representar explícitament cada connexió i neurona, permetent una representació més compacta.
L'enfocament NEAT comença amb una xarxa de feed-forward semblant a un perceptró de només neurones d'entrada i neurones de sortida. A mesura que l'evolució avança a través de passos discrets, la complexitat de la topologia de la xarxa pot créixer, ja sigui inserint una nova neurona en un camí de connexió o creant una nova connexió entre neurones (abans no connectades).

## Convencions competidores

El problema de les convencions en competència sorgeix quan hi ha més d'una manera de representar la informació en un fenotip. Per exemple, si un genoma conté neurones A, B i C i està representat per [ABC], si aquest genoma es creua amb un genoma idèntic (en termes de funcionalitat) però l'encreuament ordenat [CBA] donarà als nens als quals falta informació ([ABA] o [CBC]), de fet s'ha perdut 1/3 de la informació en aquest exemple. NEAT resol aquest problema fent un seguiment de la història dels gens mitjançant l'ús d'un nombre d'innovació global que augmenta a mesura que s'afegeixen nous gens. Quan s'afegeix un gen nou, el nombre d'innovació global s'incrementa i s'assigna a aquest gen. Així, com més gran sigui el nombre, més recentment s'ha afegit el gen. Per a una generació determinada, si es produeix una mutació idèntica en més d'un genoma, tots dos reben el mateix nombre, més enllà d'això, però, el nombre de mutació es mantindrà sense canvis indefinidament.
Aquests números d'innovació permeten a NEAT emparejar gens que es poden creuar entre si.

## Implementació

La implementació original de Ken Stanley es publica sota la GPL. S'integra amb Guile, un intèrpret d'esquemes GNU. Aquesta implementació de NEAT es considera el punt de partida bàsic convencional per a la implementació de l'algorisme NEAT.

## Extensions
### rtNEAT

L'any 2003, Stanley va idear una extensió de NEAT que permet que l'evolució es produeixi en temps real en comptes de la iteració de generacions tal com utilitzen la majoria dels algorismes genètics. La idea bàsica és posar la població sota avaluació constant amb un temporitzador "de tota la vida" a cada individu de la població. Quan caduca el temporitzador d'una xarxa, s'examina la seva mesura d'aptitud actual per veure si cau a prop de la part inferior de la població i, si és així, es descarta i se substitueix per una nova xarxa creada a partir de dos pares amb una bona condició física. S'estableix un temporitzador per a la nova xarxa i es col·loca a la població per participar en les avaluacions en curs.

### HyperNEAT

HyperNEAT està especialitzat per fer evolucionar estructures a gran escala. Originalment es va basar en la teoria CPPN i és un camp actiu d'investigació.

### cgNEAT

NEAT generador de contingut (cgNEAT) evoluciona el contingut de videojocs personalitzat en funció de les preferències de l'usuari. El primer videojoc que ha implementat cgNEAT és Galactic Arms Race, un joc de trets espacials en el qual s'evolucionen armes úniques del sistema de partícules en funció de les estadístiques d'ús dels jugadors. Cada arma del sistema de partícules del joc està controlada per un CPPN evolucionat, de manera similar a la tècnica d'evolució del programa d'art interactiu NEAT Particles.

## Referències

* ↑ «[https://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf Evolving Neural Networks through Augmenting Topologies]» (en anglès). [Consulta: 22 gener 2024].
* ↑ «Evolving Neural Networks through Augmenting Topologies | MIT Press Journals & Magazine | IEEE Xplore» (en anglès). [Consulta: 22 gener 2024].
* ↑ «A Systematic Literature Review of the Successors of “NeuroEvolution of Augmenting Topologies”» (en anglès). [Consulta: 22 gener 2024].
* ↑ «NNRG Projects - NEAT: Evolving Increasingly Complex Neural Network Topologies» (en anglès). [Consulta: 22 gener 2024].
* ↑ Papavasileiou, Evgenia; Cornelis, Jan; Jansen, Bart «A Systematic Literature Review of the Successors of "NeuroEvolution of Augmenting Topologies"». Evolutionary Computation, 29, 1, 2021, pàg. 1–73. DOI: 10.1162/evco_a_00282. ISSN: 1530-9304. PMID: 33151100.