Chapter 8 Theory and Practice of simulated Annealing (1121211), страница 2
Текст из файла (страница 2)
Belisle (1992) presents aspecial simulated annealing algorithm for global optimization, which uses a heuristically motivated cooling schedule. This algorithm is easy to implement and provides areasonable alternative to existing methods.Belisle et al. (1993) discusses convergence properties of simulated annealingalgorithms applied to continuous functions and applies these results to hit-and-runalgorithms used in global optimization. His convergence properties are consistentThe Theory and Practice of Simulated Annealing291with those presented by Hajek (1988) and he provides a good contrast between convergence in probability and the stronger almost sure convergence.
Zabinsky et al.(1993) extends this work to an improved hit-and-run algorithm used for globaloptimization.Fleischer and Jacobson (1996) proposes cybernetic optimization by simulatedannealing as a method of parallel processing that accelerated the convergence of simulated annealing to the global optima. Fleischer (1999) extends the theory of cyberneticoptimization by simulated annealing into the continuous domain by applying probabilistic feedback control to the generation of candidate solutions.
The probabilisticfeedback control method of generating candidate solutions effectively accelerates convergence to a global optimum using parallel simulated annealing on continuous variableproblems.Locatelli (1996) presents convergence properties for a class of simulated annealingalgorithms for continuous global optimization by removing the restriction that the nextcandidate point must be generated according to a probability distribution whose supportis the whole feasible set.
Siarry et al. (1997) studies simulated annealing algorithmsfor globally minimizing functions of many-continuous variables. Their work focuseson how high-dimensionality can be addressed using variables discretization, as well asconsidering the design and implementation of several complementary stopping criteria.Yang (2000) and Locatelli (2000) also provide convergence results and criteria forsimulated annealing applied to continuous global optimization problems. Kiatsupaibuland Smith (2000) introduces a general purpose simulated annealing algorithm to solvemixed integer linear programs. The simulated annealing algorithm is constructed usinga Markov chain sampling algorithm to generate uniformly distributed points on anarbitrary bounded region of a high dimensional integer lattice.
They show that theiralgorithm converges in probability to a global optimum. Romeijn et al. (1999) alsostudies a simulated annealing algorithm that uses a reflection generator for mixedinteger/continuous global optimization problems.2CONVERGENCE RESULTSConvergence results for simulated annealing have typically taken one of two directions;either the algorithm has been modeled as a sequence of homogeneous Markov chainsor as a single inhomogeneous Markov chain.The homogeneous Markov chain approach (see, e.g., Aarts and van Laarhoven,1985; Faigle and Kern, 1991; Granville et al., 1994; Johnson and Jacobson, 2002a,b;Lundy and Mees, 1986; Mitra et al., 1986; Rossier et al., 1986) assumes that eachtemperatureis held constant for a sufficient number of iterations m such that thestochastic matrixcan reach its stationary (steady state) distributionNote thatin the interest of simplifying notation, the inner loop index m is suppressed.
However,the index k should be interpreted as the double index k,m, where a sequence ofsimulated annealing iterations occur for each fixed k.) The existence ofa stationary distribution at each iteration k follows from Theorem 10.1. (Note: toensure that Theorem 1 is consistent with the simulated annealing algorithm depictedin Section 1.3, without loss of generality, let be a function only of each outer loopiteration k, and let the respective number of inner loop iterationsand outer loopiterations k each approach infinity).292 D. Henderson et al.Theorem 10.1.
Letbe the probability of moving from solutionto solutionin one inner iteration at outer loop k, and letbe the probabilityof going from solution to solutionin m inner loops. If the Markov chain associated withis irreducible and aperiodic with finitely many solutions, thenexists for alland iterations k. Furthermore,is the unique strictly positive solution ofandProof. See Cinlar (1974)p.
153.The key requirements for the existence of the stationary distributions and for theconvergence of the sequence ofvectors include1. transition matrix irreducibility (for every finite outer loop k, the transition matrixcan assign a path of non-zero probability between any two solutions2. aperiodicity (starting at solutionit is possible to return towithperiod 1. See Isaacson and Madsen (1976),3. a non-zero stationary probability distribution, as the number of outer loops kapproaches infinity.Note that all simulated annealing proofs of convergence in the literature based onhomogeneous Markov chain theory, either explicitly or implicitly, use the sufficientcondition of reversibility (also called detailed balance) (Ross, 1996), defined asReversibility is sufficient condition for a unique solution to exist for (6) and (7)at each outer loop iteration k.
Ross (1997) shows that a necessary condition forreversibility is multiplicativity (i.e., for any three solutionssuch thatand for all iterations k,whereis the probability of accepting the transition from solution to solution at outer loop iteration k). Reversibility is enforced by assuming conditions ofsymmetry on the solution generation probabilities and by either directly expressing theacceptance probability using an exponential form, or by requiring the multiplicativecondition in (9).The homogeneous Markov chain proofs of convergence in the literature (implicitlyor explicitly) require the condition in (9) to hold for the acceptance function, and thenaddress the sufficient conditions on the solution generation matrix.
For example, theoriginal homogeneous proofs of convergence (Aarts and van Laarhoven, 1985; Lundyand Mees, 1986) require the multiplicative condition for the acceptance function, andthen assume that the solution generation function is symmetric and constant for all outerThe Theory and Practice of Simulated Annealing 293loop iterations k.
Rossier et al. (1986) partitions the solution space into blocks composedof neighboring solutions of equal objective function value, and then requires that onlythe solution generation probabilities be symmetric between these blocks. Rossier et al.(1986) then expresses the acceptance function as a ratio of the stationary distributionprobabilities (discussed in Section 2.1.3). Faigle and Schrader (1988) and Faigle andKern (1991) use a graph theoretic approach to relax the solution generation functionsymmetry condition. However, they require that the solution acceptance probabilityfunction satisfies (9).Granville et al. (1994) proposes a simulated annealing procedure for filtering binaryimages, where the acceptance function is based on the probability of the current solution, instead of the change in objective function value.
The probability function thatGranville et al. (1994) present for accepting a candidate solution at (outer loop) iteration k is based on the ratio of the stationary probability of the incumbent solution fromiteration k – 1, versus the stationary probability of an initial solution (which is basedon a maximum likelihood estimate). The acceptance probability iswhere(q must also be estimated), andis aslowly increasing function. Therefore, the probability of a solution transition does notconsider the objective function value of the candidate solution.
Granville et al. (1994)provides a proof of asymptotic convergence of this approach, but note that the proofmethodology does not show that the set of globally optimal solutions are asymptoticallyuniformly distributed.Simulated annealing and the homogeneous convergence theory are based on thework of Metropolis et al. (1953), which addresses problems in equilibrium statisticalmechanics (Hammersley and Handscomb, 1964). To see this relationship, considera system in thermal equilibrium with its surroundings, in solution (state) S withenergy F(S).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
