!!Extended neighborhoods (1121209), страница 2
Текст из файла (страница 2)
However, we cancertainly raise the temperature to make escaping from the local minimum easier.This is exactly what SSA does in the early stages of the annealing. Another way toaccelerate SSA's escape from local minima is to make (19) larger. This goal can beachieved by extending the neighbourhood of SSA's search.Suppose we have extended the neighbourhoods from those of Hamming distance1 to those of Hamming distance 2, that is, instead of having NXi = fXi?1 ; Xi+1g,we have NXi = fXi?2; Xi?1 ; Xi+1; Xi+2 g.
Let Prob (X0; Xk1 ; ; ; T; jNXi j = 4) be theprobability of arriving at Xk1 from X0 for the -th time in exact steps. Then weget jNXi j = 4, andY!Prob (X0 ; Xk1 ; k1; T; jNXi j = 4)X!Xin Yao: Simulated Annealing with Extended Neighbourhood==>=k1 X XProb (X0; Xk1 ; ; ; T; jNXi j = 4) =1 =1k1 XX = k21 =1k1X = k21Prob (X0; Xk1 ; ; ; T; jNXi j = 4)Prob (X0 ; Xk1 ; ; 1; T; jNXi j = 4)k12c ?cexp ? Xk1 T X0k1 +12c ?ck11 k1 ? 2+ 2 + 2 + + 2 + 1 4exp ? Xk1 T X0...k1 ?2c ?c+ [(k1 ? 3) + (k1 ? 4) + + 2 + 1] 41exp ? Xk1 T X0k1 ?1c ?cexp ? Xk1 T X0+ (k1 ? 1) 14k1c ?c+ 14 exp ? Xk1 T X0k1 21 exp ? cXk1 ? cX04Tk1 1 exp ? cXk1 ? cX02TProb (X0 ; Xk1 ; k1; T; jNXi j = 2)14!!!>==7!!!!!That is,(20)(21)(22)Prob (X0 ; Xk1 ; k1; T; jNXi j = 4) > Prob (X0; Xk1 ; k1; T; jNXi j = 2)(23)In the above analysis, we have assumed that k1 ( 2) is even, the odd case cansimilarly be shown.
It is obvious from the above analysis that the probability ofmoving from X0 to Xk1 is controlled by the total probability of generating Xk1 fromX0; the exponential part is the same. The total generation probability is independentof the starting conguration X0 and the ending conguration Xk1 ; it only dependson the total Hamming distance between them. Let G (k; ; ; T; jNXi j = 4) be thetotal probability of generating the ending conguration which is k distance from thestarting conguration for the -th (1 ) time in exact ( k2 k) steps.Then the following recurrence holds.
?(k? )+1 1 jG (k; ; 1; T; jNXi j = 4) =4 G (k; ? 1; 1; T; jNXi j = 4) (24)j =1XXin Yao: Simulated Annealing with Extended NeighbourhoodNotice that8kG (k; k; 1; T; jNXi j = 4) = 14Using a similar analysis to (16) { (25) we get the following result:(25)Prob (X0; XlR ; lR; T; jNXi j = 4) > Prob (X0; XlR ; lR; T; jNXi j = 2)(26)where lR 2.(26) indicates that SA with large neighbourhoods is easier to escape from a localminimum than that with smaller neighbourhoods. In general, if we extend neighbourhoods from those of Hamming distance 1 to those of Hamming distance m (m 2),we can getProb (X0; Xl ; l; T; jNXi j = 2m) > Prob (X0; Xl; l; T; jNXi j = 2)(27)where l m.Although the above conclusion is derived for the case of one-dimensional problems,it also holds for multi-dimensional problems.
We can summarize this result in thefollowing theorem.Theorem 3.1 SA with larger neighbourhoods as extended above has greater probability of arriving at a global optimum than SSA has if the other conditions, i.e., the initialconguration, initial temperature and temperature decreasing rate, are the same.Proof: Suppose SSA's neighbourhood is NX SSA , i.e., those of Hamming distance1, and we extend it to NX m, i.e., those of Hamming distance m (m 2), inan n-dimensional conguration space. Because of the symmetry of the neighbourrelationship, we have, for m 2,jNX mj (jNX SSA j)m(28)For each path leading from a non-global minimum X0 to a global minimum XlRin the n-dimensional conguration space, the probability of moving from X0 to XlRalong this path using no greater than k steps can be represented asProb (X0; XlR ; k; T; jNXi j ; 0 i lR)= G (X0; XlR ; k; T; jNXi j ; 0 i lR) A (X0; XlR ; k; T; jNXi j ; 0 i lR) (29)For SSA we haveG (X0 ; XlR ; lR; T; jNX SSA j ; 0 i lR) =1lR!jNX SSA jRcXki ? cXli?1A (X0 ; XlR ; lR; T; jNX SSA j ; 0 i lR) = exp ? T1Xi=1(30)!(31)Xin Yao: Simulated Annealing with Extended Neighbourhood9For SA with neighbourhood NX m, as indicated before, function A is decided bythe problem and is the same as (31),R(32)cXki ? cXli?1A (X0; XlR ; lR; T; jNX mj ; 0 i lR) = exp ? T1i=1while from (28) and with analyses similar to before, we can getXG (X0; XlR ; lR; T; jNX mj ; 0 i lR)lRm1> jN jXmlRm1 (jNmX SSA j)lR1= jNX SSA j!!!!wherelR mHence we get the nal result: For lR m,(33)(34)Prob (X0 ; XlR ; lR; T; jNX m j ; Xi 2 S; 0 i lR)> Prob (X0 ; XlR ; lR; T; jNX SSA j ; Xi 2 S; 0 i lR)Since we have the above inequality for each path leading from a non-global minimum X0 to a global minimum XlR in the n-dimensional conguration space, it iseasy to show that the total probability of SA with neighbourhood jNX m j of movingfrom X0 to XlR by various paths is greater than that of SSA with neighbourhoodjNX SSA j.Q.E.D.It seems from Theorem 3.1 that the larger the neighbourhood is, the better.
Butthere is a precondition to this assertion, i.e., condition (34), which says that theassertion is true if the global minimum is far enough from the current conguration.Fortunately, the probability that a randomly generated initial conguration is veryclose to a global minimum is quite small in practice. It is certainly worth extendingSA's neighbourhood in the early stages of the annealing search. However, with theprogress of search, the current conguration is likely to move closer and closer towardsa global minimum. So it is necessary to restrict SA's neighbourhood in the later stagesof the annealing search.
Section 5 will describe an SA with dynamic generationand acceptance probabilities, which can gradually reduce its neighbourhood with thedecrease of temperature.Xin Yao: Simulated Annealing with Extended Neighbourhood10X := X0;f X0 is the initial conguration. gn := 0;f X is the current conguration. gTn := T0;f T0 is the initial temperature gREPEATREPEATY := generate(X; Tn);IF accept(X; Y; Tn) THEN X := YUNTIL `inner-loop stop criterion' satised;Tn+1 := update (Tn);n := n + 1UNTIL `outer-loop stop criterion' satisedFigure 3: General simulated annealing.4 A General Model of Simulated AnnealingSection 3 has shown the benet of extending SA's neighbourhood, but in doing thiscan we not only reduce the computation time but also guarantee the convergence ofSA? Instead of assuming that SA's generation probability is independent of temperature, we make no restrictions on SA's generation and acceptance probabilities in thissection and analyze the convergence conditions of SA.A general SA can be described by Figure 3.
Function generate (X; Tn ) is described by the generation probability gXY (Tn), which is the probability of generatingconguration Y from conguration X at temperature Tn. Function accept (X; Y; Tn )is described by the acceptance probability aXY (Tn), which is the probability of accepting conguration Y after it has been generated at temperature Tn. Functionupdate (Tn) represents the rate of the temperature decrease. The convergence of SAis fully determined by the above three functions, although parameters such as initialtemperature, initial conguration, inner-loop stop criterion, and outer-loop stop criterion can sometimes have signicant practical eects on the nite-time behaviour ofSA.4.1 PreliminariesBefore looking at the conditions which make SA, shown in Figure 3, converge to globalminima, we rst introduce some denitions and theorems.
The results presented inXin Yao: Simulated Annealing with Extended Neighbourhood11this subsection can be found in [21, 13, 22].Denition 4.1 A class F C 1 of functions dened on (0; 1] is a closed class ofasymptotically monotone functions (CAM) if(1) f 2 F =) f 0 2 F and ?f 2 F ;(2) f; g 2 F =) (f + g) and (f g ) 2 F ; and(3) all f 2 F change signs nitely often on (0; 1].Denition 4.2 A class F of functions dened on (0; 1] is a rationally closed class ofbounded variation (RCBV) if(1) f 2 F =) f is of bounded variation on (0; 1];(2) f 2 F =) ?f 2 F ;(3) f; g 2 F =) (f + g) and (f g ) 2 F ; and(4) f; g 2 F with (f=g) bounded on (0; 1] =) f=g is of bounded variation.Denition 4.3 A real-valued function f is an exponential sum in 1=x if it is of theform nj=1 Qj (1=x) ej=x, with j a given real number and Qj () a given polynomial(j = 1; 2; ; n).PDenition 4.4 A real-valued function f is an exponential rational in 1=x if it is theratio of two exponential sums in 1=x.Proposition 4.1 The following classes of functions dened on (0; 1] are RCBV andCAM:(1) the polynomials (RCBV) and (CAM);(2) the rational functions (RCBV) and (CAM);(3) the piecewise rationals (RCBV), and(4) the exponential rationals (CAM).Denition 4.5 Let fu(n)g1n=1 be a sequence with u(n) 2 Rm for some m 1.
The(vector) function ~u(v) : (0; 1] ! Rm is an extension of the sequence if ~u(vn) = u(n)for some sequence fvn g1n=1 , with limn!1 vn = 0.Denition 4.6 A nonstationary Markov chain fP (n)g1n=1 is said to have the regularextension P () if a real number v0 > 0 exists such that the collection of subchains ofP (v) is identical for all v < v0.Proposition 4.2 A nonstationary Markov chain fP (n)g1n=1 is said to have the regular extension P () if a real number v0 > 0 exists such that (i; j ) j pij (v) > 0 isnidentical for all v < v0.oXin Yao: Simulated Annealing with Extended Neighbourhood12Theorem 4.1 Let fP (n)g1n=1 be a weakly ergodic nonstationary Markov chain andP (v) a regular extension such that all entry functions pij (v) (1 i; j N ) belong toCAM 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) with limn!1 (n) = and limn!1 pij (m; n) = j for all 1 i; j N and m 1.Theorem 4.2 Let fXn g be a nonstationary Markov chain with transition matricesfPn g1n=1. The chain fXng is weakly ergodic if and only if there exists a subdivisionof P1 P2 P3 into blocks of matrices [P1 P2 Pn1 ] [Pn1 +1 Pn1 +2 Pn2 ] Pnj +1 Pnj +2 Pnj+1 such thathi1Xj =0 (P (nj ; nj+1)) = 1where n0 = 0.4.2 Convergence of the general simulated annealingThis subsection considers the conditions under which the general SA converges.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
