1
00:00:00,190 --> 00:00:02,222
Okay. 
Discrete Optimization, meta-heuristics. 

2
00:00:02,222 --> 00:00:04,282
So that's what we're going to talk about 
today. 

3
00:00:04,282 --> 00:00:07,653
So, we are still in local search. 
We have seen the heuristics last time. 

4
00:00:07,653 --> 00:00:10,170
What we're going to talk about today is 
meta-heuristic. 

5
00:00:10,170 --> 00:00:12,488
I want to talk about all of them, I just 
want to give you a flavor of what you can 

6
00:00:12,488 --> 00:00:15,704
do. 
And so I will talk about three of them. 

7
00:00:15,704 --> 00:00:18,520
Iterated local search, simulated 
annealing, and tabu search today. 

8
00:00:18,520 --> 00:00:20,889
Okay? 
So the goal here, you know, heuristic is 

9
00:00:20,889 --> 00:00:24,650
trying to, you know, drive you towards 
local minimum. 

10
00:00:24,650 --> 00:00:27,271
Okay. 
What the meta-heuristic is going to try 

11
00:00:27,271 --> 00:00:32,080
to do is to avoid you to be stuck in a 
pool local minimum like this one. 

12
00:00:32,080 --> 00:00:34,550
You want to go there, right? 
So, but you may be stuck here. 

13
00:00:34,550 --> 00:00:37,976
How can you escape that local minima. 
And such a way that you can still 

14
00:00:37,976 --> 00:00:40,950
actually go to a high quality solution. 
So you have this trade off. 

15
00:00:40,950 --> 00:00:42,265
Right? 
So you want to be able to go up, you 

16
00:00:42,265 --> 00:00:45,210
know, because, otherwise, you're stuck 
into this local minima. 

17
00:00:45,210 --> 00:00:49,290
But you also don't want to go too way far 
up and you never go down anymore. 

18
00:00:49,290 --> 00:00:51,312
Okay. 
So you have to find this reasonable trade 

19
00:00:51,312 --> 00:00:54,545
off in the ability to go up outside the 
local minina but at the same time you 

20
00:00:54,545 --> 00:00:57,831
have the ability to sometime dive in and 
actually get to a very high quality 

21
00:00:57,831 --> 00:01:01,200
solution. 
Okay? 

22
00:01:01,200 --> 00:01:02,900
So, that is the trade off that we need to 
explore. 

23
00:01:02,900 --> 00:01:05,255
Okay? 
So, iterate local, iterated local search 

24
00:01:05,255 --> 00:01:08,500
is a very, very simple way of trying to 
achieve that. 

25
00:01:08,500 --> 00:01:10,648
Okay? 
So, you start from the point [INAUDIBLE]. 

26
00:01:10,648 --> 00:01:13,960
You dived on to the, you know, to the 
local, to a local minimum. 

27
00:01:13,960 --> 00:01:16,064
Okay? 
Then you start from another place and you 

28
00:01:16,064 --> 00:01:17,300
dived on again. 
Okay? 

29
00:01:17,300 --> 00:01:20,180
So, you generate another point and you 
start and you try to go down and then you 

30
00:01:20,180 --> 00:01:21,890
keep doing that. 
Okay? 

31
00:01:21,890 --> 00:01:24,350
So, you start to have another point there 
and you just go down. 

32
00:01:24,350 --> 00:01:26,148
Okay? 
And so, you do that for many, many, many 

33
00:01:26,148 --> 00:01:29,272
different [INAUDIBLE] starting points and 
then at the end, you essentially take the 

34
00:01:29,272 --> 00:01:32,757
best, you know, the best solutions that 
you have found. 

35
00:01:32,757 --> 00:01:34,960
Okay? 
So that's the key idea of iterated local 

36
00:01:34,960 --> 00:01:38,185
search, okay? 
So, so basically you execute multiple 

37
00:01:38,185 --> 00:01:42,070
local search from different starting 
configurations, okay? 

38
00:01:42,070 --> 00:01:45,244
It's generic in the sense that it can be 
combined with many other meta-heuristics, 

39
00:01:45,244 --> 00:01:49,735
that I'm going to ah,show you later on. 
And it's often called multistarts search 

40
00:01:49,735 --> 00:01:52,350
or search with restarts and so on. 
Okay? 

41
00:01:52,350 --> 00:01:55,388
But the key idea is that you have a local 
search and you iterate it many, many 

42
00:01:55,388 --> 00:01:57,315
times. 
Okay? 

43
00:01:57,315 --> 00:02:00,695
And so, this is essentially the, you 
know, the pseudocode for for this, for 

44
00:02:00,695 --> 00:02:05,260
this particular iterated local search. 
So you generate an initial solution. 

45
00:02:05,260 --> 00:02:06,977
Okay? 
And then, essentia-, and this is the best 

46
00:02:06,977 --> 00:02:09,606
solution you have so far. 
And then you iterate a number of 

47
00:02:09,606 --> 00:02:10,830
searches. 
Okay? 

48
00:02:10,830 --> 00:02:13,300
And every one of these searches is one of 
the local search that I've shown you in 

49
00:02:13,300 --> 00:02:15,640
the previous lec-, in the previous 
lecture. 

50
00:02:15,640 --> 00:02:17,654
Right? 
And then at the end of the day, this will 

