The NeuroEvolution of Augmenting Topologies (NEAT) Users Page

Now there is a HyperNEAT Users Page too!

Last Updated 5/5/15 (list of updates)

I created this page because of growing interest in the use and implementation of the NEAT method. I have been corresponding with an expanding group of users. Because the same points come up more than once, it makes sense to have a place where people can come and tap into the expanding knowledge we have about the software and the method itself.

I continue to support the NEAT community from my new position as an assistant professor at the University of Central Florida in the School of Electrical Engineering and Computer Science, where my research continues as director of the Evolutionary Complexity Research Group (EPlex).

We also developed an extension to NEAT called HyperNEAT that can evolve neural networks with millions of connections and exploit geometric regularities in the task domain. The HyperNEAT Page includes links to publications and a general explanation of the approach.

New! So that the record of how I thought of NEAT is not lost, I have made available copies of the original notes from January 2000 where I first thought of NEAT. It turns out that I unintentionally documented my own thinking process when I thought of NEAT because I was scribbling notes about it as I thought it through. These are those notes, with some commentary to explain what I was thinking about.

Tutorial Available: Wesley Tansey has provided a helpful tutorial on setting up a Tic-Tac-Toe experiment in SharpNEAT 2. It should be instructive for anyone aiming to create an experiment in SharpNEAT.

-Kenneth Stanley

Want to see NEAT used in a video game? Check out Galactic Arms Race or NERO.

Contents

Introduction - Which version of NEAT should you use?

NEAT Users Group - Join the group to discuss your projects

Book available with step by step chapter on NEAT

NEAT Software FAQ - Questions that mostly relate to coding issues or using the actual software.

General NEAT Methodology FAQ - More broad questions regarding general methodology or philosophy behind NEAT.

NEAT Users and Projects

The Future of NEAT

NEAT Publications

Introduction

This page is intended for NEAT users, particularly those using one of the available versions of NEAT or writing a version of their own. Over the past few years, several versions of NEAT have become available for different platforms and languages. The remainder of this introduction will introduce the available software, and attempt to help the user choose the right package for his or her needs. The current crop of NEAT software is available at:

The NEAT Software Catalog

The question for many people first coming to NEAT is which package is right for me? There are several factors to consider:

