!!Extended neighborhoods (1121209)
Текст из файла
Simulated Annealing with ExtendedNeighbourhood1Xin YaoComputer Sciences LaboratoryResearch School of Physical Sciences and EngineeringThe Australian National UniversityGPO Box 4, Canberra, ACT 2601AUSTRALIAe-mail: xin@cslab.anu.edu.auFax: (+61 6)/(06)249 18841 Published1991.inInternational Journal of Computer Mathematics, 40:169{189,AbstractSimulated Annealing (SA) is a powerful stochastic search method applicable to awide range of problems for which little prior knowledge is available. It can producevery high quality solutions for hard combinatorial optimization problems. However,the computation time required by SA is very large. Various methods have beenproposed to reduce the computation time, but they mainly deal with the carefultuning of SA's control parameters. This paper rst analyzes the impact of SA'sneighbourhood on SA's performance and shows that SA with a larger neighbourhoodis better than SA with a smaller one.
The paper also gives a general model ofSA, which has both dynamic generation probability and acceptance probability, andproves its convergence. All variants of SA can be unied under such a generalization.Finally, a method of extending SA's neighbourhood is proposed, which uses a discreteapproximation to some continuous probability function as the generation function inSA, and several important corollaries of the general model are given.KEYWORDS | Simulated Annealing, Stochastic Search, Algorithm Analysis,Combinatorial Optimization.Xin Yao: Simulated Annealing with Extended Neighbourhood11 IntroductionSA is a powerful stochastic search method applicable to a wide range of problems forwhich little prior knowledge is available. It has been widely used in computer-aidedVLSI design [1], combinatorial optimization [2, 3, 4], neural network training [5, 6],image processing [7, 8], code design [9], function optimization [10], etc.
The mostimportant reason for SA's popularity is its ability to produce high quality solutionsfor hard problems.The basic idea of SA comes from condensed matter physics. It is well known incondensed matter physics that a good way to nd minimum energy states, calledground states, of complex systems such as solids is to use the annealing technique, inwhich the system (solid) is rst heated to some high temperature, and then slowlycooled down.
The system (solid) will reach a ground state if the cooling rate aroundthe freezing point of the system is suciently slow. This process can be simulatedon computers via abstract models, such as systems of interacting particles with manydegrees of freedom.At each step of the simulation, a new state of the system is generated from thecurrent state by giving a random displacement to a randomly selected particle.
Thenew state will be accepted as the current one if the energy of the new state is no greaterthan that of the current state, otherwise, it will only be accepted with probabilityexp ? Enew state ?TEcurrent statewhere E stands for the energy of the system and T is the temperature. This stepcan be repeated as many as necessary with a slow decrease of temperature in orderto nd a minimum energy state. Of course, only nite steps are taken in practicalsimulations. This simulation procedure was proposed by N. Metropolis et al.[11] andis called the Metropolis procedure.The analogy between nding minimum energy states in a physical system andnding minimum cost congurations in a combinatorial optimization problem wasindependently observed by S. Kirkpatrick et al.[2] and V.
C erny [12]. They proposeda new algorithm for solving combinatorial optimization problems, SA, based on theMetropolis procedure. Since then, research on SA has been booming in both theoryand applications. However, SA often suers from the long computation time, sometimes even severely. Various methods have been proposed to cope with this problem,but they mainly deal with careful tuning of SA's control parameters and the resultingimprovement of SA's performance is rather limited. This paper analyzes the impactof the neighbourhood on SA's performance and then gives a general model of SA withXin Yao: Simulated Annealing with Extended Neighbourhood2both dynamic generation and acceptance probabilities, which unies the variants ofSA under the same general model.Section 2 briey reviews SA.
Section 3 analyzes the impact of the neighbourhoodon SA's performance and shows an important result that the performance of SAwith large neighbourhoods is better than that with small neighbourhoods. Section 4gives a general model of SA as well as its convergence conditions, which removes therestriction that the generation probability of SA be independent of the control parameter, temperature. This generalization not only unies various SA's with dierentparameters and functions, but can also derive many useful results which reduce thecomputation time of SA. Section 5 is devoted to the SA with dynamic generationand acceptance probabilities. A method of using a discrete approximation of somecontinuous probability function as the generation function is proposed and a set ofcorollaries is given.
Finally, some conclusions are drawn in Section 6.2 A Brief Review of Simulated AnnealingThe combinatorial optimization problems considered herein can be described as:Given a nite conguration space S = fX j X = (x1; x2; ; xm)g, where m is calledthe dimension of the space, and a cost function c : S ?! R1, we want to nd anoptimum conguration X 2 S , such that 8Y 2 S; cX cY . (We only deal withminimization problems here. Maximization problems can be treated similarly.) Theneighbourhood system of a combinatorial optimization problem can be dened asN = fNX j X 2 S; NX S g(1)where X 62 NX and Y 2 NX () X 2 NY .
Obviously, elements in NX represent thecongurations next to X in the conguration space. They are called neighbours ofX.The standard SA (SSA) [2] starts with an initial conguration generated at random. At each step, it selects the next conguration Y from the neighbourhood NX ofthe current conguration X . The next conguration will be accepted as the currentone if its cost is no greater than that of the current conguration, otherwise it willonly be accepted with probabilitycXexp ? cY ?TThis procedure is repeated with a slow decrease of the control parameter T , calledtemperature, until a suciently good solution has been found.
SSA can be summarized as Figure 1.Xin Yao: Simulated Annealing with Extended Neighbourhood3select initial conguration X at random;select initial temperature T ;REPEATREPEATrandomly select Y from NX with uniform distribution;IF cY cXTHEN accept Y as the new congurationELSE accept Y as the new conguration with probabilityexp (? (cY ? cX ) / T )UNTIL `inner-loop stop criterion' satised;decrease temperature TUNTIL `outer-loop stop criterion' satisedFigure 1: Main steps of standard simulated annealing.The performance of SSA can be analyzed by nonstationary Markov chain theory[13]. Suppose the probability of generating the next conguration Y from the currentone X is gXY , which is independent of temperature T , and the probability of acceptingY as the new current conguration is aXY (T ).
They satisfy (2) and (3) respectively.1 ; X 2 S; Y 2 NXgXY = jNX j(2)0; X 2 S; Y 62 NX(3)aXY (T ) = min 1; exp ? cY ?T cXThe one-step transition probabilities of the nonstationary Markov chain associatedwith SSA arecY ?cX ;1X 2 S; Y 2 NXjNX j min 1; exp ? TpXY (T ) = 0;X 2 S; Y 62 NX ; X 6= Yc?c1ZX1 ? Z2NX jNX j min 1; exp ? T; X 2 S; Y 62 NX ; X = YThe convergence of SSA has been proved by several researchers [14, 15, 16]. Theirresults can be formulated as follows:Given that SSA's generation and acceptance probabilities satisfy (2) and (3) respectively, then SSA converges to global minima, i.e.,(4)nlim!1 Prob fX 2 S g = 1S = fX j X 2 S; cX cY 8Y 2 S g(5)8<:8>>><>>>:nPonoXin Yao: Simulated Annealing with Extended Neighbourhood4if the rate of temperature decrease isTn = ln(nh+ 1) ;n = 1; 2; (6)where h is a problem dependent constant and Tn stands for the temperature at timen.A better result, obtained in [17], can be stated asGiven that SSA's generation and acceptance probabilities satisfy (2) and (3) respectively, then SSA converges to global minima if the rate of temperature decreaseis(7)Tn = PN i j n k(ln)+n0i=1twhere c+ rc+ = X 2maxfjc ? cX jgS;Y 2NX Y(ln)i(f (x)) = ln((ln)i?1 (f (x))); i > 0(ln)0 (f (x)) = f (x)n0 > 1N (N 1) is an arbitrarily large integert (t < 1) is the inner ? loop iterations of SA(8)(9)(10)(11)(12)(13)(14)In practice, the cooling rates of (6) or (7) are too slow to be followed exactly.
Afrequently used method is to set the cooling rate asTn+1 = Tn(15)where is a constant normally selected between 0:80 and 0:99. Although this kindof SSA has been successfully used in many applications [2, 18, 4], it needs a largeamount of computation time. Various eorts made to reduce this time can be dividedinto two classes; one is parallel processing and the other is careful tuning of theSSA's control parameters, such as initial temperature, cooling rate, inner-loop stopcriterion and outer-loop stop criterion. Dierent acceptance probabilities have alsobeen tried [19, 20]. However, little work has done on the impact of SA's generationprobabilities, which are directly related to SA's neighbourhood system as well as itssearch behaviour in the conguration space, on SA's performance.
The followingsections will analyze this impact and give a general model of SA.Xin Yao: Simulated Annealing with Extended Neighbourhood5cost 6Xk2 rrXk1 rrrrXk1 ?1rrrrX1X0 rrXkRrrXk2 ?1 Xk2 +1Xk1 +1rrrrrrrrXl1 ?1 Xl1 +1Xl1rrrrrXl2 ?1rXl2rXkR +1rrrrrrrrXlR ?1rXlRconguration (x)-Figure 2: Conguration space of a one-dimensional optimization problem.3 Analysis of the Neighbourhood System of Simulated AnnealingIt is well known that a greedy algorithm, like hill climbing, will stick in a local minimum if the algorithm has reached it, while a stochastic algorithm such as SA can stillescape from a local minimum and move to a better region in the conguration space.Obviously, the probability of escaping from a local minimum is a very importantquantity aecting SA's performance.
A larger value will reduce the time SA stays ina local minimum and speed up its movement towards global minima. This sectionanalyzes the above probability and discusses the impact of the neighbourhood systemon it.In SSA, a neighbour Y of a conguration X in NX is dierent from X in onlyone element, as in the Metropolis procedure. That is, if X = (x1; x2; ; xi; ; xm),and Y = (y1; y2; ; yi; ; ym), then yi 6= xi; yj = xj ; i 6= j; 1 i m; j =1; 2; ; m. In the following discussion, we say that the `Hamming' distance betweentwo congurations is and they are -steps reachable from each other if there areexactly elements dierent between them. For simplicity, we rst consider onedimensional combinatorial optimization problems, i.e., the case of X = (x), whichcan be represented as in Figure 2.In the one-dimensional case, jNXi j = 2 for all Xi 2 S . Hence we can get, from (2)Xin Yao: Simulated Annealing with Extended Neighbourhood6and (3), that the probability of moving from conguration X0 to the local maximumXk1 at temperature T using no greater than k1 steps isProb (X0; Xk1 ; k1; T; jNXi j = 2)k1 1cXi ? cXi?1=exp?Ti=1 2k1c ?c= 1 exp ? Xk1 X0(16)2Tand the probability of moving from Xk1 to the local minimum Xl1 at temperature Tusing no greater than l1 ? k1 steps isl1?k1Prob (Xk1 ; Xl1 ; l1 ? k1; T; jNXi j = 2) = 12(17)Similarly, we can obtain the probability of nding the global minimum XlR fromconguration X0 using no greater than lR steps:RlRProb (X0 ; XlR ; lR; T; jNXi j = 2) = 21 exp ? T1(18)cXki ? cXli?1i=1where l0 = 0.It is clear from (18) that there are three factors which aect the probability ofreaching a global minimum from a non-global minimum: (1) the total height of thehills which have to be surmounted; (2) the temperature; and (3) the total probabilityof generating the global minimum from the non-global minimum, i.e.,1 lR(19)2The heights of the hills in the conguration space are solely decided by the problem.Hence, they are unlikely to be altered for a particular problem.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
