Okay discrete optimization, but I can tabu search.
so I want to spend a little bit of time on tabu search because this is very
interesting and I want to, I want to tell you a little bit of a story before.
So, so, John Hooker once told me that, for every invention, there are very,
there are three stages. Okay, so the first stage is that people
are going to look at the invention, and say oh, this can't work, okay, this is
all wrong, okay? And so that's the first stage and then
you go to the second stage where people realize that this is actually working,
but then would say, oh, but this is trivial, okay?
So, that's the second phase of an invention, people will say it's trivial.
And of course that lasts for a while and then the third stage is the most
interesting one. People will say, oh, that invention, I
invented it. Okay, i'ts a footnote in my thesis, okay?
So tabu searches like that. Okay, so amazing thing, you know it was
invented by you know Fred Glover. And the first time you look at this, you
say, well this can't work right? So and then could and you see on your
favorite problem these reserves that are coming up and are amazing most of the
time right? So you say, wow this actually very, you
know this is actually working. But it's so simple it's not even
interesting right? And then afterwards, you spend your life
working on tabu search. Right?
So, this is, this is what tabu search can do to you.
Okay? So, so I want to spend some time in
telling you some of the richness of this particular meta heuristic.
And, and, and all the issues that you have in trying to design the right
compromise between different aspect of, of tabu search algorithm.
So remember what we wanted to do is that we start from a point, we go back down to
a local minimum. And then sometimes we go back up, and
then, and we want, we have the ability to go back up and then to go down.
If we don't have anything, typically you, you can't escape this local minimum, you
would stay here all the time. Okay.
So the idea of tabu search is that you know, one, once you have been to, to a
particular state you consider it tabu. Okay?
So you have seen it, you don't want to go back there.
Okay? And then you can start going up to a
particular node like you know, this one. And obviously when you are there you, you
know, if you have something like a you know, greedy approach.
This guy may be in the neighborhood and then you will want to go there.
Okay? But since it's tabu you can't go there,
so you will have to find the next best. If you have let's say a greedy approach.
Okay? And this one may be the next best, and
so, so you move up there. And once again, when you are up there,
this guy will say, ooh, I want to be greedy.
And he's going to look at this one, and of course the first one, and say, ooh,
that's where I want to go. But once again, you can't do that because
you are tabu and so you go up. And now you are the top of this, top of
this landscape, and you can actually start going down.
To to the ultimate solution, okay. So in a sense, the key abstract idea of
tabu search is that you keyboard knows that you visited, okay, and you never go
back there. Okay, so you have been there, seen them,
no way you want to return to them, okay. So this is the pres, you know, the tabu
search algorithm that I've shown you. The key aspect here is that you always
skip this tabu list of all, essentially, the nodes that you have visited so far.
This tool is that you increase every time you move to another, another, another
state, okay? Now, one of the basic issues with the
tabu-search algorithm is that, you know, if, if, you, you want to select the best
configuration that is not tabu. Okay?
So that's what we have seen. But one of the basic issues is that it's
very expensive to maintain all these states that you been there.
Right? So assume that you have, you know,
thousands of variables. You would have to keep them, and you may
visit, you know. So, as I've shown you last time you know,
100's of 1000's of configuration. So you start using a lot of space and
every time you have to try to, every time you select a neighbor, you have to say,
oh, is it legal or not. So you have to compare it with all the
stuff that you have varied. That you have seen.
So it's very, you know, expensive from, let's say, a time and a space, you know,
standpoint. So what you can do is to use what is
called a Short-Term Memory. Instead of actually looking, keeping all
these notes, you are going to only look at certain, you can only keep a subset of
them. And essentially, the recent ones.
You are looking at a subset of these two lists, okay?
And so you, you look at the suffix of that list, which already knows that you
have visited recently. And what you're basically saying, I don't
want to go to the stuff that I've been recently, okay?
So, because you have, you know, you, you can expect that, you know, the nodes that
you haven't seen for a while, they are very far away.
They are not inside your neighborhood, so you don't care about that.
Okay? So if you keep, you know, if you keep a
fixed length list, tabu list, okay, so you basically, you know, keep the last
20, who knows if you have something like this, okay.
Of course, in practice, you can dynamically increase or decrease this
list to get a good compromise in not being stuck in a local minimum but not
preventing, you know, not, not preventing, you know, you to actually
diversify this this, the search too much. So you can decrease, for instance, the
size of the list if the, the objective functions is, is degrading, or, you know,
increasing it when the, when you actually improving the objective all the time.
So you can use things like this, okay? So, so, the, the question that you have
is that at that point you are still storing entire consideration.
Okay? And that means still be too costly.
Sometimes it's not. You can actually implement things like
this. But sometimes you, you are going to say,
wow, this is really costly. I have to store this entire state, I have
to do all this comparison that's, you know, taking a lot of time.
And my sense is that I want to, you know, valid, many, many configurations very,
very quickly. So, so, what you can do is, is instead
of, you know, storing these states, you are going to store an abstraction of this
suffix, okay. And the way show this abstraction can be
arbitrarily complicated or arbitrarily simple.
But you have to find a way of very concisely abstracting these sets of nodes
that you have visited recently. Okay?
Now, many possibilities, and I'm going to show you some of them.
Okay? So, this is the car sequencing
applications that I've shown you before. Okay, once again, you have this assembly
line. You can swap, you know, different
different slots of the assembly line. And this is a, this is a greedy local
improvement algorithm, and what you do is you select essentially a particular slot,
which is, which has violation. You are violating some capacity
constraint. You select another slot, that's a
quadratic neighborhood, okay. And then you are basically saying, oh, I
want to take the best of these moves, okay.
And so you apply the move and it's improved the, the value of the object if
you take it. Otherwise, you, you know, you, you're in
a local minimum, so you break the search. Okay.
So this is a greedy algorithm, okay. And so, what I want to do here is
implement a tabu search algorithm. But I wan, I don't want to keep this
configuration as I told you. We can you know, we can explore hundreds
of thousands of them and then maybe you know, 300 you know, slots you know, they,
they maybe come 300 slots or more. So this is a lot of space and a lot of
time that you would spend just comparing these things.
So what we're going to do is that instead of storing these states, we are going to
store the transition not the state them self.
And the transition in this particular case is what.
I'm just swap 2 cars, okay. So you're basically saying okay so a move
is swapping these 2 cars, okay ai and aj in the assembly line.
And so what I'm going to store inside the tabu-list is these pairs, ai, aj okay.
right actually I, I wrote ai, bi okay, so our basically you are remembering that
you swap these 2, you know you swap these 2 slots on the assembly line.
And the key idea is that you know in the future you don't want to re swap this two
because you are going back to place where you have been, okay.
So instead of keeping the state you are basically keeping the operation that have
been moving you from state to state and in this particular case is basically the
swaps, okay. And so configuration is going to be tabu
in this particular abstraction if it can be obtained by swapping two things which
are inside, inside the, the tabu list. So, so what you're going to do is that
you're only going to look at the swaps essentially which are not inside the tabu
list. Okay?
So you can swap things that you have been swapping recently.
That's basically the abstraction here. Okay?
So in a sense, you are not storing the states, you are not really, you are not
really actually abstracting them in a complete you know, exact fashion.
But you are basically remembering some operations that you have done so far.
And you don't want to apply these operations again.
That's the kind of things that you do here.
Okay, so how do we implement this. So, this is the basic idea.
So what you do is you keep a counter IT. Which basically denotes the iterations
that you are in inside the the algorithm. Okay, so every time you perform a move
that counter is going to be incremented. So this is the IT you know counter.
Then what you use is a data structure, tabu ij, okay where i and j are the 2.
Two slots that you can, can, can swap and that data structure is going to represent
the first iteration when it's going to be legal to actually swap i and j again.
So, so think about, think about it this way.
Okay? So i and j, you have just performed the
swap between i and j. Okay?
And you want to make sure that you're not going to sub these two guys for a bunch
of iterations. So inside tabu ij, you remember, you,
okay, you store the next, next iteration, where it will be legal to actually swap
these two slots, okay. So, and, and, so, in, in the next two,
two conditions here, I'm going to used a fixed tabu size of L.
But you could, you know, you could have a dynamic on each side, so the same
principle applies. Okay, so, so essentially, when is a move
tabu? Okay, so a move is going to be tabu.
Is the value tabu i,j so, i,j is going to be tabu if tabu i,j is actually greater
the iteration number. Okay.
So that means that [UNKNOWN] is only later than I will be allowed to actually
swab these 2 guys. If the counter is smaller, that mean you
okay can swap it. You know, it's allowed at this point.
It's legal at this point to swap these 2 guys.
So it's very easy here in constant time if you can find if a move is tabu.
Okay. So, and, so when you apply a move, of
course, you have to update the tabu status, okay, the tabu data structure of
that particular move, okay? So and essentially if you are basically
swapping i and j, tabu i and j is going to be the value of the iteration
constant. You know counter plus L which is the size
of the tabu list. Once again if the tabu list is dymanic
you know L is changes over time but this doesn't matter right?
So you are basically, basically saying [UNKNOWN] this is it plus L is the next
time at which you can actually swap these 2 guys again.
Okay. So that's the basic idea.
So very simple in the a sense. So you keep track of when you can perform
a move. And it's going to tabu, you still cannot
perform the move. And when you actually perform the move,
you make sure that you remember when is the next time which you can actually
apply the move again. Okay?
So this is essentially the algorithm. It's basically instrumenting, you know,
the, the, the, the greedy local search that I've shown you within this sub-data
structure, okay. And, so, so focus on the highlighted part
there. And it's actually pretty reasonably
simple right. So what you do is you compute the neighor
root. You know as usual, and then what you have
to do here is you have selection which is basically is basically trying to find out
which of these neighor roots are legal. Which of them are not tabu.
And they way you do this is you take these pairs and then you test.
If the iteration counter is actually greater than the tabu values that is
[UNKNOWN] for that particular move, okay? And then the next thing that you have to
do is that when you actually perform a particular move you've to make sure that
these counters are, these tabu data structure is updated with the right
counter. And in this particular way, we are
swapping i and j, right? So swapping i and j or swapping j and i
is the same thing so we changed basically the, the, the, the, the tabu value of
both of these move because they do the same thing, okay?
And so, essentially, what, this is what you do.
You always take, you know, you always take the, the, the neighborhood filters
it that you only can keep the values which are not tabu.
And when the, you know? When some of the moves are not tabu.
You take the best one, you apply it. You had did this tabu data structure,
such that this move becomes the, the, this move this particular move become
tab, becomes tabu and then you keep iterating this.
Of course, at every step you int, you know, you increment you know, the
iteration counters which mean that some of the moves that are currently tabu are
not tabu any more. Okay?
So that's the basic idea. Very simple filtering and then updating
the data structure. Okay?
Now what happens if all the moves are tabu?
What's going to happen? Are you going to get stuck forever?
Well, you have this very nice iteration counter.
Right? It's increasing all the time.
So if all the moves you know are tabu what is you sit around and you wait a
little until the counter has incremented eonugh such that some move is not tabu
anymore. Okay, so you don't get stuck essentially
you just have to wait, wait a little bit until the next move is not tabu.
Okay, now in practice the schematic that I've shown has a lot of things that you
can do a lot much better. So typically, you don't perform the
swaps. Okay, to find the best ones, you're
typically using chromountal data structure sets.
You can evaluate these things very quickly.
You never simulate the move and then [UNKNOWN] that's what the move is giving
me. You always try to say [UNKNOWN] if I
would perform that move that would be the value of the objective function.
This is called differentiation in sense it allows you to explore many many more
moves. And every one of these moves evaluations
is much faster. And there are a lot of paper that are
describing how you do that for various you know problems it's basically finding
the right data structures to evaluate moves very quickly.
and this is very important because in general you know tabu search is always
somewhat greedy or semi greedy. You always try to find the best or some
of the best algorithms the best neighbor to select.
Okay? So that's a key aspect here.
You are not evaluating all the moves in a systematic fashion.
You are basically using differentiation and trying to evaluate them very quickly,
not performing the actual move for actually evaluating it.
Okay? Now what you, one of the things that you
may say the, but, but what is this abstraction?
Is it too strong, is it actually stronger than the, than the, than the, the suffix
of the tabu list, or is actually weaker? And the answer is it's a bit of both.
Right? So this is too weak because it cannot
prevent cycling, right? So because you, you don't really keep the
nodes, you, you also don't keep, you know, the entire list of states that you
have visited, right? So you only consider a suffix, so, so you
can still cycle here and go back to a state that you have seen.
And then do a number of operation, go back to that state.
Do a number operation go back and you cycle.
Okay, so, so there is no way you really, your, it's a too weak in that sense.
You can go back to state that you have seen before.
When you do that, what do you do? Typical you increase you know the size of
the tabu list. Okay, but it's too weak in this
particular sense. It's also too strong because the only
thing that you are remembering here are the moves.
They are not really representing the states.
Okay? So it may very well be that this move at
this particular state, if you would apply them, would give you a state that you
haven't seen before. The only thing that you remember is one
of the moves that I have done. Okay?
But you, you have applied your sequence of move, but when you are in this state
applying maybe some of the first move, maybe completely fine.
And give you another state. Okay?
So that may happen. And so, what you have here is the fact
that, in a sense, the tabu list here is too strong.
It's actually preventing you from going to states that are actually nice, and
where haven't, that you haven't visited before.
And who can actually be pretty, and which can actually be pretty good.
So, in that sense it's too strong it prevents you it's stronger than you know,
keeping the entire list and keeping this you know, so that you don't go back to a
state that you seen before okay. It's it can prevent you from going to
states that have not been visited yet. Okay so what you can do to [INAUDIBLE]
that is a essentially strengthening the abstraction.
So instead of just storing the move you can say [UNKNOWN] but I'm going to store
more features of these particular states. I can try to refine the way I'm basically
capturing this state. So, one of the things that you can do
easily, okay, is for instance, capture the objective values, okay?
So you can say, okay, think about the, the, you know, the car sequencing
algorithm again. You had slot ai and aj that you wanted to
slot, to swap and bj, bi that you wanted to swap.
What you can do is keep inside the tabu list, this kind of four face, right, so
you can, you can store ai. You can store bi but you can also store
the value of the objective function where you are now, okay?
So this is fi, this particular function there.
And you can also store the value that you divided the objective function that you
would get if you performed the move. And this is denoted fi plus 1 there,
okay, inside the tabu list. Okay.
So this is fi plus 1 here. So, in a sense what you are saying is, if
I'm in the state with evaluation function is fi and I want to swap ai and aj, and
bi. Okay?
And that would resort in a state that is the value of the objective function,
which is fi plus 1. That move is doubled.
Okay? Now, if that gives me a, an objective
function which is different from fi plus 1.
It's not tabu, because I know that this is not the state, this is not the value
that I have performed before. So you can do something like that, so now
the definition of the tabu search is, I'm in a particular state.
This is the value of my objective function, I would perform this move and I
would get to this value of the objective function.
Okay? So these are the kind of things that you
can start doing. Okay?
So strengthening the abstraction. Okay?
Now so, so the other things that you know, we can do is using this linear
neighborhood. Okay?
So this multistage heuristic that I've shown, that I've talked to you.
You know, two lectures ago and the key idea is that they would do exactly the
same thing in this particular case. You would take this particular car that
you want to swap, okay and then you would take all the other, you know, and it has
to have some violation. Then you would take all the other slots
that you can swap that ca, that car with, okay?
And essentially the tabu list would be exactly the same, you would consider
pairs i and j. Okay?
And you would be making sure to select only the ones that are not tabu.
Okay? In this particular case, one of the
things that you can do is that the move are not symmetrical anymore necessarily,
so you update only one of them, okay? And so basically, putting your tabu
search on top of that multi-set heuristic is very easy.
It's essentially the same as in the quadratic neighborhood, okay?
So let me talk a little bit about the Queens Problem.
So you remember the Queens Problem. It's, what we did there was selecting a
queen and then moving to a position where you reduce the valuation the most.
Okay? So in this particular case, the
particular neighbor root is taking a value, no, taking a variable and
assigning a new value, taking a queen and moving it to a new position.
Okay? So, what has to be the tabu search, and
the tabu data structure in this particular case?
Well, essentially the move is moving you know a particular queen to a new
position, okay. So what, what, you know, if you go to
that state, what is the thing that you want to avoid in the next iteration?
Well, you want to avoid taking that, that queen and putting it back to initial
position, right? So what essentially you are trying to do
here is preventing the value of the queen to take its old value, right.
And so, once again, what you're going to store here, are pairs, x, v, where x is a
variable and v is a value for that variable, okay?
So we store pairs, but they have, they have a different meaning here.
It's basically, [UNKNOWN] I don't want this variable x to be assigned the value
v for a while, okay? And that's what you store inside a tabu
list. Okay?
So this is essentially the search, once again, for, the queen's example.
Okay? And what we do, is, basically, this is,
this is, this is a mean conflict heuristic.
You basically select a queen which appear in sum violation.
Then you generate all the possible position for that particular queen.
And you only the select the ones that are not tabu.
Which basically means that you even had the, that value for the queen for a
while. Okay?
And, so. Then, afterwards, you know that, you
select the best move. And then you apply this operation here.
That's what you see there. Okay?
Which basically means [UNKNOWN] I don't want in the future to return to that
value for that queen. Okay?
So use tabu i indexed to. So, you use the tabu data structure
indexed by i. That is the queen you have selected.
And then the value of the queen, at this point, which is queen c.
Okay so and basically what you do is you basically say oh I don't want to give the
value to, to do, for the queen to get the value that it currently has for a number
of iterations. Okay and the rest of the procedure is
basically the same, okay. So what you keep here is okay, I don't
want to debt queen to get back to its original value.
Okay? So once again, you know, we have a lot of
choices in this tabu search algorithm. What I've shown you here is essentially
oh, you know, I take a move, and I, and the abstraction is actually capturing
that move. And making sure that we cannot do the
reverse move, in a sense, here. Okay?
So we take the move, I want to make sure that I don't take the reverse move, for
actually getting back to the previous state.
Okay? So in the swap, it was easy to move,
where itself, the reverse move. Here, I'm basing the capturing the fact
that, you know, I'm prevent, I'm putting in the tabu search, the reverse move.
Okay? Now in practice, you may actually use
abstraction, which are even more coarse, okay.
It's really coarser abstraction. So one of the things that I may say, ooh,
that variable, you know? I'm just changing it.
I don't want to change it again for a bunch of iteration, okay?
So instead of keeping the value that I, the, the reverse move.
You are basically forbidding all the move that are involved with that variable.
So this is something you could do. There is nothing that prevents you from
doing that. Here, you are basically having a much,
much, much more coarse approximation of the tabu list.
But it's maybe very effective in diverse, you know, diversifying the search, okay?
So essentially, if you put a variable which is tabu for a number of iteration,
you can actually touch that particle variable for a while, okay?
Now, so this is, once again, the basic of, of, of essentially keeping this tabu
search, tabu list. But one of the things I have told you
sometimes too weak or sometimes too strong.
So when they asked too strong, you have the behavior that can happen is that you
are in this state. And then you want to perform his move and
then this move is so good that it will give the best solution ever that you have
seen so far right and so you say the move, unfortunately stubble so you are
like that that move is stubble with there I really want to go there.
Okay. And of course we want to allow it.
And so in tabu search you have this kind of you know technique which is called the
aspiration criterion. And what you can do is that if the move
is tabu but it's so good that you really want to take it, you basically over ride
the tabu search, the tabu status. Okay.
So essentially what you are, so you can implement some aspiration criterion.
That are basically telling, yes, it's tabu but if it, if it's that good, just
take it, okay? So, and that's what you see here.
And the reason you can do things like this is because, once again, you know,
that, to, that, what we keep is an obstruction of the tabu list.
We are preventing the search from going to state that are really that we haven't
visited so far and there is nothing you can really do.
Otherwise, you would have to start the whole thing, right?
So in, in this particular case, this is what we implement, the NotTabu.
It's going to take all the particular configurations that, all the neighbors
that we are considering and you'll see that we'll want to have two conditions.
They don't have to be tabu or if they are tabu, the move is so good that it's
better, you know better than the best solution so far and therefore you take it
anyway. Okay.
So in a sense, the neighborhoods are going to be all the move which are
NotTabu plus the one that are so good that you've, you've got to take them.
Okay, so you get to take them. Okay, so basically that's the idea behind
you know, aspiration the aspiration criteria.
You take moves that are tabu but they are so good that you know you really want to
take them. Okay so 2 more techniques that I want to
talk about and this is more long term memory.
Okay, so what you can happen to this in this tabu search is that you start from
the 1 and then you get good solution. And at some point, you start in, you
start going in this kind of long, long walk, where nothing really improves.
You improve, you improve. You degrade, you improve.
Nothing happens, okay? So you have these long, long walk,
nothing happens. But at some point, you were in a really
good state. And you thought you would find a very
high quality solution. So what you can do is what is called
intensification. You keep a set of states that have been
very good. You found them before.
They are very good. And what you do is instead of going into
this long, random work where nothing happens, you decide to go back to these
and restart the search from then. Okay?
So that's what is called intensification. You keep very high quality solution and
when you are stuck in this long, long, long walk where nothing really is
improving you know, over the best solutions you have found so far.
You return to one of these things and you restart the search from there.
Okay? Very useful technique in practice as
well. And then, diversification is just the
opposite. Okay, so in heuristics, in
meta-heuristic, what is nice is that if you have a good idea, generally the
inverse of the idea is also nice. Okay?
So instead of intensify, you want to diversify.
Okay? So what it's basically saying is that if
you have not seen this improvement for a long time, you are working in this random
work, not seeing anything interesting. What you can say is that wow, I made a
configuration where something is really wrong.
So I'm going to take part of this solution and completely change it.
And that's what is called diversification.
You can take, for instance, a bunch of, you know, in the, in the consequencing
you would take an arbitrary number of swaps, and chance completely your
configuration. Okay?
In, in the queens, you can start moving queens around in a completely random
fashion, okay? Or you can, you know, use more of the
structure of the problem to actually have a more, you know, structure based, you
know, diversification. But once again, this is very useful.
So a lot of the tabu search algorithm will have an intensification phase.
And then they will have also a diversification phase.
When the intensification is, you know, exhausted in a a sense.
Okay? And then there is this very interesting
technique as we also use for the TTP, where it's typically in problems where
you have both very difficult constraints and very difficult objective function.
Typically what you do is to solve the constraint are becoming in the objective
function, okay to drive the search of feasibility.
And then you also want to have the object, the original objective of course
to find, you know very good solution. And strategic oscillation is kind of
scheme where you want to balance the time that you spend in the feasible and the
infeasible region. Okay?
And so you basically try to adjust the power meter.
If you spend too much time in the in feasible region, you want to give more
importance to the constraint that I have violated.
To increase the weight of these constraints.
Such that you go back and you spend more time in the feasible region in the hope
of finding feasible solution that increase the best so far.
If you spend too much time in the feasible region, you may actually not
escape some local minima. So you may decide to, you know, let the,
you know, give more weight to the objective function.
You may go to the infeasible region with the hope that at some point you get back
to feasibility, and a better objective function, okay?
So once again these techniques are very useful in practice on some of the tabu
search algorithm, okay. So final remark in this particular
techniques like diversification, intensification and strategic oscillation
are actually very useful in many different settings.
They are very useful for simulating, they're needing for many other, for many
other you know meta heuristic. So use them in those settings as well
because they, they can make a big difference in practice.
Okay? So this is basically finishing the local
search part of the class. what we're going to do in the next couple
of lectures is studying looking at mathematical programming, starting with
linear programming, and integer programming.
So, very, very different paradigm, but very exciting, too.
Thank you.