Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-08T20:27:49.511Z Has data issue: false hasContentIssue false
  • English
  • Français

Restarting search algorithms with applications to simulated annealing

Part of: Markov processes Special processes Stochastic processes

Published online by Cambridge University Press:  01 July 2016

F. Mendivil ,
R. Shonkwiler  and
M. C. Spruill
F. Mendivil*
Affiliation:
Georgia Institute of Technology
R. Shonkwiler*
Affiliation:
Georgia Institute of Technology
M. C. Spruill*
Affiliation:
Georgia Institute of Technology
*
∗ Current address: Department of Mathematics and Statistics, Acadia University, Wolfville, Nova Scotia, Canada, B0P 1X0.
∗∗ Postal address: School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA.
∗∗ Postal address: School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Some consequences of restarting stochastic search algorithms are studied. It is shown under reasonable conditions that restarting when certain patterns occur yields probabilities that the goal state has not been found by the nth epoch which converge to zero at least geometrically fast in n. These conditions are shown to hold for restarted simulated annealing employing a local generation matrix, a cooling schedule Tn ∼ c/n and restarting after a fixed number r + 1 of duplications of energy levels of states when r is sufficiently large. For simulated annealing with logarithmic cooling these probabilities cannot decrease to zero this fast. Numerical comparisons between restarted simulated annealing and several modern variations on simulated annealing are also presented and in all cases the former performs better.

Keywords

random searchstochastic process renewalcoding scheduleminimization

MSC classification

Primary: 60K20: Applications of Markov renewal processes (reliability, queueing networks, etc.) 60G35: Signal detection and filtering 60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) 65K10: Optimization and variational techniques
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 33 , Issue 1 , March 2001 , pp. 242 - 259
Copyright
Copyright © Applied Probability Trust 2001 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aarts, E. and Korst, J. (1989). Simulated Annealing and the Boltzmann Machines. John Wiley, Chichester.Google Scholar
Andresen, B. (1996). Finite-time thermodynamics and simulated annealing. In Entropy and Entropy Generation, ed. Shinov, J. S.. Kluwer, Dordrecht, pp. 111–127.Google Scholar
Andresen, B. and Gordon, J. M. (1994). Constant thermodynamic speed for minimizing entropy production in thermodynamic processes and simulated annealing. Phys. Rev. E 50, 4346–4351.Google Scholar
Atkinson, A. C. (1992). A segmented algorithm for simulated annealing. Statist. Comput. 2, 221–230.CrossRefGoogle Scholar
Bélisle, C., (1992). Convergence theorems for a class of simulated annealing algorithms on Rd . J. Appl. Prob. 29, 885–895.Google Scholar
Bixby, B. and Reinelt, G. (1995). TSPLIB. Available at http://softlib.rice.edu/softlib/tsplib/.Google Scholar
Chiang, T. and Chow, Y. (1988). On the convergence rate of annealing processes. SIAM J. Control Optimization 26, 1455–1470.Google Scholar
Feller, W. (1968). An Introduction to Probability Theory. John Wiley, New York.Google Scholar
Fox, B. (1995). Faster simulated annealing. SIAM J. Optimization 5, 488–505.Google Scholar
Fox, B. and Heine, G. (1995). Probabilistic search with overrides. Ann. Appl. Prob. 5, 1087–1094.Google Scholar
Hajek, B. (1988). Cooling schedules for optimal annealing. Math. Operat. Res. 13, 311–329.Google Scholar
Hu, X., Shonkwiler, R. and Spruill, M. (1997). Randomized restarts. Submitted.Google Scholar
Kolonko, M. (1995). A piecewise Markovian model for simulated annealing with stochastic cooling schedules. J. Appl. Prob. 32, 649–658.Google Scholar
Nakakuki, Y. and Sadeh, N. (1994). Increasing the efficiency of simulated annealing search by learning to recognize (un)promising runs. In Proc. 12th Nat. Conf. Artificial Intelligence, Seattle, WA, Vol. 2, pp. 1316–1322.Google Scholar
Niemiro, W. (1995). Tail events of simulated annealing Markov chains. J. Appl. Prob. 32, 867–876.Google Scholar
Nourani, Y. and Andresen, B. (1998). A comparison of simulated annealing cooling strategies. J. Phys. A 31, 8373–8385.Google Scholar
Nourani, Y. and Andresen, B. (1999). Exploration of NP-hard enumeration problems by simulated annealing—the spectrum values of permanents. Theoret. Comput. Sci. 215, 51–68.Google Scholar
Nulton, J. D. and Salamon, P. (1988). Statistical mechanics of combinatorial optimization. Phys. Rev. A 37, 1351–1356.CrossRefGoogle ScholarPubMed
Schoen, F. (1991). Stochastic techniques for global optimization: a survey of recent advances. J. Global Optimization 1, 207–228.Google Scholar
Shonkwiler, R. and van Vleck, E. (1994). Parallel speed-up of Monte Carlo methods for global optimization. J. Complexity 10, 64–95.Google Scholar
Theodosopoulos, T. V. (1999). Some remarks on the optimal level of randomization in global optimization. In Randomization Methods in Algorithm Design (DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 43), ed. Pardalos, P.. Amer. Math. Soc., Providence, RI, pp. 303–318.Google Scholar
Tsitiklis, J. N. (1989). Markov chains with rare transitions and simulated annealing. Math. Operat. Res. 14, 70–90.CrossRefGoogle Scholar
Van Laarhoven, P. and Aarts, E. (1987). Simulated Annealing: Theory and Applications. Reidel, Boston.Google Scholar