Welcome back this is Discrete Optimization Local Search part six.
Okay so what we're going to do today? Start talking about this topic of
escaping local minima. And we'll introduce a very important
notion which is connectivity. And talk a little bit about various
neighborhoods and how they relate to this, this notion.
the big goal here is that we are setting the stage for.
Introducing techniques that will allow us to actually find higher-quality solution,
not just producing, you know, move, that are improving all the time, but allowing
the search to do more interesting things. But a requirement, you know, in general,
is that you need some property of you neighborhood to do good things, okay?
So, remember, you know what we did, that the guarantee that we have is we apply,
you know, greedy moves inside a neighborhood.
Is that when we complete the search we are guaranteed that the value of the
configuration that we find is a local minimum.
Okay, so which basically means that if you are that position in that space, if
you look around there is no place you can go which is better.
That's what it means to be a local optimum, okay?
You can move to a place which is better, okay?
But that doesn't guarantee that this place is actually good in the grand
scheme of things. They could, there may be something really
good somewhere else, and you don't know how to get to it, okay?
So, we have no guarantees for optimality, and therefore, in practice escaping these
local minima of, of poor quality is a very important issue.
And once again, the next lecture will show you two really interesting
techniques to do that. What we are doing today is setting the
stage for that, okay? So this is a beautiful picture done by
Carlton, right? So you see this is kind of the
neighborhood, the entire regions of the space, okay?
So, so, so you see you know, in this particular case, you know.
Basically, this neighborhood is colored into you know, cold and hot region.
And hot means high quality, cold means terrible, right?
And so, local search dots for you a point.
You define the neighborhood of that point.
And then, what we have done so far is taken a direction which is improving, you
know, which is improving the, the move. And so we follow this, and then we can
continue finding a path. Oops, and hopefully.
We, you know, we get to a good region of the space, okay?
So that's what we have been doing so far, okay?
Now, the, the landscape of the objective function, okay, can be complex like this
one, right? So, so what you see here is the various,
the quality of the solutions, and we are minimizing, okay?
So this is essentially all a possible solution and this is the quality.
And what you see here is there is various local minimarts in that popular place,
right? So this is a local minimart this is also
a local minimart and you know this one is actually pretty interesting.
This is the global Minimum. Okay, so that's the global minimum in
this particular case. So we want to get there but the search
that we have seen so far are not going to get you there, right?
Now, one of the things that you really don't want to happen is this, okay?
So you can't define your problem, okay, in such a way that it's not connected,
which means that if you start from that particular point.
You can move inside that region right. And find a good point in that region
which is here. But you have no way to actually get
there. There is no move that will get you there
and that's terrible. The entire region here which is where the
good things are is not accessible if you start from there.
Okay, so we don't want that. This is not good okay?
So we have no way of moving from one side of the neighbor to the other one.
And so we want to avoid that and the connectivity requirements that I'm going
to talk about is exactly avoiding this. Okay, so this is a definition but
essentially what it means is that you want to be able go from any configuration
to at least one optimal solution. Okay, so in a sense you're going to say
that neighborhood N, and remember that a neighborhood is something which given a
configuration is going to give you a set of configuration where you can go, okay.
So neighborhood N is going to be connected if from every configuration S,
anywhere, okay? So there an optimal solution O that you
can reach by taking local move and what is a local move?
Well you start from s, OK that state at zero.
Okay, and then you can take a local move to go to a s1, then to s1, to s3 and so
on up to s n which is the optimal solution that you are looking for and
everyone of these configurations can be accessed by your local move.
Which basically means that SI is in the neighborhood of SI minus 1, right?
So this is the definition of connectivity, intuitively it's very
simple. It basically means that you can apply
local move from any configuration to get to the optimum.
It doesn't mean that you will get there right?
It must means that there is a path, okay? Afterwards we need to find that path.
But what we know is that for sure there is one path to an optimum solution, okay?
Now, connectivity doesn't guarantee optimality as I just tell, told you,
right? Because so far, our local search has been
greedy, okay? So, what happens when you are greedy,
okay? When you are greedy, let's say this is
the starting point. When you are there, you're going to prove
you're not going to, you're going to take move that are basically improving, okay?
So, if you take move, that are improving, you're going to get to this local minima.
Okay, so you think, another point over there, beautiful point, you go down,
drop, that's where you get. You don't get here, right.
Because if you try to improve all the time, you're not going to get there.
You will have to go up the hill and then go down, right?
Which is not something that we have been able to do so far.
And obviously, you know, you have all these points here that are basically
bringing, oops, I want to show you that, because they are so beautiful, right.
So that are going to all these places, but they don't get to the global, to the
global optimum. Okay, so in a sense, connectivity doesn't
guarantee optimality, but it's still a very good property to have.
Because once we entry some of the techniques that we'll see, you know, in
the next lecture, you know, in connected neighbourhoods you may have more hope and
actually in some cases guarantees to get. two of the actual optimal solution.
So, what you see here is graph coloring. Remember, we had this beautiful problem
where you would color these, all these vertices, such that two adjacent nodes
were colored by had to colored by a different color.
Okay so and the neighborhood that we chose was very simple, right?
It was changing the color of a note. And usually that neighborhood is
connected, and I'm going to give you a simple algorithm, and this is actually
very interesting because we are heating like hell, but this is what you do when
you want a sure that something is connected, right?
So what you have to do is you start from the configuration.
And you have to show a path, you know, that indicates that you know, that brings
you to the optimal solution. But, we can do a really nice assumption.
We can actually postulate that we know the optimal solution, so if I know the
optimal solution and I'm in a particular configuration, I can design a very simple
algorithm to get to the optimal solution. What do I know?
I look at every note and if that note okay, doesn't have the right value that
means that it's value is different from the value in the configuration simply
assign it's value which each value which is in the optimal solution.
So I do that for all the notes okay, this, they are all legal, right?
And then essentially I get to the ultimate solution.
So, this is very easy, right? So, but all the connectivity groove are
like that. So, you, you suppose that, you basically
assume that you have the objective, the optimal solution.
And then you have a particular configuration.
And you show you can actually get there. No, this is a very simple one, right?
Some of them are very complicated, okay, but this gives you the essence of these
kinds of proofs, okay? Now, remember car sequencing, okay?
So car sequencing once again we were scheduling these cars on the assembly
line. The production unit that is to put these
options while the cars were moving, right?
And we had to satisfy the capacity constraints on this production unit to
make sure that we could put the options. On the cars, right?
So, what we designed was this beautiful neighborhood, right?
where we would basically look at the cars and swap them, okay?
And here you see the options of the various car, okay?
So we have a swap neighborhood And this swap neighborhood is connected, okay?
And why, let's look at the algorithm. So actually, let's go back and look at
the sequence right? So we can take this sequence and look at
the values and either you have the right type of car there or you don't, okay?
If you don't have the right type of car, what are you going to do?
Well, there is your type of car somewhere inside the sequence.
You can swap them, and now what do you have?
Well, the first slot is right. You move to the next one, okay?
The next one you say, well, you look. Is it right, or not?
Is it the value that you have in the optimum solution?
If it is fine, you move to the third one. If it's not, you look for the right type
of car, and you solve these two thing, okay?
And so you can continue doing that, and that's how you show connectivity, okay?
So, once again, that's what you see there.
You have an algorithm which iterates from you know, the first to the last load of
the assembly line. Then you look essentially it's the value
for the configuration s, you know, s i is the same as the value of that part, of
the slot you know, of position i in the ultimate solution that's o i.
If they are different, what you do is you look for a particular config.
[SOUND] A particular configuration inside, a particle type of car inside the
sequence S, you know, and, and further away, obviously, which is of the type,
the same time as the value which is inside the automobile solution.
And you swap these two things. And you continue like that, and
obviously, you know that you will find one, right, because it's in the optimum
solution. And therefore, you, you solve all these
things and you get an observable solution at the end.
So what I'm showing you here is a very, is essentially that by, by, by doing
swaps, you will always get to the optimal solution by a sequence of move.
Now once again, I want to repeat this. It doesn't mean that your algorithm is
going to find that sequence, right? Because we are always trying to find
improving moves and things like this. We would have to do other things.
So in practice, some of these steps here huh, may be degrading tremendously the
quality of your solution. At that's what is the challenge in local
search, right? So, let me, let me look at something
which is a little bit more complex, right.
So this is the traveling salesman problem.
Remember We had all these cities that we had to visit exactly once, okay.
And trying to minimze the total distance. And we introduce this simple
neighborhood, that's one of the simplest that [UNKNOWN] 2-OPT.
Now remember 2-OPT was basically taking two edges and replacing them by two other
edges. And the question that you may be asking
yourself, that is this neighborhood connected, okay?
So, very simple question. Because it has only two possible answer,
right? Yes or no?
So, think about it. Is it connected or not?
So, to actually find that out, so look at this thing, okay?
So, look at this particular tour. Is there another way to view this?
Well first let's, let's start numbering these guys so we have all the vertices
and the name of these vertices. Okay, and know a two, you see the two.
You know, starting from one, moving to five, then to nine, then to ten, then to
six, three and so on. Okay, so when you look at this tool, this
tool is really like a sequence, right? So you see the sequence here.
You know, one, five, nine, ten, three and so on, okay?
So basically the two here can be viewed as a sequence Right?
Now remember, what you know, two opt does is removing two edges and replacing it by
two other edges that you see over there, right?
So I have a sequence here and you know, what is going to be my sequence for this
thing, okay? So, essentially, what you know is that in
this two, right, so you were basically going to to, to, to six and, and six was
going to three, right? So what we going to do is remove this and
replace it by an edge to seven. And then we going to revert essentially
all these edges that you see on that right side.
And then connect that with an edge going from three to two.
So, we are basically taking these things, okay?
So, the edges that we are removing in the edges going from six to three, okay?
So this is the edge that you see somewhere here okay, and then we have to
revert that so we are basically reverting the sequence.
So what you really get here is that particular sequence there.
So you see you see the original sequence over there and you see the sequence which
is here, which is essentially the same sequence we have here except for we have
revert All the, the ordering. We, we basically reverse that particular
sequence, right? And that's what you see over there, okay?
So essentially what I'm telling you is that 2-opt can be view on sequence and
you isolate a sub-sequence here and what you do is you basically reverse it.
But keep it the same position, but reverse it, okay?
Now, instead of moving from six to three, you move to six to seven.
And then to 11 and eight and four and so on.
And that's what you see over there, right?
So essentially, what you do is you select a six sequence, and you reverse it, okay?
Now, I'm asking you the question. Is this neighborhood connected or not?
Okay, well, we can use a very simple algorithm again, right?
If we know the ultimate solution, okay, and we can posulte that we know it, and
we have a configuration right now, what are we going to do?
Now, assume that, for instance, this guy is the optimum solution, okay?
Which is probably not the case, but never mind.
Okay, but if we look at this thing, what we're going to say, okay, so you know, we
have 1, 5, 9, 10, 6 and this is the same in this supposedly alternate solution.
But then we see here that there is a different between these two guys, right?
There is a difference, okay? So there is one that is starting at
three, okay. This subsequence is starting with three
and that one is starting at seven, okay? So, what do we do?
Well, we say okay, so I'm going to select a move by what?
Well, I want a seven, right? So, this is what I want, okay?
And I have a three, so I'm going to look until I find a seven and then I'm
going to apply a two opt and that 2-OPT is basically going to revert that
sequence, okay? And I will obtain this [INAUDIBLE], okay?
And what is nice about this now is that I can move to the next element.
So this is all correct, okay? And then I can move inside a sequence and
try to do the same kind of things for the subsequent vertices.
So in a sense what I just told you is that I have a very simple algorithm,
okay? Which goes to the various elements of the
sequence very much like I did for the consequence example.
Any particular value in the two, I'm considering now is they're not the same
as the value in the optimum solution. I find the sequence starting at I, which
basically ends with the value in the optimal solution With the city inside the
optimal solution, right? So I have a subsequence, no?
And what do I do? [NOISE], I reverse it, okay?
And that's what you see over there. So I go up to si, I take the sequence
which brings me to the particular point that I wanted, I reverse it so I start
with that guy, which is no correct. I have all the sequence which is there,
and I have my new sequence which is correct.
Not only up to a si-, not only up to s i minus 1, but now also to s i, okay?
And I continue doing that, until I find until I get to the optimum solution.
So once again, very simple algorithm, to move from a particular configuration to
an optimum solution, okay? Now, you know, unless you, I'm going to
leave you with an interesting homework. Remember the TPP, the traveling [UNKNOWN]
problem, okay? So I will show you this beautiful
neighborhood, right, with five moves, sub homes, sub teams, sub rounds, sub partial
teams, sub partial home, okay? The question for your homework.
Is essentially, is this neighborhood connected?
And you, if you find the answer, okay, call me.
You can call me if you find the answer. I'm very interested in knowing if you
actually can find the answer to this particular problem.
Thank you very much, see you next time.