Stochastic comparison algorithm for discrete optimization with estimation
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 795-800
- https://doi.org/10.1109/cdc.1992.371616
Abstract
An iterative discrete optimization algorithm that works with Monte Carlo estimation of the objective function is developed. Two algorithms, the simulated annealing algorithm and the stochastic ruler algorithm, are considered. The authors examine some of the problems of their use and combine the advantages of both algorithms to form an iterative random search algorithm called the stochastic comparison (SC) algorithm. The SC algorithm actually solves an alternative optimization problem, and it is shown under symmetry assumption that the alternative problem is equivalent to the original one. The convergence of the SC algorithm is proved based on time-inhomogeneous Markov chain theory. Results of numerical experiments on a testbed problem with randomly generated objective function are presented Author(s) Gong, W.-B. Dept. of Electr. & Comput. Eng., Massachusetts Univ., Amherst, MA, USA Ho, Y.-C. ; Zhai, W.Keywords
This publication has 4 references indexed in Scilit:
- Ordinal optimization of DEDSDiscrete Event Dynamic Systems, 1992
- Stochastic Discrete OptimizationSIAM Journal on Control and Optimization, 1992
- A tutorial survey of theory and applications of simulated annealingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Convergence and finite-time behavior of simulated annealingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985