1 00:00:01,510 --> 00:00:04,712 Good morning. Okay, back to discrete optimization local 2 00:00:04,712 --> 00:00:07,216 search. And so, so far ,one of the things that we 3 00:00:07,216 --> 00:00:09,952 have done is looking at all these neighborhoods and you know, we saw a 4 00:00:09,952 --> 00:00:13,662 variety of them. You know, some from very simple to very 5 00:00:13,662 --> 00:00:16,550 complicated one. What we want to do today is step back a 6 00:00:16,550 --> 00:00:20,760 little and actually look at how we search these neighborhoods. 7 00:00:20,760 --> 00:00:22,374 Okay? So we have talked about the neighborhood 8 00:00:22,374 --> 00:00:24,800 but not really how we use them. For searching. 9 00:00:24,800 --> 00:00:27,229 It was very implicit. So what do we want to do in the next 10 00:00:27,229 --> 00:00:31,162 three lecture, is take a systematic look at how we can exploit these neighborhoods 11 00:00:31,162 --> 00:00:35,314 and do local search on top of that. Okay? 12 00:00:35,314 --> 00:00:38,932 So more systematic presentation, and then we going to, you know, study heuristics 13 00:00:38,932 --> 00:00:42,486 and metaheuristics, okay? And so, that's going to be a focus of 14 00:00:42,486 --> 00:00:45,980 essentially the lecture today and the next two lectures. 15 00:00:45,980 --> 00:00:49,350 So today mostly are heuristics, the next two lectures, metaheuristics. 16 00:00:49,350 --> 00:00:52,070 Okay? So remember local search work with 17 00:00:52,070 --> 00:00:55,233 states, okay. At any point, we are in a state inside a 18 00:00:55,233 --> 00:00:59,270 resolution, if we only explore you know, feasible configuration. 19 00:00:59,270 --> 00:01:01,712 Or it's a configuration where there may be violations, some of the constraints 20 00:01:01,712 --> 00:01:03,660 are violated. Okay? 21 00:01:03,660 --> 00:01:06,480 Now, essentially, the local search is going to move from the, from state to 22 00:01:06,480 --> 00:01:09,444 state, okay? And essentially, from one state, you can 23 00:01:09,444 --> 00:01:12,657 only move to a subset of states, which are called the neighborhood, okay, of 24 00:01:12,657 --> 00:01:17,111 that particular state. So, we're going to use the function N(s) 25 00:01:17,111 --> 00:01:22,495 to denote the neighborhood of state s. That's all the other states that you can 26 00:01:22,495 --> 00:01:26,716 reach when you are at s, okay? Then we're going to introduce this legal 27 00:01:26,716 --> 00:01:30,373 function, which basically tells you, you know, that from all these neighbors that 28 00:01:30,373 --> 00:01:34,530 you can go, which ones are legal and which ones are not. 29 00:01:34,530 --> 00:01:36,348 Okay? So there would be the subset of the 30 00:01:36,348 --> 00:01:39,868 states that you can move to. Otherwise, you will be basically 31 00:01:39,868 --> 00:01:42,640 preventing the search from going there, okay? 32 00:01:42,640 --> 00:01:45,772 So this is, this is kind of a being implicit to what we have done before, 33 00:01:45,772 --> 00:01:48,728 okay? So always moving to something which is a 34 00:01:48,728 --> 00:01:51,985 better place. Okay, but we'll many other ways to do 35 00:01:51,985 --> 00:01:56,014 that in this next three lectures. Okay, and then once we know which 36 00:01:56,014 --> 00:01:59,080 neighbors are legal, what we are going to do is select one of them. 37 00:01:59,080 --> 00:02:02,900 And once again there will be many many ways of actually selecting the neighbors. 38 00:02:02,900 --> 00:02:05,858 Okay, so what you get is this crazy function, you know, S of L of N of s and 39 00:02:05,858 --> 00:02:10,610 then are all the other S's that you can use in the other function. 40 00:02:10,610 --> 00:02:14,042 But essentially, what you do, you select a legal neighbor, okay, from the state 41 00:02:14,042 --> 00:02:15,970 you are in. Okay? 42 00:02:15,970 --> 00:02:19,285 So, the algorithm, and of course, what we want to do is of, is of use in some cases 43 00:02:19,285 --> 00:02:23,847 is minimizing an objective function. Almost always, either it's minimizing 44 00:02:23,847 --> 00:02:27,366 violation or it's actually optimizing an objective function from the problem 45 00:02:27,366 --> 00:02:29,260 specification. Okay? 46 00:02:29,260 --> 00:02:31,720 So, this is the general pattern that we're going to use in the next couple of 47 00:02:31,720 --> 00:02:33,120 lectures. Okay? 48 00:02:33,120 --> 00:02:35,754 So, you have the local search. You know you have the objective function 49 00:02:35,754 --> 00:02:37,826 f. You have the neighborhood N and so we'll 50 00:02:37,826 --> 00:02:41,800 give you a definition of that. We'll pass that to, to the local search. 51 00:02:41,800 --> 00:02:45,485 You have the function L and the function S, for which neighbors are legal and then 52 00:02:45,485 --> 00:02:48,300 what is the selection function. Okay. 53 00:02:48,300 --> 00:02:51,135 And most of the local search, you know we'll adapt this a little bit from time 54 00:02:51,135 --> 00:02:53,381 to time. But most of the local search, I'm 55 00:02:53,381 --> 00:02:56,176 going to start from a configuration that you generate and you can have different 56 00:02:56,176 --> 00:02:59,313 ways of doing that. And of course, that's the best solution 57 00:02:59,313 --> 00:03:02,731 you have at that point particular point. So, S star is like, keeping the best 58 00:03:02,731 --> 00:03:06,447 solutions at this point of the search. And then you're going to do a number of 59 00:03:06,447 --> 00:03:09,485 iteration, every one of them is going to go to a neighbor and so and so forth, 60 00:03:09,485 --> 00:03:12,704 okay? And obviously if the neighbor sees 61 00:03:12,704 --> 00:03:15,602 satisfiable and he has improved the current best solution you will, and you 62 00:03:15,602 --> 00:03:20,211 have found a better solution, we have found a better solution and we store it. 63 00:03:20,211 --> 00:03:24,472 And otherwise, what we do, we move to the next neighbor, and how do we do that? 64 00:03:24,472 --> 00:03:28,770 Well, basically, we select a legal neighbor in the neighborhood of s, okay. 65 00:03:28,770 --> 00:03:31,380 So and at the end of the search we returned a best solution we had found, 66 00:03:31,380 --> 00:03:34,409 okay. So this is schema that we going to use. 67 00:03:34,409 --> 00:03:37,769 And one of the goals today is give you some example of what L can be or what S 68 00:03:37,769 --> 00:03:43,535 can be or what you know and most, mostly we'd seen what the neighborhood can be. 69 00:03:43,535 --> 00:03:47,060 Okay, and so that's the goal. The goal is to look at these L and S 70 00:03:47,060 --> 00:03:50,620 function and so all the variety of things we could do there. 71 00:03:50,620 --> 00:03:52,510 Okay. So this is an illustration. 72 00:03:52,510 --> 00:03:56,196 Graphical illustration of what we do. So we start at a particular state. 73 00:03:56,196 --> 00:03:58,920 Oooo over there. Okay. 74 00:03:58,920 --> 00:04:01,516 and then essentially what we're going to do is define the neighbor of that 75 00:04:01,516 --> 00:04:04,530 station. This is the regions that you see here. 76 00:04:04,530 --> 00:04:07,595 That's all the neighbor. Eventually we can move to all of them. 77 00:04:07,595 --> 00:04:09,240 But then we put these restriction. Okay? 78 00:04:09,240 --> 00:04:13,120 So I only want to look at these neighbors which satisfy this legal condition. 79 00:04:13,120 --> 00:04:16,170 And now you see all these three neighbors there in this particular case. 80 00:04:16,170 --> 00:04:20,360 And then we select one of them. This is you know, the selected neighbor. 81 00:04:20,360 --> 00:04:21,750 Okay? And then we move. 82 00:04:21,750 --> 00:04:23,764 Okay? And so now we have moved from you know, 83 00:04:23,764 --> 00:04:26,660 the original note to the selected note. Okay? 84 00:04:26,660 --> 00:04:28,970 We restart the process. These are all the neighbors. 85 00:04:28,970 --> 00:04:31,050 Okay? Some of them are legal, some of them are 86 00:04:31,050 --> 00:04:32,240 not. Okay? 87 00:04:32,240 --> 00:04:36,139 And the, you select one of them, okay? So, you know, here and then you move to 88 00:04:36,139 --> 00:04:39,373 that place and you continue doing that and you see the search moving [SOUND] all 89 00:04:39,373 --> 00:04:43,040 over the place until it reaches the final state. 90 00:04:43,040 --> 00:04:45,170 Isn't that beautiful? We have to do it again, I mean, it's so 91 00:04:45,170 --> 00:04:47,793 beautiful, you can't imagine how much time we spent doing this so I want to 92 00:04:47,793 --> 00:04:51,242 show it again. So we start from this, we selct the 93 00:04:51,242 --> 00:04:54,440 neighbor, okay, the legal ones, we move, okay? 94 00:04:54,440 --> 00:04:57,850 We do the same thing, we selEct the neighbor, the legal ones, we move. 95 00:04:57,850 --> 00:04:59,700 Okay? And then we keep moving, okay? 96 00:04:59,700 --> 00:05:02,680 And so this is essentially, what we going to do today. 97 00:05:02,680 --> 00:05:04,836 Okay. Looking at, not the neighborhood, because 98 00:05:04,836 --> 00:05:06,858 we have already seen many of those things. 99 00:05:06,858 --> 00:05:09,400 But looking at what this legal function is, and how we select a particle and 100 00:05:09,400 --> 00:05:10,620 neighbor. Okay? 101 00:05:10,620 --> 00:05:13,485 And there are many, many ways to do this. People are really creative in this feat. 102 00:05:13,485 --> 00:05:15,847 Okay? So, for instance, one of the things we 103 00:05:15,847 --> 00:05:19,720 have seen so far, many, many times is only looking at local improvements. 104 00:05:19,720 --> 00:05:22,736 When you are in a state you only want to move to another state and in this 105 00:05:22,736 --> 00:05:26,460 particular case which is better than the current case. 106 00:05:26,460 --> 00:05:28,500 Okay, so you always want to improve. Okay. 107 00:05:28,500 --> 00:05:31,020 In a sense, you always want to go up, up, up, up. 108 00:05:31,020 --> 00:05:31,970 Okay. Better and better. 109 00:05:31,970 --> 00:05:34,070 Actually we are minimizing so down, down, down, down. 110 00:05:34,070 --> 00:05:37,880 Okay, so and the selection function many times what we have done. 111 00:05:37,880 --> 00:05:40,411 Is looking at something which is greedy. You look at all the neighbors that are 112 00:05:40,411 --> 00:05:43,556 improving, and you take the best one. Because somehow, you know, you believe 113 00:05:43,556 --> 00:05:47,220 that this is going to give you the best solution quickly, okay? 114 00:05:47,220 --> 00:05:50,420 So these two things are things that we have seen, you know, kind of implicitly 115 00:05:50,420 --> 00:05:53,390 so far. Okay, now in this field okay, in the, the 116 00:05:53,390 --> 00:05:56,974 local search we typically distinguish between heuristic and what is called 117 00:05:56,974 --> 00:06:00,114 meta-heuristic. Okay, so one of the things in, in 118 00:06:00,114 --> 00:06:02,974 optimization that you have seen so far right, is that we are always very good at 119 00:06:02,974 --> 00:06:06,962 choosing nice names. Like heuristic, metaheuristic, and you 120 00:06:06,962 --> 00:06:11,430 see many of very fancy name today, okay? So we are very creative people, okay? 121 00:06:11,430 --> 00:06:15,270 A heuristic is something that, essentially, tells you how to choose the 122 00:06:15,270 --> 00:06:19,155 next neighbor, okay? It's basically telling you, okay, this is 123 00:06:19,155 --> 00:06:22,113 the heuristic, this is the way you want to choose the next neighbor to go 124 00:06:22,113 --> 00:06:25,076 to, okay? And typically, you use only local 125 00:06:25,076 --> 00:06:27,896 information, the state s at which you, you are and then the neighborhood 126 00:06:27,896 --> 00:06:31,505 obviously. Okay and the goal of this heuristic is 127 00:06:31,505 --> 00:06:34,720 essentially to drive you down to a local minimum. 128 00:06:34,720 --> 00:06:37,780 Okay? To a local minimum, a good one hopefully. 129 00:06:37,780 --> 00:06:39,796 Okay? Now, the metaheuristic is a little bit 130 00:06:39,796 --> 00:06:40,880 different. Okay? 131 00:06:40,880 --> 00:06:43,965 So, the goal there is going to be escaping local minima, okay. 132 00:06:43,965 --> 00:06:46,905 So, so if you only do local searches let's say using greedy improvement, 133 00:06:46,905 --> 00:06:50,545 you're going to get to a local minimum. Most of the time you have no guarantee on 134 00:06:50,545 --> 00:06:51,660 the quality of it. Okay? 135 00:06:51,660 --> 00:06:54,502 So, the metaheuristic is going to say ooh, you know, I'm stuck here but, I 136 00:06:54,502 --> 00:06:57,540 want to try to get out of there and see if there are other local minima that are 137 00:06:57,540 --> 00:06:59,585 good. Okay? 138 00:06:59,585 --> 00:07:01,290 So, that's what you're going to do. Okay? 139 00:07:01,290 --> 00:07:04,042 So, essentially what you want to do is use the metaheuristic and we see a bunch 140 00:07:04,042 --> 00:07:05,900 of them. Right? 141 00:07:05,900 --> 00:07:09,186 We will see how they can derive the such all of local minima and trying to get 142 00:07:09,186 --> 00:07:12,313 closer to the global optima, optimum in, in, a by using kind of non local 143 00:07:12,313 --> 00:07:16,942 information, okay? So what typically these things have, they 144 00:07:16,942 --> 00:07:21,266 have some kind of memory, there is some kind of learning component, okay? 145 00:07:21,266 --> 00:07:24,446 So this is essentially what the difference between this two things, one 146 00:07:24,446 --> 00:07:27,626 of them is going to guide you to the local minima and the other one is going 147 00:07:27,626 --> 00:07:32,090 to try to allow you to escape from the local minima. 148 00:07:32,090 --> 00:07:36,070 And, and tries to get to global optimality. 149 00:07:36,070 --> 00:07:37,386 Okay? And so, today, we're going to talk mostly 150 00:07:37,386 --> 00:07:39,724 about heuristics. And then we'll spend the next two 151 00:07:39,724 --> 00:07:42,390 lectures talking about metaheuristic, okay? 152 00:07:42,390 --> 00:07:46,530 So, so, one of the ways that you define legal moves, okay? 153 00:07:46,530 --> 00:07:50,145 So, and that drives also the heuristic. Is by lose, use, looking at condition of 154 00:07:50,145 --> 00:07:52,645 the objective function. There will be other things that we are 155 00:07:52,645 --> 00:07:55,370 going to look at. And you'll see some of them today. 156 00:07:55,370 --> 00:07:58,924 And you know, and in the next lectures. But essentially, what I'm going to show 157 00:07:58,924 --> 00:08:02,580 you now, are just condition of the objective function, okay? 158 00:08:02,580 --> 00:08:05,804 So local improvement, we already mentioned this, essentially, you want to 159 00:08:05,804 --> 00:08:10,170 stay such that you improve the value of the objective function, okay? 160 00:08:10,170 --> 00:08:12,690 So that's a strong condition. You have always to move to someplace 161 00:08:12,690 --> 00:08:14,500 which is better. Okay? 162 00:08:14,500 --> 00:08:17,200 Now, sometimes, there is no such neighbor, but there are neighbors that 163 00:08:17,200 --> 00:08:19,510 are different from where you are. Okay? 164 00:08:19,510 --> 00:08:22,860 Okay, obviously and these neighbors may not be you know, better than, than, than 165 00:08:22,860 --> 00:08:26,890 the current state, but they can be you know, equally good. 166 00:08:26,890 --> 00:08:29,814 And so it means, still be advantageous to move there because maybe from there, you 167 00:08:29,814 --> 00:08:32,310 can move to a place which is better, okay? 168 00:08:32,310 --> 00:08:34,186 So that's called No Degradation essentially. 169 00:08:34,186 --> 00:08:37,042 And what you do is you basically select something which doesn't degrade the value 170 00:08:37,042 --> 00:08:39,650 of the objective function. Okay? 171 00:08:39,650 --> 00:08:41,660 So very useful, used in many conditions. Okay? 172 00:08:41,660 --> 00:08:45,530 And is, it, you can also use that to in, introduce randomization. 173 00:08:45,530 --> 00:08:47,050 And we'll talk about that a little bit later. 174 00:08:47,050 --> 00:08:49,163 Okay? And then you can be completely you know, 175 00:08:49,163 --> 00:08:52,970 brutal and say ooh, you know, I can [INAUDIBLE] all the neighbors. 176 00:08:52,970 --> 00:08:54,732 Okay? So and we'll see some search heuristics 177 00:08:54,732 --> 00:08:57,070 here. That would actually do that. 178 00:08:57,070 --> 00:08:58,654 Okay? And so essentially, potentially 179 00:08:58,654 --> 00:09:00,200 everything is a neighbor. Okay? 180 00:09:00,200 --> 00:09:02,948 Of course we, we're going to, you know? Once you have something with that 181 00:09:02,948 --> 00:09:04,978 consider everything. You will have to have a selection 182 00:09:04,978 --> 00:09:06,710 function that does the right thing. Okay? 183 00:09:06,710 --> 00:09:09,115 So it's going to be a combination of what is legal and how does selection function 184 00:09:09,115 --> 00:09:11,997 work? Okay so with this some kind of properties 185 00:09:11,997 --> 00:09:15,820 are what you can do, okay? So now you have also one of the things 186 00:09:15,820 --> 00:09:18,358 that you will have to see is that you will have to, once you have the 187 00:09:18,358 --> 00:09:21,460 neighborhood and once you define what is, what is legal, you will have to decide 188 00:09:21,460 --> 00:09:25,130 how to explore this neighborhood. Okay. 189 00:09:25,130 --> 00:09:27,740 And sometimes the neighborhood is tiny, sometimes it's huge. 190 00:09:27,740 --> 00:09:30,490 So the way you explore this neighbor is, is important. 191 00:09:30,490 --> 00:09:32,930 Okay. So we will see various kinds of things. 192 00:09:32,930 --> 00:09:34,710 Okay. So one of them is best neighbor. 193 00:09:34,710 --> 00:09:37,800 You want to look at the neighborhood in it's, in it's, in it's entirety. 194 00:09:37,800 --> 00:09:39,590 And you want to select the best neighborhood. 195 00:09:39,590 --> 00:09:41,920 Lot of local search are doing things like this. 196 00:09:41,920 --> 00:09:44,810 But of course that means that you have to scan the entire neighbor route. 197 00:09:44,810 --> 00:09:47,860 And select the best, you know for selecting the, the best neighbor, okay? 198 00:09:47,860 --> 00:09:51,450 But this is one of the things that is very popular, okay? 199 00:09:51,450 --> 00:09:54,488 The next thing which is, which you can do is to say ooh, I'm not interested in 200 00:09:54,488 --> 00:09:58,148 exploring the entire neighborhood. I want to stop as soon as I find 201 00:09:58,148 --> 00:10:01,188 something legal, okay? And sometimes we call that you know the 202 00:10:01,188 --> 00:10:03,360 first, the first neighborhood. Okay? 203 00:10:03,360 --> 00:10:06,150 So you want to find something which is legal and then you know, that, that's 204 00:10:06,150 --> 00:10:08,500 sufficient. You stop at that point. 205 00:10:08,500 --> 00:10:11,150 The hope is that you don't have to explore the entire neighborhood. 206 00:10:11,150 --> 00:10:13,202 You can very quickly find the neighborhood that is legal and then you 207 00:10:13,202 --> 00:10:14,870 move there. And then you stop. 208 00:10:14,870 --> 00:10:17,617 Of course, you know, when you at, at some point you will have to explore the entire 209 00:10:17,617 --> 00:10:20,530 neighborhood to find out that there is nothing legal. 210 00:10:20,530 --> 00:10:24,070 But in a sense, what you, most of time you hope that you will only explore a 211 00:10:24,070 --> 00:10:28,140 subset of the neighborhood. So if the neighborhood is big. 212 00:10:28,140 --> 00:10:30,590 You can still use something like that. It will take more time if you try to do 213 00:10:30,590 --> 00:10:33,350 the best neighbor. And then we have this thing which is 214 00:10:33,350 --> 00:10:37,230 called Multi-stage Selection. And the key idea there is that, you want 215 00:10:37,230 --> 00:10:41,370 to preserve some of the greedy aspect, that's really important for you. 216 00:10:41,370 --> 00:10:44,620 But you don't want to explore the entire neighborhood because it's very big so 217 00:10:44,620 --> 00:10:49,100 what you do is basically split the neighborhood exploration in two parts. 218 00:10:49,100 --> 00:10:51,431 The first one is going to select part of neighborhood, so you won't explore the 219 00:10:51,431 --> 00:10:54,590 entire things. You will only select a subpart of it. 220 00:10:54,590 --> 00:10:57,770 And the second one, the second part is going to explore in it's entirety the 221 00:10:57,770 --> 00:11:00,310 rest of the sub neighborhood. Okay. 222 00:11:00,310 --> 00:11:03,019 And I'm going to give an example of this because it's very interesting and very 223 00:11:03,019 --> 00:11:06,588 useful in practice. Okay, now, now lets look a little bit 224 00:11:06,588 --> 00:11:10,318 about the best neighbor. Okay, so in practice you may have many 225 00:11:10,318 --> 00:11:13,660 different neighbors that are, that have the best value okay. 226 00:11:13,660 --> 00:11:16,430 And in those cases, randomization is very important. 227 00:11:16,430 --> 00:11:19,180 So you don't want to be in in many cases in local search. 228 00:11:19,180 --> 00:11:21,030 You don't want to be completely deterministic. 229 00:11:21,030 --> 00:11:23,710 You want to introduce this randomization component. 230 00:11:23,710 --> 00:11:26,674 And that allows you to explore the search in a more, in a, in a, in a more 231 00:11:26,674 --> 00:11:29,150 interesting fashion. Okay? 232 00:11:29,150 --> 00:11:31,640 So we'll talk about this much more at some point. 233 00:11:31,640 --> 00:11:34,370 But at this point here, considering the best neighbor there is something very 234 00:11:34,370 --> 00:11:35,870 easy to do. Okay? 235 00:11:35,870 --> 00:11:39,066 So you basically you know, you basically take all the best neighbors, so this have 236 00:11:39,066 --> 00:11:42,750 the, this are really the legal move that you want to go. 237 00:11:42,750 --> 00:11:45,495 And then essentially you want to select one of them, but you want to do that 238 00:11:45,495 --> 00:11:48,446 randomly, okay? And so what you do, if they are 239 00:11:48,446 --> 00:11:52,798 essentially, if the number of neighbor is cardinality of N and star, which are the 240 00:11:52,798 --> 00:11:57,022 best neighbors, you want to select one of them with the probability which is one 241 00:11:57,022 --> 00:12:04,125 over the size of those best But, this, this, best this best neighbor, 242 00:12:04,125 --> 00:12:06,337 okay? In the sense, what you do here is you 243 00:12:06,337 --> 00:12:09,835 compute all the best neighbor and then you, you basically choose one of them you 244 00:12:09,835 --> 00:12:13,681 know, in a, in a uniform random fashion, okay? 245 00:12:13,681 --> 00:12:16,808 And so, we will, we often do things like this because it gives you ways to 246 00:12:16,808 --> 00:12:21,700 actually not going always to the same place but it gives you more variety. 247 00:12:21,700 --> 00:12:23,150 Okay? So essentially you want to see best 248 00:12:23,150 --> 00:12:25,859 improvement you can prioritize the local search that I have given you at the 249 00:12:25,859 --> 00:12:30,404 beginning. By simply using an improved essentially 250 00:12:30,404 --> 00:12:34,290 using improvement as, you know, improvement as the, as the, the legal 251 00:12:34,290 --> 00:12:38,620 moose and then selecting the best one. Okay? 252 00:12:38,620 --> 00:12:40,918 So, if you select these things, you will have a local search. 253 00:12:40,918 --> 00:12:43,498 the legal moves are going to be the one where you improve the value of the 254 00:12:43,498 --> 00:12:46,293 objective function and then you always select the one which has the best value 255 00:12:46,293 --> 00:12:49,650 with the definition that I've given you here. 256 00:12:49,650 --> 00:12:53,075 Which basically means your computer's set and then you choose one of them randomly. 257 00:12:53,075 --> 00:12:56,878 Okay, so that's one of the things. So you could do similar things for the 258 00:12:56,878 --> 00:13:00,244 first neighbor in that particular case. What you do is essentially you take the 259 00:13:00,244 --> 00:13:02,735 first neighbor in the neighborhood exploring it in some kind of 260 00:13:02,735 --> 00:13:06,740 lexicographic order. Okay, and that's what you return, okay? 261 00:13:06,740 --> 00:13:09,620 And so once again the function can be very easy to compute it. 262 00:13:09,620 --> 00:13:11,840 What you do is you, you say all the legal moves are the one that improve the 263 00:13:11,840 --> 00:13:14,660 objective function. At the current state. 264 00:13:14,660 --> 00:13:17,570 And then, You want to select the first one which is 265 00:13:17,570 --> 00:13:19,170 legal, in a sense. Okay? 266 00:13:19,170 --> 00:13:21,180 So that's how you can parameterize this search. 267 00:13:21,180 --> 00:13:24,000 The generic local search that I gave you before, okay? 268 00:13:24,000 --> 00:13:26,770 So let me talk a little bit about the multistage heuristic. 269 00:13:26,770 --> 00:13:29,426 Because, you know, as I said, you know? Some of them are really useful in 270 00:13:29,426 --> 00:13:31,928 practice. And the motivation, as I said is you 271 00:13:31,928 --> 00:13:34,996 still want to keep the greedy aspect but you don't want to scan the entire 272 00:13:34,996 --> 00:13:38,976 neighborhood because for some reason, it's too large. 273 00:13:38,976 --> 00:13:42,460 And it's not a good compromise between, you know, the quality of the solution and 274 00:13:42,460 --> 00:13:46,760 the efficiency of the algorithm, okay? So we have seen one of those, okay. 275 00:13:46,760 --> 00:13:51,480 So one of them was essentially the way did the search for the Queens problem. 276 00:13:51,480 --> 00:13:54,310 Remember, when we did the Queens problems, every Queens. 277 00:13:54,310 --> 00:13:58,535 Could be associated with a violation, that's the number of all the queens that 278 00:13:58,535 --> 00:14:03,488 are currently attacking. And then we were basically looking at the 279 00:14:03,488 --> 00:14:08,240 queen that is the most aggressive, and we were basically moving it to a position 280 00:14:08,240 --> 00:14:14,439 where it was much less aggressive. Okay, so basically the position where it 281 00:14:14,439 --> 00:14:17,670 min, which minimizes the number of violation okay? 282 00:14:17,670 --> 00:14:20,906 So, what we need was two step, right? So, we selected only one queen and then 283 00:14:20,906 --> 00:14:24,245 we moved this value to the best, to its best position as far as decreasing the 284 00:14:24,245 --> 00:14:29,366 violations are concerned, okay? So in a sense, you know, this heuristic 285 00:14:29,366 --> 00:14:34,016 is, is sometimes called max/min-conflict. You select a variable which appear in the 286 00:14:34,016 --> 00:14:36,170 most violation. It's greedy. 287 00:14:36,170 --> 00:14:38,835 Okay, so greedy choice of the variables, and then you're setting the value for 288 00:14:38,835 --> 00:14:41,448 that queen/g. So a row, okay, for the column as a 289 00:14:41,448 --> 00:14:42,790 queen/g. Okay? 290 00:14:42,790 --> 00:14:45,050 Which result in the smallest amount of violations. 291 00:14:45,050 --> 00:14:46,936 Okay? And that's also a second step, which is 292 00:14:46,936 --> 00:14:49,188 greedy. But the first step, has already selected 293 00:14:49,188 --> 00:14:51,408 one queen/g. Okay, so in the second step we only look 294 00:14:51,408 --> 00:14:54,330 at one queen/g. Not all the queens, okay? 295 00:14:54,330 --> 00:14:57,625 Now a variation on this is is the original min-conflict heuristic. 296 00:14:57,625 --> 00:15:00,586 That was proposed by Steve Minton, and what you do here is you just select the 297 00:15:00,586 --> 00:15:03,852 first screen randomly. It has to have some violation, but you, 298 00:15:03,852 --> 00:15:07,560 you select it completely randomly, okay? And the you select the value for that 299 00:15:07,560 --> 00:15:10,746 queen which minimizes set of violations. So that's typically called the 300 00:15:10,746 --> 00:15:13,520 Min-conflict Heuristic. So the first step is randomizes, the 301 00:15:13,520 --> 00:15:16,464 second step is greedy. So two examples of Multi-stage 302 00:15:16,464 --> 00:15:18,672 Heuristics. You first select some part of the 303 00:15:18,672 --> 00:15:21,524 neighborhood, you know, Queen, and then you select all, you look at all the 304 00:15:21,524 --> 00:15:24,514 possible values and you select the one which is the best in the second stage for 305 00:15:24,514 --> 00:15:29,384 that particular selected Queen. Okay, now what would be the alternative 306 00:15:29,384 --> 00:15:31,898 to that? The neighborhood that you could explore 307 00:15:31,898 --> 00:15:34,628 are all the queens and all the possible move for the queens so you would require 308 00:15:34,628 --> 00:15:36,860 a quadratic neighborhood. Okay. 309 00:15:36,860 --> 00:15:40,577 And the next state, okay, the set of state obtained by looking at the current 310 00:15:40,577 --> 00:15:46,320 state taking any queen q, and any value v and looking at what that state results. 311 00:15:46,320 --> 00:15:47,820 It result into. Okay. 312 00:15:47,820 --> 00:15:51,633 And the key point is when you do that. You, you may have solution that are 313 00:15:51,633 --> 00:15:53,930 actually better than what I've just shown you, right? 314 00:15:53,930 --> 00:15:56,990 It's not necessary the queen which has the most violation which is going to 315 00:15:56,990 --> 00:16:00,730 decrease the violation the most. It may be a queen which has, you know, 316 00:16:00,730 --> 00:16:03,700 fewer violation but then you can reduce the number of violation tremendously, 317 00:16:03,700 --> 00:16:06,247 okay? So that's basically, you know, this is a 318 00:16:06,247 --> 00:16:09,810 quadratic neighborhood. It would, gives you the best local move. 319 00:16:09,810 --> 00:16:12,460 What we do is an approximation of this, right? 320 00:16:12,460 --> 00:16:15,427 By using essentially a first selection of the variables and then a selection of the 321 00:16:15,427 --> 00:16:18,016 value. Instead of considering the entire thing 322 00:16:18,016 --> 00:16:19,370 globally. Okay? 323 00:16:19,370 --> 00:16:21,570 So, the complexity here would be quadratic. 324 00:16:21,570 --> 00:16:23,428 Okay? All the pairs, for, all the columns and 325 00:16:23,428 --> 00:16:25,010 the rows. Okay? 326 00:16:25,010 --> 00:16:28,180 So, and, and, therefore, you have a, there is a price to pay here. 327 00:16:28,180 --> 00:16:31,235 It's essentially you know, you, you are proportional to the number of parts in 328 00:16:31,235 --> 00:16:33,030 the chessboard. Okay? 329 00:16:33,030 --> 00:16:36,358 One, we look at the min-conflict of the max min-conflict heuristic, this is a 330 00:16:36,358 --> 00:16:40,230 neighborhood which is used to explore in linear time, right? 331 00:16:40,230 --> 00:16:42,810 So we basically select a queen, okay that may take at most linear time and 332 00:16:42,810 --> 00:16:46,240 min-conflict, it's constant time. And then you have to select the value 333 00:16:46,240 --> 00:16:48,560 which is also looking at all the values right? 334 00:16:48,560 --> 00:16:50,560 All the values in the column, that's linear time. 335 00:16:50,560 --> 00:16:53,584 So, you know, constant plus linear or linear plus linear, it's linear time, 336 00:16:53,584 --> 00:16:55,710 okay? So, what you see here is a trade-off, 337 00:16:55,710 --> 00:16:57,614 okay? So, we won't have the best neighbor but 338 00:16:57,614 --> 00:17:00,500 we'll have a, you know kind of a greedy neighbor anyway. 339 00:17:00,500 --> 00:17:03,590 But we take only linear time instead of quadratic time so we have. 340 00:17:03,590 --> 00:17:06,760 We can explore many many more neighbors in a sence. 341 00:17:06,760 --> 00:17:10,060 Okay, and sot the kind of trade off that you often have in local search. 342 00:17:10,060 --> 00:17:13,110 Okay, so this multi-heuristics as I said, you know are useful. 343 00:17:13,110 --> 00:17:16,719 Okay, very useful. Okay, now think about it's you know, we 344 00:17:16,719 --> 00:17:21,758 saw you the consequening example. And remember we had all these cars on the 345 00:17:21,758 --> 00:17:25,678 assembly line, there were contraints on how many you know, how many units how 346 00:17:25,678 --> 00:17:29,509 many cars. How many options a production unit can 347 00:17:29,509 --> 00:17:33,621 put on a car, okay, in a row. And then essentially, we was basically 348 00:17:33,621 --> 00:17:36,380 scheduling all these cars on the slots, okay? 349 00:17:36,380 --> 00:17:39,328 And you know, the stars here are all the cars that are basically violating some of 350 00:17:39,328 --> 00:17:43,770 these capacity constraints, okay? And the neighborhood we selected was, oh, 351 00:17:43,770 --> 00:17:47,674 we want to take two cars, one of which has to be in violation and we would just 352 00:17:47,674 --> 00:17:52,193 swap them, okay? Now, if we ac-, if we want to have a 353 00:17:52,193 --> 00:17:57,250 completely greedy procedure, okay, for this particular neighborhood, okay. 354 00:17:57,250 --> 00:18:00,610 So, and so it, it's going to be a quadratic neighborhood, right? 355 00:18:00,610 --> 00:18:03,850 So we going to take, we can scan every slot in the assembly line and then swap 356 00:18:03,850 --> 00:18:07,610 it with all the other slots in the assembly line. 357 00:18:07,610 --> 00:18:10,600 And that's a lot of swap right. So if we have an assembly line with say, 358 00:18:10,600 --> 00:18:14,590 let's say 300 you know, cars. This would be exploring about 45,000 you 359 00:18:14,590 --> 00:18:17,760 know, configurations. So it's going to take awhile to do that, 360 00:18:17,760 --> 00:18:20,134 okay? So a multistage neighborhood would just 361 00:18:20,134 --> 00:18:22,490 say ooh, I'm going to select one car, okay. 362 00:18:22,490 --> 00:18:25,550 So It's kind of a linear kind of your assembly line, okay. 363 00:18:25,550 --> 00:18:28,110 And then you're going to say ooh, which other car can I swap? 364 00:18:28,110 --> 00:18:31,550 It's another linear you know swap of the, of the neighborhood. 365 00:18:31,550 --> 00:18:34,100 And that's essentially a much smaller neighborhood, right. 366 00:18:34,100 --> 00:18:38,120 It's like you know, 600 you know, at most 600 you know, operations that you need to 367 00:18:38,120 --> 00:18:40,224 do. So it's linear in the size of the 368 00:18:40,224 --> 00:18:42,360 assembly line. So once again you have this tradeoff 369 00:18:42,360 --> 00:18:44,389 here. You know, I can get the best move or I 370 00:18:44,389 --> 00:18:47,560 can get a very good move. But much faster. 371 00:18:47,560 --> 00:18:49,954 Which one is the best? Well, that will depend on the problem but 372 00:18:49,954 --> 00:18:52,619 you have to consider these options when you're [INAUDIBLE] designing a local 373 00:18:52,619 --> 00:18:55,932 search procedure, okay? So that's, you know, to give you a sense, 374 00:18:55,932 --> 00:18:58,380 you know? you can take the best neighbor, you can 375 00:18:58,380 --> 00:19:01,140 take the first neighbor, you can take something which is in between, in a 376 00:19:01,140 --> 00:19:03,854 sense, which is, you know, taking something which is greedy but we've a 377 00:19:03,854 --> 00:19:08,060 multi-stage approach. So, what I want to talk about now is 378 00:19:08,060 --> 00:19:11,070 random work. Which is a completely crazy idea in a 379 00:19:11,070 --> 00:19:14,910 sense, but their are, there are applications which, this is the thing to 380 00:19:14,910 --> 00:19:17,020 do. Okay? 381 00:19:17,020 --> 00:19:19,855 So randomization is what? You want to select a neighbor A 382 00:19:19,855 --> 00:19:21,980 completely at random. Okay? 383 00:19:21,980 --> 00:19:25,190 And then you have to decided whether to accept it, okay? 384 00:19:25,190 --> 00:19:28,277 And so, some of them are going to accept the move if its improved or you can use 385 00:19:28,277 --> 00:19:32,500 the Metropolis algorithm that I will talk about in a later one. 386 00:19:32,500 --> 00:19:35,555 But essentially what you're going to do is select a neighbor randomly and then 387 00:19:35,555 --> 00:19:39,270 decide if you accept it. Using some time of criteria, right? 388 00:19:39,270 --> 00:19:42,470 And so essentially let's look at the first one, which is random improvement, 389 00:19:42,470 --> 00:19:46,697 what you do here is Is that, you basically look at the neighbor, okay? 390 00:19:46,697 --> 00:19:50,147 The entire neighborhood and you take one neighbor with you know, some probability 391 00:19:50,147 --> 00:19:53,397 which is, essentially you've seen that all the neighbors can be selected with 392 00:19:53,397 --> 00:19:56,887 same probability. You take one randomly, completely 393 00:19:56,887 --> 00:19:59,381 randomly, and then you look if it improves the current solution, if it 394 00:19:59,381 --> 00:20:03,254 does, you move to it, okay? If it doesn't you stay in the same state. 395 00:20:03,254 --> 00:20:07,522 And you iterate these things, okay? So, so this can be actually very 396 00:20:07,522 --> 00:20:10,342 effective, okay? In some part of your, kind of local 397 00:20:10,342 --> 00:20:13,396 search, okay? And there are var, various cases where 398 00:20:13,396 --> 00:20:19,350 this is effective and one of them is when the neighborhood is really, really large. 399 00:20:19,350 --> 00:20:22,330 Okay, so remember this traveling tournament problem, okay? 400 00:20:22,330 --> 00:20:25,270 So we had all these teams, kind of the baseball teams. 401 00:20:25,270 --> 00:20:28,218 That had to meet with you know, play against every other team twice, you know, 402 00:20:28,218 --> 00:20:31,829 it was a round robin tournament. And so you would play some games at home, 403 00:20:31,829 --> 00:20:34,366 then move, you know, play some games away, then come back and play these 404 00:20:34,366 --> 00:20:36,896 things. And the goal was to minimize, 405 00:20:36,896 --> 00:20:39,978 essentially, the travel distance. And so you had these constraints making 406 00:20:39,978 --> 00:20:43,610 sure that the team don't play too many games in a row at home or away. 407 00:20:43,610 --> 00:20:46,090 And then you had basically, this optimization, this objective, you know, 408 00:20:46,090 --> 00:20:49,705 this objective function, which was global and therefore difficult to optimize. 409 00:20:49,705 --> 00:20:51,657 Okay? And so what we saw is that there were 410 00:20:51,657 --> 00:20:53,390 plenty of moves that we could do. Right? 411 00:20:53,390 --> 00:20:56,380 So we could swap homes, swap teams, swap rounds and then the partial version of 412 00:20:56,380 --> 00:20:57,820 these guys. Okay? 413 00:20:57,820 --> 00:21:00,730 And some of these neighborhoods are actually pretty complicated. 414 00:21:00,730 --> 00:21:04,240 They are you know, let's say end cube end cube moves the, in, in some of these 415 00:21:04,240 --> 00:21:07,670 neighborhoods where n is the number of teams. 416 00:21:07,670 --> 00:21:09,880 Okay? And, and, more, more, more, more 417 00:21:09,880 --> 00:21:12,646 important you know equally important in a sense /g. 418 00:21:12,646 --> 00:21:15,010 Some of this move were affecting the entire schedule. 419 00:21:15,010 --> 00:21:17,630 So, you had a lot of operation to carry it out. 420 00:21:17,630 --> 00:21:19,702 Okay? So, this was essentially swapping 421 00:21:19,702 --> 00:21:22,960 swapping the [UNKNOWN], swapping the teams here. 422 00:21:22,960 --> 00:21:26,096 And so you know you would affect the large part of neighborhood there and then 423 00:21:26,096 --> 00:21:29,183 you need flip some of these to the rest of feasibility and so what you see here 424 00:21:29,183 --> 00:21:32,074 in color essentially in all the things that have been moved during that 425 00:21:32,074 --> 00:21:37,250 particular, that have been changing that particular move. 426 00:21:37,250 --> 00:21:40,085 When you look at somethin glike this you have many, many ,many neighbors and 427 00:21:40,085 --> 00:21:44,420 everyone is going to affect the entire scheduleso they take long to evaluate. 428 00:21:44,420 --> 00:21:48,850 So you just can't really do very effectively a, a best neighbor. 429 00:21:48,850 --> 00:21:52,110 you know, a, you know a best neighbor exploration. 430 00:21:52,110 --> 00:21:55,099 Because that would take a lot of time, and the benefits are not really very 431 00:21:55,099 --> 00:21:58,559 clear at that point, okay? So what you can do instead is just select 432 00:21:58,559 --> 00:22:01,750 one of these move randomly, see if it improve your schedule. 433 00:22:01,750 --> 00:22:04,571 If it does, yes, you take it. If it doesn't, you just say in the same 434 00:22:04,571 --> 00:22:08,120 state, pick another one, and so on. Okay, so the best research that I've 435 00:22:08,120 --> 00:22:11,882 shown you, we talked about it earlier, you know the, the, the TTP, the traveling 436 00:22:11,882 --> 00:22:16,480 time on problem, were based essentially on a random log. 437 00:22:16,480 --> 00:22:19,394 And I will tell you also what is the metaheuristic and what is a heuristic to 438 00:22:19,394 --> 00:22:24,580 decide whether we accept a move or not. But it was basically using completely 439 00:22:24,580 --> 00:22:29,530 random move at every iterations of the search, okay? 440 00:22:29,530 --> 00:22:31,452 So this is essentially the highlight of the presentation I want to give you 441 00:22:31,452 --> 00:22:33,498 today, so we saw essentially the generate search, and how you can parametize it 442 00:22:33,498 --> 00:22:36,487 with heuristic and metaheuristic. But I haven't shown you the metaheuristic 443 00:22:36,487 --> 00:22:37,823 yet. And that's what we're going to talk about 444 00:22:37,823 --> 00:22:39,964 next time. But I haven't shown you the metaheuristic 445 00:22:39,964 --> 00:22:41,974 yet. And that's what we're going to talk about 446 00:22:41,974 --> 00:22:43,360 next time. Okay? 447 00:22:43,360 --> 00:22:44,460 See you next time. Thank you.