51
00:02:17,654 --> 00:02:20,820
give you the best configuration that this 
local search has found. 

52
00:02:20,820 --> 00:02:23,690
If it's better than the best solution so 
far, you keep it. 

53
00:02:23,690 --> 00:02:25,270
Okay? 
Otherwise, you just ignore it. 

54
00:02:25,270 --> 00:02:27,242
Okay? 
And then you generate a new solution and 

55
00:02:27,242 --> 00:02:29,314
you redo another stuff. 
Okay? 

56
00:02:29,314 --> 00:02:33,920
You, you you, you, you re-, you research 
again from that you starting point. 

57
00:02:33,920 --> 00:02:37,259
Now, that starting point can be 
completely, completely generated, you 

58
00:02:37,259 --> 00:02:41,343
know, randomly or it can use a solution 
that you've found so far. 

59
00:02:41,343 --> 00:02:43,152
Okay? 
And there are techniques, like, power 

60
00:02:43,152 --> 00:02:45,420
linking which are sophisticated ways to 
do this. 

61
00:02:45,420 --> 00:02:48,272
But the basic idea here is that you do 
whatever you want but you have to have a 

62
00:02:48,272 --> 00:02:52,596
new starting point, which you believe, 
you know, is going to be interesting. 

63
00:02:52,596 --> 00:02:54,030
Okay? 
It can be completely random or it can be 

64
00:02:54,030 --> 00:02:56,700
[UNKNOWN] some of the solutions that we 
have seen so far. 

65
00:02:56,700 --> 00:02:59,270
All the current solutions that you have. 
Okay? 

66
00:02:59,270 --> 00:03:02,112
Now, let, so, so as I said, this 
technique can be most of the, most of the 

67
00:03:02,112 --> 00:03:05,199
algorithms these days in local search or 
in other, you know, even when you do 

68
00:03:05,199 --> 00:03:08,237
branch and bound or other, other 
searches, are using some form of restarts 

69
00:03:08,237 --> 00:03:13,320
for actually improving the, the quality 
of the solutions. 

70
00:03:13,320 --> 00:03:15,464
Okay? 
So what I'm going to do now is look at 

71
00:03:15,464 --> 00:03:20,130
heuristics that are most speci-, 
meta-heuristics that are most specific. 

72
00:03:20,130 --> 00:03:22,392
And so, I'm going to start here, you 
know, I'm going to talk about simulated 

73
00:03:22,392 --> 00:03:24,300
annealing. 
But I'm going to start with the 

74
00:03:24,300 --> 00:03:26,862
metropolis heuristic, which is a 
heuristic on which you build simulated 

75
00:03:26,862 --> 00:03:28,160
annealing. 
Okay? 

76
00:03:28,160 --> 00:03:31,930
And the basic idea here is, is, is, is 
the following. 

77
00:03:31,930 --> 00:03:34,576
So you want to accept the move of use if 
it improves the value of the objective 

78
00:03:34,576 --> 00:03:38,180
function. 
But, otherwise, you want also to impr, 

79
00:03:38,180 --> 00:03:42,535
you know, accept move that degrades the, 
the value of the objective function but 

80
00:03:42,535 --> 00:03:47,152
with some probability. 
And that probability has to be somewhat 

81
00:03:47,152 --> 00:03:50,980
proportional to the degradation that the 
move is going to perform. 

82
00:03:50,980 --> 00:03:54,040
If the move is terribly bad, you probably 
don't want to take it with a high 

83
00:03:54,040 --> 00:03:57,196
probability. 
If it's really, really close, you know, 

84
00:03:57,196 --> 00:04:01,550
to improving, you, you know, you want to 
take it with the higher probability. 

85
00:04:01,550 --> 00:04:02,891
Okay? 
So the whole thing here that I am 

86
00:04:02,891 --> 00:04:05,514
going to talk about is inspired by 
results in statistical physics and I will 

87
00:04:05,514 --> 00:04:09,381
come back to that later on, okay? 
So this is essentially the way you're 

88
00:04:09,381 --> 00:04:11,530
going to do. 
The probability is chosen between two 

89
00:04:11,530 --> 00:04:13,582
things. 
A temperature, you can ignore it right 

90
00:04:13,582 --> 00:04:15,704
now. 
So we'll talk little bit after, about it, 

91
00:04:15,704 --> 00:04:18,004
afterwards. 
And the essentially the key aspect is the 

92
00:04:18,004 --> 00:04:20,902
delta, the difference between the value 
of the objective function of the neighbor 

93
00:04:20,902 --> 00:04:24,360
and the current value of the objective 
function. 

94
00:04:24,360 --> 00:04:26,468
Now, of course, if this difference is 
negative, that means that the move is 

95
00:04:26,468 --> 00:04:28,490
improving. 
And, therefore, you take the move all the 

96
00:04:28,490 --> 00:04:29,360
time. 
Okay? 

97
00:04:29,360 --> 00:04:32,805
But if the value is positive, okay? 
So that means that the move is degrading 

98
00:04:32,805 --> 00:04:35,460
and you have to choose the, the 
probability of accepting that move, you 

99
00:04:35,460 --> 00:04:39,375
know, carefully. 
And the probability, it is too high. 