First, how closely does the package you want follow my (Ken's) original NEAT source code? For most people this won't be a big issue, since all the packages work. However, if you want to strictly reproduce my experimental results, you may want the most faithful code available. For this purpose, either my original version or Ugo Vierruci's JNEAT are probably the best choices, since JNEAT was written directly off of my original C++ source code.

Second, what is your favorite platform? If you prefer Linux, my C++ version is appropriate. If you prefer Windows, Mat Buckland's C++ would be better. Since Java and Matlab run on all platforms, if you want to use Java or Matlab, platform is not a consideration. SharpNEAT, written in C#, can also run on either platform.

Third, what language do you prefer? Since NEAT is available in C++, Java, Matlab, Delphi, and C#, there are now several choices.

Fourth, what experiments would you like built in? JNEAT, Matlab NEAT, SharpNEAT, ANJI, and the original NEAT C++ all come with XOR. The original NEAT C++ and SharpNEAT also come with pole balancing. Windows NEAT C++ comes with a nice graphical minesweeper demo. Delphi NEAT has some entertaining 3D robot control experiments. SharpNEAT includes an incremental predator/prey experiment. ANJI comes with Tic Tac Toe. If you are planning a new experiment, it may be helpful to look at the code for similar experiments.

Your best option will be based on some combination of the above considerations. Of course, if you want NEAT for platform X or language Y and they aren't available, you may want to write your own version of NEAT. I am happy to hear about such projects so you should let me know what you're thinking of. I can give you advice or point you to any similar projects you may not be aware of.

NEAT Users Discussion Group

Derek James created a NEAT Users Group on Yahoo to encourage the discussion of ideas, questions, and variations of NEAT. The community of NEAT users and those interested in NEAT can benefit greatly from the availability of this forum. Please feel free to join the discussion!

Paperback Book Available with Chapter on NEAT

For people who are interested in learning about NEAT, but prefer explanations intended for general audiences to reading research-level papers, I am happy to recommend AI Techniques for Game Programming by Mat Buckland. Most of the final chapter of this book describes NEAT in a fun and simple style. The book also comes with source code. This book is a good resource for hobbyists or video game programmers interested in AI techniques. (Researchers should still refer to the NEAT research publications available below.) It also includes useful introductions to genetic algorithms and neural networks. Note that coding questions in the FAQ on this page refer to my own source code release and not the code in this book, though some answers may still be useful.

NEAT Software FAQ

Please note: In general, most answers refer to the original C++ code intended for Linux, which I wrote myself. The Java code, written by Ugo Vierucci , was made to follow the C++ code faithfully, so most answers will apply to the Java version as well. However, pole balancing experiments are not included in the Java version so any questions on pole balancing will not apply to JNEAT. Mat Buckland's Windows version and also Christian Mayr's Matlab version were written independently. Therefore, code-related answers below probably do not apply to the Windows or Matlab distributions.

• What is NEAT?
  

  NEAT stands for NeuroEvolution of Augmenting Topologies. It is a method for evolving artificial neural networks with a genetic algorithm. NEAT implements the idea that it is most effective to start evolution with small, simple networks and allow them to become increasingly complex over generations. That way, just as organisms in nature increased in complexity since the first cell, so do neural networks in NEAT. This process of continual elaboration allows finding highly sophisticated and complex neural networks.
  
  

• Will you release NEAT software?
  

  Yes, a number of versions of NEAT are available. Please see the Introduction.
  
  

• When is the next version coming out?
  

  I don't have a specific software development schedule since I am mostly focused on research. I will post notification when new versions become available. Note that a number of independent projects are ongoing, so other people may also be releasing their own versions of NEAT. I will try to make all such releases available through this page. The NEAT Users Group also has new code posted occasionally.
  
  

• Can you notify me about updates?
  

  There are currently a fair amount of people working on new NEAT software and/or experiments. To keep up to date, I suggest periodically checking this page, and also joining the NEAT Users Group run by Derek James. You can also e-mail me with software-related questions.

• Does NEAT have documentation?
  

  Yes, a 17 page documentation file is included in the original (and now out-of-date) C++ software release. The more current NEAT C++ release is at http://nn.cs.utexas.edu/?neat-c However, the documentation may still be helpful.

  The Java version has its own documentation in a readme file, as well as a quickstart file. The Java version is easier to get started with and has a nice GUI. The C++ version has more experiments included, and a GUILE scripting interface.

  If you want to understand NEAT as a software package, I suggest reading the documentation in the C++ distribution whether or not you ultimately choose to use Java. That doc file will give you a good idea of how to design your own experiments in NEAT.

  The Windows version comes with a short ReadMe about running the minesweeper experiment that it comes with. However, you will have to look directly to the source code of that distribution to answer coding-related questions. You can also e-mail its author, Mat Buckland.

  The Matlab version also comes with a short README. A FAQ may eventually be made available.
  
  

• What are traits and how can I use them?
  

  This question refers to my C++ release of NEAT, which has a vector of "traits" in each genome. (JNEAT also has traits.)

  If you read the 17-page documentation, I mention that traits are not used in this release version of NEAT. Traits are reserved for future use. I built them in from the start to support some expansions I have in mind. In other words, they can be ignored and have no effect on anything.

  However, any genome must have at least 1 trait (look at xorstartgenes for example, which has 3 dummy traits) in order to be valid. (In other words, if you create a starter (spawning) genome for some new experiment, it should have at least one trait, even though that trait means nothing.)
  
  

• You say traits are reserved for future use. What will they be used for?
  

  In the future, traits will allow the system to evolve highly complex neural models, much more sophisticated than the simple sigmoidal neurons currently used. The neurons will be able to evolve plasticity parameters (like real neurons in the brain) by pointing to a trait that describes the plasticity of the neuron. The details will be made available as the related research proceeds.

  New: Preliminary work with traits and synaptic plasticity has already been completed and is now reported in this paper.
  
  

• How are networks with arbitrary topologies activated?
  

  The activation function, bool Network::activate(), gives the specifics. The implementation is of course considerably different than for a simple layered feedforward network. Each node adds up the activation from all incoming nodes from the previous timestep. (The function also handles a special "time delayed" connection, but that is not used by the current version of NEAT in any experiments that we have published.) Another way to understand it is to realize that activation does not travel all the way from the input layer to the output layer in a single timestep. In a single timestep, activation only travels from one neuron to the next. So it takes several timesteps for activation to get from the inputs to the outputs. If you think about it, this is the way it works in a real brain, where it takes time for a signal hitting your eyes to get to the cortex because it travels over several neural connections.
  
  

• Can you explain some of the NEAT Parameters?
  

  Explaining all the NEAT parameters can be tricky because there are so many different versions of NEAT. There are often subtle differences in meaning among these parameters from one version to another, even if they have the same name. However, it can still help to give a general idea what a certain set of parameters mean. Therefore, I am posting here a copy of an answer from the NEAT Users Group to one such question that explains some (though not all) parameters. While the particulars may not be exactly like your NEAT implementation, they may still help to clarify some general questions:

  > DisjointCoefficient 2.0 [?]
  > ExcessCoefficient 2.0 [?]
  > WeightDifferenceCoefficient 1.0 [?]
  

  These are the standard NEAT compatibility coefficients for the compatibility equation the determines how far apart two individuals are for the purposes of speciation. In general, the question is how many gene differences are worth an average distance of 1.0 in weights. The numbers above say that an average difference of 1.0 in weights is like having two genes not shared between the two individuals. That is pretty reasonable.

  > CompatibilityThreshold 6.0 [?]

  This parameter relates to the coefficients above. It can be thought of as, how many genes not shared does it take for individuals to be considered in a different species. However, it is only relevant at the start because the next parameter lets it change.

  > CompatibilityModifier 0.3 [?]

  This number means the threshold changes at a rate of 0.3 per generation, which is reasonable. It does not change if the SpeciesSize Target is already met.

  > DropoffAge 15.0 [?]

  In 15 generations a species will be penalized if it is not making progress.

  > SurvivalThreshold 0.2 [?]

  Only the top 20% of each species is allowed to reproduce. Controls greediness within species.

  > MutationPower 2.5 [?]

  Mutations of weight go up to 2.5 in a single mutation. You wouldn't want it over 5.0 or so.

  
  
  
• How do I compile your Linux version of NEAT in such and such operating system?
  

  As I get specific information from users about how they compiled under specific systems, I will post the information under this question. In the meantime, I have only used NEAT in Debian and Red Hat Linux, and cannot comment on other systems. Clearly, the INCLUDES and LIBS must be significantly altered to reflect the organization of your version of Linux or Unix.

  New: Linux NEAT in Windows: Darren Izzard wrote the following about compiling my C++ version of NEAT (which I wrote for Linux) under Windows:

  "I have compiled your C++ version of NEAT under Windows using Cygwin without much difficulty. I removed the visualization code, and, as you might expect, INCLUDES and LIBS needed modifying a little.

  The version of SWIG I'm using is 1.3.16 and there were two main steps getting it to work:-
  1. Change glist() to SWIG_init() as mentioned on your site
  2. Insert the following lines in neatswig.i at some point between the %} line and the class declarations:
  %nodefault Population
  %nodefault Network
  

  The output seems to require no editing, and in fact I have reinstated the wrapper-generating lines in the Makefile. (nb. "cp neatswig_wrap.c neatswig_wrap.cpp" needs changing to "cp neatswig_wrap.cxx neatswig_wrap.cpp" for 1.3.16.)"
  
  

• What are "stolen babies?"
  

  You will notice a portion of the Population::epoch() method that deals with babies_stolen. Babies stolen is something in the code that we never used in experiments described in the papers. Babies stolen takes offspring away from bad species and distributes them among the best species. In other words, it makes the search more greedy. It can speed up solutions on some problems. The more babies stolen, the more biased the search. There is a global system parameter you can set in the ".ne" files called "babies_stolen." Any number above 0 will cause the system to "steal" offspring rights from the poorer species and redistribute them to the better species. The standard algorithm works fine with babies_stolen=0. You can try setting it higher to see if it enhances performance.
  
  

