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.