What are Genetic Algorithms?

genetic algorithms are a powerful optimization technique that is inspired by the process of natural selection just like evolution in nature genetic algorithms allow us to evolve possible solutions to difficult computational problems welcome to the first video in a series on evolutionary computation today we'll be diving into the world of genetic algorithms and will visually demonstrate the principles that allow algorithms to evolve to understand genetic algorithms we'll have to review some biology all living organisms have DNA which stores their genetic information this information codes for the observable traits of the organism the genetic information is referred

to as the organism's genotype and the traits of the organism are its phenotype so how exactly do these organisms evolve well there are three ideas that explain how Evolution occurs the first idea is that there is variation within a given population in this example there is variation in color some individuals are a lighter gray and others are a darker gray the second idea is that not every individual can survive limited resources and the presence of predators means that some individuals die before they can reproduce for example individuals that cannot blend into the environment are more

likely to be eaten by predators the third idea is that traits are hereditary in other words children look very similar to their parents though the occasional mutation is possible here the individuals that blend into the environment more effectively have reproduced the combination of these three factors allows for a process called natural selection to occur individuals that have more advantageous traits tend to survive long enough to reproduce ultimately making their traits more common in the population over time the population as a whole becomes increasingly successful at surviving we can apply these same principles to computational problems

in the form of genetic algorithms let's convert the camouflage example into a working simulation the first step is to Define our problem in this example we want our virtual organisms to camouflage themselves in an arbitrary environment next we need a way to represent our candidate Solutions with genetic code and to be clear candidate Solutions just refer to our virtual organisms and while real solutions have DNA we can use binary sequences to represent our Solutions we'll use 8-bit sequences which when converted to decimal notation produce a number representing the color of the organism finally we need

to define a fitness function for our problem a fitness function is an equation that we create to evaluate how successful a given solution is in our case the fitness function is very simple we can calculate how close the organism color is to the background color and subtract that from some large number with this function we can see that organisms that are closer to the background color have higher Fitness scores and organisms that are farther have lower Fitness scores with that we have everything we need to run the genetic algorithm itself which is essentially an iterative

process of simulating natural selection first we randomly generate an initial population of solutions the next step is selection we evaluate each Solution by our fitness function and sort them by their Fitness scores we'll select the top 50 of solutions to continue on to the next generation finally we need to replace the solutions that have been eliminated so in the reproduction step we will use genetic operators to create the Next Generation in this case we are using the mutation operator each Survivor from the selection phase will get to reproduce ones but each gene has a one

percent chance of mutating and with that all we need to do is repeat steps two and three until a good solution is found [Music] [Music] by generation 10 we can see that a majority of solutions closely approximate the background color there are a few individuals standing out that are the Unlucky recipients of bad mutations but the population as a whole has done well and to be fair the problem was not very challenging let's try to make it a little bit more difficult by changing the background color over time and to more easily visualize the changes

I'll add some statistics on the left of the screen foreign [Music] [Music] foreign [Music] the genetic algorithm does a pretty good job at adapting to the changing background there are times where the population seems to stagnate on the line graph and these represent moments where a specific rare mutation is needed to adapt to the background color it can take dozens of generations for an individual to get the correct mutation but once it emerges it very quickly spreads through the population we'll count this as a success for the genetic algorithm but let's try solving a more

difficult problem is it possible for a genetic algorithm to solve a maze let's find out first we'll need to create the maze which fortunately is an easy task while our maze is being built let's talk about our approach we will represent each of our candidate Solutions as a series of moves through the maze each move can be written as a two-digit binary number allowing us to convert the entire series of moves as a long binary string for each solution we'll evaluate the list of moves through the maze if the move would cause the solution to

collide with the wall we skip it additionally we'll prevent the solution from backtracking which will prevent it from jittering back and forth finally we'll need a fitness function let's keep it simple and use the distance between the solution's final position and the exit we'll also introduce a new genetic operator known as crossover that will be used alongside mutation with crossover you take the genetic code of two parents cut them at a random point and Swap all genes after the cut point this results in two children each inheriting genes from both parents visually this is like

following the path of one parent then swapping to the path of the other parent this will allow us to explore a wide variety of different solutions and by now our maze should be completed so let's test out the algorithm instead of evaluating one solution at a time we'll evaluate the entire population at once [Music] foreign [Music] [Music] it seems like the algorithm is having a hard time making it past this corner and the problem is actually our fitness function to understand why this is happening we need to take a closer look at how genetic algorithms

make use of the fitness function imagine a hypothetical genetic algorithm using just one gene this Gene can have a range of values and we can evaluate the fitness for each possible value while the members of the initial random population could be anywhere along this curve the ones that are closest to the Peak Fitness value Will Survive to the Next Generation with random mutations over time the population will eventually settle at the top of the Curve but what if the fitness function looks more like this as we run the genetic algorithm we'll find that the population

might get stuck inside a smaller Peak even though there's higher possible Fitness values the algorithm never reaches them because that would require it to First lose Fitness this is what's known as a local maximum and it's exactly what's going on in the maze in order to progress through the maze the population needs to move further away from the exit and according to the current Fitness function that is bad let's fix our fitness function instead of only considering the distance to the exit let's add some more factors well reward solutions that Explore More Of The Maze

since this will increase the odds of finding a path to the exit will also reward solutions for making more legal moves since bumping into the walls only wastes time finally We'll add a penalty for solutions that get stuck inside of dead ends let's see it in action [Music] thank you after just 17 Generations one of our squares manages to reach the exit and the population continues to improve from here using a heat map we can see that more and more of the population begins to move towards the exit and while not everyone makes it to

the Finish Line most of them make it pretty close this is not always the case though there are some mazes where the population still gets stuck in a local maximum and progress towards the exit if any takes hundreds of generations and that's actually a problem with their approach every solution blindly follows their list of moves without actually perceiving or even understanding the maze around them they're essentially solving the maze blindfolded to get improved results we'll need to add thinking and perception in the next video we'll explore how we can use neural network brains in combination

with our genetic algorithm to get improved results see you then foreign