100
00:04:39,375 --> 00:04:41,951
You only, you, you're only going to go up 
and you will accept, you know, 

101
00:04:41,951 --> 00:04:44,870
essentially, moves around degrading all 
the time. 

102
00:04:44,870 --> 00:04:47,870
So you want this balance between 
improving and then sometime jumping up 

103
00:04:47,870 --> 00:04:51,014
and moving up, okay? 
And that's what we are trying to do with 

104
00:04:51,014 --> 00:04:54,385
this probability distribution. 
Essentially, you want to take the move or 

105
00:04:54,385 --> 00:04:57,880
probability, which is exponential in the 
basically minus the delta. 

106
00:04:57,880 --> 00:05:00,197
Okay? 
So, so remember, when the delta is 

107
00:05:00,197 --> 00:05:04,100
positive that means that we are 
degrading, okay? 

108
00:05:04,100 --> 00:05:07,180
So this value, minus delta is going to be 
negative in that point, okay? 

109
00:05:07,180 --> 00:05:09,722
So, so look at this formula and then 
there are two things that, so this is the 

110
00:05:09,722 --> 00:05:12,157
algorithm. 
And we'll look at the formula and, and 

111
00:05:12,157 --> 00:05:15,618
actually analyze it in a moment, okay? 
So, but essentially, what you do here, 

112
00:05:15,618 --> 00:05:18,700
you always combine this with a random 
selection of the neighbor, okay. 

113
00:05:18,700 --> 00:05:21,365
So you, basically, take a neighbor in the 
neighborhood with a you know, random 

114
00:05:21,365 --> 00:05:24,080
probability. 
So you get this beautiful neighbor, okay? 

115
00:05:24,080 --> 00:05:27,370
And then, if you see if it improves, you 
take the, you take the neighbor. 

116
00:05:27,370 --> 00:05:29,970
But, otherwise, if it degrades the value 
of the objective function, you flip a 

117
00:05:29,970 --> 00:05:32,570
coin and, you know, with, you know, and 
decide with, you know, along, you know, 

118
00:05:32,570 --> 00:05:36,630
with this probability distribution, if 
you except the move or not. 

119
00:05:36,630 --> 00:05:38,387
Okay? 
And if you ac-, you know, if, if, if you, 

120
00:05:38,387 --> 00:05:41,377
if you're lucky, you know, if the prob-, 
you know, coin turns well, you take the 

121
00:05:41,377 --> 00:05:44,181
move. 
Otherwise, you just ignore the more, 

122
00:05:44,181 --> 00:05:46,047
okay? 
And you stay where you are. 

123
00:05:46,047 --> 00:05:47,400
Okay? 
And so you iterate this. 

124
00:05:47,400 --> 00:05:49,700
You know, select another randomly, flip a 
coin. 

125
00:05:49,700 --> 00:05:52,970
Decide if you take it or not and continue 
the way it is. 

126
00:05:52,970 --> 00:05:54,230
Okay? 
Now lets look at this probability. 

127
00:05:54,230 --> 00:05:56,758
So, if we have a very large delta. 
Okay? 

128
00:05:56,758 --> 00:05:59,500
So look at this delta. 
Assume that it's very large. 

129
00:05:59,500 --> 00:06:01,970
What's going to happen with this 
probability? 

130
00:06:01,970 --> 00:06:03,840
Okay, the probability distribution that 
you see there. 

131
00:06:03,840 --> 00:06:08,510
Well this number here is going to be, is 
going to be very negative. 

132
00:06:08,510 --> 00:06:11,050
So the probability is going to be very 
small. 

133
00:06:11,050 --> 00:06:14,100
So if you have a big difference between 
the current value of the objective 

134
00:06:14,100 --> 00:06:17,000
function and the value of the neighbor's 
where you want to move to, the 

135
00:06:17,000 --> 00:06:21,090
probability of actually accepting is 
going to be tiny. 

136
00:06:21,090 --> 00:06:22,820
Okay? 
So you don't want to take really, really 

137
00:06:22,820 --> 00:06:24,420
bad move. 
Although you could, right? 

138
00:06:24,420 --> 00:06:27,531
There is always a small probability that 
you are going to, you're going to take 

139
00:06:27,531 --> 00:06:30,220
it, okay? 
Now, let's look at this probability now, 

140
00:06:30,220 --> 00:06:34,097
and this, this temperature now. 
Okay, so this, this temperature is very 

141
00:06:34,097 --> 00:06:36,326
large. 
What's going to happen? 

142
00:06:36,326 --> 00:06:38,084
Okay? 
So if the temperature is very large, that 

143
00:06:38,084 --> 00:06:41,598
value is going to be what? 
It's going to be, it's going to be 

144
00:06:41,598 --> 00:06:45,380
essentially tiny. 
And, therefore, you will accept the 

145
00:06:45,380 --> 00:06:49,100
probability of accepting the move is 
going to be very, very high. 

146
00:06:49,100 --> 00:06:51,180
Okay? 
So, essentially, if you have a large 

147
00:06:51,180 --> 00:06:53,950
temperature, you're going to accept many, 
many, many, many moves. 

148
00:06:53,950 --> 00:06:57,650
So, which basically means that you are 
basically performing a random walk. 

149
00:06:57,650 --> 00:06:59,500
So you are walking, walking, looking 
around. 

