Adaptive, Asynchronous Stochastic Global Optimization Algorithms for Sequential and Parallel Computation

We discuss new global optimization algorithms that are related to the stochastic methods of Rinnooy Kan and Timmer, and to our previous static, synchronous parallel version of this method. The new algorithms have two main new features. First, they adaptively concentrate the computation in the areas of the domain space that appear most likely to produce the global minimum. Secondly, on parallel computers, they use an asynchronous approach, combined with a central work scheduler, to avoid load balancing problems. We investigate several mechanisms for deciding when and how to make the adaptive adjustments. We also describe both algorithmic and implementation considerations involved in constructing the parallel asynchronous algorithm. Computational tests on sequential and parallel computers show that the adaptive and asynchronous features of our new method can substantially reduce the number of function evaluations, and the execution time, required by previous stochastic methods to solve global optimization problems.