Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Neuroevolution of augmenting topologies
open-in-new
<h2 id="performance">Performance</h2> <p>On simple control tasks, the NEAT algorithm often arrives at effective networks more quickly than other contemporary neuro-evolutionary techniques and <a href="/facts/Reinforcement_learning/NrgPPS0Q">reinforcement learning</a> methods, as of 2006.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> <h2 id="algorithm">Algorithm</h2> <p>Traditionally, a neural network topology is chosen by a human experimenter, and effective connection weight values are learned through a training procedure. This yields a situation whereby a trial and error process may be necessary in order to determine an appropriate topology. NEAT is an example of a topology and weight evolving artificial neural network (TWEANN) which attempts to simultaneously learn weight values and an appropriate topology for a neural network. </p><p>In order to encode the network into a phenotype for the GA, NEAT uses a direct encoding scheme which means every connection and neuron is explicitly represented. This is in contrast to indirect encoding schemes which define rules that allow the network to be constructed without explicitly representing every connection and neuron, allowing for more compact representation. </p><p>The NEAT approach begins with a <a href="/facts/Perceptron/ArxdkAC1">perceptron</a>-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. </p> <h3>Competing conventions</h3> <p>The competing conventions problem arises when there is more than one way of representing information in a phenotype. For example, if a genome contains neurons <i>A</i>, <i>B</i> and <i>C</i> and is represented by [A B C], if this genome is crossed with an identical genome (in terms of functionality) but ordered [C B A] crossover will yield children that are missing information ([A B A] or [C B C]), in fact 1/3 of the information has been lost in this example. NEAT solves this problem by tracking the history of genes by the use of a global innovation number which increases as new genes are added. When adding a new gene the global innovation number is incremented and assigned to that gene. Thus the higher the number the more recently the gene was added. For a particular generation if an identical mutation occurs in more than one genome they are both given the same number, beyond that however the mutation number will remain unchanged indefinitely. </p><p>These innovation numbers allow NEAT to match up genes which can be crossed with each other.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="implementation">Implementation</h2> <p>The original implementation by Ken Stanley is published under the <a href="/facts/GNU_General_Public_License/S75KhLSX">GPL</a>. It integrates with <a href="/facts/GNU_Guile/xsnGWQKV">Guile</a>, a GNU <a href="/facts/Scheme_(programming_language)/0aGdf3SC">scheme</a> interpreter. This implementation of NEAT is considered the conventional basic starting point for implementations of the NEAT algorithm. </p> <h2 id="extensions">Extensions</h2> <h3>rtNEAT</h3> <p>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. </p><p>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. </p> <h3>Phased pruning</h3> <p>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. </p> <h3>HyperNEAT</h3> <p class="note">Main article: <a href="/facts/HyperNEAT/LfeqWUSQ">HyperNEAT</a></p> <p><a href="/facts/HyperNEAT/LfeqWUSQ">HyperNEAT</a> is specialized to evolve large scale structures. It was originally based on the <a href="/facts/CPPN/kngo5bVD">CPPN</a> theory and is an active field of research. </p> <h3>cgNEAT</h3> <p>Content-Generating NEAT (cgNEAT) evolves custom video game content based on user preferences. The first video game to implement cgNEAT is <a href="/facts/Galactic_Arms_Race/lvR2S1kp">Galactic Arms Race</a>, a space-shooter game in which unique particle system weapons are evolved based on player usage statistics.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Each particle system weapon in the game is controlled by an evolved <a href="/facts/CPPN/kngo5bVD">CPPN</a>, similarly to the evolution technique in the <a href="/facts/NEAT_Particles/6IKgDqcN">NEAT Particles</a> interactive art program. </p> <h3>odNEAT</h3> <p>odNEAT is an online and decentralized version of NEAT designed for multi-robot systems.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> odNEAT is executed onboard robots themselves during task execution to continuously optimize the parameters and the topology of the artificial neural network-based controllers. In this way, robots executing odNEAT have the potential to adapt to changing conditions and learn new behaviors as they carry out their tasks. The online evolutionary process is implemented according to a physically distributed island model. Each robot optimizes an internal population of candidate solutions (intra-island variation), and two or more robots exchange candidate solutions when they meet (inter-island migration). In this way, each robot is potentially self-sufficient and the evolutionary process capitalizes on the exchange of controllers between multiple robots for faster synthesis of effective controllers. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Evolutionary_acquisition_of_neural_topologies/4Fnsp3hN">Evolutionary acquisition of neural topologies</a></li></ul> <h2 id="bibliography">Bibliography</h2> <ul><li>Kenneth O. Stanley & Risto Miikkulainen (2002). <a href="http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf">"Evolving Neural Networks Through Augmenting Topologies"</a> (PDF). <i>Evolutionary Computation</i>. 10 (2): 99–127. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.638.3910">10.1.1.638.3910</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1162%2F106365602320169811">10.1162/106365602320169811</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/12180173">12180173</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:498161">498161</a>.</li></ul> <ul><li>Kenneth O. Stanley & Risto Miikkulainen (2002). <a href="http://nn.cs.utexas.edu/downloads/papers/stanley.gecco02_1.pdf">"Efficient Reinforcement Learning Through Evolving Neural Network Topologies"</a> (PDF). <i>Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002)</i>.</li></ul> <ul><li>Kenneth O. Stanley; Bobby D. Bryant & Risto Miikkulainen (2003). <a href="http://nn.cs.utexas.edu/downloads/papers/stanley.cec03.pdf">"Evolving Adaptive Neural Networks with and without Adaptive Synapses"</a> (PDF). <i>Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC-2003)</i>.</li></ul> <ul><li>Colin Green (2004). <a href="http://sharpneat.sourceforge.net/phasedsearch.html">Phased Searching with NEAT: Alternating Between Complexification And Simplification</a> (Report).</li> <li>Kenneth O. Stanley; Ryan Cornelius; Risto Miikkulainen; Thomas D’Silva & Aliza Gold (2005). <a href="http://www.cs.utexas.edu/users/nn/downloads/papers/stanley.aiide05demo.pdf">"Real-Time Learning in the NERO Video Game"</a> (PDF). <i>Proceedings of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE 2005) Demo Papers</i>.</li></ul> <ul><li>Matthew E. Taylor; Shimon Whiteson & Peter Stone (2006). <a href="http://www.cs.utexas.edu/~ai-lab/pubs/GECCO06-matt.pdf">"Comparing Evolutionary and Temporal Difference Methods in a Reinforcement Learning Domain"</a> (PDF). <i>GECCO 2006: Proceedings of the Genetic and Evolutionary Computation Conference</i>.</li></ul> <ul><li>Shimon Whiteson & <a href="/facts/Daniel_Whiteson/vVuD5cm6">Daniel Whiteson</a> (2007). <a href="https://web.archive.org/web/20151028173703/http://www.aaai.org/Papers/AAAI/2007/AAAI07-292.pdf">"Stochastic Optimization for Collision Selection in High Energy Physics"</a> (PDF). <i>IAAI 2007: Proceedings of the Nineteenth Annual Innovative Applications of Artificial Intelligence Conference</i>. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/hep-ex/0607012">hep-ex/0607012</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2006hep.ex....7012W">2006hep.ex....7012W</a>. Archived from <a href="https://www.aaai.org/Papers/AAAI/2007/AAAI07-292.pdf">the original</a> (PDF) on 2015-10-28.</li></ul> <h2 id="implementations">Implementations</h2> <ul><li>Stanley's <a href="http://nn.cs.utexas.edu/soft-view.php?SoftID=4">original</a>, <a href="https://github.com/matheust3/mtNEAT">mtNEAT</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, and <a href="http://www.cs.utexas.edu/users/nn/keyword?rtneat">rtNEAT</a>, for <a href="/facts/C%252B%252B/Et0F2qn9">C++</a></li> <li><a href="https://cs.gmu.edu/~eclab/projects/ecj/">ECJ</a>, <a href="http://nn.cs.utexas.edu/soft-view.php?SoftID=5">JNEAT</a>, <a href="http://neat4j.sourceforge.net/">NEAT 4J</a>, <a href="http://anji.sourceforge.net/">ANJI</a>, for <a href="/facts/Java_(programming_language)/9ScgFyAL">Java</a></li> <li><a href="https://sharpneat.sourceforge.io/">SharpNEAT</a>, for <a href="/facts/C_Sharp_(programming_language)/UC2gxeyb">C#</a></li> <li><a href="http://multineat.com/features.html">MultiNEAT</a> (<a href="https://web.archive.org/web/20210515000059/http://multineat.com/features.html">MultiNEAT</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived 2021-05-15)) and <a href="https://github.com/matheust3/mtNEAT">mtNEAT</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, for <a href="/facts/C%252B%252B/Et0F2qn9">C++</a> and <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a></li> <li><a href="https://github.com/CodeReclaimers/neat-python">neat-python neat-python neat-python</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, for <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a></li> <li><a href="https://neuralfit.net/">NeuralFit</a> (inexact implementation) and <a href="https://pypi.python.org/pypi/neat-python/">neat-python</a>, for <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a></li> <li><a href="/facts/Encog/ofs2Uax8">Encog</a>, for <a href="/facts/Java_(programming_language)/9ScgFyAL">Java</a> and <a href="/facts/C_Sharp_(programming_language)/UC2gxeyb">C#</a></li> <li><a href="https://github.com/noio/peas">peas</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, for <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a></li> <li><a href="https://web.archive.org/web/20140425040155/http://rubyneat.com/">RubyNEAT</a>[<i>usurped</i>], for <a href="/facts/Ruby_(programming_language)/BeYSaPSR">Ruby</a></li> <li><a href="https://github.com/joshuadam/NEAT-JavaScript">NEAT-JavaScript</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, <a href="https://github.com/OptimusLime/neatjs">neatjs</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, <a href="https://github.com/wagenaartje/neataptic">Neataptic</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a> (inexact implementation), for <a href="/facts/JavaScript/XhhIIEsl">JavaScript</a></li> <li><a href="https://gitlab.com/onnoowl/Neat-Ex">[1]</a>, for <a href="/facts/Elixir_(programming_language)/vX1J3cgf">Elixir</a></li> <li><a href="https://github.com/BiagioFesta/EvolutionNet">EvolutionNet</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, for <a href="/facts/C%252B%252B/Et0F2qn9">C++</a></li> <li><a href="https://github.com/yaricom/goNEAT">goNEAT</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, for <a href="/facts/Go_(programming_language)/oWlsmAFJ">Go</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://web.archive.org/web/20231205130538/http://www.cs.ucf.edu/~kstanley/neat.html">The NEAT Users Page</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived 2023-12-05)</li> <li><a href="https://web.archive.org/web/20240618051618/http://eplex.cs.ucf.edu/">Evolutionary Complexity Research Group at UCF</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived 2024-06-18) – Ken Stanley's former research group</li> <li><a href="http://nerogame.org/">NERO: Neuro-Evolving Robotic Operatives</a> – an example application of rtNEAT</li> <li><a href="https://dl.acm.org/doi/10.1145/1810136.1810137">GAR: Galactic Arms Race</a> – an example application of cgNEAT</li> <li><a href="https://web.archive.org/web/20110725072615/http://picbreeder.org/">Picbreeder</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived 2011-07-25) – Online, collaborative art generated by CPPNs evolved with NEAT</li> <li><a href="https://web.archive.org/web/20181114121019/http://endlessforms.com/">EndlessForms</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived 2018-11-14) – A 3D version of Picbreeder, where you interactively evolve 3D objects that are encoded with CPPNs and evolved with NEAT</li> <li><a href="https://web.archive.org/web/20241224160241/http://beacon-center.org/blog/2012/08/13/evolution-101-neuroevolution/">BEACON Blog: Evolution 101: Neuroevolution</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived 2024-12-24)</li> <li><a href="https://www.youtube.com/watch?v=qv6UVOQ0F44">MarI/O - Machine Learning for Video Games</a>, a <a href="/facts/YouTube/db276jst">YouTube</a> video demonstrating an implementation of NEAT learning to play <i><a href="/facts/Super_Mario_World/azAJFo1r">Super Mario World</a></i></li> <li><a href="https://web.archive.org/web/20220210191421/http://gekkoquant.com/2016/03/13/evolving-neural-networks-through-augmenting-topologies-part-1-of-4/">Gekko Quant: Evolving Neural Networks through Augmenting Topologies</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived 2022-02-10) – A visual tutorial series on NEAT, including solving the classic pole balancing problem using NEAT in R</li> <li><a href="https://www.engadget.com/2015/06/17/super-mario-world-self-learning-ai/">Artificial intelligence learns Mario level in just 34 attempts</a> NEAT explained via MarI/O program</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Kenneth O. Stanley and Risto Miikkulainen (2002). "Evolving Neural Networks Through Augmenting Topologies". Evolutionary Computation 10 (2): 99-127 <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Kenneth O. Stanley and Risto Miikkulainen (2002). "Evolving Neural Networks Through Augmenting Topologies". Evolutionary Computation 10 (2): 99-127 <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Silva, Fernando; Urbano, Paulo; Correia, Luís; Christensen, Anders Lyhne (2015-09-15). "odNEAT: An Algorithm for Decentralised Online Evolution of Robotic Controllers". Evolutionary Computation. 23 (3): 421–449. doi:10.1162/evco_a_00141. hdl:10071/10504. PMID 25478664. S2CID 20815070. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> </ol>