150
00:06:59,500 --> 00:07:00,912
Ooh, is this good? 
Is this good or not? 

151
00:07:00,912 --> 00:07:02,880
And then, and then you're looking around 
essentially. 

152
00:07:02,880 --> 00:07:05,896
But you accept move, that can be really 
bad, degrading you of function 

153
00:07:05,896 --> 00:07:07,570
tremendously. 
Okay? 

154
00:07:07,570 --> 00:07:10,800
So in a sense, if you have a very large t 
here, okay? 

155
00:07:10,800 --> 00:07:13,740
So what's going to happen is that you are 
going to have a really, a random walk, 

156
00:07:13,740 --> 00:07:16,290
okay? 
If you have a small t, the opposite is 

157
00:07:16,290 --> 00:07:19,720
going to happen. 
If you have a tiny, tiny, tiny t, like 

158
00:07:19,720 --> 00:07:23,250
0.00001, okay? 
So that value here is going to be really 

159
00:07:23,250 --> 00:07:25,710
negative. 
And, therefore, you're only going to 

160
00:07:25,710 --> 00:07:29,110
consider, very, very, you're going to 
accept the move we've, we've on degrading 

161
00:07:29,110 --> 00:07:32,380
move. 
Very, very, very low probability. 

162
00:07:32,380 --> 00:07:35,247
Which basically means that in this 
particular case, you are kind of being 

163
00:07:35,247 --> 00:07:38,070
greedy, right? 
So now what you have to think about is 

164
00:07:38,070 --> 00:07:40,612
you have this temperature, you have also 
this difference in the objective 

165
00:07:40,612 --> 00:07:43,340
function. 
And, of course, that's basically specific 

166
00:07:43,340 --> 00:07:46,791
to the particular problem that you have. 
And you have to kind of balance these two 

167
00:07:46,791 --> 00:07:49,752
so that you get a compromise between 
accepting degrading move and, then, at 

168
00:07:49,752 --> 00:07:54,060
some point, being greedy enough to 
actually get to a local minima. 

169
00:07:54,060 --> 00:07:55,673
Okay? 
And so you have to balance these two 

170
00:07:55,673 --> 00:07:56,880
things. 
Okay? 

171
00:07:56,880 --> 00:08:00,282
So what the simulated annealing algorithm 
is really trying to do is to try to 

172
00:08:00,282 --> 00:08:03,470
achieve this balance in a dynamic 
fashion. 

173
00:08:03,470 --> 00:08:05,849
Okay? 
So it's based on material physics where 

174
00:08:05,849 --> 00:08:09,881
you try to, essentially, heat and then 
cool, you know, the materials, is that 

175
00:08:09,881 --> 00:08:15,540
you, you know, generate beautiful 
crystals with almost no defects. 

176
00:08:15,540 --> 00:08:17,052
Okay? 
And so, what you do is essentially here 

177
00:08:17,052 --> 00:08:19,635
the key idea is that you start with a 
very high temperature, which means that 

178
00:08:19,635 --> 00:08:22,660
you are essentially performing this 
random move. 

179
00:08:22,660 --> 00:08:25,114
Moving along, looking hm, is this 
[INAUDIBLE] look here, is this 

180
00:08:25,114 --> 00:08:29,118
[INAUDIBLE] look there and so on. 
Looking around and then progressively you 

181
00:08:29,118 --> 00:08:33,900
are going to cool this temperature. 
And then becoming more and more greedy. 

182
00:08:33,900 --> 00:08:35,638
Okay? 
So in a sense you start with a high 

183
00:08:35,638 --> 00:08:39,148
temperature which is like a random walk 
and then more and more you are making it 

184
00:08:39,148 --> 00:08:41,940
more and more greedy. 
Okay? 

185
00:08:41,940 --> 00:08:45,255
And so when the temperature is really, 
really low you are basically doing a 

186
00:08:45,255 --> 00:08:47,610
local improvement search. 
Okay? 

187
00:08:47,610 --> 00:08:50,665
So essentially, the key here is that you 
start with a reasonable temperature, 

188
00:08:50,665 --> 00:08:53,673
you're looking around and then, you 
decrease it, such that, at some point it, 

189
00:08:53,673 --> 00:08:58,430
you know, it becomes greedy and you focus 
to a local minima. 

190
00:08:58,430 --> 00:09:01,310
So in a sense, you bounce inside the 
search space everywhere. 

191
00:09:01,310 --> 00:09:04,421
And when you think that you have a very 
good you know, neighborhood in that 

192
00:09:04,421 --> 00:09:07,634
particular search you know, in that 
particular space, you dive down and try 

193
00:09:07,634 --> 00:09:12,170
to get this good local minimum, that 
minimum that you want. 

194
00:09:12,170 --> 00:09:13,928
Okay? 
So this is the description of the search 

195
00:09:13,928 --> 00:09:17,152
procedure in a more formal way. 
So what you see is that once again is 

196
00:09:17,152 --> 00:09:21,730
basically a set of of searches and 
everyone of these search is going to use. 

197
00:09:21,730 --> 00:09:25,080
the, the metropolis algorithm is a lot of 
search with the metropolis algorithm. 

198
00:09:25,080 --> 00:09:27,400
You are at a particular temperature and 
then you bounce around. 

