Improving simulated annealing through derandomization

Mathieu Gerber, Luke Bornn

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)
277 Downloads (Pure)

Abstract

We propose and study a version of simulated annealing (SA) on continuous state spaces based on (t,s)R-sequences. The parameter R ∈ Ν regulates the degree of randomness of the input sequence, with the case R=0 corresponding to IID uniform random numbers and the limiting case R=∞ to (t,s)-sequences. Our main result, obtained for rectangular domains, shows that the resulting optimization method, which we refer to as QMC-SA, converges almost surely to the global optimum of the objective function φ for any R ∈ N. When φ is univariate, we are in addition able to show that the completely deterministic version of QMC-SA is convergent. A key property of these results is that they do not require objective-dependentconditions on the cooling schedule. As a corollary of our theoretical analysis, we provide a new almost sure convergence result for SA which shares this property under minimal assumptions on φ. We further explain how our results in fact apply to a broader class of optimization methods including for example threshold accepting, for which to our knowledge no convergence results currently exist. We finally illustrate the superiority of QMC-SA over SA algorithms in a numerical study.
Original languageEnglish
Pages (from-to)189-217
Number of pages29
JournalJournal of Global Optimization
Volume68
Issue number1
Early online date8 Sept 2016
DOIs
Publication statusPublished - May 2017

Keywords

  • Global optimization
  • Quasi-Monte Carlo
  • Randomized quasi-Monte Carlo
  • Simulated annealing
  • Threshold accepting

Fingerprint

Dive into the research topics of 'Improving simulated annealing through derandomization'. Together they form a unique fingerprint.

Cite this