3.4.4 Simulated Annealing

Loading...

來自 The University of Melbourne 的課程

Solving Algorithms for Discrete Optimization

2 個評分

The University of Melbourne

Solving Algorithms for Discrete Optimization

2 個評分

Discrete Optimization aims to make good decisions when we have many possibilities to choose from. Its applications are ubiquitous throughout our society. Its applications range from solving Sudoku puzzles to arranging seating in a wedding banquet. The same technology can schedule planes and their crews, coordinate the production of steel, and organize the transportation of iron ore from the mines to the ports. Good decisions on the use of scarce or expensive resources such as staffing and material resources also allow corporations to improve their profit by millions of dollars. Similar problems also underpin much of our daily lives and are part of determining daily delivery routes for packages, making school timetables, and delivering power to our homes. Despite their fundamental importance, these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students who have completed Advanced Modelling for Discrete Optimization. In this course, you will extend your understanding of how to solve challenging discrete optimization problems by learning more about the solving technologies that are used to solve them, and how a high-level model (written in MiniZinc) is transformed into a form that is executable by these underlying solvers. By better understanding the actual solving technology, you will both improve your modeling capabilities, and be able to choose the most appropriate solving technology to use. Watch the course promotional video here: https://www.youtube.com/watch?v=-EiRsK-Rm08

從本節課中

Local Search

This module takes you into the exciting realm of local search methods, which allow for efficient exploration of some otherwise large and complex search space. You will learn the notion of states, moves and neighbourhoods, and how they are utilized in basic greedy search and steepest descent search in constrained search space. Learn various methods of escaping from and avoiding local minima, including restarts, simulated annealing, tabu lists and discrete Lagrange Multipliers. Last but not least, you will see how Large Neighbourhood Search treats finding the best neighbour in a large neighbourhood as a discrete optimization problem, which allows us to explore farther and search more efficiently.

3.4.1 Local Search15:34

3.4.2 Constraints and Local Search12:15

3.4.3 Escaping Local Minima- Restart6:49

3.4.4 Simulated Annealing7:06

3.4.5 Tabu List9:09

3.4.6 Discrete Langrange Multiplier Methods28:50

3.4.7 Large Neighbourhood Search24:36

3.4.8 MiniZinc to Local Search16:41

3.4.9 Module 4 Summary8:19

與講師見面

Prof. Jimmy Ho Man Lee
Professor
Department of Computer Science and Engineering
Prof. Peter James Stuckey
Professor
Computing and Information Systems

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.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取