199
00:09:27,400 --> 00:09:30,235
You look, you look around and you try to 
find you know, you move from you know, 

200
00:09:30,235 --> 00:09:33,155
state to state, configuration to 
configuration. 

201
00:09:33,155 --> 00:09:35,440
Okay? 
So that will, you know, at the end of 

202
00:09:35,440 --> 00:09:39,190
this particular search you will get a 
particular objective value. 

203
00:09:39,190 --> 00:09:41,700
If it's better than the best solution 
you've found so far, you keep it. 

204
00:09:41,700 --> 00:09:44,560
And then, what you do is you decrease 
this temperature and then you iterate the 

205
00:09:44,560 --> 00:09:46,150
process. 
Okay? 

206
00:09:46,150 --> 00:09:49,064
And the point is that at some point, the 
temperature is going to be so low, that 

207
00:09:49,064 --> 00:09:51,884
the only thing that will is accepting, 
you know, moves that are, that are 

208
00:09:51,884 --> 00:09:55,623
improving. 
And you, basically, convert to something 

209
00:09:55,623 --> 00:09:57,707
which is a local improvement. 
Okay? 

210
00:09:57,707 --> 00:10:00,930
So this is basic idea with the simulated 
annealing. 

211
00:10:00,930 --> 00:10:04,002
So, what kind of random search will the 
particular probability of accepting 

212
00:10:04,002 --> 00:10:07,266
degrading move the beginning, the first 
searches that you are looking at, you 

213
00:10:07,266 --> 00:10:12,200
essentially accept everything. 
You are really, you know, looking around. 

214
00:10:12,200 --> 00:10:15,400
And then as, as time goes on, you are 
[UNKNOWN] becoming more and more and more 

215
00:10:15,400 --> 00:10:19,345
greedy until you really converge to a 
local improvement search. 

216
00:10:19,345 --> 00:10:22,080
Okay? 
So now this, this simulated annealing you 

217
00:10:22,080 --> 00:10:25,296
know, came from, you know, physicists and 
it, it has a very interesting property 

218
00:10:25,296 --> 00:10:29,120
actually is that if your neighborhood is 
connected, okay? 

219
00:10:29,120 --> 00:10:31,690
So you are guaranteed to converge to the 
global optimum. 

220
00:10:31,690 --> 00:10:33,193
Okay? 
So you only need this, this, this 

221
00:10:33,193 --> 00:10:37,051
connected neighborhood, you know property 
that I mentioned before. 

222
00:10:37,051 --> 00:10:40,040
And if this is the case, if you have a 
very, very slow schedule, then you are 

223
00:10:40,040 --> 00:10:43,323
guaranteed, you know, in the expected 
sense to actually converge to the optimal 

224
00:10:43,323 --> 00:10:45,600
solution. 
Okay? 

225
00:10:45,600 --> 00:10:48,687
The real, the only real issue is that 
this is actually slower than excess/g, 

226
00:10:48,687 --> 00:10:51,660
exhaustive search. 
So, if you actually use this really, 

227
00:10:51,660 --> 00:10:55,610
really slow schedule, it's going to take 
a long time to get to this optimal value. 

228
00:10:55,610 --> 00:10:57,781
Okay? 
So, but in practice, in a sense, you will 

229
00:10:57,781 --> 00:11:00,742
never use this kind of really, really 
slow schedule, where you decrease the 

230
00:11:00,742 --> 00:11:04,340
temperature so slow that it's become 
boring, right? 

231
00:11:04,340 --> 00:11:08,025
So what you are basically doing is that 
you're temperature cooling which is, 

232
00:11:08,025 --> 00:11:11,710
which is much faster, okay? 
So let's say linear or geometric 

233
00:11:11,710 --> 00:11:15,075
progressions or something like this. 
And once you do that, you can have 

234
00:11:15,075 --> 00:11:17,910
really, really amazing bench, you know, 
results, on some very complicated 

235
00:11:17,910 --> 00:11:20,910
applications or benchmarks. 
So the [INAUDIBLE], you know? 

236
00:11:20,910 --> 00:11:23,946
The, the, the, the, the traveling term 
and problem, for instance has, you know, 

237
00:11:23,946 --> 00:11:27,460
the best, the best solutions for the, for 
some of the larger. 

238
00:11:27,460 --> 00:11:29,917
Initial instances has been found using 
simulated annealing on the complex 

239
00:11:29,917 --> 00:11:32,540
neighborhood that I've shown you before. 
Okay? 

240
00:11:32,540 --> 00:11:36,280
Same thing for some of your, you know 
some complex problems in [UNKNOWN] in, in 

241
00:11:36,280 --> 00:11:40,780
scheduling, where you try to minimize 
tardiness of various tasks. 

242
00:11:40,780 --> 00:11:42,546
Okay? 
So the basic idea here is that in 

243
00:11:42,546 --> 00:11:45,582
practice, obviously, you don't use that 
slow schedule but you use the schedule 

244
00:11:45,582 --> 00:11:49,225
which is reasonably fast. 
But still, the ability at the beginning 

245
00:11:49,225 --> 00:11:51,835
to explore the search you know, to 
looking around and seeing where you 

246
00:11:51,835 --> 00:11:55,143
should search. 
And then, you know, progressively 

