Neuroevolution is one of the most satisfying machine learning algorithms to build, tweak, and play around with. In today’s article we’ll be building our very own Neuroevolution algorithm to teach a population of cars how to successfully navigate through a race track.
We’ll be using P5.js for the graphics engine, Tensorflow to handle our neural networks, and Javascript to put it all together!
You can check out the project, hosted on Codesphere, here: https://38098-3000.codesphere.com/
Let’s jump right in!
What is Neuroevolution?
Neuroevolution is a method in AI that simulates evolution and genetic reproduction to create ‘intelligent’ models, most often in the form of Artificial Neural Networks.
Neuroevolution is most commonly done by first creating a generation of agents(in our case cars) that have completely random weights and biases. This means they will effectively make decisions randomly, and therefore will not get very far.
Next, we simulate how this generation of cars performs on the task we want it to learn(In this case driving around a race track).
Then we assign each car in the generation a score on how well it’s done. This is where evolution comes in, because we use the highest scoring cars to create the new generation.
More specifically, Neuroevolution takes inspiration from actual genetic processes, through what is known as Selection and Mutation.
Selection is the process by which we pick traits from the parent generation. Mutation is the process by which we randomly generate traits for the new generation.
Neuroevolution will generate a new generation through both selection and mutation. Just like actual evolution, this tends to result in the next generation being slightly better than the previous.
Over time, our population of cars will get better and better until they are able to perform at a level that we are happy with.
Our Driving Environment
I’ve taken the time to pre build the driving simulator with the help of P5.js, a Javascript graphics library, and a lot of cartesian geometry(Shoutout Desmos).
If you want the blank driving simulator to follow along with, it is all contained within two files, an index.html and a car.js:
If you run the above starter code, you should have your first generation of cars at the starting line. Since we haven’t yet given them any way to move, they will all be standing still.
The first step in any neuroevolution algorithm is defining the inputs and outputs that your species has access to. In our case, each car can detect how close an object is in each of 5 directions(Represented by the red lines). It will receive a number between 1 and 20 representing how close the object is. If there is no object, they will also receive a 20.
In terms of output, each car can make four decisions:
- Accelerate
- Brake
- Turn Right
- Turn Left
Of course, if a car runs into the wall or an obstacle, it will die.
A car’s fitness score(How well it does) is determined by how many laps they do(Worth 100 each) plus how far along on the track they are(ranging from 0 to 100). For example, if a car completes 2 and a half laps before dying, it will have a fitness of 250.
Creating Our Neural Network with Tensorflow
Now let’s give each car the ability to make driving decisions. We will be equipping each car object with an Artificial Neural Network which takes 5 integers representing the proximity to an obstacle in each direction. Then we will have one hidden layer of 8 neurons with ReLU activations. Finally, the Neural net will output 4 values for each of the decisions it can make:
- Accelerate
- Brake
- Turn Right
- Turn Left
The output layer will be using a sigmoid activation function, which will give us values between 0 and 1 for each decision. The car will then multiply each decision output by the maximum rate at which it can perform an action.
For example, let’s say we allow each car to accelerate at a maximum acceleration of 0.50. If it outputs 0.20 for the first neuron, then we will add 0.2 * 0.5 to the speed(So 0.1).
Let’s first create the model in the Car class:
Make sure to call the above function in the constructor for the Car class.
Then, before we update the position of each car class in our draw function, let’s collect the inputs and use this model to make decisions for the car:
Now, our cars can make decisions, but keep in mind that the weights and biases of our neural networks are completely random. Thus the cars will most likely be doing nonsense:
In fact, many of our cars simply turn around in circles aimlessly or do nothing at all. There’s no need to worry, since all we need is one to randomly decide to drive forward to get our evolution going in the right direction!
Genetic Selection and Breeding New Generations
The next step is to breed a new generation. We’ll be using what is known as Fitness Proportionate, or Roulette Wheel, Selection.
This algorithm works by considering the fitness scores of each car in the parent generation, and randomly picking traits from all the parents such that the best performing parents have the highest probability of passing on their traits.
To compute this, we are going to take the sum of each car's fitness score, and use a Cumulative Distribution function to pick a car. If you want a more detailed explanation of the math here, reach out and we would happy to explain more thoroughly.
Additionally, let’s create a function that will compute the total fitness at the end of a generation, as well as compute the highest fitness in the generation for benchmarking purposes(We’ll use a label later to show the highest score and the current generation)
The last helper function we need is a way to copy the weights from each car so we can pass these onto new generations:
Now let’s write our function to create the new generation.
For each new child, we will iterate through weight in its model and randomly assign it a weight from a parent(using our selection algorithm).
Finally, let’s start this new generation whenever every car is inactive, or after a certain amount of time passes.
Let’s create an integer in our index.html called frameCount, to keep track of how long a generation lasts. Then let’s add the following code at the end of our draw function:
Now if everything is implemented correctly we might start to see some progress within a couple of generations:
But its also incredibly likely you might see something like this:
This is because the traits of a generation are completely determined by the traits of their parents. That means if you have a particularly horrible generation, you will continue to get horrible children and get stuck in an endless loop.
That’s where mutation comes in.
Genetic Mutation
Mutation is when a certain weight is given a random value. The probability of a weight being mutated, as opposed to being selected from a parent, is our mutation rate.
We’ll pull our mutation rate from the text field we’ve created, and update our new generation function like so:
This will allow generations to have wildcard traits and rise above the competition.
Now we should see some great generational progress:
Thus mutation allows our cars to experiment with novel strategies, and selection allows the good strategies to spread through the population.
After just 50 generations, we have most of our cars able to complete laps.
Final Code
What’s Next
If you really want to give yourself a challenge, play around with the obstacles.We purposely made it so you can very easily make a harder track.
Additionally, there are all sorts of algorithms that you can use for mutation and selection, playing around with those are a great way to try to improve your Neuroevolution algorithms performance!
That’s all from us today!
Live Demo(Deployed on Codesphere): https://38098-3000.codesphere.com/
Have any questions? Drop them down below and we’d be happy to help.
As always, happy coding from the Codesphere team. We’re building a Web IDE that runs on cloud infrastructure so that your ability to build and deploy software is never limited by your local machine.
Top comments (3)
Thanks for sharing. I would like to add by combining selection and mutation, Neuroevolution generates a new generation of cars. Similar to real evolution, this iterative process tends to result in each subsequent generation being slightly better than the previous one. I read an article about cars here truecarexpert.com/guide/bmw-vs-mer...
Over time, the population of cars improves gradually until they reach a level of performance that satisfies our objectives. It's a rewarding journey to witness how Neuroevolution enhances the abilities of the cars until they can navigate the race track adeptly.
Really great tutorial✨ and thanks :)
Driving lessons should be taken very seriously. So that there will be no unpleasant situations on the road later. You also need to know how to behave in case of minor accidents huffingtonpostlawsuit.com/en-us/la... Me this once helped a lot to avoid an unpleasant situation.