Stochastic comparison algorithm for discrete optimization with estimation

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>