Stochastic Adaptive Search for Global Optimization

Front Cover
Springer Science & Business Media, Sep 30, 2003 - Computers - 224 pages
0 Reviews
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

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
Index
223
Copyright

Other editions - View all

Common terms and phrases

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.

References to this book

All Book Search results »

Bibliographic information