Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010038886 | QA274 Z32 2003 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
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.
Table of Contents
List of Figures | p. xi |
List of Tables | p. xv |
Preface | p. xvii |
1. Introduction | p. 1 |
1 Classification of Optimization Problems | p. 2 |
2 Types of Algorithms | p. 4 |
3 Definitions and Assumptions | p. 5 |
3.1 Assumptions for Continuous Problems | p. 7 |
3.2 Assumptions for Discrete Problems | p. 8 |
3.3 Mixed Continuous-discrete Problems | p. 9 |
4 Overview of Random Search Methods | p. 9 |
4.1 Enumeration or Exhaustive Search | p. 10 |
Grid Search | p. 10 |
Pure Random Search | p. 11 |
Other Covering Methods | p. 11 |
4.2 Sequential Random Search | p. 11 |
Simulated Annealing | p. 12 |
Step Size Algorithms | p. 16 |
Convergence | p. 17 |
4.3 Two-Phase Methods | p. 19 |
4.4 Genetic Algorithms | p. 20 |
4.5 Other Stochastic Methods | p. 21 |
5 Overview of this Book | p. 22 |
6 Summary | p. 22 |
2. Pure Random Search and Pure Adaptive Search | p. 25 |
1 Pure Random Search (PRS) | p. 25 |
2 Pure Adaptive Search (PAS) | p. 30 |
3 Comparison of PRS and PAS | p. 33 |
4 Distribution of Improvement for PAS | p. 37 |
4.1 Continuous PAS Distribution | p. 37 |
4.2 Finite PAS Distribution | p. 42 |
5 Linearity Result for PAS | p. 45 |
6 Summary | p. 54 |
3. Hesitant Adaptive Search | p. 55 |
1 Hesitant Adaptive Search (HAS) | p. 56 |
2 Number of HAS Iterations to Convergence | p. 57 |
2.1 Continuous HAS Distribution | p. 58 |
2.2 Discrete HAS Distribution | p. 62 |
2.3 General HAS Distribution | p. 64 |
3 Numerical Examples of HAS | p. 67 |
4 Combination of PRS and PAS, (1-p)PRS+pPAS | p. 70 |
4.1 Continuous PRS and PAS Combination | p. 73 |
4.2 Discrete PRS and PAS Combination | p. 75 |
5 Summary | p. 80 |
4. Annealing Adaptive Search | p. 83 |
1 Annealing Adaptive Search (AAS) | p. 84 |
2 Bounds on Performance of Annealing Adaptive Search | p. 89 |
3 Cooling Schedule for Annealing Adaptive Search | p. 98 |
4 Summary | p. 104 |
5. Backtracking Adaptive Search | p. 105 |
1 Mixed Backtracking Adaptive Search (Mixed BAS) | p. 106 |
2 Discrete Backtracking Adaptive Search (Discrete BAS) | p. 111 |
2.1 Markov Chain Models of Discrete BAS | p. 114 |
2.2 Range embedded Markov chain model | p. 117 |
2.3 Examples of Discrete BAS | p. 122 |
3 Summary | p. 128 |
6. Hit-and-Run Based Algorithms | p. 129 |
1 Hit-and-Run | p. 130 |
1.1 Implementation of Hit-and-Run | p. 131 |
1.2 Convergence to Uniform Distribution | p. 133 |
1.3 Metropolis Hit-and-Run | p. 136 |
1.4 Rate of Convergence to Target Distribution | p. 139 |
2 Improving Hit-and-Run (IHR) | p. 140 |
2.1 Definition of Improving Hit-and-Run | p. 141 |
2.2 Polynomial Performance of IHR | p. 143 |
2.3 Discussion | p. 159 |
3 Hide-and-Seek | p. 159 |
3.1 Definition of Hide-and-Seek | p. 160 |
3.2 Acceptance Criterion and Cooling Schedule | p. 161 |
3.3 Convergence of Hide-and-Seek | p. 162 |
4 Extensions to Hit-and-Run Based Optimization Methods | p. 163 |
4.1 Variations to Direction Generator | p. 164 |
4.2 Discrete Variations of Hit-and-Run | p. 166 |
Step-function Approach | p. 167 |
Rounding Approach | p. 168 |
Discrete Biwalk Hit-and-Run | p. 168 |
5 Computational Results | p. 171 |
6 Summary | p. 176 |
7. Engineering Design Applications | p. 177 |
1 Formulating Global Optimization Problems | p. 179 |
1.1 Hierarchical Formulation | p. 179 |
1.2 Penalty Formulation | p. 181 |
2 Fuel Allocation Problem | p. 182 |
3 Truss Design Problem | p. 184 |
3.1 Three-Bar Truss Design | p. 184 |
3.2 Ten-Bar Truss Design | p. 186 |
4 Optimal Design of Composite Structures | p. 188 |
4.1 Optimal Design of a Composite Stiffened Panel | p. 190 |
4.2 Extensions to Larger Structures | p. 196 |
5 Summary | p. 207 |
References | p. 209 |
Index | p. 223 |