247
00:11:55,143 --> 00:11:58,919
narrowing down the search towards the 
local improvement is actually pretty 

248
00:11:58,919 --> 00:12:01,790
effective, okay? 
So that's the key idea. 

249
00:12:01,790 --> 00:12:04,342
Now, in practice you can add a variety of 
techniques. 

250
00:12:04,342 --> 00:12:07,270
And so in, in some of the case that's 
what, you know, has been done on the TTP 

251
00:12:07,270 --> 00:12:10,470
and other problems. 
You can always have restart. 

252
00:12:10,470 --> 00:12:12,330
You can always start from multiple 
points. 

253
00:12:12,330 --> 00:12:13,924
Okay? 
You can also do something which is called 

254
00:12:13,924 --> 00:12:16,023
a reheat. 
If you're going too fast, you say ooh, 

255
00:12:16,023 --> 00:12:19,116
ooh, ooh, I'm going way too fast. 
Now let's step back and, you know, 

256
00:12:19,116 --> 00:12:22,260
increase the temperature again. 
Look around, you know, and then dive 

257
00:12:22,260 --> 00:12:23,640
again. 
Okay? 

258
00:12:23,640 --> 00:12:26,492
And there are also many properties of, 
of, of, of tabu search that I'm going to 

259
00:12:26,492 --> 00:12:29,574
talk in a mom, about in a moment that you 
could actually incorporate in simulated 

260
00:12:29,574 --> 00:12:32,760
annealing algorithm. 
So this is. 

261
00:12:32,760 --> 00:12:34,630
So, once again, you know? 
This is an introduction. 

262
00:12:34,630 --> 00:12:36,854
I'm giving you the basics. 
But there are many other techniques that 

263
00:12:36,854 --> 00:12:40,270
you can actually use, okay? 
so I talked about this already. 

264
00:12:40,270 --> 00:12:42,296
So we can, you know? 
Like in most restarts, you can always 

265
00:12:42,296 --> 00:12:45,060
start from multiple points. 
It's very useful for the TTP as well. 

266
00:12:45,060 --> 00:12:49,092
And then you can also increase the 
temperature if you want to at some point. 

267
00:12:49,092 --> 00:12:51,752
Okay? 
Now, let me talk about Tabu search now, 

268
00:12:51,752 --> 00:12:56,127
which is the, the last meta-heuristic 
that I want to talk about today. 

269
00:12:56,127 --> 00:12:58,873
And so, so I'm going to first give you 
the intuition. 

270
00:12:58,873 --> 00:13:02,137
And, and most of the presentation in this 
lecture is going to a high level on tabu 

271
00:13:02,137 --> 00:13:06,624
search and the next lecture is going to 
focus on tabu searh exclusively. 

272
00:13:06,624 --> 00:13:09,154
But, this is the idea. 
This is what we really want to do in 

273
00:13:09,154 --> 00:13:11,860
practice, right? 
So, you start with a node and you dive 

274
00:13:11,860 --> 00:13:14,309
down. 
You get to this beautiful local minima 

275
00:13:14,309 --> 00:13:18,358
but you, you know, it's a local minima. 
So what you want to do is to say, oh, can 

276
00:13:18,358 --> 00:13:21,630
I step up now and try to find something 
which is better? 

277
00:13:21,630 --> 00:13:24,230
So you can, you decide, oh, I want to 
step up over there. 

278
00:13:24,230 --> 00:13:27,640
And then, you go down, you know, again 
and you say, oh, this is a better local 

279
00:13:27,640 --> 00:13:29,602
minima. 
Okay? 

280
00:13:29,602 --> 00:13:31,870
So the problem is that this is actually 
difficult to do. 

281
00:13:31,870 --> 00:13:33,583
Why? 
Because Tabu search is this kind of 

282
00:13:33,583 --> 00:13:36,280
greedy search procedure. 
And typically, when you are at a 

283
00:13:36,280 --> 00:13:39,241
particular place, if you select the best 
neighbor, he's going to be, you know, 

284
00:13:39,241 --> 00:13:43,185
where you are or where you have been. 
So you're going to stay at the same 

285
00:13:43,185 --> 00:13:45,892
position, okay? 
So what you need to do is something that 

286
00:13:45,892 --> 00:13:49,370
essentially, keep track of the nodes that 
you have visited. 

287
00:13:49,370 --> 00:13:52,286
And these nodes are going to be blue. 
Okay, I wanted them to be yellow but 

288
00:13:52,286 --> 00:13:54,970
count on Tony they have to be blue. 
Okay? 

289
00:13:54,970 --> 00:13:58,300
So this is a blue neighbor. 
A blue neighbor is a neighbor which is 

290
00:13:58,300 --> 00:14:02,050
essentially tabu. 
I have seen it already. 

291
00:14:02,050 --> 00:14:04,600
I don't want to go back there. 
Okay. 

292
00:14:04,600 --> 00:14:06,880
Yellow was a better color but anyway. 
Okay. 

293
00:14:06,880 --> 00:14:10,280
So, what we see here we are in this 
particular blue state. 

294
00:14:10,280 --> 00:14:11,790
Okay? 
That means I have been there. 

295
00:14:11,790 --> 00:14:14,030
And now I can move to that particular 
position here. 

296
00:14:14,030 --> 00:14:14,870
Okay? 
So, that's fine. 

