Optimal Sampling for Simulated Annealing Under Noise

Robin C. Ball (), Juergen Branke () and Stephan Meisel ()
Additional contact information
Robin C. Ball: Department of Physics, University of Warwick, Coventry, CV4 7AL, United Kingdom
Juergen Branke: Warwick Business School, University of Warwick, Coventry, CV4 7AL, United Kingdom
Stephan Meisel: Münster School of Business and Economics, University of Münster, 48149 Münster, Germany

INFORMS Journal on Computing, 2018, vol. 30, issue 1, 200-215

Abstract: This paper proposes a simulated annealing variant for optimization problems in which the solution quality can only be estimated by sampling from a random distribution. The aim is to find the solution with the best expected performance, as, e.g., is typical for problems where solutions are evaluated using a stochastic simulation. Assuming Gaussian noise with known standard deviation, we derive a fully sequential sampling procedure and decision rule. The procedure starts with a single sample of the value of a proposed move to a neighboring solution and then continues to draw more samples until it is able to make a decision to accept or reject the move. Under constraints of equilibrium detailed balance at each draw, we find a decoupling between the acceptance criterion and the choice of the rejection criterion. We derive a universally optimal acceptance criterion in the sense of maximizing the acceptance probability per sample and thus the efficiency of the optimization process. We show that the choice of the move rejection criterion depends on expectations of possible alternative moves and propose a simple and practical (albeit more empirical) solution that preserves detailed balance. An empirical evaluation shows that the resulting approach is indeed more efficient than several previously proposed simulated annealing variants.

Keywords: heuristic: simulated annealing; simulation optimization; simulation: statistical analysis; statistics: sampling (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0774 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:1:p:200-215

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().