After making it into the princes's stomach,
Wu kong and Zhuge Liang made it to find the deepest possible entry point into her intestine,
whilst avoiding stepping on the detection lines.
Zhuge Liang summonned the dragon of dimensions for assistance from your professors.
All right.
Wu kong and Zhuge Lian have made their way into the stomach.
But now, they need to find their way into the intestine.
So again, there are alarms,
magical defenses inside Princes Iron Fan.
So, There are untouchable lines.
The same area which they can't enter.
And so, the intestine problem is very similar to the stomach problem.
We're searching for the entrance to the intestine.
We have these constraint this untouchable lines that we
can't use and we are trying to find the global minima.
That's where the entrance to the intestine is,
in a complex and non complex landscape.
So, if we look at the stomach, landscape,
it's very complicated but more rocky than
the esophagus and non-convex with many local minima.
So, we look from above.
Again, we see obvious local minima.
Things like this, the darker it is, the lower it is.
All right, there's something interesting and different about the stomach
is that Princes Iron Fan just had a meal.
So, the stomach is it's quite hot.
It's processing food, but that will reduce over time.
So, there'll be less and less heat in the stomach as the meal is processed.
But this is going to give us energy which we're going
to be able to use to do a new kind of search.
So, in stochastic search,
we've seen where we basically have to try to escape these local minima.
Now, what we're going to do is make use of that heat energy in
the stomach to occasionally allow us to do uphill moves.
So you can see, if we start here we go down into this local minima, we can't escape.
Unless we can do some uphill moves and we can get in there and
maybe find a better local or global minima.
So, having this heat energy is going to allow Zhuge Liang and his son Wu kong to
move upwards in the landscape on occasions. All right.
And this is simulated annealing.
It's possibly the most common form of stochastic search.
It's very simple. We try a move, if it improves.
So, if we're going downhill,
then we just take the move.
Otherwise, with some probability,
we'll take a move even if it's uphill.
And that's going to allow us to escape from local minima.
And it's based, and the name is based on this physical process of annealing.
So, when you slowly cool a metal,
so the crystalline structure is as regular as possible.
That's what's happening to the atoms in that metal.
It will eventually find a minimal energy state.
And atoms move around trying to find the best thing but occasionally,
they move into high energy positions using the heat of the annealing process.
All right, so simulated annealing as an algorithm looks like this.
So, we are going to start with our initial valuation.
So, just our normal local search,
we'll find the neighborhood of the current position.
We'll choose a single neighbor.
Then we'll work out this delta as in how good this neighbor is
compared to the one where current position we are now f(d).
And since we're doing minimization,
if this delta is negative,
we're just going, for sure, to do the move.
Otherwise, we have the new part.
We're going to basically get a random number between zero and one,
and compare it with this expression here,
which is dependent on the temperature.
So, this is our threshold for making an uphill move.
And you can see, it has some constant here,
it has the current temperature, and it also takes into account the delta.
So, if we're going to move uphill,
if we aren't moving a little bit uphill,
there'll be more chance that we can do it.
If we try to move a lot uphill,
there'll be less chance that we can do it. So, this is our threshold.
So, the other important thing we're going to do,
is as we go around this loop,
we're going to reduce the temperature, right?
So eventually, the temperature has to be small enough so that
these uphill moves are very very unlikely.
And that's going to hopefully make sure that we end
up in a global minima or something close to global minima.
All right.
So, let's have a look at simulated annealing in action for Sun Wukong in the stomach.
All right, so we start off at a position here.
We start off with the initial temperature.
And we're going to use this cooling schedule where the temperature is
going to decrease by 0.9 of its current value,
to decreased 2.9 of its current value.
So, we're here we're going to pick a random neighbor just this one that's happened.
So that is an uphill move.
And then, we'll look the threshold,
is going to work out to be 0.81,
but we'll roll a random dice and it finds that it fits within that threshold.
So we're going to make the move, even though it was uphill.
All right.
Then at this point,
we're going to pick a neighbor let's say this one here.
And this is a downhill move.
So, there's no notion of threshold needed, we're just going to take it.
Now we're going to pick a random neighbor from this one.
Again, this is an uphill move.
But I calculate the threshold and run my random number generator.
And for instance, I'm going to take that move uphill I go.
Then, here we are, we find another neighbor.
This is downhill move, so we just take it.
When we're here, we find an uphill move.
And we get a threshold 0.77,
but our random number generator generated 0.83.
So, we're not going to take this move. We're going to reject that move.
We're going to stay where we are. We're going to take it another neighbor.
So in this case, it's a downhill move.
So, we can just move there. We will look at this guy.
Now the neighbor, this neighbor here.
Again, the threshold, that random number is over the threshold.
So, we won't make it, you can see, the temperatures reducing,
so that threshold for moving is getting smaller.
So, we'll try another random neighbor that's one here to downhill move, we get to them.
All right. We look at this.
Now, this is an uphill move but we're under the threshold.
So, we'll move them. We're here.
We've got an uphill move but it's rejected by the threshold.
You can see the temperatures keeps dropping,
so we get less and less chance of taking a move.
We try this one. It's a downhill moves, so we'll take it.
Try this one, it's an uphill move but we reject it.
This one, we also reject.
This one is downhill move, we get there.
And this one's an uphill move.
In fact, we're actually at the global minima now.
So, everything's an uphill move. We reject that one.
And you can see by the end,
we're at the global minima in this particular case.
So, in simulated Annealing,
we're gradually reducing this temperature.
And that means that there's less and less probability
that the algorithm will make an uphill move as it goes along.
And this cooling schedule is typically
negative exponential like the example we showed there.
So basically, we gradually reduce the temperature heading towards zero, all right.
But one of the difficulties of using simulated annealing,
and basically this happens in almost all local searches,
there'll be some parameters we need to tune.
So here, we need to think about the initial temperature,
this constant c, and the cooling schedule.
And there's lots of work out there,
how to tune those or how to discover the best ones for your particular problem.
Prof. Jimmy Ho Man LeeProfessor
Prof. Peter James StuckeyProfessor
