!!Extended neighborhoods (1121209), страница 3
Текст из файла (страница 3)
Forsimplicity, we abbreviate generation probability gXY (Tn) as gXY (n) and acceptanceprobability aXY (Tn) as aXY (n). The method used to prove the convergence of SAis straightforward. We rst prove the weak ergodicity of the nonstationary Markovchain associated with the general SA, and then prove the strong ergodicity and theconvergence. Denoteg?(n) =a?(n) =min fgXY (n)gmin faXY (n)gX 2S; Y 2NX 2S; Y 2NXX(35)(36)The following theorem pertains to the weak ergodicity of the nonstationary Markovchain associated with SA.Theorem 4.3 Suppose the generation probability gXY (n); X 2 S; Y 2 NX of SAsatises:(g1) gXY (n) is a non-increasing function of n for suciently large n and limn!1 gXY (n)exists;and the acceptance probability aXY (n); X; Y 2 S satises:(a1) For cX < cY , aXY (n) is a decreasing function of n for suciently large n andlimn!1 aXY (n) = 0;Xin Yao: Simulated Annealing with Extended Neighbourhood13(a2) For cX cY , aXY (n) = 1, n = 0; 1; 2; ;then the nonstationary Markov chain associated with SA is weakly ergodic if1rX hk=n1ig? (kr)a?(kr) = 1(37)where n1 (n1 > 1) is an integer, r is the radius of the graph G = (S; E ), S is the setof congurations, E = f(X; Y ) j X 2 NY ; X; Y 2 S g, i.e.,r = X 2minmax fd g(38)S ?Slm Y 2S XYSlm = fX j X 2 S; cX cY 8Y 2 NX g(39)where dXY stands for the length of the shortest path from node X to node Y in graphG.
The center of the graph, denoted by Xc , is the node which obtains the minimumin (38).Proof: According to conditions (g) and (a) in Theorem 4.3 and (35) and (36), forsuciently large n and 8X 2 S; Y 2 NX ,pXY (n) = gXY (n)aXY (n) g? (n)a?(n)(40)and 8X 2 S ? Slm ; Y 2 NX ,c Y cX(41)pXY (n) = gXY (n);gXY (n)aXY (n); cY > cXIt is obvious from (41) that 8X 2 S ? Slm ; 9Y 2 NX , such that pXY (n) is thedecreasing function of n for suciently large n. Since 8X 2 S ,pXZ (n)pXX (n) = 1 ?8<:XZ 2NXwe know that pXX (n) is an increasing function of n for suciently large n.
Becauseg? (n)a?(n) is a decreasing function of n, we get, for suciently large n and 8X 2S ? Slm,pXX (n) g?(n)a?(n)(42)From (40) and (42) we have, 8X 2 S; 9n1 > 1, such that 8n n1r,pXXc (n ? r; n)n=pXXc (k)Yk=n?r+1n hYg?(k)a?(k)k=n?r+1hirg?(n)a? (n)i(43)Xin Yao: Simulated Annealing with Extended Neighbourhood14Then we can get a lower bound on the ergodic coecient (see Denition V.2.1 in[13]) of the nonstationary Markov chain associated with SA,(P (n ? r; n))= minmin(pXY (n ? r; n); pZY (n ? r; n))X;Z()XY 2S minfmin(pXXc (n ? r; n); pZXc (n ? r; n))gX;Z g? (n)a?(n) rhi(44)The above result (44) and condition (37) of the Theorem lead to1Xk=1 (P (kr ? r; kr)) 1X hk=n1rig? (kr)a?(kr) = 1(45)Now the weak ergodicity of the nonstationary Markov chain associated with SAcan easily be seen by Theorem 4.2.Q.E.D.The strong ergodicity and the convergence of general SA are described by Theorem 4.4.Theorem 4.4 Suppose the conditions specied in Theorem 4.3 are satised, andfP (n)g1n=1 are the transition matrices of the nonstationary Markov chain associated with SA.
If P (n) has a regular extension P (x), where 8X; Y 2 S , pXY (x)belongs to CAM or RCBV, then fP (n)g1n=1 is strongly ergodic. Moreover, for suciently large n, each P (n) has a unique quasi-stationary state distribution (n) withlimn!1 (n) = and 8X; Y 2 S; m 1, limn!1 pXY (m; n) = Y .
The general SAconverges if satises, 8X 2 S ,X =8<:where S is dened by (5), andX (X > 0); X 2 S 0;X 2 S ? SXX 2S (46)X = 1Proof: By Theorem 4.1 and Theorem 4.3.Q.E.D.The main dierence between Theorem 4.4 and the earlier convergence theorems isthat this theorem allows the generation probability to change dynamically accordingto dierent temperatures. The earlier convergence theorems can all be treated ascorollaries of Theorem 4.4.
Further important corollaries will be given in Section 5.Xin Yao: Simulated Annealing with Extended Neighbourhood15The conditions (g) and (a) in Theorem 4.3 are easy to verify in practice. Thereare many functions which satisfy these conditions and belong to CAM or RCBV aswell. In some sense, condition (37) determines the convergence of the general SA. Atoo rapid cooling rate will lead to convergence of the sum in (37).
This means thatthe probability of the uphill movement decreases quickly and the search is more likelyto stick in a local minimum. Hence, condition (37) actually sets an upper bound onhow fast generation and acceptance probabilities can decrease, or in other words, howfast the temperature can decrease.5 Simulated Annealing with Dynamic Generationand Acceptance ProbabilitiesAs indicated in Section 3, the larger an SA's neighbourhood is, the easier it is toarrive at a global minimum, provided the global minimum is far enough from thecurrent conguration. In practice, the probability that a randomly selected initialconguration is very close to a global minimum is quite small.
Hence, it is benecialto have large neighbourhoods in the initial stages of SA's search, i.e., at high temperatures. With the progress of the search, i.e., the decrease of temperature, the currentconguration will move closer and closer to a global minimum, and SA's neighbourhood should be reduced accordingly. This section gives a method of changing SA'sneighbourhoods according to the temperature.
An important feature of the methoddescribed here is that it enjoys the global convergence, and at the same time increasesthe eciency of SA's search.According to Theorem 4.4, many real-valued probability distribution functions canbe used as the generation probability of SA, but for combinatorial optimizations theyhave to be discrete as we are dealing with a discrete conguration space. Supposewe are going to use a continuous density function f (x) to generate the Hammingdistance between the current conguration and the next one.
Denote the set ofcongurations which are distant from current conguration X as SX (),SX () = fY j Y 2 S; dXY = g(47)The probability of generating conguration Y , which is dXY distant from conguration X , could be dened asgXY (Tn) = jS (1d )j Prob dXY ? 12 < dXY + 12X XYdXY + 12= jS (1d )j1 f (x)dxZXXYdXY ? 2Xin Yao: Simulated Annealing with Extended Neighbourhood16 jSf ((ddXY ))jX XY(48)Suppose the maximum Hamming distance allowed for one move is dmax, then thenormalized generation function isgXY (Tn) = f (dXYF) / j(STX)(dXY )j(49)X nwheredmaxf (dXZ )(50)FX (Tn) =jS (d )jXXXdXZ =1 Z 2SXZCorollary 5.1 Suppose the generation and acceptance probabilities of SA are (49)and (3) respectively, and f (x) is the Normal function N (0; Tn).
Then the SA converges to global minima if the cooling rate isTn =Ni=1PwhereGh(ln)ijntk+ n0in = 0; 1; 2; ;(51)G 12 (dmax )2 + c+ r(52)and other denitions are the same as (9) { (14).Proof: We rst show the weak ergodicity of the nonstationary Markov chainassociated with SA. Under the assumption of the Normal function,2f (dXY ) = p 1 exp ? d2XYTn2TnAccording to (35) and (49), for k = 0; 1; 2; ;!Qg? (kr) =N ?1i=0h(ln)ijkrtkwhere)2 /(2 )?(drPmaxGN (ln)i+ n0p2 jS + (d)j F + (Ti=1)GnihjS + (d) = maxfjSX ()j ; = 1; 2; ; dmaxgX 2SF + (Tn ) = maxfF (T )gX 2S X nAccording to (36) and (3), for k = 0; 1; 2; ;a?(kr)+ exp ? Tckrtk+ n0i(53)(54)(55)!=NY?1i=0kr"(ln)i$kr + n0t%!#?(c+ )/ G(56)Xin Yao: Simulated Annealing with Extended Neighbourhood17Hence, for k = 0; 1; 2; ;1Xhg? (kr)a?(kr)rik=0 "#jhi? 1 d2iir=2kkj+ ]r/ G hP h+cP1Q N ?1[max2Ni kr + n0i kr + n0k=0 i=0 (ln)i=1 (ln)tthpir2G jS +(d)j F + (Tn)We know from (52) that the above sum is innite.
By Theorem 4.3 we obtain theweak ergodicity. To show the strong ergodicity and convergence, let us rst examinethe one-step transition probabilities of the nonstationary Markov chain,8>>>>><2cY ?cXexp ? d2XYTn minf1;exp(? Tn )gp2T jS (d )j F (T );n X XY X nY 2 NX(57)0;Y 62 NX ; Y 6= XY 62 NX ; Y = X1 ? Z2S pXZ (Tn) ;Substituting v for Tn in (57), we can get functions pXY (v), which satises pXY (v) >0 for all X 2 S; Y 2 NX and Y = X; v > 0. That is, f(X; Y ) j pXY (v) > 0g is thesame for all 0 < v < v0, where v0 (> 0) can be any real number. Hence, P (v)is a regular extension of the nonstationary Markov chain fP (n)g1n=0 according toProposition 4.2.
It is easy to see that the sequence fTng1n=0 satises limn!1 Tn = 0from (51). Furthermore, we know, by Denition 4.3 and 4.4 and Proposition 4.1, thatpXY (Tn) belongs to CAM for all X; Y 2 S . Now the strong ergodicity can be arrivedat by Theorem 4.4, and at the same time we conclude that there exists a uniquequasi-stationary distribution (Tn) for each P (Tn) for suciently large n, i.e.,pXY (Tn) =>>>>>:P (Tn ) = (Tn) P (Tn)(58)(58) implies that 8X; Y 2 S ,X (Tn) pXY (Tn) = Y (Tn) pY X (Tn)Hence we get, 8X 2 S ,X (Tn) =Obviously,exp (?cX / Tn)Z 2S exp (?cZ / Tn )Pnlim!1 X (Tn ) = qX =where8<:jS j ;10;q = qX 1 ; qX 2 ; ; qX jSj ;X 2 SX 2 S ? SXi 2 S(59)(60)(61)Xin Yao: Simulated Annealing with Extended Neighbourhood18is called the optimum distribution of congurations in the conguration space.Q.E.D.The same technique can be used to derive a set of corollaries, including the following relatively important ones.Corollary 5.2 Suppose the generation and acceptance probabilities of SA are (49)and (3) respectively, and f (x) is the exponential function E (0; Tn).
Then the SAconverges to global minima if the cooling rate isTn =Ni=1PEh(ln)iwherejntk+ n0in = 0; 1; 2; ;E dmax + c+ r(62)(63)and other denitions are the same as (9) { (14).Proof: The same as Corollary 5.1. Note that 8X; Y 2 S ,f (dXY ) = T1 exp ? dTXYnn!Q.E.D.Corollary 5.3 Suppose the generation and acceptance probabilities of SA are (49)and (3) respectively, and f (x) is Cauchy function C (0; Tn ). Then the SA convergesto global minima if the cooling rate isTn =whereNi=1PCh(ln)ijntk+ n0in = 0; 1; 2; ;C c+ + 1 r(64)(65)and other denitions are the same as (9) { (14).Proof: The same as Corollary 5.1.
Note that 8X; Y 2 S ,f (dXY ) = 1 d2 T+n T 2XYnQ.E.D.Although we adopted (3) as the acceptance probability in the above analyses,others can also be used, such as [20] (c ? c )c; 0aXY (Tn) = min 1; exp X XT Ynor those described in [23, 19].(!)Xin Yao: Simulated Annealing with Extended Neighbourhood196 ConclusionThis paper gives a probabilistic analysis of the impact of SA's neighbourhood on SA'sperformance and shows that an SA with large neighbourhoods is easier to arrive ata global minimum than that with smaller ones, thus reduces the computation time.A general model of SA with both dynamic generation and acceptance probabilitiesis also studied and its convergence conditions are shown.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
