BOUNDING THE PROBABILITY OF SUCCESS OF STOCHASTIC METHODS FOR GLOBAL OPTIMIZATION

In this paper, we establish some bounds for the probability that simulated annealing produces an optimal or near-optimal solution. Such bounds are given for both asymptotical and finite number of steps in the algorithm, and they depend only on the instance of the problem to be treated. Then we compare its performance with a randomized local search, showing that actually simulated annealing behaves worse than such a very simple global optimization technique. Furthermore, since many parallel implementations of simulated annealing exist, we also address its behavior in the parallel model of computation. Even in this case, similar bounds hold and we can prove that the most simple parallel version of randomized local search is more likely to find optimal or near-optimal solutions than any version of parallel simulated annealing.