Okay. Discrete Optimization, meta-heuristics. So that's what we're going to talk about today. So, we are still in local search. We have seen the heuristics last time. What we're going to talk about today is meta-heuristic. I want to talk about all of them, I just want to give you a flavor of what you can do. And so I will talk about three of them. Iterated local search, simulated annealing, and tabu search today. Okay? So the goal here, you know, heuristic is trying to, you know, drive you towards local minimum. Okay. What the meta-heuristic is going to try to do is to avoid you to be stuck in a pool local minimum like this one. You want to go there, right? So, but you may be stuck here. How can you escape that local minima. And such a way that you can still actually go to a high quality solution. So you have this trade off. Right? So you want to be able to go up, you know, because, otherwise, you're stuck into this local minima. But you also don't want to go too way far up and you never go down anymore. Okay. So you have to find this reasonable trade off in the ability to go up outside the local minina but at the same time you have the ability to sometime dive in and actually get to a very high quality solution. Okay? So, that is the trade off that we need to explore. Okay? So, iterate local, iterated local search is a very, very simple way of trying to achieve that. Okay? So, you start from the point [INAUDIBLE]. You dived on to the, you know, to the local, to a local minimum. Okay? Then you start from another place and you dived on again. Okay? So, you generate another point and you start and you try to go down and then you keep doing that. Okay? So, you start to have another point there and you just go down. Okay? And so, you do that for many, many, many different [INAUDIBLE] starting points and then at the end, you essentially take the best, you know, the best solutions that you have found. Okay? So that's the key idea of iterated local search, okay? So, so basically you execute multiple local search from different starting configurations, okay? It's generic in the sense that it can be combined with many other meta-heuristics, that I'm going to ah,show you later on. And it's often called multistarts search or search with restarts and so on. Okay? But the key idea is that you have a local search and you iterate it many, many times. Okay? And so, this is essentially the, you know, the pseudocode for for this, for this particular iterated local search. So you generate an initial solution. Okay? And then, essentia-, and this is the best solution you have so far. And then you iterate a number of searches. Okay? And every one of these searches is one of the local search that I've shown you in the previous lec-, in the previous lecture. Right? And then at the end of the day, this will give you the best configuration that this local search has found. If it's better than the best solution so far, you keep it. Okay? Otherwise, you just ignore it. Okay? And then you generate a new solution and you redo another stuff. Okay? You, you you, you, you re-, you research again from that you starting point. Now, that starting point can be completely, completely generated, you know, randomly or it can use a solution that you've found so far. Okay? And there are techniques, like, power linking which are sophisticated ways to do this. But the basic idea here is that you do whatever you want but you have to have a new starting point, which you believe, you know, is going to be interesting. Okay? It can be completely random or it can be [UNKNOWN] some of the solutions that we have seen so far. All the current solutions that you have. Okay? Now, let, so, so as I said, this technique can be most of the, most of the algorithms these days in local search or in other, you know, even when you do branch and bound or other, other searches, are using some form of restarts for actually improving the, the quality of the solutions. Okay? So what I'm going to do now is look at heuristics that are most speci-, meta-heuristics that are most specific. And so, I'm going to start here, you know, I'm going to talk about simulated annealing. But I'm going to start with the metropolis heuristic, which is a heuristic on which you build simulated annealing. Okay? And the basic idea here is, is, is, is the following. So you want to accept the move of use if it improves the value of the objective function. But, otherwise, you want also to impr, you know, accept move that degrades the, the value of the objective function but with some probability. And that probability has to be somewhat proportional to the degradation that the move is going to perform. If the move is terribly bad, you probably don't want to take it with a high probability. If it's really, really close, you know, to improving, you, you know, you want to take it with the higher probability. Okay? So the whole thing here that I am going to talk about is inspired by results in statistical physics and I will come back to that later on, okay? So this is essentially the way you're going to do. The probability is chosen between two things. A temperature, you can ignore it right now. So we'll talk little bit after, about it, afterwards. And the essentially the key aspect is the delta, the difference between the value of the objective function of the neighbor and the current value of the objective function. Now, of course, if this difference is negative, that means that the move is improving. And, therefore, you take the move all the time. Okay? But if the value is positive, okay? So that means that the move is degrading and you have to choose the, the probability of accepting that move, you know, carefully. And the probability, it is too high. You only, you, you're only going to go up and you will accept, you know, essentially, moves around degrading all the time. So you want this balance between improving and then sometime jumping up and moving up, okay? And that's what we are trying to do with this probability distribution. Essentially, you want to take the move or probability, which is exponential in the basically minus the delta. Okay? So, so remember, when the delta is positive that means that we are degrading, okay? So this value, minus delta is going to be negative in that point, okay? So, so look at this formula and then there are two things that, so this is the algorithm. And we'll look at the formula and, and actually analyze it in a moment, okay? So, but essentially, what you do here, you always combine this with a random selection of the neighbor, okay. So you, basically, take a neighbor in the neighborhood with a you know, random probability. So you get this beautiful neighbor, okay? And then, if you see if it improves, you take the, you take the neighbor. But, otherwise, if it degrades the value of the objective function, you flip a coin and, you know, with, you know, and decide with, you know, along, you know, with this probability distribution, if you except the move or not. Okay? And if you ac-, you know, if, if, if you, if you're lucky, you know, if the prob-, you know, coin turns well, you take the move. Otherwise, you just ignore the more, okay? And you stay where you are. Okay? And so you iterate this. You know, select another randomly, flip a coin. Decide if you take it or not and continue the way it is. Okay? Now lets look at this probability. So, if we have a very large delta. Okay? So look at this delta. Assume that it's very large. What's going to happen with this probability? Okay, the probability distribution that you see there. Well this number here is going to be, is going to be very negative. So the probability is going to be very small. So if you have a big difference between the current value of the objective function and the value of the neighbor's where you want to move to, the probability of actually accepting is going to be tiny. Okay? So you don't want to take really, really bad move. Although you could, right? There is always a small probability that you are going to, you're going to take it, okay? Now, let's look at this probability now, and this, this temperature now. Okay, so this, this temperature is very large. What's going to happen? Okay? So if the temperature is very large, that value is going to be what? It's going to be, it's going to be essentially tiny. And, therefore, you will accept the probability of accepting the move is going to be very, very high. Okay? So, essentially, if you have a large temperature, you're going to accept many, many, many, many moves. So, which basically means that you are basically performing a random walk. So you are walking, walking, looking around. Ooh, is this good? Is this good or not? And then, and then you're looking around essentially. But you accept move, that can be really bad, degrading you of function tremendously. Okay? So in a sense, if you have a very large t here, okay? So what's going to happen is that you are going to have a really, a random walk, okay? If you have a small t, the opposite is going to happen. If you have a tiny, tiny, tiny t, like 0.00001, okay? So that value here is going to be really negative. And, therefore, you're only going to consider, very, very, you're going to accept the move we've, we've on degrading move. Very, very, very low probability. Which basically means that in this particular case, you are kind of being greedy, right? So now what you have to think about is you have this temperature, you have also this difference in the objective function. And, of course, that's basically specific to the particular problem that you have. And you have to kind of balance these two so that you get a compromise between accepting degrading move and, then, at some point, being greedy enough to actually get to a local minima. Okay? And so you have to balance these two things. Okay? So what the simulated annealing algorithm is really trying to do is to try to achieve this balance in a dynamic fashion. Okay? So it's based on material physics where you try to, essentially, heat and then cool, you know, the materials, is that you, you know, generate beautiful crystals with almost no defects. Okay? And so, what you do is essentially here the key idea is that you start with a very high temperature, which means that you are essentially performing this random move. Moving along, looking hm, is this [INAUDIBLE] look here, is this [INAUDIBLE] look there and so on. Looking around and then progressively you are going to cool this temperature. And then becoming more and more greedy. Okay? So in a sense you start with a high temperature which is like a random walk and then more and more you are making it more and more greedy. Okay? And so when the temperature is really, really low you are basically doing a local improvement search. Okay? So essentially, the key here is that you start with a reasonable temperature, you're looking around and then, you decrease it, such that, at some point it, you know, it becomes greedy and you focus to a local minima. So in a sense, you bounce inside the search space everywhere. And when you think that you have a very good you know, neighborhood in that particular search you know, in that particular space, you dive down and try to get this good local minimum, that minimum that you want. Okay? So this is the description of the search procedure in a more formal way. So what you see is that once again is basically a set of of searches and everyone of these search is going to use. the, the metropolis algorithm is a lot of search with the metropolis algorithm. You are at a particular temperature and then you bounce around. You look, you look around and you try to find you know, you move from you know, state to state, configuration to configuration. Okay? So that will, you know, at the end of this particular search you will get a particular objective value. If it's better than the best solution you've found so far, you keep it. And then, what you do is you decrease this temperature and then you iterate the process. Okay? And the point is that at some point, the temperature is going to be so low, that the only thing that will is accepting, you know, moves that are, that are improving. And you, basically, convert to something which is a local improvement. Okay? So this is basic idea with the simulated annealing. So, what kind of random search will the particular probability of accepting degrading move the beginning, the first searches that you are looking at, you essentially accept everything. You are really, you know, looking around. And then as, as time goes on, you are [UNKNOWN] becoming more and more and more greedy until you really converge to a local improvement search. Okay? So now this, this simulated annealing you know, came from, you know, physicists and it, it has a very interesting property actually is that if your neighborhood is connected, okay? So you are guaranteed to converge to the global optimum. Okay? So you only need this, this, this connected neighborhood, you know property that I mentioned before. And if this is the case, if you have a very, very slow schedule, then you are guaranteed, you know, in the expected sense to actually converge to the optimal solution. Okay? The real, the only real issue is that this is actually slower than excess/g, exhaustive search. So, if you actually use this really, really slow schedule, it's going to take a long time to get to this optimal value. Okay? So, but in practice, in a sense, you will never use this kind of really, really slow schedule, where you decrease the temperature so slow that it's become boring, right? So what you are basically doing is that you're temperature cooling which is, which is much faster, okay? So let's say linear or geometric progressions or something like this. And once you do that, you can have really, really amazing bench, you know, results, on some very complicated applications or benchmarks. So the [INAUDIBLE], you know? The, the, the, the, the traveling term and problem, for instance has, you know, the best, the best solutions for the, for some of the larger. Initial instances has been found using simulated annealing on the complex neighborhood that I've shown you before. Okay? Same thing for some of your, you know some complex problems in [UNKNOWN] in, in scheduling, where you try to minimize tardiness of various tasks. Okay? So the basic idea here is that in practice, obviously, you don't use that slow schedule but you use the schedule which is reasonably fast. But still, the ability at the beginning to explore the search you know, to looking around and seeing where you should search. And then, you know, progressively narrowing down the search towards the local improvement is actually pretty effective, okay? So that's the key idea. Now, in practice you can add a variety of techniques. And so in, in some of the case that's what, you know, has been done on the TTP and other problems. You can always have restart. You can always start from multiple points. Okay? You can also do something which is called a reheat. If you're going too fast, you say ooh, ooh, ooh, I'm going way too fast. Now let's step back and, you know, increase the temperature again. Look around, you know, and then dive again. Okay? And there are also many properties of, of, of, of tabu search that I'm going to talk in a mom, about in a moment that you could actually incorporate in simulated annealing algorithm. So this is. So, once again, you know? This is an introduction. I'm giving you the basics. But there are many other techniques that you can actually use, okay? so I talked about this already. So we can, you know? Like in most restarts, you can always start from multiple points. It's very useful for the TTP as well. And then you can also increase the temperature if you want to at some point. Okay? Now, let me talk about Tabu search now, which is the, the last meta-heuristic that I want to talk about today. And so, so I'm going to first give you the intuition. And, and most of the presentation in this lecture is going to a high level on tabu search and the next lecture is going to focus on tabu searh exclusively. But, this is the idea. This is what we really want to do in practice, right? So, you start with a node and you dive down. You get to this beautiful local minima but you, you know, it's a local minima. So what you want to do is to say, oh, can I step up now and try to find something which is better? So you can, you decide, oh, I want to step up over there. And then, you go down, you know, again and you say, oh, this is a better local minima. Okay? So the problem is that this is actually difficult to do. Why? Because Tabu search is this kind of greedy search procedure. And typically, when you are at a particular place, if you select the best neighbor, he's going to be, you know, where you are or where you have been. So you're going to stay at the same position, okay? So what you need to do is something that essentially, keep track of the nodes that you have visited. And these nodes are going to be blue. Okay, I wanted them to be yellow but count on Tony they have to be blue. Okay? So this is a blue neighbor. A blue neighbor is a neighbor which is essentially tabu. I have seen it already. I don't want to go back there. Okay. Yellow was a better color but anyway. Okay. So, what we see here we are in this particular blue state. Okay? That means I have been there. And now I can move to that particular position here. Okay? So, that's fine. Now, look at this thing. Okay? See, if I had a neighborhood here. If I, if I look at the neighborhood here. Okay? And I use tabu search, where I always want to improve in a greedy fashion. Right? So, I would go back here. Right? So that's what I would do immediately, okay? But no, no, no, no no, no. I can't do that because this guy now is tabu, okay? Tabu means, I can't go back there. I have visited that node, I want, I can't go back. So you are kind of forced to move to a node which is, which isn't ever, you know, as good an objective function. And, therefore, you move to this thing there, okay? And once again, once you are there, you know, tabu search is going to say, oh, [UNKNOWN] while local improvement is going to say, oh, I want to go there, oh, I want to go there, that's better, that's better, that's where I want to go. But of course, these things are tabu, so you can go there. So this thing is forced to go up there. Okay? And that's good because now you can go down and hopefully find the optimal solution in this particular case. Okay? So this is the abstract idea behind tabu search. Okay? So you maintain something which is called the tabu list. Think of it, this is all the nodes you have visited so far, and you never want to go there again, you have been there. Okay? Seen that. Okay? I know what these nodes are, okay? And this is a set, this tabu list is a set of tabu nodes, nodes that you've seen already. Okay? So what you do, is, as usual, you start from an initial state and then we build a sequence, okay? Two is a sequence of, of, of nodes that we've seen so far, okay. That's the tabu list, okay. That's all the strings that I have seen, okay. And then you do a local search, like normally, right? So if it, it's a number of iterations at every iteration, you take, you, you look at the, you look at the state that you are in. And if it proved the best solution so far, you take that move and you're satisfied that's the best solution you found. Otherwise, you generate a new neighbor, which is essentially which is essentially, which select the legal moves, and we're going to see what these legal moves are. But they have to be moved around that tabu, right? And then in the neighborhood. Okay? And what you do then afterwards is that you increase this two function, and the two function is node, another node now, another node now that you have visited, right? So, and that's what this, basically, generative framework does, okay? And so in, when you do tabu search, the only thing that you do is you have to use legal move config legal move functions that tells you the node cannot be tabu. Okay? So, in a sense it's the traditional local search, but you have to say. Oh, I won't select neighbors that are tabu, okay? And, of course, you've this list, this [UNKNOWN] and you can just test if the [INAUDIBLE] states that you want to move to is, well, you, you want to test if the, the le-, is this movie's going to be legal if its not tabu. Okay? And so that's what you see here. Okay? So basically look inside the tow is the move, is inside the tow. Okay, so you know that you visited, so far, you do not take it. So the legal moves are all the moves in the neighborhood that are not in tow, that are, haven't been visited so far. Okay? Now, this the kind of crazy behavior that you get with tabu search. And that's what I love about tabu search. It just go up and down [SOUND] like crazy. Okay? So it's very interesting to see what it does. Okay? So this is on a resource allocation problem where we are trying to minimize the violation. So the y axis here are violations and these are the iteration of time. And, what you see if that are these are, this objective function is going up and, up and down. The, you will get this good trade-off trying to escape and then trying to focus on trying to find a good solution. And in this particular case, you see at the end, we find, we find a violation of zero, so we find a feasible solution to this particular problem. Okay? And it takes, you know, 160,000 iterations, 160 1, 1, 6, 160, hundredth thousandth iteration. Okay? So this is zooming about the last set of iterations here, and what you can see as well is this kind of very, very, you know, chaotic behavior of our tabu search. But in a sense, you go up but you always, you know, go down reasonably soon afterwards. And that's typical behavior of tabu search in this particular case. This is a graph coloring application where you try to minimize the numbers of colors this, you know, using satisfiability as as a subroutine. And once again, you see this behavior, kind of chaotic behavior, where you go up and down, you go up and down, and so on and so forth. Okay? So, so that's what I wanted to talk about today. Next lecture I will focus again on tabu search and give you all you can actually implement this because so far it has been at the very abstract level. But there are many, many other heurist-, meta-heuristics that have been in, in you know, implemented in, in, in and proposed. You know? Variable, you know, neighborhood search. Guided local search and colony optimization. Hybrid evolutionary algorithm reactive search. Scatter search. Plenty of others. some of my colleagues are going to be completely upset with me. Because I forgot to include, you know, their favorite ones. but I did this slide since 5 AM, so, you know, bear with me. but essentially, there are, you know, once again, this is an introduction. I gave you some of the principles. There are many other ones that you can, that you can actually study. Okay? See you next time for more on tabu search.