So, that's kind of just the motivation for the
simulating the Annealing Algorithm, but there's an actual algorithm and
it's, it's remarkably simple and remarkably effective. So, the algorithm
goes like this, for, we're just going to repeat for some
finite set of iterations. We're going to be at some
point x, and we're going to sample a new point
x of t, from the neighborhood of x. And then
what are we going to do? Well, we're going to move
our x to that x t, probabilistically. So
in particular, we've got this probability function pxxtt, which
is going to help us decide whether or not
to actually make the move. And it's, and, and
the form of that function is written out
here. So, the probability that if we're currently at
x, and we're thinking about moving to x sub
t, little t, and the current temperature is capital
T, then what's going to happen? If the fitness of the new
point is bigger than or equal to the old point, we're
just going to make the move. Right? So we always hill climb
when we are at a point where we can do that.
>> So that's just rigorall hill climbing.
>> It's kind of like hill climbing, exactly. It's a little different from
the hill climbing the way we described it, where we said let's
visit all the points in the neighborhood. This is kind of a
useful thing to be able to do when the neighborhood's really large,
just choose anything in the neighborhood, and if
it's an improvement, you know, go for it.
>> Okay.
>> But, what if it's not an improvement? Well
if it's not an improvement, what we're going to do is
we're going to look at the fitness difference between the point
that we're evaluating, and the point where we are now.
Look at the difference between those two, divide that by
the temperature, take E to that, and interpret that as
a probability. And we either make the move or not
with that probability. So, alright, so let's, we've gotta dive
in a little bit to this expression to make some sense out of
it. So, what happens, Charles, if the point that we currently visited x,
then we visit a neighbor point X T, what if their fitnesses are
really close to each other, say you
know, just Infinitimally close to each other.
>> Well, if they're infinitesimally close to one another, then
that means that difference is going to be very close to 0.
>> Right, and so we get
0 over doesn't matter what the temperature is, we get 0. E to the 0 is 1,
so we make the move if it's you
know, infinitesimally smaller than, than where we are now.
>> Mm-hm. Alright, what if it's a, what if it's a big step down?
>> Well, then, that means that number's really, really, negative.
>> Yes.
>> And the negative divided by some positive number T is
the temperature, so T's always greater than or equal to 0.
[BLANK_AUDIO]
>> Yeah, let's say that.
>> Okay.
>> In fact, probably making it equal to 0 could run
us into trouble. So let's just say that it's bigger this year.
>> So it's Kelvin. So it's in Kelvin. Okay, so
>> [LAUGH]. we, that'd be a really, really big
negative number, and E to a really big negative
number is 1 over E to a really big number. So that makes it very close to 0.
>> Good, right. So, in other words, if
a giant step down, we probably won't take it.
>> Right, okay, that makes sense, so you're sort
of smoothly going in directions that kind of look bad as a function of how
bad they look, and sort of exaggerating
that difference through an exponential function. [LAUGH] Right?
>> [LAUGH] Sure. If, if that, if that gets you going.
>> Well so 3 isn't 3 times worse than 1.
It's you know, 2 to the 3 times worse than 1.
>> I see, or E to the. Well so, so good, but let's, let's look
at one more thing with this equation here. let's,
let's say that there's You know, a moderate step down.
>> Mm-hm. So, it's not so huge that when we divide it by T, it's essentially
negative infinity. Let's just say it's a smaller
thing, you know, - 5 or something like that.
>> Okay.
>> Then what, what happens? Now we get some E
to the that is going to be some probability between 0
and 1. What does the T, what does T do?
In this case. What if T is something really big?
What if, what if, what if T is something really small?
>> Well, T is something really big. Let's say, infinity then,
it doesn't matter what the difference is. It's effectively going to be 0.
>> Right, so really big temperature here means that we're going to have some
negative thing divided by something else. This
is going to be, essentially 0. It's going to
be E to the 0, so it's going to be 1. So, when the temperature's
really high, we're actually willing to take
downward steps. So, we don't even sort
of notice that it's going down.
>> Right.
>> There's lots of randomness happening.
>> Right. So, in fact, if key is infinity, it's really, really, really,
really hot then even if the neighbor, is much, much worse off. He'll
be less worse off than, infinity, and so, basically you're always just going to
jump to the next person. To the next neighbor. To the next point.
>> Right. So we're very likely to accept.
So the, so it's going to move freely. If
T is really small, as T approaches 0
what happens? Well let's just take the extreme
case. So T was 0 or effectively 0,
then that means any difference whatsoever basically becomes infinity.
>> Right, it gets magnified by this very, very small T.
>> Right. And so then it's not going to take
any downwards steps. It's only going to go uphill. Yeah, so
that's kind of the essence of the Similarity Annealing Algorithm,
so maybe we can talk about some of its properties.
>> OK.