Neuro-Evolution of Augmenting Topologies Algorithm

Overview:

This article explains the Neuro-Evolution of Augmenting Topologies (NEAT) and real-time Neuro-Evolution of Augmenting Topologies (rtNEAT) algorithms, discussing how they can endow agents with learning capabilities.

Neuro-Evolution of Augmenting Topologies

As discussed in the Introduction to Evolutionary Algorithms, Neuro-Evolution of Augmenting Topologies (NEAT) is a Neuro-Evolution (NE) algorithm that mimics how biological systems work in nature presenting them as evolving virtual organisms that increase complexity over time. NEAT was developed by Ken Stanley in 2002 while at The University of Texas at Austin.

NEAT uses a Genetic Algorithm to allow a network to evolve by finding the best topology and connection weights for the Neural Network. This algorithm keeps the network size to a minimum by starting with a minimal network structure and gradually increasing complexity by adding hidden nodes and connections to create a sophisticated, evolving Neural Network over several generations. This process is referred to as ‘complexification’.

NEAT keeps track of the created nodes and links chronologically, using historical gene markers. When a new structure is created, whether it is a new hidden neuron or connection, NEAT generates historical marking, which is also referred to as innovation. A database of all innovations is maintained. Each innovation has a unique ID in order to identify and keep track of it. Every time a neuron or link is generated, NEAT checks to see if the innovation has already occurred. If not, new innovation with a unique ID is created otherwise the existing innovation ID is used to create the new gene.

The innovation ID can determine the origin of genes, which helps with lining up genes with the same origin for the crossover operation. Therefore, by using these historical markings (innovations), disparate topologies can be crossed over in a meaningful way and the competing conventions problem (as mentioned in the Introduction to Evolutionary Algorithms) is mitigated.

The NEAT Genome

The network structure in NEAT is represented using Node-based Encoding (as explained in the Graph Encoding section). This method encodes the required information about the Neural Network structure (phenotype) inside genes. Genes hold information about neurons or connections, which are referred to as neuron genes and link genes, respectively. A genome structure also referred to as a ‘genotype’ is defined in NEAT to hold the list of link genes and neuron genes. The Figure below shows how the structure of a Neural Network (phenotype) is represented as a genome (genotype) using link genes and neuron genes.

A neuron gene contains information about a neuron including its unique ID and type. The type of neuron indicates the layer it is placed in, which can be the input (sensor), output, or hidden layer. Each neuron gene also stores the activation response (p) of the neuron as discussed in Activation Function of Neural Network neurons.

Link genes (or ‘connection genes’) contain information about the connections between neurons. The information includes the ID of neurons that are connected via the link (the input and output neurons), the weight of the connection, and variables to indicate whether the connection is enabled and whether it is a recurrent link. Link genes also contain a reference to the innovation ID, which allows them to identify which genes from one genome match up with genes of another.

Crossover Operation in NEAT

The crossover process recombines two parent genomes from random points to create a new offspring genome. The crossover operator of NEAT acts like a multi-point crossover, where the genomes are cut and swapped from multiple points, as shown in the Figure below.

The crossover operator is often a troublesome operator as it can create an invalid Neural Network, leading to the competing conventions problem. NEAT manages to solve these issues by using innovation IDs as historical markers to define which genes of different genomes match up. As discussed before, each structural change is given a unique innovation ID and stored in a database. When the crossover operator is performed, the genes are tracked chronologically and similar ones are aligned. When aligning genomes and comparing them in this way, the first set of genes in one genome is matched with the first set of the other genome. The Figure above illustrates how the genomes are matched based on innovation IDs.

Genes on a parent genome that do not match any gene on the other parent genome and are located in the middle of the genome are referred to as disjoints. The genes that do not match any gene on the other genome and are at the end of the genome are referred to as excess genes. When creating the offspring genome, matching genes are inherited from both parent genomes. Consequently, both dis- joint and excess genes are inherited from the fitter parent genome.

Mutation Operation in NEAT

The mutation operation randomly selects and changes the value of one or more genes in a genome. There are a number of ways a genome may be mutated in NEAT. These mutation operations include:

• Mutating the connection weights.
• Mutating the activation response.
• Mutating to add a new neuron.
• Mutating to add a new link.

A mutation rate is predefined for each type of mutation, and this rate specifies the probability that the mutation may occur. The function for mutating the connection weights goes through all the link genes of a genome. Based on the mutation rate, it creates a random new weight or perturbs the current weight of the connection within the predefined limits. Similarly, the activation response is mutated based on a predefined mutation rate. The other two mutation processes are structural mutations, which are described as follows.

Adding a New Neuron

The mutation process for adding a new neuron goes through all the link genes of the genome and finds a valid link to split and insert the new neuron. A valid link is a link that is enabled, but not a recurrent link, and does not have a bias input.

