Hill Climbing Algorithm In Artificial Intelligence | Artificial Intelligence Tutorial | Simplilearn

[0:08]Hill Climbing Algorithm, AI. My name is Richard Kirshner, with the Simply Learn team, www.simplylearn.com, get certified, get ahead. We're going to go ahead and cover the hill climbing algorithm. And as we focus on this, you'll probably really want to look more at the mental process, the soft skill of how to solve this. As a whole concept of hill climbing, um in finding solutions this way are becoming more and more embedded in other projects and other models. What's in it for you? We'll start with what is hill climbing algorithm? We'll look at hill climbing algorithm features, state and space diagram, types of hill climbing algorithms, problems in hill climbing algorithms, uses of hill climbing algorithms, and we'll finish with a demo of this very simple, um setup. What is Hill Climbing Algorithm? Hill climbing algorithm is a local search algorithm which is used to find the peak of a mountain or the best solution to a problem by continuously moving in the direction of increasing elevation. Now, instead of elevation, you can also look at this as um inverted where you're looking for the minimal error, which is what we see in almost all our models. But a lot of times with hill climbing, we are looking for the highest elevation or the best solution or the best set of matches. Consider the elevation shown. Using Hill Climbing Algorithms, we'll select a point to start at and move upwards until we reach the highest peak in a local area. And we can see here a nice, uh, algorithm of the flowchart, you're going to select a current solution. You're going to evaluate that solution. Select a new solution X from the neighborhood. And then evaluate X and you look at is S better than X? Yes, select S as current solution. No, we go back and select a new neighbor from the thing. So it's a lot of guessing. You really think of hill climbing as just a lot of guessing, but we want to educate the guess a little bit by guessing which way is uphill or which way gives us a better solution. So let's take a look at the hill climbing algorithm features. Features of Hill Climbing Algorithm. The generate and test an alternative. So the hill climbing algorithm is a variation of generate and test algorithm which generates alternative courses of action to see if they will solve the problem. You can look at this as a little bit of, of a game of hot and cold, if you ever played that as a kid, when you're getting closer or farther from something or high low in a number game. There's what they call the greedy approach. Hill climbing algorithm will always move in a direction which will give the best outcome. This is done to optimize the cost. One of the interesting features of hill climbing is there's no backtracking. You don't go back to the old solution, either move forward, um onto your new one, or if it's not as good, you try something new from your original point. The algorithm cannot go back to its old path. It does not remember its previous state and cannot backtrack. This comes so important when we're talking about, um, uh, especially reinforced learning. How do we guess what the next choice is and things like that. Uh, you really can't go back to the beginning, you have to go from wherever you're at. So let's take a look at the state and space diagram. The state and space diagram is a representation of the Hill Climbing Algorithm which shows the various states of the algorithm and their corresponding cost function values. The Global Maxima represents the highest peak in the entire state space diagram. This region has the best cost function in the entire area. And you can say that'd be your primary goal is to find the global maxima. The Local Maxima is the highest peak in its neighborhood, but there exists a better state (Global Maxima). It has the best cost function in its area. So we have our full area where you have your global maxima, and then we have our local maxima, so this is a peak that's somewhere else in there. A Plateau is a flat region in space. The neighboring points in a plateau have the same cost function. And hopefully you're already thinking ahead that that is a major problem because you don't know which direction to go, uh to maximize your um value on here. The Shoulder is a plateau which has an upwards edge. It curves up a bit further on and leads to a higher elevation. Very much like the plateau. And then we have the current state is the region of the state space diagram where we are present during the search. And you can see here a nice full diagram where we have the shoulder, the global maxima, the current state, the local maxima, and the plateau. Um, all the different objects we're going to be working with when you're looking at doing hill climbing solutions. So let's take a look at types of Hill Climbing Algorithms. And the types of hill climbing algorithms, we have the simple hill climbing algorithm. It is the easiest variation of the algorithm. It examines neighboring points one at a time and selects the one which optimizes the current cost as the next state. The steepest ascent hill climbing. In this variation, first all the neighboring points are examined and the point closest to the solution is taken as next state. This more time consuming. Uh, so you can see here where we select an initial point and evaluate it. If it is goal state, then stop or set current state as initial state. Loop until a solution is found, current state does not change. Stochastic Hill Climbing. This algorithm does not examine its neighbors before moving. It selects a random neighbor and decides whether to update it as current state or not. Uh, so select a random point and evaluate. If it is a goal state, then stop or set current state as initial state, or select another point. Loop until a solution is found, current state does not change. So problems in hill climbing algorithm. These are the, the um, things that come up and we've already looked at some of the vocabulary words. Uh, and so we look at this, local maxima. The algorithm might arrive at a local maxima and take it to be the highest elevation. This can be solved by backtracking. We can simply keep a list of promising paths for the algorithm to follow up on. We have our local maxima. Uh, so it says, hey, this is a really good value. Any direction I go in is going to be worse. And so you might uh, save that and then increase how wide your random selection is going in each direction until you find it a another switch in the slope. Your plateau, um, is not you what direction is the best direction? Well, you have to just keep going again. You keep going to random points until you go to one side where you're either going down, and then you might go random in the other direction. Uh, again, this is very conceptual. There's a lot of different algorithms out there to solve these. Uh, being aware of how they work and the problems that come up when you are working in a specific domain greatly helps in solving these solutions. And the ridge, again, we're looking at, um, it it's the highest area in the area, but uh, you have to overcome this problem by again. You have to get off of this ridge onto the next ridge to see if there's a better top part on there. So what is the uses of hill climbing algorithm? Hill climbing algorithm can be used for solving various problems such as evaluation problems, robotic coordination, and inductive circuit design. And you can see here we have problems which require evaluation and thinking, coordination between robots and the circuit design. And you can really think of this in, um, a number of terms. One, you is really hard to use the hill climbing algorithm if there is a huge amount of uh, features. So you're usually looking at the hill climbing as a single point or a very small amount of changes uh to solve the solution of things you're trying. I've seen this a lot in gaming. Uh people build their Robo character and they the Robo character moves left, right, up, down. It has a very limited amount of things it does and it just tries a number of different movements until it gets the right one in that situation. And this is also true when dealing with robotics. A lot of times the end output for robotics is uh, left, right, or on, off. In which case, it's very easy to start looking at, hey, what's the best algorithm for solving that. Uh, the algorithm can also be used to solve the Traveling Salesman problem. If you're not familiar with it is worth looking up because it takes just a massive amount of computation to figure out what is the best route, um, for the salesman to go in. Which, uh, in which, given a set of cities and the distances between the cities, we want to look for the shortest route to take to visit each city. How can they cut their cost and traveling? Uh, and there's a lot of different form of this for this, but the traveling salesman, this is one of the solutions they come up with the traveling salesman on here. So let's go ahead and take a look at a Python demo for hill climbing algorithm and just see what kind of setup we're looking at. And we'll we'll keep it simple. Uh in this demo, we will implement hill climbing algorithm using Python and get a step-by-step viewing of its working. Now, I'll be using the Anaconda navigator for the Jupyter notebook. Um and then I'll create my a new uh Python 3 version. This is actually 3.6 that I'm in. Uh, there's newer versions out, but 3.6 is very stable and it functions with all the modules I use for other things. And the first thing, when you thought when we did the hill climbing, the one thing I kept talking about and repeating over and over was random. So the first thing we want to do is import um random, we'll go ahead and import string. Depending on your setup, they might already be part of the packages, but we're going to bring it in anyway. Uh, and the first thing we want to do is create a little uh function to generate um random solution. And I'm going to send it answer. Uh and so, when we do this, let's just go ahead and and uh print it's going to return a random string. So we'll just go ahead and generate just so you can see what this does. Random solution. Um, and then I have to send it a string and we'll go ahead and send it. Hello, world. I'm going to have to work on my typing today. Run. And you can see that it generates a random string. And the string is the same length as hello world. So it has as many letters in it as hello world has in it. Uh, that's just going to be our our initial seed. Um, we need something to initialize whatever we're going to do on here. And then we're going to evaluate the solution. Um, evaluating a solution for the solutions, for solution S. Uh, and again, I want to send a solution in and an answer and the difference. And we'll go ahead and print this. If you remember up here, um, let me go ahead and and just grab this. There we go. And here's our solution. Uh, our solution is going to look like our answer. Oops, our solution that we're trying. Get a little confused here. So we're going to try this. And our answer we're going to have is hello world. So let's just paste that in there. And let's run that. And you see right here, it generates a uh, different by 400. So it's going to give us a value on here. Uh, and this is just looking at um, uh, 01234, the absolute minus the ordinates. What we've done is each one of these letters is a, um, representation. You can represent it with a number. And so we're saying, hey, um, the difference between these two numbers, like the difference between W, lowercase W and uppercase, um, in this case, uppercase W over here, I don't know if that's matches or not. Uh, but the difference between those is an actual number we can look at. And so we want to keep evaluating until this number goes down and then just adds those all together. And then if we're going to do a lot of guessing, we'll go ahead and create a mutation. Uh, to mutate means to change in a small way. Here, we change random letters in our string to arrive at the best solution. Uh, and sometimes you actually, um, there's you can play all kinds of games and instead of doing one index, maybe change two indexes. There's a lot of different options you can do in here. Uh but you can see, if I take uh this solution here, which I printed up, which I pulled from up here on the top, and I run through and I print it out, if you go through letter by letter, you'll see that one of these changed. Um, let's see if we can find it. Here it is. The W became a greater sign. And then we take this and we'd run it through the evaluation and say, is this closer to the solution or not? And depending on this W versus the, you know, with the evaluation of this on the, um, hello world is it closer or is it not? Then we'd either keep the new solution, or go back and try another random one. We'd mutate it again. And so we can go ahead and take all of this and we can put it through into a uh loop here. And so we're going to take our answer, we're going to set it up as hello world. I'm going to find the best, uh, generate random solution answer. So I'm looking for the best and we're just going to keep generating a new solution on there. Uh, best score. So we're going to evaluate it. And then let's just go ahead and loop through that. This is just initializing our our best and best score values. And it says, while true, print the best score, best score, um dot join best. And uh if best score equals zero, we're done. We match the algorithm. Uh if not, we're going to go ahead and find a new solution, which we want to turn into a list. Um, and then mutate the solution. So here's our um, mutation of the new solution of new solution. And then we're going to score, score equals a new solution to the answer. Remember I put the answer up here as hello world. And then if evaluate new solution answer is less than best score, best equals new solution, best score equals score. And so we're just going to keep improving the score on here and we're going to keep guessing. And if we run this, it's going to generate a lot of um, data coming out here. It has a page break in there. Let me uh, just stop that and run it again. There we go. Um, because it's random, it include page breaks. And so here's our guess down here. It says best score is 620. This is what we're guessing. Um, and then somewhere in there it does a bunch of guesses and it keeps changing and it keeps changing it and then you see the score drop to 585. And so one of these changed and the difference in value was so huge that you see a huge drop on there as far as the um, letter, the the integer value we connect to that letter. Um, and as it goes down, it just keeps dropping and dropping and dropping. Let me just scroll way down here. And you'll see eventually it gets down to Helmo world. And then eventually it guesses, hello world. It just keeps trying this until it finds a new best. And of course, we can change this, um, I like putting in the answer in here just because I can also run it like high. Something real simple. We can run that. And you can see quickly goes through and calculates high. It doesn't take it very long to get to the high value, um, compared to many letters. And when you're doing guessing, the first thing I want you to notice, is look how much guessing you had to do. Uh, it takes a lot of guessing. And so you want to keep your guesses very limited. If you're running this on a huge model to predict something, you're going to run into resource problems, especially time. It's going to take a lot of time to guess this many. Um, so you want to make sure your guesses are good and you optimize your guessing patterns. The second thing you really want to be aware of, and I've seen solutions that do this also with the guessing, is they might, uh, split this. And so we might have five different solutions guessing the answer and split it is because you'll end up with local maxima. And by splitting it and doing randomization across multiple solutions, you that's one of the ways to get away from that and have a higher chance of finding the global maxima. So there you have it. There is the hill climbing algorithm. Thank you for joining us today at Simply Learn. For more information, please visit www.simplylearn.com. Get certified, get ahead.