0:00

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.

Â