Neuroevolution of augmenting topologies

NeuroEvolution of Augmenting Topologies (NEAT) is a genetic algorithm for the generation of evolving artificial neural networks (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").

Performance

On simple control tasks, the NEAT algorithm often arrives at effective networks more quickly than other contemporary neuro-evolutionary techniques and reinforcement learning methods.^[1][2]

Complexification

Ordinarily, a neural network topology is designed by a human experimenter, and a genetic algorithm is used to try out effective connection weights for it^{[citation needed]}. 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.

Implementation

The original implementation by Ken Stanley is published under the GPL. 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.

Extensions to NEAT

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

HyperNEAT 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.^[3] Each particle system weapon in the game is controlled by an evolved CPPN, similarly to the evolution technique in the NEAT Particles interactive art program.

See also

• Evolutionary Acquisition of Neural Topologies

References

1. ^ Kenneth O. Stanley and Risto Miikkulainen (2002). "Evolving Neural Networks Through Augmenting Topologies". Evolutionary Computation 10 (2): 99-127
2. ^ Matthew E. Taylor, Shimon Whiteson, and Peter Stone (2006). "Comparing Evolutionary and Temporal Difference Methods in a Reinforcement Learning Domain". GECCO 2006: Proceedings of the Genetic and Evolutionary Computation Conference.
3. ^ Erin J. Hastings, Ratan K. Guha, and Kenneth O. Stanley (2009). "Automatic Content Generation in the Galactic Arms Race Video Game ". IEEE Transactions on Computational Intelligence and AI in Games, volume 4, number 1, pages 245-263, New York: IEEE Press, 2009.

Bibliography

• Kenneth O. Stanley and Risto Miikkulainen (2002). "Evolving Neural Networks Through Augmenting Topologies". Evolutionary Computation 10 (2): 99–127. doi:10.1162/106365602320169811. PMID 12180173. http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf. 

• Kenneth O. Stanley and Risto Miikkulainen (2002). "Efficient Reinforcement Learning Through Evolving Neural Network Topologies". Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002). http://nn.cs.utexas.edu/downloads/papers/stanley.gecco02_1.pdf. 

• Kenneth O. Stanley, Bobby D. Bryant, and Risto Miikkulainen (2003). "Evolving Adaptive Neural Networks with and without Adaptive Synapses". Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC-2003). http://nn.cs.utexas.edu/downloads/papers/stanley.cec03.pdf. 

• Colin Green (2004). Phased Searching with NEAT: Alternating Between Complexification And Simplification. http://sharpneat.sourceforge.net/phasedsearch.html. 

• Kenneth O. Stanley, Ryan Cornelius, Risto Miikkulainen, Thomas D’Silva, and Aliza Gold (2005). "Real-Time Learning in the NERO Video Game". Proceedings of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE 2005) Demo Papers. http://www.cs.utexas.edu/users/nn/downloads/papers/stanley.aiide05demo.pdf. 

• Matthew E. Taylor, Shimon Whiteson, and Peter Stone (2006). "Comparing Evolutionary and Temporal Difference Methods in a Reinforcement Learning Domain". GECCO 2006: Proceedings of the Genetic and Evolutionary Computation Conference. http://www.cs.utexas.edu/~shimon/pubs/taylorgecco06.pdf. 

• Shimon Whiteson and Daniel Whiteson (2007). "Stochastic Optimization for Collision Selection in High Energy Physics". IAAI 2007: Proceedings of the Nineteenth Annual Innovative Applications of Artificial Intelligence Conference. http://www.cs.utexas.edu/~shimon/pubs/whitesoniaai07.pdf. 

Implementations

• Stanley's original and rtNEAT for C++
• JNEAT, NEAT 4J, ANJI for Java
• SharpNEAT for C#
• NEAT-Python for Python
• Encog for Java 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.