Abstract
This paper proposes a new method that extends the efficient global optimization to address stochastic black-box systems. The method is based on a kriging meta-model that provides a global prediction of the objective values and a measure of prediction uncertainty at every point. The criterion for the infill sample selection is an augmented expected improvement function with desirable properties for stochastic responses. The method is empirically compared with the revised simplex search, the simultaneous perturbation stochastic approximation, and the DIRECT methods using six test problems from the literature. An application case study on an inventory system is also documented. The results suggest that the proposed method has excellent consistency and efficiency in finding global optimal solutions, and is particularly useful for expensive systems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
D.H. Ackley (1987) A Connectionist Machine for Genetic Hill-climbing Kluwer Academic Publishers Boston Occurrence Handle10.1007/978-1-4613-1997-9
S. Andradóttir (1998) Simulation optimization J. Banks (Eds) Handbook on Simulation Wiley New York
Angün, E., Kleijnen, J.P., Hertog, D.D. and Gürkan, G. (2002), Response surface methodology revised. In: Proceedings of the 2002 Winter Simulation Conference, pp. 377–383.
R. R. Barton (1984) ArticleTitleMinimization algorithms for functions with random noise American Journal of Mathematical and Management Sciences 4 109–138
R.R. Barton J.S. Ivey (1996) ArticleTitleNelder–Mead simplex modifications for simulation optimization Management Science 42 954–973 Occurrence Handle10.1287/mnsc.42.7.954
F.H. Branin (1972) ArticleTitleWidely convergent methods for finding multiple solutions of simultaneous nonlinear equations IBM Journal of Research Developments 16 504–522 Occurrence Handle10.1147/rd.165.0504
F.H. Branin S.K. Hoo (1972) A method for finding multiple extrema of a function of n variables F.A. Lootsma (Eds) Numerical Methods of Nonlinear Optimization Academic Press London 231–237
N.A.C. Cressie (1993) Statistics for Spatial Data Wiley New York
C. Currin M. Mitchell M. Morris D. Ylvisaker (1991) ArticleTitleBayesian prediction of deterministic functions, with applications to the design and analysis of computer experiments Journal of American Statistics Association 86 953–963 Occurrence Handle10.2307/2290511
K.-T. Fang D.K. Lin P. Winker Y. Zhang (2000) ArticleTitleUniform design: theory and application Technometrics 42 237–248 Occurrence Handle10.2307/1271079
M.C. Fu (1994) ArticleTitleOptimization via simulation: a review Annals of Operations Research 53 199–247 Occurrence Handle10.1007/BF02136830
J.M. Gablonsky C.T. Kelley (2001) ArticleTitleA locally-biased form of the direct algorithm Journal of Global Optimization 21 27–37 Occurrence Handle10.1023/A:1017930332101
R.T. Haftka Z. Gürdal (1993) Elements of Structural Optimization EditionNumber3 Kluwer Boston, MA
J.K. Hartman (1973) ArticleTitleSome experiments in global optimization Naval Research Logistics Quarterly 20 569–576 Occurrence Handle10.1002/nav.3800200316
D.G. Humphrey J.R. Wilson (2000) ArticleTitleA revised simplex search procedure for stochastic simulation response-surface optimization INFORMS Journal on Computing 12 272–283 Occurrence Handle10.1287/ijoc.12.4.272.11879
M.E. Johnson L.M. Moore D. Ylvisaker (1990) ArticleTitleMinimax and maximin distance designs Journal of Statistical Planning and Inference 26 131–148 Occurrence Handle10.1016/0378-3758(90)90122-B
D. Jones M. Schonlau W. Welch (1998) ArticleTitleEfficient global optimization of expensive black-box functions Journal of Global Optimization 13 455–492 Occurrence Handle10.1023/A:1008306431147
J. Kiefer J. Wolfowitz (1952) ArticleTitleStochastic estimation of a regression function Annals of Mathematical Statistics 23 462–466 Occurrence Handle10.1214/aoms/1177729392
J.R. Koehler A.B. Owen (1996) Computer experiments S. Ghosh C.R. Rao (Eds) Handbook of Statistics Elsevier Science B.V. Amsterdam, the Netherlands
H.J. Kushner (1964) ArticleTitleA new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise Journal of Basic Engineering 86 97–106 Occurrence Handle10.1115/1.3653121
H.J. Kushner D.C. Clark (1978) Stochastic Approximation Methods for Constrained and Unconstrained Systems Springer New York
A.M. Law W.D. Kelton (2000) Simulation Modeling and Analysis EditionNumber3 McGraw-Hill Boston 60–80
D.V. Lindley (1956) ArticleTitleOn a measure of information provided by an experiment Annals of Mathematical Statistics 27 986–1005 Occurrence Handle10.1214/aoms/1177728069
M.D. McKay R.J. Beckman W.J. Conover (1979) ArticleTitleA comparison of three methods for selecting values of input variables in the analysis of output from a computer code Technometrics 21 239–245 Occurrence Handle10.2307/1268522
Neddermeijer, H.G., Piersma, N., van Oortmarssen, G.J., Habbema, J.D.F. and Dekker, R. (1999), Comparison of response surface methodology and the Nelder and Mead simplex method for optimization in microsimulation models, Econometric Institute Report EI-9924/A, Erasmus University Rotterdam, The Netherlands.
Neddermeijer, H.G., van Oortmarssen, G.J., Piersma N. and Dekker R. (2000), A framework for response surface methodology for simulation optimizaton. In: Proceedings of the 2000 Winter Simulation Conference, pp. 129–136.
H. Niederreiter (1992) Random number generation and quasi-Monte-Carlo methods SAIM Philadelphia Occurrence Handle10.1137/1.9781611970081
A. O’Hagan (1989) ArticleTitleComment: design and analysis of computer experiments Statistic Science 4 430–432 Occurrence Handle10.1214/ss/1177012418
C.D. Perttunen D.R. Jones B.E. Stuckman (1993) ArticleTitleLipschitzian optimization without the lipschitz constant Journal of Optimization Theory and Application 79 IssueID1 157–181 Occurrence Handle10.1007/BF00941892
J.F. Rodriguez V.M. Perez D. Padmanabhan J.E. Renaud (2001) ArticleTitleSequential approximate optimization using variable fidelity response surface approximation Structure Multidiscipline Optimization 22 23–34
J. Sacks W.J. Welch T.J. Mitchell H.P. Wynn (1989a) ArticleTitleDesign and analysis of computer experiments (with discussion) Statistical Science 4 409–435 Occurrence Handle10.1214/ss/1177012413
J. Sacks S.B. Schiller W. Welch (1989b) ArticleTitleDesign for computer experiments Technometrics 31 41–47 Occurrence Handle10.2307/1270363
M.H. Safizadeh B.M. Thornton (1984) ArticleTitleOptimization in simulation experiments using response surface methodology Comparative Industrial Engineering 8 11–27 Occurrence Handle10.1016/0360-8352(84)90018-4
T.J. Santner B.J. Williams W.I. Notz (2003) The Design and Analysis of Computer Experiments Springer New York
Sasena, M.J., Papalambros, P.Y. and Goovaerts, P. (2001), The use of surrogate modeling algorithms to exploit disparities in function computation time within simulation-based optimization. In: Proceedings of the 4th Congress on Structural and Multidisciplinary Optimization, Dalian, China, June 4–8, 2001.
M.J. Sasena P.Y. Papalambros P. Goovaerts (2002) ArticleTitleExploration of metamodeling sampling criteria for constrained global optimization Engineering Optimization 34 263–278 Occurrence Handle10.1080/03052150211751
Sasena, M.J. (2002), Flexibility and Efficiency Enhancements for Constrained Global Design Optimization with Kriging Approximations, Ph.D. dissertation, University of Michigan.
Sóbester, A., Leary, S. and Keane, A.J. (2002), A parallel updating scheme for approximating and optimizing high fidelity computer simulation. In: The Third ISSMO/AIAA Internet Conference on Approximations in Optimization, October 14–18, 2002.
J.C. Spall (1992) ArticleTitleMultivariate stochastic approximation using a simultaneous perturbation gradient approximation IEEE Transactions on Automatic Control 37 332–341 Occurrence Handle10.1109/9.119632
J.C. Spall (1998) ArticleTitleImplementation of the simultaneous perturbation algorithm for stochastic optimization IEEE Transactions on Aerospace and Electronics Systems 34 817–823 Occurrence Handle10.1109/7.705889
M. Stein (1987) ArticleTitleLarge sample properties of simulation using Latin hypercube sampling Technometrics 29 143–151 Occurrence Handle10.2307/1269769
B.J. Williams T.J. Santner W.I. Notz (2000) ArticleTitleSequential design of computer experiments to minimize integrated response functions Statistica Sinica 10 1133–1152
A. Žilinskas (1980) ArticleTitleMINUN – Optimization of one-dimensional multimodal functions in the presence of noise, algorithms 44 Aplikace Matematiky 25 392–402
Author information
Authors and Affiliations
Corresponding author
Additional information
An erratum to this article can be found at http://dx.doi.org/10.1007/s10898-011-9821-z
Rights and permissions
About this article
Cite this article
Huang, D., Allen, T.T., Notz, W.I. et al. Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models. J Glob Optim 34, 441–466 (2006). https://doi.org/10.1007/s10898-005-2454-3
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10898-005-2454-3