Transcript:
Hey, what is going on guys? And welcome back to our fifth video in the series again Confusingly called part four, but it is way too late to fix that now. So I’m just going to own it before we get into things. I’d like to share a small clip with you from the coming one day. Self-driving video now. I’m sure you’ve all seen self-driving videos before here on Youtube. So I’ll make this one really quick here. You can see a generation of our self-driving simulation with our population of 500 cars. Each car has seven. Rays that are cast out to see its environment, each of those. Rays returns a value indicating the distance from hitting the wall, where one means it’s not intersecting at all and zero means it’s touching the car. Additionally, you can see the large white dots on the map that act as checkpoints, these checkpoints act as positive reinforcement if the car goes forwards through them and negative if they drive backwards through them, the input to our neural network uses each of these seven rays, as well as an XY offset to the next Waypoint, the X Y offset from our previous position and our current heading now. This repo is a little old. I’ve just moved it from Bitbucket to Github So but I’ve linked it down below. If you want to check it out, so my question to you is, how would you encode the genome of the neural network for your car? Now, what would your spawning method Look like, and what would your crossover operator? Look, like, let me know in the comments down below in today’s video. We will be writing the mutation operator for our. Ga, a super quick recap. Before we get started over the last few videos, we’ve been writing a genetic algorithm to solve the Traveling Salesman problem so far, we’ve written a method of spawning individuals, a method of selecting parents for the breeding process, as well as in the last video, a method of combining the genetic material of two parents to create offspring, the crossover now thinking all the way back to our video on spawning the way that we’re creating unique solutions to the problem is by creating a list of integers from 0 to 9 and then we’re shuffling that list, but does this really guarantee that unique solutions will be generated? Well, no, not at all. It’s possible that two solutions will be the same, in fact with our population of 100 in a sea of 3.6 million potential solutions. We have a zero point zero zero to seven percent chance of it happening, but stick with me here for a minute. What would happen? If by some impossibly small chance, all of the individuals that were spawned were the same. Well, the spawning method wouldn’t really care it would just fill our population with individuals when we get the due generation method, we would select two parents. We then perform the crossover, however, no matter where we pick as the split position when we combine the individuals to create our offspring that will be identical to their parents again. This won’t really bother our GA. All the checks that we currently have to test. If two individuals the same will return false because we’re testing to see if these two parent objects are the same or two instances are the same, not if they have the same sequence and sure we could overload the Equality method for our individual to check the sequence instead, but this would impact the performance of our GA. So with this basic check, the Ga will just go on running and running with nothing ever changing, and since we don’t have any convergence checks yet coming in the next video by the way AB Ga, would just run indefinitely. Never improving. So obviously this scenario is absurd. We’re never going to create a hundred individuals with the same sequence. I mean, never say never, but this is just an example, highlighting a real problem that comes up in any GA. So let’s take a really large step back here and just think about what the point of the crossover fundamentally is. What are we trying to accomplish with this process? And the simple answer is we’re trying to explore the potential solution space, where the solution space is every possible sequence, consisting of ten, non repeating integers ranging from zero to nine, but remember the testing. Every single possible solution would be horrendously slow, at least in more complicated scenarios, so what we’re really trying to do is test enough of the potential solutions to find one that’s good enough to meet our requirements, so from this, we can conclude that with a crossover alone, we can’t guarantee that we’ll get good coverage of the solution space. The simplest example is our scenario before if we have all individuals that are identical using the crossover operator will only ever test a single solution. So clearly here we have quite a problem, and I’ve a feeling most of you know where I’m going with this. We need some method of introducing variability into the breeding process and the way that we do that with. Ga s is through the mutation operator. Wow, okay! I’m sorry that was a lot more build-up than I thought it would be so before we dive into writing a mutation operator. Trust me. I’m really as keen as you are. Let’s just talk through the ideal mutation operator and how it should impact our individuals. So the goal of our mutation is to produce new unique offspring by modifying existing individuals as our Ga is breeding successive generations. It will start out with a wide spread of individuals. Some of them will be terrible. Some will be okay, and then some of them might even be good. However, over time that terrible solutions will be replaced with. Okay ones and the okay ones will be replaced with the ones that are really good until almost our entire population is pretty good. If we’re going to mutate a bad individual, you might imagine that we’d be happier, making a larger change with a hope of turning it into a good result while, in contrast, if we have a good individual, we might only want to tweak it slightly to make it a bit better and not lose the progress that we’ve made getting it as good as it already is considering we have more bad individuals towards the start and less and less as we go on. We would also want to go from mutating a large amount to mutating a very small amount. Essentially, this is simulated annealing now that that’s our way. Let’s talk about our mutation operator or should. I say operators because we are going to write two of them. The first we’ll introduce a larger amount of diversity into the population and the second will introduce slightly less for this video. We’re going to have an equal chance of picking either, but in a future video, we will add the annealing along with a bunch of other. Polish, so let’s get that first part out of the way jumping to our configuration class. We’re going to add a new double variable called mutation chance and we’re going to set it to a value of 0.05 Yes, we are going to have a 5% chance of mutating in our first pass and mutation we’re only ever going to mutate offspring and not parents as mutating parents could cause our result to degrade over time. There is an opportunity to clone one of our parents and then mutate it. However, we won’t be doing that in this video going to the do Generation Loop. Each offspring will have a chance of being mutated before it is added to our population, So lets type offspring A comma offspring. B is equal to mutate and we’ll pass in offspring, A comma offspring B and then we’ll allow a visual studio to create as a method. Now let’s jump down and create a copy of each of our individuals, so we can write Var new offspring. A is equal to a new individual and we’ll pass in offspring a dot sequence. Then let’s copy and paste that for offspring B So now let’s write If random dot next double is less than configuration dot mutation chance, then we’re going to say that new offspring a is equal to mutates and we’ll pass in offspring A and then again, all that Visual Studio make the method for us awesome, so let’s copy and paste the same thing for offspring be great, so the last thing that we need to do is jump down to our mutate method where 50% of the time we want to use one method and 50% the time we want to use the other so. I’m sure you’ve all done this before we can type. If random dot next double is greater than 0.5 we’ll add a comment to do swap mutates else we will do rotate mutate, okay, so the first and more disruptive mutation method is probably the one that first comes to mind when thinking about adding diversity into the population that is taking a sequence picking two random indices and then swapping them now originally to me. This felt like one of the smallest changes. You could make. How could you even make one? That’s smaller for some problems that are encoded as sequence. This may not be that large of a change, however, in our particular problem it is, we will explore why that is the case when we come to our rotation mutation, but have a little think about that in the mean time, but that’s really it. We just pick two individuals and we switch them. This is actually how the shuffle was working from our original spawning video. Go check it out here. If you haven’t watched that one yet so jumping down to the code, let’s create a new private method that returns an individual and let’s call it swap mutate and it should take in an individual inside. The method we’re going to grab a copy of the offspring sequence by calling VAR sequence is equal to individual dot sequence dot to list next. We need to pick two towns that we want to swap as this will be required for both of our mutation types. Let’s break it out into a method, so let’s create a new private method that returns two ends and let’s call it get unique towns and that doesn’t need to take in any parameters, then inside the method. Let’s write Var town. A is equal to random next and we will pass in configuration town counts. I’m sure you all know what this does by. Now, then let’s copy and paste that for town B. Now, let’s handle the case where town B is equal to town a so we can type while time. B is equal to town a town. B is equal to random dot next and we will pass in configuration town. Count sorry back in our do swap mutates. We can get our two parents by typing Var town, A comment town. B is equal to get unique towns great. So now we need to swap the two towns once again with a deep love for c-sharp in my heart. I have written another extension method on list shown here that simply swaps two values in place so back on our mutation method. I will call sequence swap in place and I will pass in town A and town B Next. We can return a new individual with our new sequence and just like that we’re done. So how does our rotation mutation work and how does it add less disruption into our individuals? So let’s start with a 100% random not selectively chosen by me to make my point at the sequence? Now, let’s see what that sequence looks like on our map. Great, so now what would happen if we pick two points? And we flipped them like we did before? Whoa, okay, right well. That seems to have messed things up a bit. Our solution got a little bit worse, so let’s just undo that. And now, instead of switching the two values, let’s rotate this entire chunk of values between those points. A hundred and eighty degrees really were just reversing the chunk. Wow, okay, that seems to have given us a really good result, Almost like magic, but no, that isn’t the case. I picked this sequence because I knew it would show the point. I was trying to make, but I’m not here trying to convince you that this mutation operator is better. How would we even define what makes something better? This operation worked perfectly for this sequence, but it could completely destroy another no instead. I’m trying to convince you that it’s less disruptive to our sequence than the swap method to explain. Let’s go back to the original sequence that we had up until now. We’ve had two ways of thinking about our sequences, their genome or lists of numbers and the path or decoded genome as a result, while our first mutation method only interacted with two towns in our genome, the rotation method interacted with six, But how do they actually impact the result? Well, let’s take a look in a swap approach. We have the links coming into and out of town five as well as into town eight when we do the swap. All of these links are broken so three broken links again, While this example is chosen to highlight the biggest difference between the two approaches, there will always be up to four broken links using this approach. This goes down in some scenarios where the towns selected at the end of the sequence like this or is the -. Tao selected our neighbors next up to the ranks. We have our rotation method applying it here with the same index positions of town, 5 and Town 8 We can see that while the order of the sequence inside the rotation is flipped, the connections themselves remain this results in us, only having a single split link, so if our result was not Direction, Invariant meaning it mattered which direction the paths went, then this operator could make a huge change, however, for us here that isn’t the case as with a swap method the indice’s chosen impacts. How many links are broken using this technique? However, there is a maximum of two links that could be broken as a result of using this mutation method so jumping back to the code. We are going to create a new private method that will return an individual. We will call it rotate mutate and it will take in an individual at the start of the method. We will grab our rotation points by typing Var town, A comma town. B is equal to get unique towns. Now, while the ordering of these two values were not important with our swap mutates. They are important here. We need to know which town has the lower indices so we can do this by typing Var. First index is equal to town. A is less than town. B question, mark. In other words, if town a is less than town B then will store the value of town, a otherwise well set it to town B. Then let’s copy and paste this for a second index, then we can update it a second and switch around town, be in town a great so now we have the indices of our towns, then we’re going to explicitly grab the three parts of the sequence, the head, the middle and the tail, so we can do this by typing Var. New sequence is equal to individual dot sequence dot take and pass in the first index. Then let’s call Dot to list then we can grab the middle by typing. Var middle is equal to individual dot sequence dot skip and we’ll skip the head. So in this case, that’s the first index, then we want to take second index minus first index. Then let’s call DA Traverse to apply our rotation. Lastly, we want to create the tail, which can be done by typing via tail is equal to individual dot sequence dot skip and we’ll pass in the second index. Great, so we now have our three components. Let’s combine them into the new sequence, so we can type new sequence dot add range and pass in the middle. Then we can type new sequence dot add range and pass in the end. Then Lastly, let’s return a new individual and pass in our new sequence. Okay, so we are very nearly ready to go now. Let’s just scroll up to our mutate method and replace our two comments by calling our respective mutating methods. Then, Lastly, we just need to jump up to our mutate, method and return new offspring, A comma new offspring be awesome, so hitting run, we can see a population is improving over time, and it is very likely that you will see the same numbers that. I’m seeing on the screen here note that there is a local minimum that your Ga might get stuck in. It’s shown here, and this is a result of us not guaranteeing that the individuals in our population are unique. If you put a breakpoint in your code right now, you will be able to check your population and it is very likely that every individual in your population is identical, but that is a problem for a future video. That is it. Thank you for watching. In our next video. We will cover convergence as well as a few other minor tweaks as with the previous videos. I’m going to leave you with a challenge question. At what point do we know to stop our GA from running and take our best results? Good luck, leave your ideas down below and I will see you in the next one.