The Library
Optimal sampling for simulated annealing under noise
Tools
Ball, Robin, Branke, Jürgen and Meisel, Stephan (2018) Optimal sampling for simulated annealing under noise. INFORMS Journal on Computing, 30 (1). pp. 200-215. doi:10.1287/ijoc.2017.0774 ISSN 1091-9856.
|
PDF
WRAP-optimal-sampling-annealing-noise-Ball-2017.pdf - Accepted Version - Requires a PDF viewer. Download (1318Kb) | Preview |
Official URL: https://doi.org/10.1287/ijoc.2017.0774
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 nd the solution with the best expected performance, as for example 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 finally 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 e ciency 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 still preserves detailed balance. An empirical evaluation shows that the resulting approach is indeed more efficient than several previously proposed Simulated Annealing variants.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Physics Faculty of Social Sciences > Warwick Business School |
||||||
Library of Congress Subject Headings (LCSH): | Heuristic algorithms., Simulated annealing (Mathematics), Computer software., Computational intelligence. | ||||||
Journal or Publication Title: | INFORMS Journal on Computing | ||||||
Publisher: | Institute for Operations Research and the Management Sciences (I N F O R M S) | ||||||
ISSN: | 1091-9856 | ||||||
Official Date: | 6 February 2018 | ||||||
Dates: |
|
||||||
Volume: | 30 | ||||||
Number: | 1 | ||||||
Page Range: | pp. 200-215 | ||||||
DOI: | 10.1287/ijoc.2017.0774 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 28 June 2017 | ||||||
Date of first compliant Open Access: | 19 April 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year