NeuroEvolution, NEAT Algorithm and My NEAT
Humans are known to have big brains.
In fact, across seven million years, the human brain has tripled in size, from only around 500 ml to 1,200 or more today! The change in shape and volume of our brain are evidence of a process called evolution which allows the brain to adapt to cultural/ linguistic complexity, and dietary needs. Needless to say, these changes are good. They allow us to better plan, communicate and even perform more advanced cognitive tasks such as 12345*54321.
From a primitive brain, the average brain today allows the human species to perform at its optimal level!
Fast forward to the 21st century, we are envisioning the “artificial brain” which includes artificial neural networks (ANNs). ANN are computational models that seek to mimic the behavioral and adaptive capabilities of central nervous systems.
What’s amazing about them is they are actually able to solve fairly complicated tasks like classifying whether a cancer tumor is malignant and benign much more accurate than a trained doctor (You can see my friends Samarth, Anish, and Sameer’s neural network for this application here!). Overall, as universal function approximators, they are excellent in solving regression, classification and complex non-linear problems.
This is all pretty interesting… so I hope you’re wondering:
What’s the structure behind these ANNs, and how they actually work?
It’s actually quite similar to the human brain. Typically, an ANN is composed of interconnected processing units called nodes or neurons. The connection between the neurons are called synaptic weights, just like the synapses in your brain that receives signals from your environment.
The neurons can be classified as input, hidden or output, all of which varies depending on the task at hand. For instance, if you want to classify an image, the inputs can be the features of your dataset and the many outputs are classes to predict.
To make it simpler, think of the baby! When the baby was born, she “sees” oranges and apples (the inputs) but she doesn’t know how to name them yet — just as how our “naive” neural network doesn’t know what names to put on images. After a couple rounds of practice, the baby’s brain picks up the words, and in her mind, she knows: “Ah, that’s an apple!”. Similarly, our ANN post-training will ideally be able to classify oranges and apples with an ideally high accuracy rate. Bam!
The architecture of an ANN is characterized by its topology, i.e. the specific structure of nodes and connections that create a certain network. Usually, the topologies of ANNs are predetermined be the programmer, but the problem is that they may not be the most efficient model. That’s why we have something known as back propagation, or more intuitively speaking “the backpropagation of errors”. Like how it sounds, the ANN compares the predicted output with the actual output. Then, it essentially uses this information to adjust the synaptic weight with the hope to minimize the cost/error function.
Alright, now we have a good idea of what Artificial Neural Networks are, here is an interesting question: Given that we have 100 neural networks randomly generated, how can we know which one is the most efficient one? What if, these neural networks could evolve, just as how we humans evolved over the past million of years, to have an optimal brain?
Welcome to the world of genetic evolution algorithms (or GE)!
Genetics algorithm was inspired Charles Darwin’s theory of natural selection. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.
Here’s how it works in nature on a macro scale:
- The process of natural selection starts with a population with individuals who have different characteristics. Let’s take the example of a giraffe population that has both long-necked and short-necked giraffes. These giraffes have different phenotypes (think visible features) because they have different genomes (think codes for life).
- The long-necked giraffes can more easily reach the leaves at the top and thus have a higher survival advantage than their short-necked peers. As a result, more of them will survive and pass their genes to the next generation. In other words, the long-necked giraffes are considered to be more “fit”.
- The fittest giraffes would survive and through hundreds or maybe thousands of generations, all individuals in the giraffe population will have long neck. In short, nature favors the survival of the fitness.
If you used to think that giraffes have always had long necks and think that this is quite interesting, let’s dive even deeper into the molecular level of things and understand the root of evolution. This will give you an intuition to understand the genetic algorithms we’ll discuss later on.
- Crossover: This happens when two chromosomes exchange their genes during meiosis. Crossover is also one of the reasons why your (future) son or daughter won’t look exactly like you!
- Random mutations: This is when there is a change in one letter of your gene, giving rise to a whole new phenotype!
A genetic algorithm encodes a potential solution to a problem (the phenotype) in a chromosome-like data structure called the genotype or genome. Recapitulating this process of natural selection, the genetic algorithm creates an initial population of random genomes, which are materialized as phenotypes and evaluated on the basis of some fitness function. Basically, using genetic algorithm, you can determine the “survival of the fittest ANNs”.
This evolution of neural networks is called neuroevolution!
One of the genetic algorithms that I’m specifically interested in is NEAT, or NeuroEvolution of Augmenting Topologies, as they can solve problems inherent to neuroevolution (which I will explain later). Based on the principles of NEAT, I trained a bot to play Flappy Bird in Keras, which I’m pretty sure is better than a human being. You’ll also read about it at the end, so stay excited!
NEAT — NeuroEvolution of Augmenting Topologies
As the name implies, the architectures of the neural networks, i.e. topology, becomes better and better at completing a certain task in the course of evolution.
The genome of an ANN contains two parts: node genes and connection genes. Each node gene specifies a single neuron. On the other hand, the connection genes represent the connection between the neurons, the weight of the connection, whether or not the connection is enabled, and a historical marker that provides information about the ancestral history of the gene.
Avoiding the Competing Convention Problem using Historical Marking
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, such as adding a new node or gene), it is assigned an innovation 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.
For example, if we look at the diagram below, let’s say the two mutations occur one after another in the system. The new connection created in the first mutation is assigned the number 7, and the two new connection genes added during the new node mutation are assigned the number 8 and 9. In the future, whenever these genomes crossover, the offspring will inherit the same innovation number on each gene. Innovation numbers are never changed. Thus, the historical origin of every gene is known through the course of evolution.
Protection of Innovation Through Speciation
When a new structure is added to a network, it may reduce fitness. The addition of a new structure is known as topological innovation. As any innovation in real life, such as the replacement of horses with tricycles, it may not be initially good; the wheels may be too big, the seat may be too high. But through a couple rounds of iterations, the innovation becomes better at its job — the seat and wheel achieve the right size for an average human to ride the tricycle, or later on, bicycle. The innovation needs to be given the chance to optimize before being rejected completely.
Moving forward with this logic, NEAT speciates the population, so that individuals compete primarily within their own niches instead of with the population at large. Working with species, NEAT divides the population based on the dissimilarity of individuals which are computed based on the alignments of genotypes during crossover. In short, topological innovations are protected and have time to optimize their structure before they have to compete with other niches in the population!
My NEAT: Training a Bot to Play Flappy Bird in Keras
Here, the inputs are three parameters that the bird sees, and the output determines the probability that the bird will flap.
First, certain libraries like Keras are required to be imported as their functions are needed to build a deep neural network. I also imported a sequential model and a dense model. The Sequential() call returns an empty container that allows us to add the layers we want, while the Dense() is the actual layers of our neural net. Also, there is an Activation function attached to the NN, specifically Sigmoid function, to ensure the non-linear nature of the problem.
In other occasions, we would have to define a loss function and an optimizer to train the network via back-propagation, but since our genetic algorithm doesn’t use back-propagation, we can ignore this part for now. Moving on, we also created a pool of (total_models) (it’s a 100 in our case), which are all randomly initialized.
To define the crossover function, we select the set of weights in our network that connect the 3 nodes in the first layer to the 7 nodes in the second layer and then swap these weights for the given two networks from the pool.
Next, for random mutations, we select the weights randomly with a 0.15 probability and then change its value with a random number between -0.5 to +0.5.
Moving on, our fitness function is simply the amount of time that the bird stays alive in the game! The higher the fitness score is for a given neural network, the fitter it is compared to the others. The fitness of the neural networks is updated every game loop.
Finally, we define the action prediction function, which is called for each neural net in the game as long as the bird corresponding to that neural net is alive.
Then, the below function is called when the game ends and all birds have died. Here, we select pairs of parents based on their fitness scores from the previous run of the game and call the crossover and mutation functions to get pairs of children which would be used as our new pool.
With all that done, once we initialize a pool of 100 random neural networks, we will ultimately achieve the “fittest bird”, who can be even better than a human being at playing this game!
Here are some training samples:
Initial stage: Generation 12, when training just started.
Final stage: Generation 1000, when training was over.
I hope you enjoyed reading my article and learned something new!