NeuroEvolution of Augmented Topologies
Encyclopedia
NeuroEvolution of Augmenting Topologies (NEAT) is a genetic algorithm
for the generation of evolving artificial neural network
s (a neuroevolution
technique) developed by Ken Stanley in 2002 while at The University of Texas at Austin. It alters both the weighting parameters and structures of networks, attempting to find a balance between the fitness of evolved solutions and their diversity. It is based on applying three key techniques: tracking genes with history markers to allow crossover among topologies, applying speciation (the evolution of species) to preserve innovations, and developing topologies incrementally from simple initial structures ("complexifying").
methods.
is designed by a human experimenter, and a genetic algorithm is used to try out effective connection weights for it . The topology of the network remains unaltered.
The NEAT approach begins with a perceptron
-like feed-forward network of only input neurons and output neurons. As evolution progresses through discrete steps, the complexity of the network's topology may grow, either by inserting a new neuron into a connection path, or by creating a new connection between (formerly unconnected) neurons.
. It integrates with Guile
, a GNU scheme interpreter. This implementation of NEAT is considered the conventional basic starting point for implementations of the NEAT algorithm.
The first application of rtNEAT is a video game called Neuro-Evolving Robotic Operatives, or NERO. In the first phase of the game, individual players deploy robots in a 'sandbox' and train them to some desired tactical doctrine. Once a collection of robots has been trained, a second phase of play allows players to pit their robots in a battle against robots trained by some other player, to see how well their training regimens prepared their robots for battle.
is specialized to evolve large scale structures. It was originally based on the CPPN theory and is an active field of research.
interactive art program.
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
for the generation of evolving artificial neural network
Artificial neural network
An artificial neural network , usually called neural network , is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes...
s (a neuroevolution
Neuroevolution
Neuroevolution, or neuro-evolution, is a form of machine learning that uses evolutionary algorithms to train artificial neural networks. It is useful for applications such as games and robot motor control, where it is easy to measure a network's performance at a task but difficult or impossible to...
technique) developed by Ken Stanley in 2002 while at The University of Texas at Austin. It alters both the weighting parameters and structures of networks, attempting to find a balance between the fitness of evolved solutions and their diversity. It is based on applying three key techniques: tracking genes with history markers to allow crossover among topologies, applying speciation (the evolution of species) to preserve innovations, and developing topologies incrementally from simple initial structures ("complexifying").
Performance
On simple control tasks, the NEAT algorithm often arrives at effective networks more quickly than other contemporary neuro-evolutionary techniques and reinforcement learningReinforcement learning
Inspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
methods.
Complexification
Ordinarily, a neural network topologyNetwork topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
is designed by a human experimenter, and a genetic algorithm is used to try out effective connection weights for it . The topology of the network remains unaltered.
The NEAT approach begins with a perceptron
Perceptron
The perceptron is a type of artificial neural network invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt. It can be seen as the simplest kind of feedforward neural network: a linear classifier.- Definition :...
-like feed-forward network of only input neurons and output neurons. As evolution progresses through discrete steps, the complexity of the network's topology may grow, either by inserting a new neuron into a connection path, or by creating a new connection between (formerly unconnected) neurons.
Implementation
The original implementation by Ken Stanley is published under the GPLGNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
. It integrates with Guile
GNU Guile
GNU Guile is an interpreter/virtual machine for the Scheme programming language. It was first released in 1993. Guile includes modularized extensions for POSIX system calls, APL array functionality, and others packaged as an object library...
, a GNU scheme interpreter. This implementation of NEAT is considered the conventional basic starting point for implementations of the NEAT algorithm.
rtNEAT
In 2003 Stanley devised an extension to NEAT that allows evolution to occur in real time rather than through the iteration of generations as used by most genetic algorithms. The basic idea is to put the population under constant evaluation with a "lifetime" timer on each individual in the population. When a network's timer expires its current fitness measure is examined to see whether it falls near the bottom of the population, and if so it is discarded and replaced by a new network bred from two high-fitness parents. A timer is set for the new network and it is placed in the population to participate in the ongoing evaluations.The first application of rtNEAT is a video game called Neuro-Evolving Robotic Operatives, or NERO. In the first phase of the game, individual players deploy robots in a 'sandbox' and train them to some desired tactical doctrine. Once a collection of robots has been trained, a second phase of play allows players to pit their robots in a battle against robots trained by some other player, to see how well their training regimens prepared their robots for battle.
Phased Pruning
An extension of Ken Stanley's NEAT, developed by Colin Green, adds periodic pruning of the network topologies of candidate solutions during the evolution process. This addition addressed concern that unbounded automated growth would generate unnecessary structure.HyperNEAT
HyperNEATHyperNEAT
Hypercube-based NEAT, or HyperNEAT, is a generative encoding that evolves artificial neural networks with the principles of the widely used NeuroEvolution of Augmented Topologies algorithm. It is a novel technique for evolving large-scale neural networks utilizing the geometric regularities of...
is specialized to evolve large scale structures. It was originally based on the CPPN theory and is an active field of research.
cgNEAT
Content-Generating NEAT (cgNEAT) evolves custom video game content based on user preferences. The first video game to implement cgNEAT is Galactic Arms Race, a space-shooter game in which unique particle system weapons are evolved based player usage statistics. Each particle system weapon in the game is controlled by an evolved CPPN, similarly to the evolution technique in the NEAT ParticlesNEAT Particles
NEAT Particles is an Interactive evolutionary computation program that enables users to evolve particle systems intended for use as special effects in video games or movie graphics. Rather than being hand-coded like typical particle systems, the behaviors of NEAT Particle effects are evolved by...
interactive art program.
Implementations
- Stanley's original and rtNEAT for C++C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
- JNEAT, NEAT 4J, ANJI for JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
- SharpNEAT for C#
- NEAT-Python for PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
- EncogEncogEncog is a neural network and artificial intelligence framework available for Java, .Net, and Silverlight. Encog contains classes to create a wide variety of networks, as well as support classes to normalize and process data for these neural networks. Encog trains using many different techniques. ...
for JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and C#
External links
- NEAT Homepage
- "Evolutionary Complexity Research Group at UCF" - Ken Stanley's current research group
- NERO: Neuro-Evolving Robotic Operatives - an example application of rtNEAT
- GAR: Galactic Arms Race - an example application of cgNEAT
- "PicBreeder.org" - Online, collaborative art generated by CPPNs evolved with NEAT.
- "EndlessForms.com" - A 3D version of Picbreeder, where you interactively evolve 3D objects that are encoded with CPPNs and evolved with NEAT.