NEAT checks if an innovation already exists by adding a new neuron between the neurons of the selected link. If the innovation already exists, the innovation ID for the new neuron and the links connected to it is obtained from the innovation database. These innovation IDs are then assigned to both the new neuron and the links.

In the case that the innovation is new (does not exist in the innovation database), new innovations are added to the database for the newly created neuron gene, and link genes are connected to it. The previous link gene is disabled and its weight is used as the weight of one of the newly created links. The reason for this is to avoid perturbing what the Neural Network has already learned.

The figure above illustrates how a new neuron is added to the phenotype by splitting an existing link between nodes 3 and 4. It also shows the effects of this operation on the structure of a genotype. These changes include; disabling the existing link of 3->4, and adding the links 3->6 and 6->4. The number on the top of each gene is its innovation ID.

Adding a New Link

The mutation process for adding a new link also uses a mutation rate, as all the other mutation processes do, to define the probability that a new link will be added to the Neural Network structure. NEAT can add different types of links, which include forward, recurrent, and looped. A looped link is a link that loops back into the same neuron. The algorithm first tries to create a looped link based on a predefined probability rate.

If there is no chance of creating a looped link, the algorithm then tries to find two neurons that are not linked together. The second neuron must not be an input neuron or a bias neuron. When a new link is discovered NEAT examines the innovation database to see if this innovation has already been previously recorded. If it has, then its innovation ID is retrieved and assigned to the new link. Otherwise, a new innovation is created and its ID is then assigned to the new link gene.

The figure above illustrates how this mutation process works by use of an example. In this example, a new link is added between neurons 3 and 5, and new innovation is created and added to the genome.

Speciation Process in the NEAT Algorithm

One issue in Neuro-Evolution processes is that when topological innovations occur, they often initially have low fitness compared to the rest of the population that has been created before. Since the selection process is based on the fitness value, the newly created innovations have less chance of surviving. These innovations need a few generations in order to optimise [4]. NEAT solves this problem and protects these innovations by allocating them to new species. As a result, diversity is promoted and also the competing conventions problem is reduced.

Speciation is a way of protecting new innovations in the early stages of their development. This process splits the population of genomes into different species. Each species contains genomes with the same characteristics so that its members may only interbreed with each other. This means they have time to optimise their structure before they have to compete with the rest of the population. This procedure is briefly demonstrated below:

The Genome Loop: 
While there is an unchecked genome in population P:
    Get the next unchecked genome g from P
    The Species Loop:
    While species S has an unchecked member and g is not placed in any species:
        Get the next unchecked species i from S
        If g is compatible with i, add g to i
    END of Species Loop.
    If g is not placed in any species
        Create a new species and place g in it
END of the Genome Loop.

The population of genomes is divided into species based on topological similarity of individuals, which can be derived from historical markings [211]. The distance δ between the encoding of two networks can be calculated by the equation below, where D and E are the disjoint and excess genes respectively and W is the average difference in weight of matching genes. The coefficients c1, c2, and c3 adjust the importance of the mentioned factors respectively. The value of N is the number of genes in the larger genome and is used to normalise the genome size.

δ = c₁ E / N + c₂ D / N + c₃.W

During every update cycle of the algorithm, each genome is compared against a randomly chosen member of a species and the distance δ is measured between them. If δ is less than the predefined compatibility threshold (δ_t) then this genome is placed in that species. Each genome is only placed in one species. If the genome is not compatible with any of the previous species then a new species is created.

In order to further protect the new innovations within each species, another technique is used in NEAT, which is called explicit fitness sharing [3]. This

method is a way of retaining diversity by sharing the fitness scores of similar genomes. The algorithm divides the fitness of each individual by the size of the species before the selection process. The older species are penalised while the younger species are given a strengthening boost before performing the fitness sharing process. The fitness sharing process adjusts the fitness of each genome so the ones that are younger and more diverse remain active longer and a single species cannot become too large to take over the entire population. “The speciation procedure consists of two nested loops that allocate the entire population into species” [2].

Real-time Neuro-Evolution of Augmenting Topologies 

NEAT was originally designed to run off-line. The NEAT algorithm evaluates all individuals in each generation before creating the next generation. This results in large gaps of time between generations. It makes human interaction with agents difficult. The system also looks inconsistent because in each generation the behaviour of all agents changes at once. real-time Neuro-Evolution of Augmenting Topologies (rtNEAT) is a technique based on NEAT that makes agent behaviour evolve continuously at run-time and also adapt to varying environmental dynamics and environmental changes [2]. This algorithm makes it possible for humans to interact with the evolving agents in real-time.

