Chapter 8 Theory and Practice of simulated Annealing (1121211), страница 8
Текст из файла (страница 8)
All generalized hill climbing algorithms have the same basicstructure, but can be tailored to a specific instance of a problem by changing thehill-climbing random variable (which is used to accept or reject inferior solutions)and neighborhood functions. Generalized hill climbing algorithms are described inpseudo-code form:Select an initial solutionSet the outer loop counter bound K and the inner loop counter boundsDefine a set of hill-climbing (random) variables310D. Henderson et al.Set the iteration indices k = m = 1Repeat whileRepeat whileGenerate a solutionCalculateIfthenIfthenUntil k = KNote that the outer and inner loop bounds, K andrespectively,may all be fixed, or K can be fixed with thedefined as randomvariables whose values are determined by the solution at the end of each set of innerloop iterations satisfying some property (e.g., the solution is a local optima).Generalized hill climbing algorithms can be viewed as sampling procedures overthe solution spaceThe key distinction between different generalized hill climbingalgorithm formulations is in how the sampling is performed.
For example, simulatedannealing produces biased samples, guided by the neighborhood function, the objectivefunction, and the temperature parameter. More specifically, simulated annealing can bedescribed as a generalized hill climbing algorithm by setting the hill-climbing randomvariable,and theareindependent and identically distributed U(0,1) random variables. To formulate MonteCarlo search as a generalized hill climbing algorithm, setDeterministic local search accepts only neighbors ofimproving (lower) objective function value and can be expressed as a generalized hillclimbing algorithm withOtheralgorithms that can be described using the generalized hill climbing framework includethreshold accepting (1990) some simple forms of tabu search (1997), and Weibullaccepting.
Jacobson et al. (1998), Sullivan and Jacobson (2001), and Johnson andJacobson (2002b) provide a complete discussion of these algorithms and a descriptionof how these algorithms fit into the generalized hill climbing algorithm framework.5.2Convergence versus Finite-Time PerformanceThe current literature focuses mainly on asymptotic convergence properties of simulated annealing algorithms (Section 2 outlines and describes several of these results);however, considerable work on finite-time behavior of simulated annealing has beenpresented over the past decade.
Chiang and Chow (1989) and Mazza (1992) investigate the statistical properties of the first visit time to a global optima which providesinsight into the time-asymptotic properties of the algorithm as the outer loop counter,Catoni (1996) investigates optimizing a finite-horizon cooling schedule tomaximize the number of visits to a global optimum after a finite number of iterations.Desai (1999) focuses on finite-time performance by incorporating size-asymptoticinformation supplied by certain eigenvalues associated with the transition matrix. Desaiprovides some quantitative and qualitative information about the performance of simulated annealing after a finite number of steps by observing the quality of solutionsrelated to the number of steps that the algorithm has taken.The Theory and Practice of Simulated Annealing311Srichander (1995) examines the finite-time performance of simulated annealingusing spectral decomposition of matrices.
He proposes that an annealing scheduleon the temperature is not necessary for the final solution of the simulated annealingalgorithm to converge to the global minimum with probability one. Srichander showsthat initiating the simulated annealing algorithm with high initial temperatures producesan inefficient algorithm in the sense that the number of function evaluations requiredto obtain a global minima is very large. A modified simulated annealing algorithm ispresented with a low initial temperature and an iterative schedule on the size of theneighborhood sets that leads to a more efficient algorithm.
The new algorithm is appliedto a real-world example and performance is reported.Fleischer and Jacobson (1999) uses a reverse approach to establish theoretical relationships between the finite-time performance of an algorithm and the characteristicsof problem instances. They observe that the configuration space created by an instanceof a discrete optimization problem determines the efficiency of simulated annealingwhen applied to that problem. The entropy of the Markov chain embodying simulatedannealing is introduced as a measure that captures the entire topology of the configuration space associated with the particular instance of the discrete optimization problem.By observing the expected value of the final state in a simulated annealing algorithmas it relates to the entropy value of the underlying Markov chain, the article presentsmeasures of performance that determine how well the simulated annealing algorithmperforms in finite-time.
Their computational results suggest that superior finite-timeperformance of a simulated annealing algorithm are associated with higher entropymeasures.5.3ExtensionsThe popularity of simulated annealing has spawned several new annealing-like algorithms. Pepper et al. (2000) introduce demon algorithms and test them on the travelingsalesman problem. Ohlmann and Bean (2000) introduce another variant of simulatedannealing termed compressed annealing. They incorporate the concepts of pressureand volume, in addition to temperature, to address discrete optimization problems withrelaxed constraints. They also introduce a primal/dual meta-heuristic by simultaneouslyadjusting temperature and pressure in the algorithm.Much work continues in the area of convergence and comparing the performance ofsimulated annealing algorithms to other local search strategies.
Jacobson and Yücesan(2002b) presents necessary and sufficient (asymptotic) convergence conditions for generalized hill climbing algorithms that include simulated annealing as a special case.They also introduce new performance measures that can be used to evaluate and compare both convergent and non-convergent generalized hill climbing algorithms withrandom restart local search (Jacobson, 2002). Such a comparison provides insightsinto both asymptotic and finite-time performance of discrete optimization algorithms.For example, they use the global visit probability to evaluate the performance of simulated annealing using random restart local search as a benchmark.
These results suggestthat random restart local search may outperform simulated annealing provided that asufficiently large number of restarts are executed. Ferreira and Zerovnik (1993) developbounds on the probability that simulated annealing obtains an optimal (or near-optimal)solution, and use these bound to obtain similar results for random restart local searchand simulated annealing. Fox (1994) notes that this result is only true if both the number312D. Henderson et al.of accepted and rejected moves are counted. Fox (1994) also provides a clever example to illustrate this point, and notes that comparing random restart local search andsimulating annealing may not be prudent. Fox (1993, 1995) presents modifications ofsimulated annealing that circumvent this counting issue, hence yielding superior performing simulated annealing algorithm implementations.
The primary value of usingsimulated annealing may therefore be for finite-time executions that obtain near-optimalsolutions reasonably quickly. This, in turn, suggests that one should focus on the finitetime behavior of simulated annealing rather than the asymptotic convergence resultsthat dominate the literature.ACKNOWLEDGEMENTSThis work is supported in part by the Air Force Office of Scientific Research (F4962001-1-0007) and the National Science Foundation (DMI-9907980).BIBLIOGRAPHYAarts, E.H.L. and Korst, J. (1989) Simulated Annealing and Boltzmann Machines: AStochastic Approach to Combinatorial Optimization and Neural Computing.
JohnWiley & Sons, Chichester, England.Aarts, E.H.L. and Lenstra, J.K. (1997) Local Search in Combinatorial Optimization.John Wiley & Sons, Chichester, England.Aarts, E.H.L. and van Laarhoven, P.J.M. (1985) Statistical cooling: A general approachto combinatorial optimization problems. Phillips Journal of Research, 40, 193–226.Abramson, D., Krishnamoorthy, M. and Dang, H.
(1999) Simulated annealing coolingschedules for the school timetabling problem. Asia-Pacific Journal of OperationalResearch, 16, 1–22.Alrefaei, M.H. and Andradottir, S. (1999) A simulated annealing algorithm with constant temperature for discrete stochastic optimization. Management Science, 45,748–764.Althofer, I.
and Koschnick, K.U. (1991) On the convergence of threshold accepting.Applied Mathematics and Optimization, 24, 183–195.Aluffi-Pentini, F., Parisi, V. and Zirilli, F. (1985) Global optimization and stochasticdifferential equations. Journal of Optimization Theory and Applications, 47, 1–16.Anily, S. and Federgruen, A. (1987) Simulated annealing methods with generalacceptance probabilities.
Journal of Applied Probability, 24, 657–667.Belisle, C.J.P. (1992) Convergence theorems for a class of simulated annealingalgorithms on. Journal of Applied Probability, 29, 885–895.Belisle, C.J.P, Romeijn, H.E. and Smith, R.L. (1993) Hit-and-run algorithms forgenerating multivariate distributions. Mathematics of Operations Research, 18,255–266.Bohachevsky, I.O., Johnson, M.E. and Stein, M.L. (1986) Generalized simulatedannealing for function optimization. Technometrics, 28, 209–217.The Theory and Practice of Simulated Annealing 313Borkar, V.S. (1992) Pathwise recurrence orders and simulated annealing.
Journal ofApplied Probability, 29, 472–476.Bratley, P., Fox, B.L. and Schrage, L. (1987) A Guide to Simulation, Springer-Verlag,New York.Cardoso, M.F., Salcedo, R.L. and de Azevedo, S.F. (1994) Nonequilibrium simulatedannealing: a faster approach to combinatorial minimization.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