297
00:14:14,870 --> 00:14:16,240
Now, look at this thing. 
Okay? 

298
00:14:16,240 --> 00:14:19,180
See, if I had a neighborhood here. 
If I, if I look at the neighborhood here. 

299
00:14:19,180 --> 00:14:20,660
Okay? 
And I use tabu search, where I always 

300
00:14:20,660 --> 00:14:22,780
want to improve in a greedy fashion. 
Right? 

301
00:14:22,780 --> 00:14:24,210
So, I would go back here. 
Right? 

302
00:14:24,210 --> 00:14:26,050
So that's what I would do immediately, 
okay? 

303
00:14:26,050 --> 00:14:28,736
But no, no, no, no no, no. 
I can't do that because this guy now is 

304
00:14:28,736 --> 00:14:31,585
tabu, okay? 
Tabu means, I can't go back there. 

305
00:14:31,585 --> 00:14:33,920
I have visited that node, I want, I can't 
go back. 

306
00:14:33,920 --> 00:14:36,693
So you are kind of forced to move to a 
node which is, which isn't ever, you 

307
00:14:36,693 --> 00:14:40,777
know, as good an objective function. 
And, therefore, you move to this thing 

308
00:14:40,777 --> 00:14:42,990
there, okay? 
And once again, once you are there, you 

309
00:14:42,990 --> 00:14:45,430
know, tabu search is going to say, oh, 
[UNKNOWN] while local improvement is 

310
00:14:45,430 --> 00:14:47,910
going to say, oh, I want to go there, oh, 
I want to go there, that's better, that's 

311
00:14:47,910 --> 00:14:52,350
better, that's where I want to go. 
But of course, these things are tabu, so 

312
00:14:52,350 --> 00:14:55,550
you can go there. 
So this thing is forced to go up there. 

313
00:14:55,550 --> 00:14:57,146
Okay? 
And that's good because now you can go 

314
00:14:57,146 --> 00:15:00,780
down and hopefully find the optimal 
solution in this particular case. 

315
00:15:00,780 --> 00:15:03,235
Okay? 
So this is the abstract idea behind tabu 

316
00:15:03,235 --> 00:15:04,430
search. 
Okay? 

317
00:15:04,430 --> 00:15:07,090
So you maintain something which is called 
the tabu list. 

318
00:15:07,090 --> 00:15:09,352
Think of it, this is all the nodes you 
have visited so far, and you never 

319
00:15:09,352 --> 00:15:11,620
want to go there again, you have been 
there. 

320
00:15:11,620 --> 00:15:12,564
Okay? 
Seen that. 

321
00:15:12,564 --> 00:15:14,840
Okay? 
I know what these nodes are, okay? 

322
00:15:14,840 --> 00:15:17,423
And this is a set, this tabu list is a 
set of tabu nodes, nodes that you've seen 

323
00:15:17,423 --> 00:15:18,902
already. 
Okay? 

324
00:15:18,902 --> 00:15:22,742
So what you do, is, as usual, you start 
from an initial state and then we build a 

325
00:15:22,742 --> 00:15:26,908
sequence, okay? 
Two is a sequence of, of, of nodes that 

326
00:15:26,908 --> 00:15:30,370
we've seen so far, okay. 
That's the tabu list, okay. 

327
00:15:30,370 --> 00:15:32,300
That's all the strings that I have seen, 
okay. 

328
00:15:32,300 --> 00:15:34,771
And then you do a local search, like 
normally, right? 

329
00:15:34,771 --> 00:15:37,807
So if it, it's a number of iterations at 
every iteration, you take, you, you look 

330
00:15:37,807 --> 00:15:40,666
at the, you look at the state that you 
are in. 

331
00:15:40,666 --> 00:15:43,334
And if it proved the best solution so 
far, you take that move and you're 

332
00:15:43,334 --> 00:15:46,360
satisfied that's the best solution you 
found. 

333
00:15:46,360 --> 00:15:49,522
Otherwise, you generate a new neighbor, 
which is essentially which is 

334
00:15:49,522 --> 00:15:52,684
essentially, which select the legal 
moves, and we're going to see what these 

335
00:15:52,684 --> 00:15:56,325
legal moves are. 
But they have to be moved around that 

336
00:15:56,325 --> 00:15:58,910
tabu, right? 
And then in the neighborhood. 

337
00:15:58,910 --> 00:16:01,036
Okay? 
And what you do then afterwards is that 

338
00:16:01,036 --> 00:16:04,798
you increase this two function, and the 
two function is node, another node now, 

339
00:16:04,798 --> 00:16:08,800
another node now that you have visited, 
right? 

340
00:16:08,800 --> 00:16:12,740
So, and that's what this, basically, 
generative framework does, okay? 

341
00:16:12,740 --> 00:16:15,578
And so in, when you do tabu search, the 
only thing that you do is you have to use 

342
00:16:15,578 --> 00:16:20,114
legal move config legal move functions 
that tells you the node cannot be tabu. 

343
00:16:20,114 --> 00:16:21,832
Okay? 
So, in a sense it's the traditional local 

344
00:16:21,832 --> 00:16:25,117
search, but you have to say. 
Oh, I won't select neighbors that are 

345
00:16:25,117 --> 00:16:27,721
tabu, okay? 
And, of course, you've this list, this 

