𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bounding the probability of success of stochastic methods for global optimization

✍ Scribed by Afonso G. Ferreira; Janez Žerovnik

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
582 KB
Volume
25
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we estabfish some bounds for the probability that simulated annealing produces an optimal or near-optlmal solution. Such bounds are giveat for both asymptotical and finite mlmher 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 implementatiolm of simulated annealing exist, we also address its behavior in the parallel model of computation. Even in this case, similar bounds bold and we can prove that the moat simple parallel version of randomized local search is more likely to find optimal or near-optimal solutions than any version of parallel simulated annealing.

📜 SIMILAR VOLUMES

Successive approximation methods for the
Successive approximation methods for the solution of optimal control problems
✍ S.K. Mitter 📂 Article 📅 1966 🏛 Elsevier Science 🌐 English ⚖ 801 KB

IN THIS paper we present some successive approximation methods for the solution of a general class of optimal control problems. The class of problems considered is known as the Bolxa Problem in the Calculus of Variations [l]. The algorithms considered are extensions of the gradient methods due to KE

Discrete stochastic optimization using v
Discrete stochastic optimization using variants of the stochastic ruler method
✍ Mahmoud H. Alrefaei; Sigrún Andradóttir 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB

## Abstract We present two random search methods for solving discrete stochastic optimization problems. Both of these methods are variants of the stochastic ruler algorithm. They differ from our earlier modification of the stochastic ruler algorithm in that they use different approaches for estimat