• I want to rewrite NEAT in a new programming language. Would you be interested?

  Absolutely. Let me know your plans! Remember, NEAT already exists in C++, Java, and Matlab, and a Delphi version is partially available.
  
  

• How should I test my own version of NEAT to make sure it works?

  Most people choose XOR as their first test. XOR is very simple and does not make a very interesting scientific experiment; however, it is a good way to check whether your system works. Here are some things to consider if you are testing with XOR and not finding a solution:

  • Make sure recurrency is disabled for the XOR test. If NEAT is able to add recurrent connections, it may solve XOR by memorizing the order of the training set. (Which is why you may even want to randomize order to be most safe) All documented experiments with XOR are without recurrent connections. Interestingly, XOR can be solved by a recurrent network with no hidden nodes.
  • Most people report XOR is easier to solve with a steepened gain on the sigmoid function.
  • Some have suggested that a weight cap can help, though I haven't had a problem solving XOR without a weight cap myself.
  • Be careful about what you consider a 1 and what you consider a 0 and how they are penalized/rewarded. I generally said < 0.5 is 0 and >= 0.5 is 1 for the purposes of a solution. However, for the purposes of fitness, the distance from the actual output to the intended output is used, which provides a gradient. For example 0.9 is 0.1 away from 1. Most people use sum squared error.
  • The weight mutation power is important. You may want to fiddle with it a bit because sometimes it is too low or too high when you first set up the system. Also, some people like to use uniform mutation distributions and others use normal distributions, and the two distributions may benefit from different mutation powers.
  • If you decide to use the species compatibility coefficients and thresholds from my own .ne settings files (provided with my NEAT release), then do not normalize the terms in the compatibility function, because I did not do this with my .ne files. In other words, even though my papers suggest normalizing (dividing my number of genes), since I didn't do that the coefficients that I used will not work the same for you if you normalize. If you strongly desire to normalize, you will need to find your own appropriate coefficients and threshold.
  • Please let me know if you remember any of your own problems that you eventually fixed when you were expeirmenting with XOR.

  Thanks to Bryan Adams, Derek James, John Arrowwood, and Colin Green for providing input about this question
  
  

• I can get xor_test and pole1_test working but pole2_test does not work. What's going on?
  

  You probably have the wrong starter genome in the file pole2startgenes. In the documentation it mentions this, but it is a confusing aspect of the distribution.

  There are 2 different kinds of pole2_test experiments: the markov and the non-markov. They both use a different starter genome, because the non-markov one uses fewer sensors. However, the pole2_test always reads from the file "pole2startgenes," no matter which version of the experiment you run.

  That means the correct version must be copied into pole2startgenes before you begin. Notice there are two files, "pole2startgenes1" and "pole2startgenes2." pole2startgenes1 has the right genes for the markovian test, whereas pole2startgenes2 has the non-markovian version. So, for example, you have to do:

  % cp pole2startgenes1 pole2startgenes

  if you are running the markovian version.

  Of course, when you run the Markov version (which takes 7 inputs) and run it with the 4 input non-markov network, it can never solve the problem and only gets up to about 60 steps.
  
  

• I am trying to write my own speciation code and I can't get it to work! Help!
  

  Well, this could mean a lot of things, but the NEAT software may be a good reference point for you. Also, you may be having trouble with getting the right parameters. Take a look at some of the ".ne" files to see good parameters for speciation. Also, please see the next question, which may give you some helpful ideas.
  
  

• Is there a way to automatically set the compatibility threshold for speciation? (IMPORTANT)
  

  Yes, and this technique may be crucial for problems that take hundreds of generations or more. This technique keeps the number of species stable in NEAT. There is some commented-out code in Population::epoch that adjusts the compatibility threshold up or down depending on whether you have fewer or more than a specified target number of species::

  //We can try to keep the number of species constant at this number
  int num_species_target=10;
  int num_species=species.size();
  double compat_mod=0.3; //Modify compat thresh to control speciation
  
  //Keeping species diverse
  //This commented out code forces the system to aim for
  // num_species species at all times, enforcing diversity
  //This tinkers with the compatibility threshold, which
  // normally would be held constant
  if (generation>1) {
  if (num_species<num_species_target)
  compat_threshold-=compat_mod; //compat_mod works well at about 0.3
  else if (num_species>num_species_target)
  compat_threshold+=compat_mod;
  
  if (compat_threshold<0.3) compat_threshold=0.3;
  }
  

  This dynamic thresholding allows NEAT to control the number of species, saving you from needing to guess the right threshold for your experiment. (Although you must still specify a reasonable number of species for your population size.) Uncomment this code in genetics.cpp in order to get the benefits of dynamic thresholding.

• Too many genes are becoming disabled! What should I do?
  

  If you have the mutate_toggle_enable_prob too high (in your .ne file), this an obvious culpit.

  Otherwise, it may be that your task surprisingly doesn't need all the inputs you are providing it. NEAT may have discovered this and disabled a lot of genes in order to get rid of those useless inputs.

  It is still possible that somehow, NEAT prematurely discovered genes that it disabled to get some early gains, but is having trouble making progress beyond that point because those genes turned out to be needed in the long run. In such a situation (which I have found to be rare) you may want to edit the mating code such that disabled genes are only disabled in the offspring if they are disabled in the more fit parent. This fix will keep the disabling of genes to a minimum.

  Note that genes in NEAT often become reenabled in mating, because there is a built-in probability that genes will become reenabled during mating even if they are disabled in one or more parent.

  One user suggested that instead of disabling genes, they can be reset to a 0 weight, and gradually climb back into significance. I have not tried this idea but you may want to play with it if you have time.