The rtNEAT algorithm uses a mechanism to allow agents to evolve continuously. Every few update cycles (also referred to as ticks in this research), the program selects two agents with the best-fitted genomes to produce a new offspring through crossover and mutation operations. The newly-created offspring then replaces an agent of lower fitness, as demonstrated in the Figure below. The real-time NEAT algorithm is an effective method for evolving agent behaviour in a dynamic environment where new agents can be reconstructed to replace weak and older agents.

The dynamics of real-time NEAT are the same as NEAT in the sense that it protects innovation through speciation and complexification. However, it cannot assign agents to species all at once because only one offspring is created at a time.

Speciation Process in the rtNEAT Algorithm

The reproduction cycle of real-time NEAT is designed to allow speciation in real-time. Every n ticks (as defined by the equation below), the algorithm repeats a sequence of operations as shown below [2]:

1. Step 1: Calculate the adjusted fitness of all current individuals in the population.
2. Step 2: Remove the agent with the worst adjusted fitness from the population, provided one has been alive sufficiently long so that it has been properly evaluated.
3. Step 3: Re-estimate the average fitness for all species.
4. Step 4: Choose a parent species to create the new offspring.
5. Step 5: Adjust the compatibility threshold dynamically and reassign all agents to species.
6. Step 6: Replace the old agent with the new one.

Firstly, real-time NEAT calculates the adjusted fitness of all agents using the fitness sharing technique as discussed in the previous section above (NEAT). The agent with the least adjusted fitness is then selected and removed from the population. Since the fitness sharing technique takes into account the size of species the new, smaller species are protected from early elimination.

The algorithm also takes into account the amount of time the agent has been alive before removing it. The reason for this is to give it sufficient time to be evaluated properly. This time constraint is decided experimentally, and based on the observation of the amount of time required for an agent to achieve a certain level of the desired behaviour. After the agent is removed, the average fitness of the species needs to be updated. This is important for the next step where a parent species is selected to create a new offspring. The parent species is chosen probabilistically based on its average fitness compared to the sum of the average fitness of all species.

In the next step, all agents need to be reassigned to species based on the new compatibility threshold δ_t, which is adjusted dynamically in order to stabilise the number of species throughout the evolution process. The frequency at which δ_t is adjusted is set by the designer based on how rapidly the species are desired to be made to evolve.

The above steps are repeated in regular intervals to create new generation agents and eventually evolve agents.  The frequency at which evolution occurs is important because if agents are replaced quickly then they do not have enough time to be evaluated. “On the other hand, if agents are replaced too infrequently, evolution slows down” [2]. The time between evolutions is calculated by the following Equation.

n = m / ( |P | * I)

where n is the number of ticks between evolutions, P is the size of the population, m is the minimum time the agent is alive, and I “specifies what fraction of the population can be expected to be ineligible once evolution reaches a steady-state” [2]. If this value is too high there may not be enough agents eligible for the evolution process. This value is predefined in the program. It is set to 40% in this project and based on trial and error to improve performance.

Conclusion

In this article, I discussed the Neuro-Evolution of Augmenting Topologies (NEAT) and real-time NEAT algorithms. NEAT works by adding neurons and links to the phenotype and defining historical markings (innovations) to keep track of structural changes. It checks the innovation database when new structural changes are about to occur and assigns the correct innovation ID to the newly-created neuron and link genes. This ensures that the genes contain historical markings of all changes in the phenotype, and helps to find the origin of genes. Using these innovations, genes of the same origin can be lined up when performing the crossover operation so disparate topologies can be crossed over in a consequential manner.

NEAT also protects these innovations by allocating them to a new species and thereby reducing the competing conventions problem. The NEAT algorithm evolves the entire genome population at once and necessarily is performed offline or at certain intervals. This results in large gaps in time between generations and causes the process to look inconsistent. Meanwhile,  real-time NEAT is based on the NEAT algorithm and performs the evolution process one or a few genomes at a time. This is particularly useful for dynamic environments and helps agents to adapt to environmental changes. It also makes it possible to interact with evolving agents in real-time.

In the next article, I’ll discuss how I trained agents to navigate a virtual environment using the NEAT Algorithm.

References

1. K. O. Stanley and R. Miikkulainen. Evolving neural networks through augmenting topologies. Technical Report AI2001-290, Department of Computer Sciences, The University of Texas at Austin, 2002.
2. K. O. Stanley, B. D. Bryant, and R. Miikkulainen. Real-time neuroevolution in the NERO video game. IEEE Transactions on Evolutionary Computation, 9:653–668, 2005.
3. D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In J. J. Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms, pages 148–154. Morgan Kaufmann, San Francisco, CA, 1987.
4. M. Buckland. AI Techniques for Game Playing. Premier Press, Cincinnati, OH, USA, 2002.