lundy mees (1121217)
Текст из файла
Mathematical Programming 34 (1986) 111-124North-HollandCONVERGENCEO F AN A N N E A L I N GALGORITHMM. L U N D YDepartment of Pure Mathematics and Mathematical Statistics, Cambridge University, 16 Mill Lane,Cambridge CB2 1SB, UKA. MEESDepartment of Mathematics, University of Western Australia, Nedlands, Western Australia 6009Received 14 November 1983Revised manuscript received 7 October 1984The annealing algorithm is a stochastic optimization method which has attracted attentionbecause of its success with certain difficult problems, including NP-hard combinatorial problemssuch as the travelling salesman, Steiner trees and others. There is an appealing physical analogyfor its operation, but a more formal model seems desirable.
In this paper we present such a modeland prove that the algorithm converges with probability arbitrarily close to 1. We also show thatthere are cases where convergence takes exponentially l o n g - - t h a t is, it is no better than adeterministic method. We study how the convergence rate is affected by the form of the problem.Finally we describe a version of the algorithm that terminates in polynomial time and allows agood deal of 'practical' confidence in the solution.Key words: Global Optimization, Stochastic Optimization, Annealing, Metropolis Method, NP,Hill Climbing, Local Improvement.1.
IntroductionThe main idea used in the annealing algorithm was first described by Metropoliset al. (1953), though not in an optimization context. It was recently de;celoped andapplied to optimization problems independently by Kirkpatrick et al. (1982) andCerny (1984). Other applications have also been reported by Schwarzschild (1982)and Giman and Giman (1984). These authors attempt to solve difficult optimizationproblems by what amounts to a combination of a Monte Carlo method and adeterministic descent process. This may be thought of as an attempt to get some ofthe speed and reliability of descent algorithms while avoiding their propensity tostick at local minima.The idea came from an analogy with the annealing process used in making spinglasses.
The physical system operates so as to minimize potential energy, which isrelated to the extent to which atomic spins fail to line up with one another. If theglass is held at any nonzero temperature it eventually reaches thermodynamicequilibrium in which there are typically a number of domains within which thespins are (approximately) aligned, but between which spins differ. Random kineticfluctuations prevent a global minimum of potential energy from being attained over111112M.
Lundy, A. Mees / Annealing algorithmany reasonable time, giving instead an average of a (local) minimum state andnearby states. In addition, the system is prevented from sticking in local minimawhose basins are not very deep compared with the size of typical fluctuations. Morephysically, we never get exact alignment of spins, but we avoid a huge number ofsmall domains.
The global m i n i m u m - - i n which the whole piece of glass is a singledomain--will probably never be attained, but by gradually lowering the temperatureone hopes to end up with relatively few domains. The point is that at low temperaturesthe macroscopic form of the domains is fixed over very long times. Low temperaturesare needed to get good alignment within single domains but must be approachedcautiously to avoid being stuck in local minima corresponding to many domains.This analogy was first pointed out by Kirkpatrick et al. (1982). The purpose ofthis paper is to formalize 'annealing' so as to allow the application of other powerfulmetaphors (Markov chains) that might give additional insights.
Although optimization problems of almost any sort may be solved, we shall concentrate on combinatorial problems.In our formulation, the temperature becomes a control parameter that changesas the optimization proceeds, and thermodynamic equilibrium is replaced by equilibrium of a Markov process. We will prove that the algorithm converges in that itcan be made to terminate arbitrarily close to the global optimum with probabilityarbitrarily near one. Unfortunately the time to termination cannot be shown to bepolynomially bounded for a general NP-hard problem. In fact, we give exampleswhere the time is exponentially long, and the annealing method may actually takelonger than a deterministic algorithm that simply examines all the solutions.
It maybe that for certain types of problem the time for stochastic convergence is polynomial,and we discuss conditions that would ensure this.These conditions are not generally practical to check, so we describe a cautiousheuristic method of adjusting the control parameter which leads to termination inpolynomial time and which has behaved well in tests we have made on the travellingsalesman, cluster analysis, subset selection, evolutionary trees and some problemsin wood stocking (Lundy, 1984, 1985).2.
The algorithmThe problem is to minimize a function f : X ~ R where X is a space with a finitenumber IX[ of points. IX I is exponentially large in terms of a natural measure ofthe size of the problem: for example, a travelling salesman problem with n citieshas IX[ = ( n - 1)!So far, X has no structure at all. Now we define neighbours of the points of X:that is, we define a topology on X. In the travelling salesman case, if we regard apermutation of the integers {2 . . . . , n} as a point in X then its neighbours might beall routes generated from this one by interchanging two city indices.
The essentialfeature of the topology is that every point must be eventually reachable from everyM. Lundy, A. Mees / Annealing algorithm113other point. We shall prove that in equilibrium, the relative amounts of time spentin different states are independent o f the topology.At the ith step, call the current solution xi, call the control parameter (a nonnegative number) ci, and write f~ = f(x~). Start with an initial solution Xo, possibly selectedrandomly, and assume we are given values Co, dci and cI of the control parameter,obtained as discussed later.The algorithm repeats the following steps until ci <~ cs:1. Generate a neighbour Xp of the current solution x~. This is a potential candidatefor xi+ 1.2.
Set X~+l to xp with probability min{1, exp((f-fp)/C~)}, and to x~ with thecomplementary probability.3. Set c~+1 to c~- dci and replace i with i + 1.Note that we may set dci = 0; that is, we may hold the system at a fixed controlvalue for many iterations. Also, the above choice of acceptance probability is naturalbut is not the only possibility, as we shall see later. The effect is that downhill stepsare always accepted while uphill steps are more likely to be accepted if they aresmall than if they are large.As an illustration of this effect, Fig. 2.1 shows a series of steps taken for each oftwo separate fixed values of c, in a two dimensional problem with two local minima.(The space has been discretised in a simple way.) A deterministic descent methodwill always go to the minimum in whose basin it finds itself, whereas the annealingmethod can climb out of one basin into the next.
In the long run, the annealingmethod will spend a proportion of its time in each basin determined by the functionvalues there, together with the current value of the control parameter. As the controlparameter decreases, the proportion of time spent at the global optimum increases:if we run for long enough at a small enough value of c, the global optimum willconsume almost all of the steps.Because of its ability to make uphill steps, the annealing method avoids beingtrapped in local optima. However, it is far from apparent at first that one could notalways do at least as well by running a deterministic algorithm many times, withrandomly chosen starting points.
The following example shows that cases existwhere the annealing algorithm performs much better than such a method.Let X c R 2 be the square centred at 0 and of side 2 N (see Fig. 2.2a) ; discretiseX on a grid of mesh size 8, centre 0. Let r=max{[xl[, Ix~l} be the 1o~ distance ofany point x c X from 0; and let f : X-~ R, a function of r only, be as shown in Fig.2.2b. In fact, f ( x ) = r except when r = n + 6 where n is any positive integer; in thatcase, f = n - e for some e << 6.
The problem is to find the minimum o f f on X, whichof course lies at 0.We describe two search techniques to do the minimization. They are a versionof downhill search with random starting point, and the annealing method. To providea realistic comparison with combinatorial problems, we assume that the downhillsearch takes steps of size ~ and does not have access to gradient information, so itlocates a local optimum in a time which is much the same as the annealing methodM. Lundy, A. Mees / Annealing algorithm1143.02.52.~1,51.00.5@.0-0.5-1 .(3-1.5-2.0-2,5-3.8-2.5-2.9-1.5-1.0 -0.5-3.0- 2 . 5 -2.@ - 1 .
5 - i . 08,00.S1.01,52,8• ,53.00.00.51.01.52.02.53.[33.02.5 j2.01.51.0[3.50.0-0.5- I .[3- i .5-2.0-2.5-3 .@-[3.5Fig. 2.1. Random walk on a contour map. (a) garce c. (b) Small c.M. Lundy, A. Mees / Annealing algorithm1152N42Nftrin+2~InD-Cnn+6 n+2~n+l n+1+6n+1+2~rFig. 2.2. Descent vs. annealing method. (a) Square solution space for example. (b) Radial behaviour ofobjective function.116M. Lundy, A. Mees / Annealing algorithmw o u l d if it were run with c = 0 (when downhill steps are always accepted whileuphill steps never are).
Let S be the n u m b e r o f steps taken to reach the globalminimum. We use the expected value E(S) to c o m p a r e the two methods.Method 1. Downhill search. R a n d o m l y select a starting point Xo, so E(f(xo))=O ( N ) . Carry out a strict downhill search to locate the local m i n i m u m value m(xo)which is [ r ] - e where I t ] is the integer part of r(xo), unless [r] = 0 in which casem(xo) = 0. With this m e t h o d we reach f ( 0 ) when and only w h e n we generate astarting point in [ - 1 , 1] × [ - 1 , 1] (ignoring uncertainties which o c c u r when [r] = r).Thus the n u m b e r of starts $6/4 is geometrically distributed with parameter 1 / N 2and E(S)=4N2/6.Method 2.
Annealing method. R a n d o m l y select a starting point Xo, so E(f(xo))=O ( N ) . Assume e<< c<< 6. At any point xi, choose (randomly) one o f the fourneighbours ( x i + 6 , yi) and (x~, y~+3). Let df be the change in objective functionvalue on moving to the chosen neighbour. I f df< 0 then accept the chosen neighbour,while if df> 0 accept it with probability e -ds/c. Since df> 0 implies df= e + 2 6 ordf = e or df = 6, the choice o f c ensures that uphill steps are taken with probabilityessentially zero except for the step o f e, which is taken with probabilityessentially 1.C o n s e q u e n t l y the m e t h o d proceeds in a deterministic m a n n e r between r = n + 1and r=n+6, for any integer n > 0 , taking a time O ( 1 / 6 ) to do so.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
