Stochastic Adaptive Search for Global OptimizationThe 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. |
Contents
INTRODUCTION | 1 |
1 Classification of Optimization Problems | 2 |
2 Types of Algorithms | 4 |
3 Definitions and Assumptions | 5 |
31 Assumptions for Continuous Problems | 7 |
32 Assumptions for Discrete Problems | 8 |
33 Mixed Continuousdiscrete Problems | 9 |
41 Enumeration or Exhaustive Search | 10 |
1 Mixed Backtracking Adaptive Search Mixed BAS | 106 |
2 Discrete Backtracking Adaptive Search Discrete BAS | 111 |
21 Markov Chain Models of Discrete BAS | 114 |
22 Range embedded Markov chain model | 117 |
23 Examples of Discrete BAS | 122 |
3 Summary | 128 |
HITANDRUN BASED ALGORITHMS | 129 |
1 HitandRun | 130 |
Pure Random Search | 11 |
Simulated Annealing | 12 |
Step Size Algorithms | 16 |
Convergence | 17 |
43 TwoPhase Methods | 19 |
44 Genetic Algorithms | 20 |
45 Other Stochastic Methods | 21 |
5 Overview of this Book | 22 |
PURE RANDOM SEARCH AND PURE ADAPTIVE SEARCH | 25 |
2 Pure Adaptive Search PAS | 30 |
3 Comparison of PRS and PAS | 33 |
4 Distribution of Improvement for PAS | 37 |
42 Finite PAS Distribution | 42 |
5 Linearity Result for PAS | 45 |
6 Summary | 54 |
HESITANT ADAPTIVE SEARCH | 55 |
1 Hesitant Adaptive Search HAS | 56 |
2 Number of HAS Iterations to Convergence | 57 |
21 Continuous HAS Distribution | 58 |
22 Discrete HAS Distribution | 62 |
23 General HAS Distribution | 64 |
3 Numerical Examples of HAS | 67 |
4 Combination of PRS and PAS tpPRS+pPAS | 70 |
41 Continuous PRS and PAS Combination | 73 |
42 Discrete PRS and PAS Combination | 75 |
5 Summary | 80 |
ANNEALING ADAPTIVE SEARCH | 83 |
1 Annealing Adaptive Search AAS | 84 |
2 Bounds on Performance of Annealing Adaptive Search | 89 |
3 Cooling Schedule for Annealing Adaptive Search | 98 |
4 Summary | 104 |
BACKTRACKING ADAPTIVE SEARCH | 105 |
11 Implementation of HitandRun | 131 |
12 Convergence to Uniform Distribution | 133 |
13 Metropolis HitandRun | 136 |
14 Rate of Convergence to Target Distribution | 139 |
2 Improving HitandRun IHR | 140 |
21 Definition of Improving HitandRun | 141 |
22 Polynomial Performance of IHR | 143 |
23 Discussion | 159 |
31 Definition of HideandSeek | 160 |
32 Acceptance Criterion and Cooling Schedule | 161 |
33 Convergence of HideandSeek | 162 |
4 Extensions to HitandRun Based Optimization Methods | 163 |
41 Variations to Direction Generator | 164 |
42 Discrete Variations of HitandRun | 166 |
Stepfunction Approach | 167 |
Rounding Approach | 168 |
5 Computational Results | 171 |
6 Summary | 176 |
ENGINEERING DESIGN APPLICATIONS | 177 |
1 Formulating Global Optimization Problems | 179 |
12 Penalty Formulation | 181 |
2 Fuel Allocation Problem | 182 |
3 Truss Design Problem | 184 |
32 TenBar Truss Design | 186 |
4 Optimal Design of Composite Structures | 188 |
41 Optimal Design of a Composite Stiffened Panel | 190 |
42 Extensions to Larger Structures | 196 |
5 Summary | 207 |
References | 209 |
| 223 | |
Other editions - View all
Common terms and phrases
acceptance probability accepting non-improving analysis annealing adaptive search backtracking adaptive search blending rules Boltzmann distribution candidate point Chapter combined PRS-PAS algorithm computational constraints continuous and discrete convex cooling schedule Corollary cumulative distribution function current point defined denote dimension discrete BAS discrete problem dp(t Equation example expected number feasible region fiber angles Figure finite formulation geometric distribution global optimization problem hesitant adaptive search Hide-and-Seek hypersphere Improving Hit-and-Run improving points iterations to convergence laminate Lemma level set linear lower bounds mixed BAS moment-generating function n-dimensional non-improving point number of iterations objective function value one-step transition matrix optimum panel parameter performance Poisson process probability of sampling Proof pure adaptive search pure random search range Markov chain record values sample points sampling distribution Section sequence sequential random search simulated annealing spherical program stiffener stiffness temperature Theorem tion transition matrix uniform distribution uniformly Xk+1 YAAS YHAS
Popular passages
Page 216 - Watson LT. Improved genetic algorithm for the design of stiffened composite panels.
Page 221 - Wood, GR, Zabinsky, ZB, and Kristinsdottir, BP, "Hesitant Adaptive Search: the Distribution of the Number of Iterations to Convergence," Mathematical Proyramminy 89 (3), 479-486, 2001.
Page 221 - Zabinsky, Z,B., Smith, RL, McDonald, JF, Romeijn, HE, and Kaufman, DE, "Improving Hit-and-Run for Global Optimization," Journal of Global Optimization 3, 171- 192, 1993.
Page 216 - The Use of COSTADE in Developing Composite Commercial Aircraft Fuselage Structures," Proceedinys of the 35th AIAA/ASME/ASCE/AHS/ASC Structure, Structural Dynamics, and Materials Conference, April 1994.
Page 218 - Stochastic Global Optimization Methods Part I: Clustering Methods," Mathematical Proyramminy 39, 27-56, 1987. [138( Rinnooy Kan, AHG, and Timmer, GT, "Stochastic Global Optimization Methods Part II: Multi-level Methods," Mathematical Pro9rammin9 39, 57-78, 1987.