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.