Simulated Annealing

The Monte Carlo philosophy says: If you want to find out what’s best, try out a lot of different
things at random and see which one of these is best. If you try enough different things, the best you find will be almost certainly be a decent guess at the best overall. This is a common
approach to both mathematical and intuitive optimization problems. Its advantages are simplicity
and universal applicability. Its disadvantage is, it doesn’t work very well. It is very slow. This can be proved mathematically under very broad conditions, and it is also apparent from practical experience. In general, proceeding by selecting things at random, one has to try an awful lot of things before one finds something good.
In contrast to the Monte Carlo philosophy, the Multistart philosophy depends on local search.
It begins with a random guess x0, and then looks at all the possibilities which are very close to x0. The best from among these possibilities is called x1. Then it looks at all the possibilities which are very close to x1, selects the best, and calls it x2. It continues in this manner — generating x3, x4, and so on — until it arrives at a guess xn which seems to be better than anything else very close to it. This xn is called a local optimum — it is not necessarily the best solution to the optimization problem, but it is better than anything in its immediate vicinity.

Local search proceeds by looking for a new answer in the immediate locality surrounding the
best answer one has found so far. The goal of local search is to find a local optimum. But, as
Figure 1 illustrates, a local optimum is not always a good answer. It could be that, although there is nothing better than xn in the immediate vicinity of xn, there is something much better than xn somewhere else.
In mathematical optimization, it is usually easy to specify what "very close" means. In other
domains things may be blurrier. But that doesn’t mean the same ideas aren’t applicable. For
instance, suppose a politician is grappling with the problem of reducing carbon monoxide
emissions to a safe level. Maybe the best idea she’s found so far is "Pass a law requiring that all cars made after 1995 emit so little carbon monoxide that the total level of emissions is safe".

Then two ideas very near this one are: "Pass a law giving tax breaks to corporations which make
cars emitting safe levels of carbon monoxide", or "Pass a law requiring that all cars made after
1992 emit so little carbon monoxide that the total level of emissions is safe." And two ideas
which are not very near x0 are: "Tax automakers more and give the money to public transportation" and "Give big tax breaks to cities which outlaw driving in their downtown areas." If she decides that none of the ideas near "Pass a law requiring that all cars made after 1995 emit so little carbon monoxide that the total level of emissions is safe" is as attractive as it is, then this idea is a local optimum (from her point of view). Even if she felt that taxing automakers more and giving the money to public transportation were a better solution, this would have no effect on the fact that giving tax breaks to corporations that make safe cars was a local optimum. A local optimum is only better than those things which are very similar to it.

The Multistart philosophy says: Do a bunch of local searches, from a lot of different starting
points, and take the best answer you get as your guess at the overall best.

Sometimes only one starting point is needed. For many of the optimization problems that arise
in physics, one can pick any starting point whatsoever and do a local search from that point, and one is guaranteed to arrive at the absolute best answer. Mathematically, a problem of this sort is called convex. Unfortunately, most of the optimization problems that occur in politics, sensation, motor control, biology, economics and many other fields are nonconvex. When dealing with a convex optimization problem, the only thing you have to worry about is how well you go about picking the best from among those entities close to your best guess so far. Each year dozens of papers are written on this topic. But convexity is a very special property. In general, local search will not be effective unless it is applied according to the Multistart philosophy.

The Multistart philosophy works well for problems that don’t have too many local optima. For
instance, it would take a very long time to solve the problem in Figure 1 according to the
Multistart philosophy. In this case the Monte Carlo approach would be preferable; the local
searches are essentially a waste of time.

belgesi-934

Belgeci