• NEAT takes up too much memory. Can I save memory somehow?
  

  Yes. Look at this constructor inside the Organism class (from the C++ code; the Java code should be similar):

  Organism(double fit, Genome *g,int gen) {
  fitness=fit;
  orig_fitness=fitness;
  gnome=g;
  net=gnome->genesis(gnome->genome_id);
  species=0; //Start it in no Species
  expected_offspring=0;
  generation=gen;
  eliminate=false;
  error=0;
  winner=false;
  champion=false;
  super_champ_offspring=0;
  
  //DEBUG vars
  pop_champ=false;
  pop_champ_child=false;
  high_fit=0;
  mut_struct_baby=0;
  mate_baby=0;
  }
  

  Note the line: net=gnome->genesis(gnome->genome_id); What this means is that as soon as an organism is created (inside the reproduce method) with its constructor, its respective network is also created through genesis. In other words, all phenotypes are represented in memory simultaneously, even though they don't have to be. In most cases, you only need 1 phenotype (network) represented in memory at a time, at the time of evaluation.

  Therefore, you simply need to change the constructor and comment out the genesis line. Instead, perform genesis immediately preceding evaluation of an organism, and then, immediately after that, delete the network. Thus, networks are created and destroyed serially, freeing up an enormous amount of space. You will notice 50-75% memory usage reductions. (The next release of NEAT will work this way, but it's easy enough to edit the code in the version you have. Note that the provided experiments in general do not take up very much memory and thus won't need this fix. However, if you are using massive populations or working in high-dimensional domains, it may help you a lot!)

• How do I get SWIG to work?
  

  First, download the latest version. If you are still having problems, make sure you read the SWIG-related documentation in the 17-page doc file that came with C++ NEAT.

  SWIG is buggy in my experience. You may have to play around to get casts right and functions names may change with different versions. Different C++ compilers may react differently to the same SWIG code.

  One important problem that has been pointed out: SWIG may replace underscores "_" with hyphens "-", causing great confusion! If you are trying to run "pole2_test", for example, and it is not working, SWIG may have changed the name to "pole2-test." The following also may help (from a NEAT user who had SWIG problems):

  "The version of SWIG I have generates a function called SWIG_init() instead of glist(). I've replaced the code in neatmain.cpp with the following, and now it compiles":

  extern "C" {
  extern void SWIG_init(void);
  };
  
  void
  main_prog(int argc, char *argv[])
  {
  SWIG_init();
  scm_shell(argc, argv);
  }
  

• How do I ensure that a network stabilizes before taking its output(s) for a classification problem?
  

  The cheap and dirty way to do this is just to activate n times in a row where n>1, and hope there are not too many loops or long pathways of hidden nodes.

  The proper (and quite nice) way to do it is to check every hidden node and output node from one timestep to the next, and see if nothing has changed, or at least not changed within some delta. Once this criterion is met, the output must be stable.

  Note that output may not always stabilize in some cases. Also, for continuous control problems, do not check for stabilization as the network never "settles" but rather continuously reacts to a changing environment. Generally, stabilization is used in classification problems, or in board games.

• Why is there no hard bound to the maximum and minimum possible connection weight strengths?
  Please note: The short answer to this question is that there really should be a bound.

  The mutation strength itself basically causes a natural soft bound to arise on its own. By imposing your own bounds, you may have created a range that is intolerant to the strength of your mutation operator. Note that it is the relative strengths of weights that matters towards creating their functionality, so no bound is necessary. However, networks with low bounds on weights will tend to produce smoother output (i.e. numbers between 0 and 1 rather than only 0 and 1). If you must have a bound, you need to be careful it is high enough to allow several weight mutations to carry you from 0 to either the higher or lower bound (you don't want your smallest mutations to cause radical relative differences). In very long evolutionary runs (say 500 or more generations), a limit may be helpful in preventing some connections from becoming so powerful that new connections cannot hope to compete. It is a simple matter to put in hard bounds if you desire.

  Here is some code to put in bounds. It can be inserted at the end of mutate_link_weights:

  //Cap the weights at 8.0 (experimental)
  if (((*curgene)->lnk)->weight>8.0) ((*curgene)->lnk)->weight=8.0;
  else if (((*curgene)->lnk)->weight<-8.0) ((*curgene)->lnk)->weight=-8.0;
  
  

• Are there any heuristics for deciding on the weight mutation rate?
  

  Preliminary experiments indicate that high weight mutation rates (i.e. 50% or more) are useful for control tasks, but lower rates (i.e. under 1%) are more appropriate for high input games like Othello. It may be that the number of inputs is the critical factor, and that low-input tasks respond better to high mutation weights. Although I do not have concrete statistics from which to draw strong conclusions, a good rule of thumb is to change the weight mutation rate if the systems seems to be performing below expectations.
  
  

• Can the speciation code be made more efficient?
  

  Since the NEAT algorithm in general takes up far less computation time than the actual evaluations in the task, improving the code's efficiency is not an urgent need. However, there is a clever way to make speciation faster. Thanks to Mattias Fagerlund for this idea:

  "If you add a species hint to your individuals, speciation runs much faster. When a child is created, copy the species of the mother into the species_hint of the child. When it's time to place the child in a species, first try the species hint. If the child belongs there, then we're ready. If it doesn't test all species and pick the first species that's compatible. Since the speciating events are few and far between, each individual will be tested against 1 species instead of maybe 13-30 species. If the number of species is great, the saving can be great too."
  
  

• Can I start NEAT with some inputs disconnected? (IMPORTANT)
  

  The reason this question is important is that if we can start NEAT with some inputs disconnected, then we can allow NEAT to decide which inputs are important. This process has two good effects: (1) You can start minimally even in problems with many inputs and (2) you don't need to know a priori what the important features of the domain are. Recent results (2005) reported in this paper suggest that this approach can be quite effective.

  Unfortunately, my C++ version of NEAT, Ugo's JNEAT, and possibly other versions cannot automatically start this way, even if given a genome with some nodes disconnected. The reason is that in crossover, NEAT was originally designed to drop nodes that aren't connected to the network. Therefore all the disconnected inputs would be lost forever.

  However, NEAT can easily be fixed to allow starting this way. All that needs to be done is to insert some code into the mating routines that ensures all nodes get inserted into the offspring's genome:
  
  //NEW: Make sure all sensors and outputs are included
  for(curnode=(g->nodes).begin();curnode!=(g->nodes).end();++curnode)
  {
  if ((((*curnode)->gen_node_label)==INPUT)||
  (((*curnode)->gen_node_label)==BIAS)||
  (((*curnode)->gen_node_label)==OUTPUT)) {
  if (!((*curnode)->nodetrait)) nodetraitnum=0;
  else
  nodetraitnum=(((*curnode)->nodetrait)->trait_id)-(*(traits.begin()))->trait_id;
  
  //Create a new node off the sensor or output
  new_onode=new NNode((*curnode),newtraits[nodetraitnum]);
  
  //Add the new node
  node_insert(newnodes,new_onode);
  
  }
  
  }
  
  In my C++ code, this must be placed in mate_multipoint, mate_multipoint_avg, and mate_singlepoint. (Note that in general no one uses mate_singlepoint so if you don't use it, you don't need to worry about it.) A similar piece of code would need to be inserted into JNEAT's corresponding functions.

  The place to put the code in mate_multipoint is right after the section starting with the comment, "Figure out which genome is better," that ends with "else p1better=false." (Near the beginning of mate_multipoint.) In mate_multipoint_avg, it should be placed after the line "avgene=new Gene(0,0,0,0,0,0,0);".

  The insertion of this code will now allow you to start with genomes with some inputs disconnected, and NEAT will add inputs as it sees fit!

  Additional code: One nice mutation which that be helpful if you start with some sensors disconnected is an add_sensor mutation, which immediately connects a randomly chosen sensor which was previously disconnected to all the outputs at once. That way, the sensor can be fully integrated immediately. Here is Java code for JNEAT by Shimon Whiteson and C++ code for Ken's original NEAT (translated from Shimon's code by Ken) that give NEAT this new kind of mutation. Note that the call for this mutation still must be added to Species::reproduce in order for NEAT to use it!

  More information: The newer rtNEAT code distirbution includes the above fixes. However, Peter Chervenski notes an additional possible problem and its fix:
  Consider a network with no genes at all - where even a single link does not exist. In the first few generations, there are such networks - due to the very small probability for adding a link. When mutate_add_node() is called for such a genome, something happens or it just tries to traverse the genes vector, but there is nothing to be split. So I added this line of code (before everything in the function):
  
  // there is no link to split
  if (this->genes.size() == 0) return false;
  
  

