×

Simulated annealing for discrete optimization with estimation. (English) Zbl 1009.90076

Summary: We extend the basic convergence results for the Simulated Annealing (SA) algorithm to a stochastic optimization problem where the objective function is stochastic and can be evaluated only through Monte Carlo simulation (hence, disturbed with random error). This extension is important when either the objective function cannot be evaluated exactly or such an evaluation is computationally expensive. We present a modified SA algorithm and show that under suitable conditions on the random error, the modified SA algorithm converges in probability to a global optimizer. Computational results and comparisons with other approaches are given to demonstrate the performance of the proposed modified SA algorithm.

MSC:

90C15 Stochastic programming
90C40 Markov and semi-Markov decision processes
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gross, D.; Miller, D. R.; Soland, R. M., A closed queueing network model for multi-echelon repairable item provisioning, IIE Transactions, 15, 344-352 (1983)
[2] Gross, D.; Miller, D. R., Multi-echelon repairable item provisioning in a time-varying environment using the randomization technique, Naval Research Logistics Quarterly, 31, 347-361 (1984) · Zbl 0544.90042
[5] Haddock, J.; Mittenthal, J., Simulation optimization using simulated annealing, Computers and Industrial Engineering, 20, 4, 387-395 (1992)
[9] Gelfand, S. B.; Mitter, S. K., Simulated annealing with noisy or imprecise energy measurements, Journal of Optimization Theory and Applications, 62, 49-62 (1989) · Zbl 0651.90059
[10] Gutjahr, W. J.; Pflug, G. C., Simulated annealing for noisy cost functions, Journal of Global Optimization, 8, 1-13 (1996) · Zbl 0857.90095
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.