346
00:16:27,721 --> 00:16:30,885
[UNKNOWN] and you can just test if the 
[INAUDIBLE] states that you want to move 

347
00:16:30,885 --> 00:16:33,835
to is, well, you, you want to test if 
the, the le-, is this movie's going to be 

348
00:16:33,835 --> 00:16:37,720
legal if its not tabu. 
Okay? 

349
00:16:37,720 --> 00:16:39,590
And so that's what you see here. 
Okay? 

350
00:16:39,590 --> 00:16:42,710
So basically look inside the tow is the 
move, is inside the tow. 

351
00:16:42,710 --> 00:16:45,260
Okay, so you know that you visited, so 
far, you do not take it. 

352
00:16:45,260 --> 00:16:48,050
So the legal moves are all the moves in 
the neighborhood that are not in tow, 

353
00:16:48,050 --> 00:16:50,881
that are, haven't been visited so far. 
Okay? 

354
00:16:50,881 --> 00:16:55,110
Now, this the kind of crazy behavior that 
you get with tabu search. 

355
00:16:55,110 --> 00:16:58,176
And that's what I love about tabu search. 
It just go up and down [SOUND] like 

356
00:16:58,176 --> 00:16:59,156
crazy. 
Okay? 

357
00:16:59,156 --> 00:17:01,190
So it's very interesting to see what it 
does. 

358
00:17:01,190 --> 00:17:03,339
Okay? 
So this is on a resource allocation 

359
00:17:03,339 --> 00:17:06,463
problem where we are trying to minimize 
the violation. 

360
00:17:06,463 --> 00:17:09,880
So the y axis here are violations and 
these are the iteration of time. 

361
00:17:09,880 --> 00:17:13,312
And, what you see if that are these are, 
this objective function is going up and, 

362
00:17:13,312 --> 00:17:16,526
up and down. 
The, you will get this good trade-off 

363
00:17:16,526 --> 00:17:20,750
trying to escape and then trying to focus 
on trying to find a good solution. 

364
00:17:20,750 --> 00:17:23,566
And in this particular case, you see at 
the end, we find, we find a violation of 

365
00:17:23,566 --> 00:17:27,210
zero, so we find a feasible solution to 
this particular problem. 

366
00:17:27,210 --> 00:17:29,638
Okay? 
And it takes, you know, 160,000 

367
00:17:29,638 --> 00:17:35,046
iterations, 160 1, 1, 6, 160, hundredth 
thousandth iteration. 

368
00:17:35,046 --> 00:17:37,641
Okay? 
So this is zooming about the last set of 

369
00:17:37,641 --> 00:17:41,981
iterations here, and what you can see as 
well is this kind of very, very, you 

370
00:17:41,981 --> 00:17:46,830
know, chaotic behavior of our tabu 
search. 

371
00:17:46,830 --> 00:17:49,770
But in a sense, you go up but you always, 
you know, go down reasonably soon 

372
00:17:49,770 --> 00:17:52,220
afterwards. 
And that's typical behavior of tabu 

373
00:17:52,220 --> 00:17:55,528
search in this particular case. 
This is a graph coloring application 

374
00:17:55,528 --> 00:17:58,408
where you try to minimize the numbers of 
colors this, you know, using 

375
00:17:58,408 --> 00:18:02,754
satisfiability as as a subroutine. 
And once again, you see this behavior, 

376
00:18:02,754 --> 00:18:05,762
kind of chaotic behavior, where you go up 
and down, you go up and down, and so on 

377
00:18:05,762 --> 00:18:07,895
and so forth. 
Okay? 

378
00:18:07,895 --> 00:18:10,490
So, so that's what I wanted to talk about 
today. 

379
00:18:10,490 --> 00:18:13,686
Next lecture I will focus again on tabu 
search and give you all you can actually 

380
00:18:13,686 --> 00:18:18,160
implement this because so far it has been 
at the very abstract level. 

381
00:18:18,160 --> 00:18:21,403
But there are many, many other heurist-, 
meta-heuristics that have been in, in you 

382
00:18:21,403 --> 00:18:24,340
know, implemented in, in, in and 
proposed. 

383
00:18:24,340 --> 00:18:26,600
You know? 
Variable, you know, neighborhood search. 

384
00:18:26,600 --> 00:18:28,780
Guided local search and colony 
optimization. 

385
00:18:28,780 --> 00:18:31,420
Hybrid evolutionary algorithm reactive 
search. 

386
00:18:31,420 --> 00:18:33,320
Scatter search. 
Plenty of others. 

387
00:18:33,320 --> 00:18:35,610
some of my colleagues are going to be 
completely upset with me. 

388
00:18:35,610 --> 00:18:39,460
Because I forgot to include, you know, 
their favorite ones. 

389
00:18:39,460 --> 00:18:42,600
but I did this slide since 5 AM, so, you 
know, bear with me. 

390
00:18:42,600 --> 00:18:45,250
but essentially, there are, you know, 
once again, this is an introduction. 

391
00:18:45,250 --> 00:18:47,778
I gave you some of the principles. 
There are many other ones that you can, 

392
00:18:47,778 --> 00:18:49,613
that you can actually study. 
Okay? 

393
00:18:49,613 --> 00:18:51,890
See you next time for more on tabu 
search.