General NEAT Methodology FAQ

This FAQ addresses questions that are more abstract or philosophical in nature.

• Can you tell me more about speciation and how your method of speciation compares to other methods?
  

  If you look in the references section of our paper, you will notice a reference to "Mahfoud," which you can get off of Citeseer. This dissertation is probably the single best review of speciation methods that exists.

  That said, the history of speciation is mostly in the area "Multi-modal function optimization," where evolution is looking for multiple solutions at the same time. For example, you might want to find several optima for a problem, or several solutions that can work together to form a supersolution.

  In contrast, NEAT uses it for a much different purpose, which is protecting innovation. You might wonder why no one has used speciation for this purpose in neuroevolution before (in fact, I am not sure if it has been used explicitly for this purpose at all in the past). The reason is that neural networks previously seemed virtually impossible to compare, particularly when their topologies differed. In order to speciate, there needs to be some distance metric, but if you have no idea how two genomes compare with one another, there is no hope for comparison. Historical markings suddenly made comparison easy, changing the entire problem. In addition, perhaps people did not identify the need for speciation in neuroevolution.

  You may want to know why we used speciation over the Island model (or any other model- many exist). The answer is that speciation is very natural- it is much the way it works in the real world. The main point is that in our speciation model, species arise for intrinsic reasons. In other words, the species "just pop up on their own," naturally, rather than being imposed extrinsically, from the outside, as in the island model. No one knows what species or how many species should arise, so NEAT lets evolution sort it out. If a new species appears, the system detects it and separates it out. If a species gets good, NEAT lets it grow relative to other species. This is opposed to models where the programmer decides what the species are, how big they are, etc..
  
  

