×

zbMATH — the first resource for mathematics

Efficient global optimization algorithm assisted by multiple surrogate techniques. (English) Zbl 1275.90072
Summary: Surrogate-based optimization proceeds in cycles. Each cycle consists of analyzing a number of designs, fitting a surrogate, performing an optimization based on the surrogate, and finally analyzing a candidate solution. Algorithms that use the surrogate uncertainty estimator to guide the selection of the next sampling candidate are readily available, e.g. the efficient global optimization (EGO) algorithm. However, adding one single point at a time may not be efficient when the main concern is the wall-clock time (rather than the number of simulations) and simulations can run in parallel. Also, the need for uncertainty estimates limits EGO-like strategies to surrogates normally implemented with such estimates (e.g. kriging and polynomial response surface). We propose the multiple surrogate efficient global optimization (MSEGO) algorithm, which adds several points per optimization cycle with the help of multiple surrogates. We import uncertainty estimates from one surrogate to another to allow the use of surrogates that do not provide them. The approach is tested on three analytic examples for nine basic surrogates including kriging, radial basis neural networks, linear Shepard, and six different instances of support vector regression. We find that MSEGO works well even with imported uncertainty estimates, delivering better results in a fraction of the optimization cycles needed by EGO.

MSC:
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Wang, L.; Shan, S.; Wang, G.G., Mode-pursuing sampling method for global optimization on expensive black-box functions, Eng. Optim., 36, 419-438, (2004)
[2] Kleijnen, J.P.C.; Sanchez, S.M.; Lucas, T.W.; Cioppa, T.M., A user’s guide to the brave new world of designing simulation experiments, INFORMS J. Comput., 17, 263-289, (2005) · Zbl 1239.62092
[3] Sóbester, A.; Leary, S.; Keane, A., On the design of optimization strategies based on global response surface approximation models, J. Glob. Optim., 33, 31-59, (2005) · Zbl 1137.90743
[4] Simpson, T.W., Toropov, V., Balabanov, V., Viana, F.A.C.: Design and analysis of computer experiments in multidisciplinary design optimization: a review of how far we have come—or not. In: 12th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, AIAA-2008-5802. AIAA, Victoria, BC, Canada (2008) · Zbl 0888.90135
[5] Forrester, A.I.J.; Keane, A.J., Recent advances in surrogate-based optimization, Prog. Aerosp. Sci., 45, 50-79, (2009)
[6] Viana, F.A.C., Gogu, C., Haftka, R.T.: Making the most out of surrogate models: tricks of the trade. In: ASME 2010 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, DETC2010-28813, ASME, Montreal, QC, Canada (2009) · Zbl 0917.90270
[7] Jones, D.R.; Schonlau, M.; Welch, W.J., Efficient global optimization of expensive black-box functions, J. Glob. Optim., 13, 455-492, (1998) · Zbl 0917.90270
[8] Jin, R., Chen, W., Sudjianto, A.: On sequential sampling for global metamodeling for in engineering design. In: ASME 2002 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, DETC2002-34092. ASME, Montreal, QC, Canada (2002) · Zbl 1075.68632
[9] Huang, D.; Allen, T.; Notz, W.; Zeng, N., Global optimization of stochastic black-box systems via sequential Kriging meta-models, J. Glob. Optim., 34, 441-466, (2006) · Zbl 1098.90097
[10] Henkenjohann, N.; Kunert, J., An efficient sequential optimization approach based on the multivariate expected improvement criterion, Qual. Eng., 19, 267-280, (2007)
[11] Ponweiser, W., Wagner, T., Vincze, M.: Clustered multiple generalized expected improvement: a novel infill sampling criterion for surrogate models. In: IEEE Congress on Evolutionary Computation, pp. 3514-3521. IEEE, Hong Kong (2008) · Zbl 0415.62011
[12] Jones, D.R., A taxonomy of global optimization methods based on response surfaces, J. Glob. Optim., 21, 345-383, (2001) · Zbl 1172.90492
[13] Ginsbourger, D.; Le Riche, R.; Carraro, L.; Tenne, Y. (ed.); Goh, C. (ed.), Kriging is well-suited to parallelize optimization, 131-162, (2010), Heidelberg
[14] Samad, A.; Kim, K.Y.; Goel, T.; Haftka, R.T.; Shyy, W., Multiple surrogate modeling for axial compressor blade shape optimization, J. Propuls. Power, 24, 302-310, (2008)
[15] Viana, F.A.C., Haftka, R.T.: Using multiple surrogates for metamodeling. In: 7th ASMO-UK ISSMO International Conference on Engineering Design Optimization, pp. 1-18. ISSMO, Bath, UK (2008) · Zbl 0972.90055
[16] Gorissen, D.; Dhaene, T.; Turck, F., Evolutionary model type selection for global surrogate modeling, J. Mach. Learn. Res., 10, 2039-2078, (2009) · Zbl 1235.62008
[17] Cho, Y.C.; Jayaraman, B.; Viana, F.A.C.; Haftka, R.T.; Shyy, W., Surrogate modeling for characterizing the performance of dielectric barrier discharge plasma actuator, Int. J. Comput. Fluid Dyn., 24, 281-301, (2010) · Zbl 1271.76392
[18] Gutmann, H.M., A radial basis function method for global optimization, J. Glob. Optim., 19, 201-227, (2001) · Zbl 0972.90055
[19] Stein M.L.: Interpolation of Spatial Data: Some Theory for Kriging. Springer, Berlin (1999) · Zbl 0924.62100
[20] Martin, J.D.; Simpson, T.W., Use of Kriging models to approximate deterministic computer models, AIAA J., 43, 853-863, (2005)
[21] Yamamoto, J.K., An alternative measure of the reliability of ordinary Kriging estimates, Math. Geol., 32, 489-509, (2000) · Zbl 0971.86006
[22] den Hertog, D.; Kleijnen, J.P.C.; Siem, A.Y.D., The correct Kriging variance estimated by bootstrapping, J. Oper. Res. Soc., 57, 400-409, (2006) · Zbl 1086.62042
[23] Kleijnen, J.P.C., van Beers, W.C.M., van Nieuwenhuyse, I.: Expected improvement in efficient global optimization through bootstrapped kriging. J. Glob. Optim. (available online), pp. 1-15 (2011) · Zbl 1254.90176
[24] Forrester A.I.J., Sóbester A., Keane A.J.: Engineering Design Via Surrogate Modelling: A Practical Guide. Wiley, New York (2008)
[25] Forrester, A.I.J.; Sóbester, A.; Keane, A.J., Multi-fidelity optimization via surrogate modeling, Proc. R. Soc. A Math. Phys. Eng. Sci., 463, 3251-3269, (2007) · Zbl 1142.90489
[26] Fang, H.; Horstemeyer, M.F., Global response approximation with radial basis functions, Eng. Optim., 38, 407-424, (2006)
[27] Goel, T.; Stander, N., Comparing three error criteria for selecting radial basis function network topology, Comput. Methods Appl. Mech. Eng., 198, 2137-2150, (2009) · Zbl 1227.74126
[28] Berry, M.W.; Minser, K.S., Algorithm 798: high-dimensional interpolation using the modified Shepard method, ACM Trans. Math. Softw., 25, 353-366, (1999) · Zbl 0963.65015
[29] Thacker, W.I.; Zhang, J.; Watson, L.T.; Birch, J.B.; Iyer, M.A.; Berry, M.W., Algorithm 905: sheppack: modified Shepard algorithm for interpolation of scattered multivariate data, ACM Trans. Math. Softw., 37, 1-20, (2010) · Zbl 1364.65028
[30] Cristianini N., Shawe-Taylor J.: An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods. Cambridge University Press, Cambridge (2000) · Zbl 0994.68074
[31] Smola, A.J.; Schölkopf, B., A tutorial on support vector regression, Stat. Comput., 14, 199-222, (2004)
[32] Viana, F.A.C., Haftka, R.T.: Importing uncertainty estimates from one surrogate to another. In: 50th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference, pp. AIAA-2009-2237. AIAA, Palm Springs, CA, USA (2009) · Zbl 1172.90492
[33] Viana, F.A.C.; Haftka, R.T.; Steffen, V., Multiple surrogates: how cross-validation errors can help us to obtain the best predictor, Struct. Multidiscip. Optim., 39, 439-457, (2009)
[34] Lophaven, S.N., Nielsen, H.B., Søndergaard, J.: Dace—a matlab kriging toolbox. Tech. Rep. IMM-TR-2002-12, Technical University of Denmark, Denmark (2002). Available at http://www2.imm.dtu.dk/ hbn/dace/ · Zbl 1098.90097
[35] MathWorks contributors: MATLAB The language of technical computing. The MathWorks, Inc, Natick, MA, USA, version 7.0 release 14 edn. (2004)
[36] Jekabsons, G.: RBF: Radial Basis Function interpolation for MATLAB/OCTAVE. Riga Technical University, Latvia, version 1.1 edn. (2009). Available at http://www.cs.rtu.lv/jekabsons/regression.html · Zbl 1271.76392
[37] Viana, F.A.C.: SURROGATES Toolbox User’s Guide. Gainesville, FL, USA, version 3.0 edn. (2011). Available at http://sites.google.com/site/felipeacviana/surrogatestoolbox · Zbl 1172.90492
[38] Gunn, S.R.: Support vector machines for classification and regression. Tech. rep., University of Southampton, UK (1997). Available at http://www.isis.ecs.soton.ac.uk/resources/svminfo/
[39] Roustant, O. Ginsbourger, D., Deville, Y.: DiceKriging, DiceOptim: two R packages for the analysis of computer experiments by kriging-based metamodeling and optimization. Ecole Nationale Supérieure des Mines de Saint-Etienne, France and University of Bern, Switzerland (2010). Available at http://hal.archives-ouvertes.fr/hal-00495766/
[40] Cherkassky, V.; Ma, Y., Practical selection of svm parameters and noise estimation for svm regression, Neural Netw., 17, 113-126, (2004) · Zbl 1075.68632
[41] Sasena, M.J.: Optimization of computer simulations via smoothing splines and kriging metamodels. Master’s thesis, University of Michigan, Ann Arbor, MI, USA (1998) · Zbl 1194.74259
[42] Dixon, L.C.W., Szegö, G.P.: Towards Global Optimization 2. North Holland, Amsterdam (1978)
[43] McKay, M.D.; Beckman, R.J.; Conover, W.J., A comparison of three methods for selecting values of input variables from a computer code, Technometrics, 21, 239-245, (1979) · Zbl 0415.62011
[44] Price K.V., Storn R.M., Lampinen J.A.: Differential Evolution: A Practical Approach to Global Optimization. Springer, New York (2005) · Zbl 1186.90004
[45] Storn, R.; Price, K., Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces, J. Glob. Optim., 11, 341-359, (1997) · Zbl 0888.90135
[46] Schutte, J.F.; Haftka, R.T.; Fregly, B.J., Improved global convergence probability using multiple independent optimizations, Int. J. Numer. Methods Eng., 71, 678-702, (2007) · Zbl 1194.74259
[47] Viana, F.A.C.; Haftka, R.T., Cross validation can estimate how well prediction variance correlates with error, AIAA J., 47, 2266-2270, (2009)
[48] Meckesheimer, M.; Booker, A.J.; Barton, R.R.; Simpson, T.W., Computationally inexpensive metamodel assessment strategies, AIAA J., 40, 2053-2060, (2002)
[49] Picard, R.R.; Cook, R.D., Cross-validation of regression models, J. Am. Stat. Assoc., 79, 575-583, (1984) · Zbl 0547.62047
[50] Varma, S.; Simon, R., Bias in error estimation when using cross-validation for model selection, BMC Bioinf., 7, 1290-1300, (2006)
[51] Myers R.H.: Classical and Modern Regression with Applications. Duxbury Press, Belmont (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.