Stochastic Simulation Optimization: An Optimal Computing Budget Allocation

✍ Scribed by Chun-hung Chen, Loo Hay Lee

• Publisher: World Scientific
• Year: 2010
• Tongue: English
• Leaves: 246
• Series: Series on System Engineering and Operations Research volume 1
• Edition: 1
• Category: Library

✦ Synopsis

With the advance of new computing technology, simulation is becoming very popular for designing large, complex and stochastic engineering systems, since closed-form analytical solutions generally do not exist for such problems. However, the added flexibility of simulation often creates models that are computationally intractable. Moreover, to obtain a sound statistical estimate at a specified level of confidence, a large number of simulation runs (or replications) is usually required for each design alternative. If the number of design alternatives is large, the total simulation cost can be very expensive. Stochastic Simulation Optimization addresses the pertinent efficiency issue via smart allocation of computing resource in the simulation experiments for optimization, and aims to provide academic researchers and industrial practitioners with a comprehensive coverage of OCBA approach for stochastic simulation optimization. Starting with an intuitive explanation of computing budget allocation and a discussion of its impact on optimization performance, a series of OCBA approaches developed for various problems are then presented, from the selection of the best design to optimization with multiple objectives. Finally, this book discusses the potential extension of OCBA notion to different applications such as data envelopment analysis, experiments of design and rare-event simulation.

✦ Table of Contents

Contents......Page 16
Foreword......Page 6
Preface......Page 8
Acknowledgments......Page 12
1.1 Introduction......Page 20
1.2 Problem Definition......Page 26
1.3.1. Design space is small......Page 29
1.3.2. Design space is large......Page 30
1.4 Summary......Page 32
2.1 Simulation Precision versus Computing Budget......Page 34
2.2 Computing Budget Allocation for Comparison of Multiple Designs......Page 36
2.3 Intuitive Explanations of Optimal Computing Budget Allocation......Page 38
2.4 Computing Budget Allocation for Large Simulation Optimization......Page 45
2.5 Roadmap......Page 47
3. Selecting the Best from a Set of Alternative Designs......Page 48
3.1 A Bayesian Framework for Simulation Output Modeling......Page 49
3.2 Probability of Correct Selection......Page 55
3.3 Maximizing the Probability of Correct Selection......Page 59
3.3.1. Asymptotically optimal solution......Page 61
3.3.2. OCBA simulation procedure......Page 68
3.4 Minimizing the Total Simulation Cost......Page 70
3.5 Non-Equal Simulation Costs......Page 74
3.6 Minimizing Opportunity Cost......Page 76
3.7 OCBA Derivation Based on Classical Model......Page 83
4.1.1. OCBA algorithm......Page 88
4.1.2. Different allocation procedures for comparison......Page 91
4.1.3. Numerical experiments......Page 93
4.2.1. Initial number of simulation replications, n0......Page 107
4.2.2. One-time incremental computing budget, .......Page 108
4.2.3. Rounding off Ni to integers......Page 109
4.2.4. Variance......Page 110
4.2.5. Finite computing budget and normality assumption......Page 111
5. Selecting An Optimal Subset......Page 112
5.1 Introduction and Problem Statement......Page 113
5.2 Approximate Asymptotically Optimal Allocation Scheme......Page 115
5.2.1. Determination of c value......Page 121
5.2.2. Sequential allocation scheme......Page 123
5.3 Numerical Experiments......Page 125
5.3.2. Numerical results......Page 126
6. Multi-objective Optimal Computing Budget Allocation......Page 136
6.1 Pareto Optimality......Page 137
6.2 Multi-objective Optimal Computing Budget Allocation Problem......Page 139
6.2.1. Performance index for measuring the dominance relationships and the quality of the selected Pareto set......Page 140
6.2.1.1. A performance index to measure the degree of non-dominated for a design......Page 141
6.2.1.2. Construction of the observed Pareto set......Page 142
6.2.1.3. Evaluation of the observed Pareto set by two types of errors......Page 143
6.2.2. Formulation for the multi-objective optimal computing budget allocation problem......Page 146
6.3 Asymptotic Allocation Rule......Page 147
6.4 A Sequential Allocation Procedure......Page 151
6.5.1. A 3-design case......Page 152
6.5.2. Test problem with neutral spread designs......Page 156
6.5.3. Test problem with steep spread designs......Page 158
7. Large-Scale Simulation and Optimization......Page 160
7.1 A General Framework of Integration of OCBA with Metaheuristics......Page 163
7.2.1. Neighborhood random search (NRS)......Page 166
7.2.2. Cross-entropy method (CE)......Page 167
7.2.3. Population-based incremental learning (PBIL)......Page 168
7.2.4. Nested partitions......Page 169
7.3 Numerical Experiments......Page 171
7.4.1. Nested partitions......Page 175
7.4.2. Evolutionary algorithm......Page 176
7.5 Concluding Remarks......Page 178
8. Generalized OCBA Framework and Other Related Methods......Page 180
8.1 Optimal Computing Budget Allocation for Selecting the Best by Utilizing Regression Analysis (OCBA-OSD)......Page 183
8.2 Optimal Computing Budget Allocation for Extended Cross-Entropy Method (OCBA-CE)......Page 186
8.3 Optimal Computing Budget Allocation for Variance Reduction in Rare-event Simulation......Page 188
8.4 Optimal Data Collection Budget Allocation (ODCBA) for Monte Carlo DEA......Page 190
8.5 Other Related Works......Page 192
A.1 What is Simulation?......Page 194
A.2 Steps in Developing A Simulation Model......Page 195
A.3 Concepts in Simulation Model Building......Page 197
A.4 Input Data Modeling......Page 200
A.5 Random Number and Variables Generation......Page 202
A.5.1. The Linear congruential generators (LCG)......Page 203
A.5.2.1. Inverse transform method......Page 205
A.5.2.2. Acceptance rejection method......Page 206
A.6 Output Analysis......Page 207
A.6.1. Output analysis for terminating simulation......Page 209
A.6.2. Output analysis for steady-state simulation......Page 210
A.7 Verification and Validation......Page 211
B.1 Probability Distribution......Page 214
B.3 Goodness of Fit Test......Page 218
C.1 Proof of Lemma 6.1......Page 220
C.3 Proof of Lemma 6.3......Page 223
C.4.1. Determination of roles......Page 225
C.4.2.1. h ∈ SA, o ∈ SA......Page 228
C.4.2.2. d ∈ SB......Page 229
Appendix D: Some OCBA Source Codes......Page 232
References......Page 238
Index......Page 244

✦ Subjects

Финансово-экономические дисциплины;Математические методы и моделирование в экономике;