• Is NEAT similar to the GEP method of Genetic Programming?
  

  A description of the GEP method can be found here . The paper is referenced:

  Ferreira, C., (2001). Gene Expression Programming: A New Adaptive Algorithm for Solving Problems, Complex Systems, 13 (2): 87 - 129.

  I will contrast the methods. GEP evolves program trees while NEAT evolves neural networks, but since both evolve structures they are worth comparing.

  On the surface GEP has several similarities to NEAT:

  • Evolves structure to some extent (up to a fixed size, unlike NEAT)
  • linear chromosomes
  • Preserves syntactic correctness

  However, the differences are very significant:

  • In GEP, chromosomes have fixed length. Complexification is not possible. GEP does what almost every other structure evolving system does, which is arbitrarily permute over different structures in no particular direction (either from more complex to less, or less comples to more).
  • Although syntactic correctness is preserved (which is a gain in the Genetic Programming world), there is no provision for preventing radically different parents from mating. (i.e. the analogue of the competing conventions problem for GP's still exists) In other words, there is nothing like NEAT's historical marking mechanism.
  • There is no speciation, and no forseeable systematic method for speciating under the GEP framework, so innovation cannot be protected and, as in the last point, many innappropriate crossovers will occur.

  It is clear that the authors had a similar vision in mind when they created this algorithm to what I was aiming for with NEAT, but the algorithms are quite different in the end. It does bring up the possibility of applying NEAT to evolving non-neural structures such as genetic programs, since NEAT is in principle a general algorithm for evolving structure.
  
  

• Does NEAT solve the competing conventions problem?
  

  First let me clarify, as Darrell Whitley pointed out, the competing conventions problem is the problem of having the same functionality represented by different permutations of the same set of connection weights. Thus, NEAT is addressing a broader problem, which really should be termed the "variable length genome problem," which arises from having different topologies and weight configurations in the same population. That said, the variable length genome problem is the problem of crossing over or comparing neural networks (or other structured phenotypes) with different topologies and weights that implement similar functionalities. NEAT's method of matching up genomes and measuring compatility for speciation using historical markings may be considered a "solution" to the problem of variable length genomes in the sense that any two genomes can now be matched up in the most sensible manner possible no matter how divergent their topologies, and NEAT can also be considered a solution because genomes that are too divergent are not allowed to mate at all, avoiding incompatibilities. However, in another sense, one could say that the variable length genome problem can never be "solved" because it is inherent in any system that generates different constructions that solve the same problem. For example, both a bird and a bat represent solutions to the problem of flight, yet they are not compatible since they are different conventions of doing the same thing. The same situation can happen in NEAT, where very different structures might arise that do the same thing. Of course, such structures will not mate, avoiding the serious consequence of damaged offspring. Still, it can be said that since disparate representations can exist simultaneously, incompatible genomes are still present and therefore the problem is not "solved." Ultimately, it is subjective whether or not the problem has been solved. It depends on what you would consider a solution. However, it is at least correct to say, "the problem of variable length genomes is avoided."

  Note that for those who do not consider NEAT a solution, it follows that nature also does not solve the problem, since disparate solutions exist in nature. This line of thought generally implies that nothing can solve the variable length genome problem.
  
  

• What if I want to evolve a network with self-similarities/symmetries/repeating patterns?
  New It turns out that you can do this kind of evolution with NEAT. A recent theory (2006) explaining how is in our paper, Compositional Pattern Producing Networks: A Novel Abstraction of Development .

  A broad review is in our paper, A Taxonomy for Artificial Embryogeny.
  
  

• Why does NEAT use a bias node instead of having a bias parameter in each node?
  

  Mainly because not all nodes need a bias. Thus, it would unnecessarily enlarge the search space to be searching for a proper bias for every node in the system. Instead, we let evolution decide which nodes need biases by connecting the bias node to those nodes. This issue is not a major concern; it could work either way. You can easily code a bias into every node and try that as well.
  
  

• Have you tried using non-sigmoid activation functions?
  

  Yes, that is what CPPNs do. See Compositional Pattern Producing Networks: A Novel Abstraction of Development .

  The kinds of activation functions available to NEAT biases the kinds of functions it is likely to evolve. As in all machine learning, the right bias (if you can find it) provides and advantage.
  
  

• How does NEAT avoid bloat?
  

  For those who don't know, bloat is a major problem in Genetic Programming (GP) that results from genomes getting bigger and bigger without any corresponding increase in fitness, leading to unwieldy programs that cannot be optimized further.

  GP permutes through different structures of widely varying size and topology. NEAT does not permute in this way. Rather, it builds up structures slowly, piece by piece, each piece being tested carefully. As structures diverge in NEAT, they are placed into different species so they won't interfere with each other. Thus there are multiple simultaneous and divergent lines of principled build-up of structure. Such an approach is more bloat-proof. Also, crossover in NEAT is itself bloat-proof, since it does not involve tacking on arbitrary trees of structure from widely varying topologies. Finally, the way NEAT is implemented, it only adds excess or disjoint genes from the more fit parent in a crossover of genomes with divergent histories. Therefore, you don't get excess baggage from inferior solutions.

  There is another important reason that NEAT avoids bloat that I did not mention above. As long as a network represented by a small number of genes is competitive, its species will survive in the population. In other words, if a species of small genomes "bloats" through some genetic cause such as mutation or crossover, the new bloated offspring will end up in a different species. Unless the new species is superior to the old one, the old species will survive unbloated and separated from its more bloated successor. Only when a more complex species displays superior performance will the less bloated species become obsolete and begin to shrink. Thus, unbloated species stick around for as long as they can perform well. The moral: Speciation prevents bloat!

• How can NEAT "start minimally" in a high-input/high-output domain?
  

  Recall that "starting minimally" means beginning evolution with a population of networks with minimal structure. In the experiments in our papers so far, "minimal structure" means no hidden nodes. However, in domains with a very large number of inputs and/or outputs, things get weird. Let us say you have 50 inputs and 50 outputs, which might be reasonable for a board-game type domain. Then if you start with networks with only direct connections, you would have 2,500 connections. In contrast, a network with 5 hidden nodes would have only 50*5+5*50=500 connections. So at a certain point, when the input/output space becomes quite large, the meaning of a minimal network changes. In general this happens when a reasonable number of hidden nodes for solving the task is significantly lower than the number of inputs and/or outputs.

  The conclusion is that you need to be creative about the topologies of your initial population in such high-dimensional domains. One option, which has not been explored much, is to begin with a fully-connected network of a few hidden nodes and without direct connections. Direct connections will then evolve on their own, and new nodes will be added as needed.

  That said, the real answer is that if you are starting with a lot of inputs and outputs fully connected, then you are violating the principal of starting minimally! However, to be true to the NEAT method, the more appropriate approach would be to start with only a subset of the total inputs and outputs, and allow evolution to add inputs and outputs as it sees fit, as they help increase fitness. My current software distribution does not implement this idea, but if you are working in such domains, you should consider that it is really the most appropriate approach, and perhaps you should consider implementing it before proceeding. Question "Can I start NEAT with some inputs disconnected?" above gives the code necessary to start this way, with some inputs not present in the initial genome. Update: Based on recent results (2005), starting with many inputs disconnected appears to be a powerful and effective approach. See this paper for more info on these results.

  Here is a tip for game-playing domains: If you have, say, a board with n possible positions, you can get away with only 1 output instead of n outputs by moving all n outputs to the inputs. You concatenate these n extra inputs with the 2n (or however many) normal inputs you have for specifying board position. We will call the new n inputs, "candidate inputs." Interpret the single output as answering the question, "Should I move to position [the current 1 of n candidate inputs nodes that is active]?" So you would poll the network for every possible move of the n candidate moves, and see which one it likes best. If you try this idea, let me know how it compares to the standard n-output method of deciding the next move since I don't know of much research on this idea. It greatly reduces the number of connections needed to represent a solution.

  This paper explains yet another approach to dealing with high input/output domains: instead of evolving a complete set of inputs for the whole field of a game, you can evolve a smaller "roving eye" that scans the board at will.
  
  

• Should a record of innovations be kept around forever, or only for the current generation?
  

  In my implementation of NEAT, the record is only kept for a generation, but there is nothing wrong with keeping them around forever. In fact, it may work better. Here is the long explanation:

  The reason I didn't keep the record around for the entire run in my implementation of NEAT was because I felt that calling something the same mutation that happened under completely different circumstances was not intuitive. That is, it is likely that several generations down the line, the "meaning" or contribution of the same connection relative to all the other connections in a network is different than it would have been if it had appeared generations ago. I used a single generation as a yardstick for this kind of situatiom, although that is admittedly ad hoc.

  That said, functionally speaking, I don't think there is anything wrong with keeping innovations around forever. The main effect is to generate fewer species. Conversely, not keeping them around leads to more species..some of them representing the same thing but separated nonetheless. It is not currently clear which method produces better results under what circumstances.

  Note that as species diverge, calling a connection that appeared in one species a different name than one that appeared earlier in another just increases the incompatibility of the species. This doesn't change things much since they were incompatible to begin with. On the other hand, if the same species adds a connection that it added in an earlier generation, that must mean some members of the species had not adopted that connection yet...so now it is likely that the first "version" of that connection that starts being helpful will win out, and the other will die away. The third case is where a connection has already been generally adopted by a species. In that case, there can be no mutation creating the same connection in that species since it is already taken. The main point is, you don't really expect too many truly similar structures with different markings to emerge, even with only keeping the record around for 1 generation.

  Which way works best is a good question. If you have any interesting experimental results on this question, please let me know.
  
  

• Is there another way to do fitness sharing?
  

  Yes. It turns out that the number of offspring alotted to a species using fitness sharing as I implemented it is equivalent to the following:

  Offspring = (AverageSpeciesFitness / Total_of_AverageSpeciesFitnesss) * PopulationSize

  Note that this treatment penalizes species that have very high quality solutions if they also have poor solutions. That means that species need to produce consistently good solutions in order to survive, rather than just produce one rare good solution. It is possible that the maximum species fitness could be used instead of the average fitness, which would result in this equation:

  Offspring = (MaxSpeciesFitness / Total_of_AverageSpeciesFitnesses) * PopulationSize

  In this case, species with a single very good member would be highly rewarded. It is not immediately clear which method is better, but both the latter is certainly worth trying. Note that rewarding species based on their max fitness means investing in solutions that may be very inconsistent. In other words, if the best member of a species consistently produces poor offspring, the algorithm will not detect this. Thus, there may be an advantage to using the average fitness as my implementation of NEAT does, since it promotes more robust solutions. However, on the other hand, the downside of using the average fitness is that we might miss very good peak solutions because they happen to be occur in species that otherwise contain many mediocre or poor solutions. Thus, there appears to be a trade-off between the two strategies and further research is warranted. In preliminary experiments, Mattias Fagerlund reported no noticable difference between the two alternatives.

  A possible compromise is to take the average of only the top n% of a species (those members that get to reproduce).
  
  

• Is there a way to use negative fitnesses in NEAT?
  

  You may have noticed that if you try to use negative fitnesses, NEAT breaks down because of fitness sharing, which requires positive fitness values.

  Real Carbonneau suggested the following solution to this problem: Compute fitness as you wish, with negative values if desired. Then, adjust all the fitnesses by replacing them with the distance between the actual fitness and the lowest fitness in the population. This will scale all the fitnesses above zero, keeping the relationships stable.
  
  

NEAT Users and Projects

There is so much work going on with NEAT that I have stopped trying to keep track of it here. Instead, one way to find information projects with NEAT (aside from the several NEAT packages available) is to search Google for "Augmenting Topologies" or to search Google Scholar for "Augmenting Topologies" also.

The Future of NEAT

Hypercube-based NEAT (HyperNEAT) is the future of NEAT.

HyperNEAT software and source has also become available:

• HyperSharpNEAT C# by David D'Ambrosio. This package extends Colin Green's SharpNEAT to run as HyperNEAT. A scalable robot food gathering domain is included.
  
  
• HyperNEAT C++ by Jason Gauci. Includes the scalable big box/little box visual discrimination task and a convenient GUI for exploring the substrate.

NEAT Publications

Note More recent papers from after I moved to UCF are here.

Note: The last three papers are the best introduction to NEAT

The following papers talk about the NEAT method. I conclude each reference with some commentary describing what the paper is about. The links also lead to abstracts before you download the papers. My homepage has links to all my papers, including papers not specifically about NEAT.

Ph.D. Dissertation: EFFICIENT EVOLUTION OF NEURAL NETWORKS THROUGH COMPLEXIFICATION
Kenneth O. Stanley
Department of Computer Sciences, The University of Texas at Austin
Technical Report~AI-TR-04-39, August 2004.
Comment: Extensive descriptions of both the NEAT method and associated experiments. 180 pages.

EVOLVING NEURAL NETWORK AGENTS IN THE NERO VIDEO GAME
Kenneth O. Stanley, Bobby D. Bryant, and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
Proceedings of the IEEE 2005 Symposium o n Computational Intelligence and Games (CIG'05). Piscataway, NJ: IEEE, 2005.
Winner of the Best Paper Award at CIG'05
Comment: This 8-page paper describes how NEAT was adapted to work in real-time in the NERO video game.

AUTOMATIC FEATURE SELECTION IN NEUROEVOLUTION
Shimon Whiteson, Peter Stone, Kenneth O. Stanley, Risto Miikkulainenn and Nate Kohl
Department of Computer Sciences, The University of Texas at Austin
To appear in:Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005).
Comment: Describes how starting NEAT with most inputs disconnected and letting NEAT decide which ones to connect is more effective than starting with all inputs connected, particularly in problems with many potential inputs.

REAL-TIME NEUROEVOLUTION IN THE NERO VIDEO GAME
Kenneth O. Stanley, Bobby D. Bryant, and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
IEEE Transactions on Evolutionary Computation, volume 9, number 6, pages 653-668, December 2005.
Comment: Journal paper describes how NEAT was enhanced to run in real-time inside a new genre of video game where agents are trained by the player during gameplay.

EVOLVING A ROVING EYE FOR GO
Kenneth O. Stanley and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004). New York, NY: Springer-Verlag, 2004
Comment: This conference paper describes how a roving eye of a fixed input size can be evolved to play Go on boards of different sizes, and how an eye trained on a smaller board can go on to learn on a larger board better than an eye trained starting on the larger board.

