Stochastic Adaptive Search for Global Optimization

1. Front Matter

   Pages i-xviii

   PDF

2. Introduction

   • Zelda B. Zabinsky

   Pages 1-23

3. Pure Random Search and Pure Adaptive Search

   • Zelda B. Zabinsky

   Pages 25-54

4. Hesitant Adaptive Search

   • Zelda B. Zabinsky

   Pages 55-81

5. Annealing Adaptive Search

   • Zelda B. Zabinsky

   Pages 83-104

6. Backtracking Adaptive Search

   • Zelda B. Zabinsky

   Pages 105-128

7. Hit-and-Run Based Algorithms

   • Zelda B. Zabinsky

   Pages 129-176

8. Engineering Design Applications

   • Zelda B. Zabinsky

   Pages 177-208

9. Back Matter

   Pages 209-224

   PDF

The field of global optimization has been developing at a rapid pace. There is a journal devoted to the topic, as well as many publications and notable books discussing various aspects of global optimization. This book is intended to complement these other publications with a focus on stochastic methods for global optimization. Stochastic methods, such as simulated annealing and genetic algo­ rithms, are gaining in popularity among practitioners and engineers be­ they are relatively easy to program on a computer and may be cause applied to a broad class of global optimization problems. However, the theoretical performance of these stochastic methods is not well under­ stood. In this book, an attempt is made to describe the theoretical prop­ erties of several stochastic adaptive search methods. Such a theoretical understanding may allow us to better predict algorithm performance and ultimately design new and improved algorithms. This book consolidates a collection of papers on the analysis and de­ velopment of stochastic adaptive search. The first chapter introduces random search algorithms. Chapters 2-5 describe the theoretical anal­ ysis of a progression of algorithms. A main result is that the expected number of iterations for pure adaptive search is linear in dimension for a class of Lipschitz global optimization problems. Chapter 6 discusses algorithms, based on the Hit-and-Run sampling method, that have been developed to approximate the ideal performance of pure random search. The final chapter discusses several applications in engineering that use stochastic adaptive search methods.

• algorithms
• complexity
• global optimization
• operations research
• optimization
• combinatorics

• University of Washington, Seattle, USA

  Zelda B. Zabinsky

Policies and ethics