NEAT (Neural Evolution of Augmented topologies)

You would probably be wondering what this blog post is all about. Anyway, I will just jump into the topic. NEAT stands for NeuroEvolution of Augmented topologies. It is a method for evolving artificial neural networks with a genetic algorithm. NEAT implements the idea that 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.

So what is so special about NEAT. Ken Stanley (from UTexas Austin) who developed this algorithm (in 2002) claims that NEAT outperforms fixed topology method primarily for three reasons.

1.       Employing a principled method of crossover of different topologies

2.       Protecting structural innovation through speciation (formation of new and distinct species in the course of evolution)

3.       Incrementally growing from minimal structure

In traditional Neural Evolution approaches, a topology is chosen for the evolving network before the experiment begins. Usually, the network topology is a single hidden layer of neurons connected to every network input and every network output. Evolution searches the space of connection weights of this fully, connected topology by high-performing network to reproduce. The weight space is explored through crossover of network weight vectors and through the mutation (the process of mutating/alteration) of single networks’ weights. Thus, the goal of Neuro evolution is to optimize the connection weights that determine the functionality of a network.

Many systems have been developed over the last decade to evolve both neural network topologies and weights. These methods encompass a range of ideas about how Topology and Weight Evolving Artificial Neural Networks (TWEANNs) should be implemented. NEAT focused on how a neuro evolution method can use the evolution of topology to increase its efficiency. In TWEANNs, innovation takes place by adding new structure to networks through mutation. Protecting this innovation is achieved through the GNARL system (adding a node to the genome without any connections) by adding non-functional structure. NEAT uses explicit fitness sharing which forces individuals with similar genomes to share their fitness payoff.

The two types of structural mutation in NEAT. Both types, adding a connection and adding a node, are illustrated with the connection genes of a network above their phenotypes. The top number in each genome is the innovation number of that gene. The innovation numbers are historical markers that identify the original historical ancestor of each gene. New genes are assigned new increasingly higher numbers. In adding a connection, a single new connection gene is added to the end of the genome and given the next available innovation number. In adding a new node, the connection gene being split is disabled, and two new connection genes are added to the end the genome. The new node is between the two new connections. A new node gene representing this new node is added to the genome as well. Matching up genomes for different network topologies using innovation numbers. Although Parent 1 and Parent 2 look different, their innovation numbers (at the top of each gene) tell us which genes match up with which. Even without any topological analysis, a new structure that combines the overlapping parts of the two parents as well as their different parts can be created. Matching genes are inherited randomly, whereas disjoint genes (those that do not match in the middle) and excess genes (those that do not match in the end) are inherited from the more fit parent. In this case, equal fitnesses are assumed, so the disjoint and excess genes are also inherited randomly. The disabled genes may become enabled again in future generations: there’s a preset chance that an inherited gene is disabled if it is disabled in either parent.

NEAT biases the search towards minimal-dimensional spaces by starting out with a uniform population of networks with zero hidden nodes (i.e., all inputs connect directly to outputs). New structure is introduced incrementally as structural mutations occur, and only those structures survive that are found to be useful through fitness evaluations. In other words, the structural elaborations that occur in NEAT are always justified. Since the population starts minimally, the dimensionality of the search space is minimized, and NEAT is always searching through fewer dimensions than other TWEANNs and fixed-topology NE systems.

The main conclusion is that NEAT is a powerful method for artificially evolving neural networks. NEAT demonstrates that evolving topology along with weights can be made a major advantage.

There are various sources in the internet where you can find information about NEAT.

Stay tuned to the blog for more.