EVOLVING ADAPTIVE NEURAL NETWORKS WITH AND WITHOUT ADAPTIVE SYNAPSES
Kenneth O. Stanley, Bobby D. Bryant, and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC-2003). Canberra, Australia: IEEE Press, 2003
Comment: Conference paper describing experiments evolving neural networks with synpatic weights that change over time according to local Hebbian rules. Explains how traits are used in NEAT: See Section 2.4 of this paper. Traits are referred to as a rule set in the paper.

COMPETITIVE COEVOLUTION THROUGH EVOLUTIONARY COMPLEXIFICATION
Kenneth O. Stanley and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
Journal of Artificial Intelligence Research 21: 63-100, 2004.
Comment: This 38 page journal article expands on the importance complexification from a minimal starting point, and shows how it leads to the discovery of more complex structures than would otherwise be possible.

CONTINUAL COEVOLUTION THROUGH COMPLEXIFICATION
Kenneth O. Stanley and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
To appear in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002). San Francisco, CA: Morgan Kaufmann, 2002
Comment: Conference paper about using the idea of complexification in NEAT to allow for continual elaboration on strategies leading to a sustained arms race in competitive coevolution.

EFFICIENT EVOLUTION OF NEURAL NETWORK TOPOLOGIES
Kenneth O. Stanley and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
Proceedings of the 2002 Congress on Evolutionary Computation (CEC '02). Piscataway, NJ: IEEE, 2002
Comment: A short conference paper that describes NEAT from the perspective of deconstructing the system using ablation studies.

EFFICIENT REINFORCEMENT LEARNING THROUGH EVOLVING NEURAL NETWORK TOPOLOGIES
Kenneth O. Stanley and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
To appear in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002). San Francisco, CA: Morgan Kaufmann, 2002
Comment: A conference paper that describes NEAT from the point of view of performance and visualization.
Winner of the Best Paper Award in Genetic Algorithms

