1 00:00:00,012 --> 00:00:05,814 Now that we've seen a concrete example of Local Search in the specific context of 2 00:00:05,814 --> 00:00:11,404 the maximum cup problem, let's move toward talking about this technique more 3 00:00:11,404 --> 00:00:14,822 generally. So lets think, abstractly, about some 4 00:00:14,822 --> 00:00:18,902 computational problem. Lets say there's a set X of the candidate 5 00:00:18,902 --> 00:00:23,077 solutions to this problem. Maybe you want to search whether or not 6 00:00:23,077 --> 00:00:27,652 their exists a solution with a given property, maybe you want to find the 7 00:00:27,652 --> 00:00:32,848 solution which is optimal, in some sense. What are some examples? Well, in our last 8 00:00:32,848 --> 00:00:35,299 video x was the cuts of some given graph g. 9 00:00:35,299 --> 00:00:39,695 Other examples would include the tours of an instance of traveling salesmen 10 00:00:39,695 --> 00:00:43,490 problem, or perhaps the possible assignment to variables in some 11 00:00:43,490 --> 00:00:48,747 constraint satisfaction problem. A fundamental ingredients to the local 12 00:00:48,747 --> 00:00:52,797 search approach is the definition of a neighborhood. 13 00:00:52,797 --> 00:00:58,552 That is, for each candidate solution x in the space of all possible solutions X, 14 00:00:58,552 --> 00:01:03,582 you need to define which other solutions that are y, are the neighbors of x. 15 00:01:03,582 --> 00:01:08,734 Let's look at some concrete examples. In the maximum cut problem last video, we 16 00:01:08,734 --> 00:01:13,717 were implicitly defining the neighbors of a given cut to be those cuts you can 17 00:01:13,717 --> 00:01:18,027 obtain from the given one by moving a single vertex from one side to the other. 18 00:01:19,115 --> 00:01:24,264 If you're taking a local search approach to a constraint satisfaction problem, 19 00:01:24,264 --> 00:01:28,840 something like 2 SAT or 3 SAT, a common approach is to define 2 variable 20 00:01:28,840 --> 00:01:34,072 assignments to be neighbors, if and only if they differ in the value of a single 21 00:01:34,072 --> 00:01:37,031 Variable. So, for the Boolean case, where variables 22 00:01:37,031 --> 00:01:41,457 are either true or false, you're going to define 2 assignments to be neighbors, if 23 00:01:41,457 --> 00:01:45,750 you can get from one to the other, by flipping the value of a single variable. 24 00:01:45,750 --> 00:01:50,065 For the travelling salesman problem, there's a lot of sensible ways to define 25 00:01:50,065 --> 00:01:53,207 neighborhoods. One simple, and popular approach, is to 26 00:01:53,207 --> 00:01:56,142 define 2 travelling salesman tours to be neighbors. 27 00:01:56,142 --> 00:02:00,452 If and only if they differ in the minimum possible number of edges. 28 00:02:00,452 --> 00:02:05,363 If you think about it for a second, you'll realize that the minimum possible 29 00:02:05,363 --> 00:02:08,399 number of edges that 2 TSP tours differ in is 2. 30 00:02:08,399 --> 00:02:12,522 So, for example, in pink I have shown you 2 neighboring TSPs. 31 00:02:12,522 --> 00:02:17,419 P tours, the first tour has edges from u to v and from w to x, but by contrast the 32 00:02:17,419 --> 00:02:21,545 second tour has the crisscrossing edges from u to x and from v to w. 33 00:02:21,545 --> 00:02:24,672 All of the other edges in the 2 tours are the same. 34 00:02:24,672 --> 00:02:29,034 Once you've identified the space of candidate solutions to your computational 35 00:02:29,034 --> 00:02:32,994 problem, and once you've settled on a neighborhood for every candidate 36 00:02:32,994 --> 00:02:35,978 solution, you're in a position to run a local search. 37 00:02:35,978 --> 00:02:40,451 Local search just iteratively improves the current solution, always moving to a 38 00:02:40,451 --> 00:02:44,362 neighboring solution, until you can't improve things any further. 39 00:02:44,362 --> 00:02:48,342 I'm going to specify here a highly under determined version of the local search to 40 00:02:48,342 --> 00:02:52,242 highlight the number of design decisions that you've gotta make if you really 41 00:02:52,242 --> 00:02:55,237 want to apply local search to a problem in your own projects. 42 00:02:55,237 --> 00:02:58,732 We'll talk about the possible instantiations of the different design 43 00:02:58,732 --> 00:03:03,041 decisions in the next couple of slides. So, for starters, you have to initialize 44 00:03:03,041 --> 00:03:06,278 the search with one of the candidate solutions, some little x. 45 00:03:06,278 --> 00:03:10,231 How do you pick it? Well, there's a number of approaches, we'll discuss that 46 00:03:10,231 --> 00:03:13,487 in more detail in a sec. Now, just like in our maximum cut local 47 00:03:13,487 --> 00:03:16,917 search algorithm, we take the current solution, whatever it is x. 48 00:03:16,917 --> 00:03:19,432 We look for a neighboring 1y, which is superior. 49 00:03:19,432 --> 00:03:22,495 If we find such a y, then we move to that superior solution. 50 00:03:22,495 --> 00:03:25,372 If there is no superior y, we're locally optimal. 51 00:03:25,372 --> 00:03:27,873 And then and we just return to the current solution. 52 00:03:27,873 --> 00:03:31,484 Our local search algorithm for the maximum cut problem, that we discussed 53 00:03:31,484 --> 00:03:35,566 last video, is in fact an instinctiation, of this generic procedure, where the set 54 00:03:35,566 --> 00:03:38,301 X of all solutions, is just the cuts of the given graph. 55 00:03:38,301 --> 00:03:42,165 And, 2 cuts are defined to be neighbors, if and only if you can get from 1 to the 56 00:03:42,165 --> 00:03:45,236 other, by moving A single vertex from one group to the other. 57 00:03:45,236 --> 00:03:48,797 And that algorithm, as we are here, we just started from some arbitrary 58 00:03:48,797 --> 00:03:52,229 solution, some arbitrary cut. We repeatedly searched for a superior 59 00:03:52,229 --> 00:03:55,200 neighboring solution. That is we tried to see if there was a 60 00:03:55,200 --> 00:03:58,541 way to move a vertex from one group to the other to get a better cut. 61 00:03:58,541 --> 00:04:02,605 If we found such a superior neighboring solution We iterated from that better 62 00:04:02,605 --> 00:04:06,539 solution, and then when we couldn't iterate it any more, when there were no 63 00:04:06,539 --> 00:04:10,284 better neighboring cuts, we just halted and returned the final result. 64 00:04:10,284 --> 00:04:14,371 You can apply this generic local search procedure to other problems in exactly 65 00:04:14,371 --> 00:04:17,236 the same way. As an example, think about the traveling 66 00:04:17,236 --> 00:04:20,393 salesman problem. Let's say we define neighborhoods like we 67 00:04:20,393 --> 00:04:24,466 did on the last slide with 2 tours being neighbors if and only if they differ in 68 00:04:24,466 --> 00:04:26,820 exactly 2 edges, n - 2 edges. Are in common. 69 00:04:26,820 --> 00:04:30,853 What do you do? You start from some arbitrary traveling salesmen tour, and 70 00:04:30,853 --> 00:04:33,640 now you iterate. You keep looking for a neighboring 71 00:04:33,640 --> 00:04:36,343 superior solution that is from the current tour,. 72 00:04:36,343 --> 00:04:40,671 You consider all tours you can reach by changing exactly two edges of the current 73 00:04:40,671 --> 00:04:42,997 tour. You check if any of those end choose 2 74 00:04:42,997 --> 00:04:47,077 solutions have strictly smaller costs. If any of them do you iterate from that 75 00:04:47,077 --> 00:04:50,455 new superior solution. When you can't iterate anymore, when all 76 00:04:50,455 --> 00:04:54,788 of the neighboring solutions are at least as costly as the one you're working with, 77 00:04:54,788 --> 00:04:58,542 that's a locally optimal tour and you return that as your final output. 78 00:04:58,542 --> 00:05:02,457 And the rest of the video I want to continue discussing local search at a 79 00:05:02,457 --> 00:05:06,647 high level talking about some of the design decisions that you've got to make 80 00:05:06,647 --> 00:05:10,307 as well as some of the performance characteristics you can expect. 81 00:05:10,307 --> 00:05:14,172 After we finish this high level discussion we'll move on to some videos 82 00:05:14,172 --> 00:05:16,852 on another concrete example of local search. 83 00:05:16,852 --> 00:05:21,622 Specifically to 2 SAT, a specific example of a constraint satisfaction problem. 84 00:05:21,622 --> 00:05:25,747 Let's begin with 3 frequently asked questions about under-determined 85 00:05:25,747 --> 00:05:30,077 characteristics of the generic local search procedure I just showed you. 86 00:05:30,077 --> 00:05:33,537 Question number 1 concerns step number 1 of the algorithm. 87 00:05:33,537 --> 00:05:37,552 You need to somehow come up with this arbitrary starting point, x. 88 00:05:37,552 --> 00:05:41,657 How do you do it? To answer this question, let me crudely classify the 89 00:05:41,657 --> 00:05:45,907 situations in which you might be using local search, into 2 categories. 90 00:05:45,907 --> 00:05:50,312 In the first category, you're really depending on local search, to come up 91 00:05:50,312 --> 00:05:54,032 with a good approximate solution, to an optimization problem. 92 00:05:54,032 --> 00:05:58,397 You really have no idea how to get close to an optimal solution, other than 93 00:05:58,397 --> 00:06:03,021 through, some local search Approach. The second category of scenarios is where 94 00:06:03,021 --> 00:06:07,204 you have some pretty good heuristics that seem to be delivering to you pretty good 95 00:06:07,204 --> 00:06:11,194 solutions to your optimization problem and you just want to use a local search 96 00:06:11,194 --> 00:06:13,491 as a post-processing step to do even better. 97 00:06:13,491 --> 00:06:17,475 So let's start with the first category where all of your eggs are in one basket 98 00:06:17,475 --> 00:06:21,179 and you need a local search to deliver to you a pretty good solution to an 99 00:06:21,179 --> 00:06:24,563 optimization Problem. So this is a tricky spot to find yourself 100 00:06:24,563 --> 00:06:26,860 in. Local search is guaranteed to deliver to 101 00:06:26,860 --> 00:06:30,408 you a locally optimal solution. But in many problems locally optimal 102 00:06:30,408 --> 00:06:34,255 solutions can be much, much worse than what you're looking for, a globally 103 00:06:34,255 --> 00:06:37,162 optimal solution. In the special case of the maximum cut 104 00:06:37,162 --> 00:06:39,932 problem, we had a performance guarantee of 50%. 105 00:06:39,932 --> 00:06:43,861 Which already is only a so-so guaranteed but for most optimization problems even 106 00:06:43,861 --> 00:06:46,602 that kinds of performance guarantee is out of question. 107 00:06:46,602 --> 00:06:50,425 There are locally optimal solutions far worse than the globally optimal ones. 108 00:06:50,425 --> 00:06:54,192 On the other hand, you know there are some good locally optimal solutions out 109 00:06:54,192 --> 00:06:56,275 there. In particular the globally optimal 110 00:06:56,275 --> 00:07:00,667 solution is also a locally optimal one. Now if you just run local search once, 111 00:07:00,667 --> 00:07:05,332 it's not clear how to evaluate the quality of the solution that's returned 112 00:07:05,332 --> 00:07:08,152 to you. You run the algorithm, it hands you a 113 00:07:08,152 --> 00:07:12,350 solution, it has cost 79,217. is that good or bad? Who knows? An 114 00:07:12,350 --> 00:07:16,321 obvious approach to doing better is to run the local search many times, say 115 00:07:16,321 --> 00:07:20,433 thousands of times, even millions of times, and then amongst all of the local 116 00:07:20,433 --> 00:07:24,553 optima of the different runs of your local search algorithm returns, you pick 117 00:07:24,553 --> 00:07:27,641 the best one and you make that your final Final solution. 118 00:07:27,641 --> 00:07:31,870 To encourage your local search algorithm to hand back to you different local 119 00:07:31,870 --> 00:07:34,255 optima when you run it over and over again. 120 00:07:34,255 --> 00:07:36,737 You want to be making some random deicsions. 121 00:07:36,737 --> 00:07:40,711 An extremely common point to make a random decision is in step 1 of local 122 00:07:40,711 --> 00:07:43,229 search. Is in choosing your initial starting 123 00:07:43,229 --> 00:07:47,428 point .x so, for example in the maximum cut problem, you'd want to start with a 124 00:07:47,428 --> 00:07:50,457 random cut with each vertex equally likely to be in a or b. 125 00:07:50,457 --> 00:07:54,594 With the traveling salesman problem, you might want to start from a random tour, 126 00:07:54,594 --> 00:07:57,181 that is a random permutation of the end vertices. 127 00:07:57,181 --> 00:08:00,819 And if it's a straint satisfaction problem you could begin by giving each 128 00:08:00,819 --> 00:08:05,367 variable Independently a random value. If this seems kind of like throwing darts 129 00:08:05,367 --> 00:08:09,391 at a dartboard, that's what it is. It turns out there's a lot of stubbornly 130 00:08:09,391 --> 00:08:13,281 difficult problems out there for which the state of the art is not really 131 00:08:13,281 --> 00:08:17,307 substantially better than running independent trials of local search with 132 00:08:17,307 --> 00:08:22,385 different random initial positions and returning the best of the local optimal 133 00:08:22,385 --> 00:08:24,893 that you find. Now let's suppose you're in this second, 134 00:08:24,893 --> 00:08:28,098 happier category of scenarios, where you've got a better handle on your 135 00:08:28,098 --> 00:08:30,700 optimization problem. Maybe you've figured out how to use 136 00:08:30,700 --> 00:08:33,204 greedy algorithms, or maybe mathematical programming. 137 00:08:33,204 --> 00:08:37,007 Anyways, you have techniques that generate close to optimal solutions to 138 00:08:37,007 --> 00:08:40,692 some optimization problem. But why not make these nearly optimal 139 00:08:40,692 --> 00:08:44,328 solutions even better? How do you do that? We'll feed the output 140 00:08:44,328 --> 00:08:48,224 of your current suit of heuristics into a local search post processing step. 141 00:08:48,224 --> 00:08:52,716 After all, local search only moves to better solutions. It can only make your 142 00:08:52,716 --> 00:08:54,565 pretty good solution even better.