What is NEAT (Neuroevolution of Augmenting Topologies)?
I have looked up what NEAT is on youtube and the internet, but I can only find projects using NEAT, but apart from the wikipedia entry (which only says what it is in introduction, and is very confusing), I still have no idea what it is, is it a library, is it a type of neural network, is it a method of training neural networks? Sorry if this is an obvious question.
Answer
NEAT, or Neuro-Evolution of Augmenting Topologies, is a population-based evolutionary algorithm introduced by Kenneth O'Stanley [1].
The algorithm is based on several key features:
Complexification
The networks in the initial population are the simplest possible (up to the extreme of no connections at all, leaving the input and output neurons unconnected) and the algorithm only adds new structural elements (neurons, connections). This way, the resulting networks tend to be very small.
Avoiding competing conventions via historical markings
In ordinary evolutionary algorithms it can easily happen that two individuals encode the same (or very similar) behaviour but with very different genotype. This is called competing conventions. When such individuals are subject to crossover, their children are likely to be worse than either parent. NEAT solves this by keeping historical markings of new structural elements. When a new structural element is created (via structural mutation), it is assigned an innovation number (and all such mutations that produced the same element, even in different individuals are also assigned this same number). Then, when two individuals are crossed over, their genotypes are aligned in such a way that the corresponding innovation numbers match and only the differing elements are exchanged.
Speciation and fitness sharing
NEAT works with the concept of species. That is simply a subdivision of the population into several groups of individuals, called species. This subdivision is based on the dissimilarity of the individuals that is computed based on similar alignment of their genotypes as is used when doing crossover. Probability of crossing over individuals from different species is then much smaller than crossover inside species. By promoting the mating of more similar parents, the children are less likely to be much worse than the parents because the parents just were compatible.
Also, within the species, the fitness is shared among the individuals. This serves two purposes. (1) It protects individuals from mutations - when a mutation happens, the fitness would normally be low but because there is fitness sharing, the individual has time to optimize itself (the weights) to adapt to this new structural change. (2) Promotes diversity because the bigger the species, the more is the fitness shared and the less fit are the members of the species.
I strongly recommend reading the original paper [1]. The algorithm is described very well. Also there is a NEAT Users Page that has more links to more papers and also implementations and uses of NEAT.
[1] Kenneth O. Stanley and Risto Miikkulainen. Evolving Neural Networks Through Augmenting Topologies. Evolutionary Computation, 10(2):99-127, 2002.