Tip:
Highlight text to annotate it
X
Now that we've seen a concrete example of Local Search in the specific context of
the maximum cup problem, let's move toward talking about this technique more
generally. So lets think, abstractly, about some
computational problem. Lets say there's a set X of the candidate
solutions to this problem. Maybe you want to search whether or not
their exists a solution with a given property, maybe you want to find the
solution which is optimal, in some sense. What are some examples? Well, in our last
video x was the cuts of some given graph g.
Other examples would include the tours of an instance of traveling salesmen
problem, or perhaps the possible assignment to variables in some
constraint satisfaction problem. A fundamental ingredients to the local
search approach is the definition of a neighborhood.
That is, for each candidate solution x in the space of all possible solutions X,
you need to define which other solutions that are y, are the neighbors of x.
Let's look at some concrete examples. In the maximum cut problem last video, we
were implicitly defining the neighbors of a given cut to be those cuts you can
obtain from the given one by moving a single vertex from one side to the other.
If you're taking a local search approach to a constraint satisfaction problem,
something like 2 SAT or 3 SAT, a common approach is to define 2 variable
assignments to be neighbors, if and only if they differ in the value of a single
Variable. So, for the Boolean case, where variables
are either true or false, you're going to define 2 assignments to be neighbors, if
you can get from one to the other, by flipping the value of a single variable.
For the travelling salesman problem, there's a lot of sensible ways to define
neighborhoods. One simple, and popular approach, is to
define 2 travelling salesman tours to be neighbors.
If and only if they differ in the minimum possible number of edges.
If you think about it for a second, you'll realize that the minimum possible
number of edges that 2 TSP tours differ in is 2.
So, for example, in pink I have shown you 2 neighboring TSPs.
P tours, the first tour has edges from u to v and from w to x, but by contrast the
second tour has the crisscrossing edges from u to x and from v to w.
All of the other edges in the 2 tours are the same.
Once you've identified the space of candidate solutions to your computational
problem, and once you've settled on a neighborhood for every candidate
solution, you're in a position to run a local search.
Local search just iteratively improves the current solution, always moving to a
neighboring solution, until you can't improve things any further.
I'm going to specify here a highly under determined version of the local search to
highlight the number of design decisions that you've gotta make if you really
want to apply local search to a problem in your own projects.
We'll talk about the possible instantiations of the different design
decisions in the next couple of slides. So, for starters, you have to initialize
the search with one of the candidate solutions, some little x.
How do you pick it? Well, there's a number of approaches, we'll discuss that
in more detail in a sec. Now, just like in our maximum cut local
search algorithm, we take the current solution, whatever it is x.
We look for a neighboring 1y, which is superior.
If we find such a y, then we move to that superior solution.
If there is no superior y, we're locally optimal.
And then and we just return to the current solution.
Our local search algorithm for the maximum cut problem, that we discussed
last video, is in fact an instinctiation, of this generic procedure, where the set
X of all solutions, is just the cuts of the given graph.
And, 2 cuts are defined to be neighbors, if and only if you can get from 1 to the
other, by moving A single vertex from one group to the other.
And that algorithm, as we are here, we just started from some arbitrary
solution, some arbitrary cut. We repeatedly searched for a superior
neighboring solution. That is we tried to see if there was a
way to move a vertex from one group to the other to get a better cut.
If we found such a superior neighboring solution We iterated from that better
solution, and then when we couldn't iterate it any more, when there were no
better neighboring cuts, we just halted and returned the final result.
You can apply this generic local search procedure to other problems in exactly
the same way. As an example, think about the traveling
salesman problem. Let's say we define neighborhoods like we
did on the last slide with 2 tours being neighbors if and only if they differ in
exactly 2 edges, n - 2 edges. Are in common.
What do you do? You start from some arbitrary traveling salesmen tour, and
now you iterate. You keep looking for a neighboring
superior solution that is from the current tour,.
You consider all tours you can reach by changing exactly two edges of the current
tour. You check if any of those end choose 2
solutions have strictly smaller costs. If any of them do you iterate from that
new superior solution. When you can't iterate anymore, when all
of the neighboring solutions are at least as costly as the one you're working with,
that's a locally optimal tour and you return that as your final output.
And the rest of the video I want to continue discussing local search at a
high level talking about some of the design decisions that you've got to make
as well as some of the performance characteristics you can expect.
After we finish this high level discussion we'll move on to some videos
on another concrete example of local search.
Specifically to 2 SAT, a specific example of a constraint satisfaction problem.
Let's begin with 3 frequently asked questions about under-determined
characteristics of the generic local search procedure I just showed you.
Question number 1 concerns step number 1 of the algorithm.
You need to somehow come up with this arbitrary starting point, x.
How do you do it? To answer this question, let me crudely classify the
situations in which you might be using local search, into 2 categories.
In the first category, you're really depending on local search, to come up
with a good approximate solution, to an optimization problem.
You really have no idea how to get close to an optimal solution, other than
through, some local search Approach. The second category of scenarios is where
you have some pretty good heuristics that seem to be delivering to you pretty good
solutions to your optimization problem and you just want to use a local search
as a post-processing step to do even better.
So let's start with the first category where all of your eggs are in one basket
and you need a local search to deliver to you a pretty good solution to an
optimization Problem. So this is a tricky spot to find yourself
in. Local search is guaranteed to deliver to
you a locally optimal solution. But in many problems locally optimal
solutions can be much, much worse than what you're looking for, a globally
optimal solution. In the special case of the maximum cut
problem, we had a performance guarantee of 50%.
Which already is only a so-so guaranteed but for most optimization problems even
that kinds of performance guarantee is out of question.
There are locally optimal solutions far worse than the globally optimal ones.
On the other hand, you know there are some good locally optimal solutions out
there. In particular the globally optimal
solution is also a locally optimal one. Now if you just run local search once,
it's not clear how to evaluate the quality of the solution that's returned
to you. You run the algorithm, it hands you a
solution, it has cost 79,217. is that good or bad? Who knows? An
obvious approach to doing better is to run the local search many times, say
thousands of times, even millions of times, and then amongst all of the local
optima of the different runs of your local search algorithm returns, you pick
the best one and you make that your final Final solution.
To encourage your local search algorithm to hand back to you different local
optima when you run it over and over again.
You want to be making some random deicsions.
An extremely common point to make a random decision is in step 1 of local
search. Is in choosing your initial starting
point .x so, for example in the maximum cut problem, you'd want to start with a
random cut with each vertex equally likely to be in a or b.
With the traveling salesman problem, you might want to start from a random tour,
that is a random permutation of the end vertices.
And if it's a straint satisfaction problem you could begin by giving each
variable Independently a random value. If this seems kind of like throwing darts
at a dartboard, that's what it is. It turns out there's a lot of stubbornly
difficult problems out there for which the state of the art is not really
substantially better than running independent trials of local search with
different random initial positions and returning the best of the local optimal
that you find. Now let's suppose you're in this second,
happier category of scenarios, where you've got a better handle on your
optimization problem. Maybe you've figured out how to use
greedy algorithms, or maybe mathematical programming.
Anyways, you have techniques that generate close to optimal solutions to
some optimization problem. But why not make these nearly optimal
solutions even better? How do you do that? We'll feed the output
of your current suit of heuristics into a local search post processing step.
After all, local search only moves to better solutions. It can only make your
pretty good solution even better.