EVOLVING NEURAL NETWORKS THROUGH AUGMENTING TOPOLOGIES
Kenneth O. Stanley and Risto Miikkulainen
Department of Computer Sciences, The University of Texas at Austin
Evolutionary Computation 10(2):99-127, 2002.
Comment: A journal paper including a comprehensive description of the NEAT method, as well as substantial background information and performance analysis. Should be useful for implementing your own version of NEAT.

Note: A complete list of my publications can be found on my homepage.

Contact me here:

kstanley@cs.ucf.edu

Last Updated 12/12/14

Updates: This page has been substantially revised on 8/31/03. New answers were added to the ends of both FAQs as of 5/8/03. A new paper on evolving synaptic plasticity (using traits) is available through the this page as of 6/22/03. A NEAT User's Group opened on Yahoo on 8/26/03. More projects listed on 12/4/03. On 12/21/03 Mattias Fagerlund released full source code and demos for Delphi NEAT. 2/16/04: A new question explains how to start NEAT with genomes with some inputs initially disconnected from the the network. 3/5/04: The question on starting disconnected now links to code for mutate_add_sensor both in Java and C++. 3/24/04: Added link to new paper on evolving a roving eye with NEAT for Go. 4/7/04: Added link to SharpNEAT, a new NEAT software package. 6/9/04: Added link to ANJI (Another NEAT Java Implementation). 9/14/04: Added question and answer about testing with XOR. 9/15/04: Elaborated answer on testing with XOR. 10/27/04: Added 2 more papers to the publications list. 5/4/05: Added 2 more papers (feature selection and NERO award winner) and updated answers to FAQ questions on starting with some inputs disconnected, also pointing them to the new paper. 9/7/05: Linked Ashot Petrosian's NEAT Code Documentation 1/20/06: Changed link to NERO tech report to the journal paper that replaced it. 9/8/06: Added links to rtNEAT source code and NEAT4J, a new Java-based NEAT release. 10/12/06: Updated answer to question, "Can I start NEAT with some inputs disconnected?" 5/20/07: Added link to EPlex in intro text. 1/10/08: Fixed broken links, updated out-of-date text, added HyperNEAT links. 1/16/08: Updated answer to "Have you tried using non-sigmoid activation functions" to cite CPPNs. 4/24/08: Added link to my original notes wherein I thought of the NEAT algorithm. 5/9/08: Updated mention of HyperNEAT at top of page to link to more papers. 2/8/09: Added link to eplex publications. 4/17/09: Linked to HyperNEAT Users Page. 1/6/10: Removed broken link to NEAT Code Documentation. 3/9/10: Fixed link to DelphiNEAT (now goes to eplex server) 6/15/10: Added links to NEAT4J and Encog NEAT. 7/19/10: Added question, "Can you explain some of the NEAT Parameters?" 7/19/10: Added link to Wesley Tansey's SharpNEAT 2 TTT tutorial. 9/5/11: Small change to HyperNEAT text and links at top of page. 1/12/12: Added link to ObjectiveNEAT package. 9/19/12: Added link to Peter Chervenski's MultiNEAT software package. 3/2/13: Added link to Eric Laukien's NEAT Visualizer package. 9/17/13: Added link to Fernando Torres' reorganized github version of NEAT C++. 4/21/14: Added link to Fred Mitchell's RubyNEAT platform. 10/30/14: Added link to Sean Dougherty's AccNEAT software package. 12/12/14: Added link to Daniel Jallov's UnityNEAT software package. 5/5/15: Switched list of NEAT software packages to link to NEAT Software Catalog