Skip to main content
SpringerLink
Log in

Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

This paper examines the influence of two major aspects on the solution quality of surrogate model algorithms for computationally expensive black-box global optimization problems, namely the surrogate model choice and the method of iteratively selecting sample points. A random sampling strategy (algorithm SO-M-c) and a strategy where the minimum point of the response surface is used as new sample point (algorithm SO-M-s) are compared in numerical experiments. Various surrogate models and their combinations have been used within the SO-M-c and SO-M-s sampling frameworks. The Dempster–Shafer Theory approach used in the algorithm by Müller and Piché (J Glob Optim 51:79–104, 2011) has been used for combining the surrogate models. The algorithms are numerically compared on 13 deterministic literature test problems with 2–30 dimensions, an application problem that deals with groundwater bioremediation, and an application that arises in energy generation using tethered kites. NOMAD and the particle swarm pattern search algorithm (PSWARM), which are derivative-free optimization methods, have been included in the comparison. The algorithms have also been compared to a kriging method that uses the expected improvement as sampling strategy (FEI), which is similar to the Efficient Global Optimization (EGO) algorithm. Data and performance profiles show that surrogate model combinations containing the cubic radial basis function (RBF) model work best regardless of the sampling strategy, whereas using only a polynomial regression model should be avoided. Kriging and combinations including kriging perform in general worse than when RBF models are used. NOMAD, PSWARM, and FEI perform for most problems worse than SO-M-s and SO-M-c. Within the scope of this study a Matlab toolbox has been developed that allows the user to choose, among others, between various sampling strategies and surrogate models and their combinations. The open source toolbox is available from the authors upon request.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. For example, in iteration \(m\) a combination of RBF and kriging may be used, and in iteration \(m+1\) a combination of MARS, kriging, and polynomial may be used.

  2. If there were failed trials for a test problem, the corresponding average relative errors are computed based on the successful trials.

  3. For generating the data and performance profile plots the results of the algorithms for these problems are included.

  4. For the 20-dimensional problem L20, for which a single function evaluation takes only fractions of a second, each trial needed approximately 30 days to complete the 2,000 evaluations due to the computational expense of updating the kriging surface and maximizing the expected improvement.

Abbreviations

DACE:

Design and analysis of computer experiments

DST:

Dempster–Shafer Theory

FEI:

Expected improvement algorithm by Forrester et al. [12]

GM:

Global minima

K:

Kriging model

LM:

Local minima

LOOCV:

Leave-one-out cross-validation

M, MARS:

Multivariate adaptive regression spline

NOMAD:

Nonlinear optimization by mesh adaptive direct search

P:

Polynomial regression model

PSWARM:

Particle swarm pattern search algorithm

R, RBF:

Radial basis function surrogate model

SEM:

Standard error of means

SO–M:

Surrogate Optimization-Mixture

SO-M-c:

Surrogate Optimization-Mixture-candidate sampling

SO-M-s:

Surrogate Optimization-Mixture-surface minimum sampling

\(\mathbf {x}\) :

Continuous variable vector, \(\mathbf {x}\in \mathbb {R}^d\)

\(\mathbf {x}^T\) :

Transpose of \(\mathbf {x}\)

\(x_i\) :

\(i\)th Continuous variable, see Eq. (1b)

\(d\) :

Problem dimension

\(n_{0}\) :

Number of points in the initial experimental design

\(n\) :

Number of function evaluations obtained so far

\(k\) :

Number of points in the validation set for cross-validation

\(\Omega \) :

Box-constrained variable domain

\(w_{r}\) :

Weight of the \(r\)th model in the combination, see Eq. (2)

\(s_{r}(\cdot )\) :

\(r\)th Surrogate model in the combination, see Eq. (2)

\(\mathcal {S}\) :

Set of already evaluated sample points, \(\mathcal {S}=\{\mathbf {x}_1,\ldots ,\mathbf {x}_n\}\)

\(\varvec{\chi }_\jmath \) :

\(\jmath \)th Candidate point, \(\jmath = 1,\ldots ,t\)

\(\mathbf {x}_\text {best}\) :

Best point found so far

\(\mathbb {P}\) :

Perturbation probability of each variable, see Eq. (3)

References

  1. Ackley, D.H.: A connectionist machine for genetic hillclimbing. Kluwer, Boston (1987)

    Book  Google Scholar 

  2. Argatov, I., Rautakorpi, P., Silvennoinen, R.: Estimation of the mechanical energy output of the kite wind generator. Renew. Energy 34, 1525–1532 (2009)

    Article  Google Scholar 

  3. Audet, C., Béchard, V., Le Digabel, S.: Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search. J. Glob. Optim. 41, 299–318 (2008)

    Article  Google Scholar 

  4. Björkman, M., Holmström, K.: Global optimization of costly nonconvex functions using radial basis functions. Optim. Eng. 1, 373–397 (2001)

    Article  Google Scholar 

  5. Booker, A.J., Dennis Jr, J.E., Frank, P.D., Serafini, D.B., Torczon, V., Trosset, M.W.: A rigorous framework for optimization of expensive functions by surrogates. Struct. Multidiscip. Optim. 17, 1–13 (1999)

    Article  Google Scholar 

  6. Breukels, J.: An engineering methodology for kite design. Ph.D. thesis, Delft University of Technology (2011)

  7. Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. SIAM, Philadelphia (2009)

    Book  Google Scholar 

  8. De Jong, K.A.: An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D. thesis, University of Michigan (1975)

  9. Dixon, L.C.W., Szegö, G. P. (eds.): The global optimization problem: an introduction. In: Towards Global Optimization, vol. 2. North-Holland, Amsterdam (1978)

  10. Espinet, A.J., Shoemaker, C.A.: Estimation of plume distribution for carbon sequestration using parameter estimation, optimization and monitoring data. Water Resour. Res. 49, 4442–4464 (2013)

    Article  Google Scholar 

  11. Fagiano, L.: Control of tethered airfoils for high-altitude wind energy generation. Ph.D. thesis, Politecnico di Torino (2009)

  12. Forrester, A., Sóbester, A., Keane, A.: Engineering Design Via Surrogate Modelling—a Practical Guide. Wiley, New York (2008)

    Book  Google Scholar 

  13. Friedman, J.H.: Multivariate adaptive regression splines. Ann. Stat. 19, 1–67 (1991)

    Article  Google Scholar 

  14. Glaz, B., Friedmann, P.P., Liu, L.: Surrogate based optimization of helicopter rotor blades for vibration reduction in forward flight. Struct. Multidiscip. Optim. 35, 341–363 (2008)

    Article  Google Scholar 

  15. Goel, T., Haftka, R.T., Shyy, W., Queipo, N.V.: Ensemble of surrogates. Struct. Multidiscip. Optim. 33, 199–216 (2007)

    Article  Google Scholar 

  16. Gutmann, H.-M.: A radial basis function method for global optimization. J. Glob. Optim. 19, 201–227 (2001)

    Article  Google Scholar 

  17. Holmström, K., Quttineh, N.-H., Edvall, M.M.: An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization. J. Glob. Optim. 41, 447–464 (2008)

    Article  Google Scholar 

  18. Houska, B.: Robustness and stability optimization of open-loop controlled power generating kites. Master’s thesis, Ruprecht-Karls-Universität Heidelberg, Fakultät für Mathematik und Informatik (2007)

  19. Jekabsons, G.: ARESLab: adaptive regression splines toolbox for Matlab. Available at http://www.cs.rtu.lv/jekabsons/ (2010)

  20. Jones, D.R.: A taxonomy of global optimization methods based on response surfaces. J. Glob. Optim. 21, 345–383 (2001)

    Article  Google Scholar 

  21. Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13, 455–492 (1998)

    Article  Google Scholar 

  22. Jouhaud, J.-C., Sagaut, P., Montagnac, M., Laurenceau, J.: A surrogate-model based multidisciplinary shape optimization method with application to a 2D subsonic airfoil. Comput. Fluids 36, 520–529 (2007)

    Article  Google Scholar 

  23. Lam, X.B., Kim, Y.S., Hoang, A.D., Park, C.W.: Coupled aerostructural design optimization using the kriging model and integrated multiobjective optimization algorithm. J. Optim. Theory Appl. (2009). doi:10.1007/s10957-009-9520-9

    Google Scholar 

  24. Le Digabel, S.: Algorithm 909: nomad: nonlinear optimization with the MADS algorithm. ACM Trans. Math. Softw. 37:44:1–44:15 (2011)

  25. Levy, A., Montalvo, A., Gomez, S., Galderon, A.: Topics in Global Optimization. Springer, New York (1981)

    Google Scholar 

  26. Li, C., Wang, F.-L., Chang, Y.-Q., Liu, Y.: A modified global optimization method based on surrogate model and its application in packing profile optimization of injection molding process. Int. J. Adv. Manuf. Technol. 48, 505–511 (2010)

    Article  Google Scholar 

  27. Liao, X., Li, Q., Yang, X., Zhang, W., Li, W.: Multiobjective optimization for crash safety design of vehicles using stepwise regression model. Struct. Multidiscip. Optim. 35, 561–569 (2008)

    Article  Google Scholar 

  28. Lophaven, S.N., Nielsen, H.B., Søndergaard, J.: DACE a Matlab kriging toolbox. Technical report, IMM-TR-2002-12 (2002)

  29. Martin, J.D., Simpson, T.W.: Use of kriging models to approximate deterministic computer models. AIAA J. 43, 853–863 (2005)

    Article  Google Scholar 

  30. Matheron, G.: Principles of geostatistics. Econ. Geol. 58, 1246–1266 (1963)

    Article  Google Scholar 

  31. Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin (1992)

    Book  Google Scholar 

  32. Moré, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20, 172–191 (2009)

    Article  Google Scholar 

  33. Mühlenbein, H., Schomisch, D., Born, J.: The parallel genetic algorithm as function optimizer. Parallel Comput. 17, 619–632 (1991)

    Article  Google Scholar 

  34. Müller, J., Piché, R.: Mixture surrogate models based on Dempster–Shafer theory for global optimization problems. J. Glob. Optim. 51, 79–104 (2011)

    Article  Google Scholar 

  35. Myers, R.H., Montgomery, D.C.: Response Surface Methodology, Process and Product Optimization Using Designed Experiments. Wiley-Interscience Publication, New York (1995)

    Google Scholar 

  36. Powell, M.J.D.: An efficient method for finding the minimum of a function of several variables without calculating derivatives. Comput. J. 7, 155–162 (1964)

    Article  Google Scholar 

  37. Powell, M.J.D.: The theory of radial basis function approximation in 1990. In: Light, W.A. (ed.) Advances in Numerical Analysis, vol. 2: Wavelets, Subdivision Algorithms and Radial Basis Functions. pp. 105–210, Oxford University Press, Oxford (1992)

  38. Queipo, N.V., Haftka, R.T., Shyy, W., Goel, T., Vaidyanathan, R., Tucker, P.K.: Surrogate-based analysis and optimization. Prog. Aerosp. Sci. 41, 1–28 (2005)

    Article  Google Scholar 

  39. Regis, R.G., Shoemaker, C.A.: Constrained global optimization of expensive black-box functions using radial basis functions. J. Glob. Optim. 31, 153–171 (2005)

    Article  Google Scholar 

  40. Regis, R.G., Shoemaker, C.A.: A stochastic radial basis function method for the global optimization of expensive functions. INFORMS J. Comput. 19, 497–509 (2007)

    Article  Google Scholar 

  41. Regis, R.G., Shoemaker, C.A.: Improved strategies for radial basis function methods for global optimization. J. Glob. Optim. 37, 113–135 (2007)

    Article  Google Scholar 

  42. Regis, R.G., Shoemaker, C.A.: Parallel radial basis function methods for the global optimization of expensive functions. Eur. J. Oper. Res. 182, 514–535 (2007)

    Article  Google Scholar 

  43. Regis, R.G., Shoemaker, C.A.: Parallel stochastic global optimization using radial basis functions. INFORMS J. Comput. 21, 411–426 (2009)

    Article  Google Scholar 

  44. Regis, R.G., Shoemaker, C.A.: A quasi-multistart framework for global optimization of expensive functions using response surface models. J. Glob. Optim. (2012). doi:10.1007/s10898-012-9940-1

  45. Regis, R.G., Shoemaker, C.A.: Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization. Eng. Optim. 45, 529–555 (2013)

    Article  Google Scholar 

  46. Schoen, F.: A wide class of test functions for global optimization. J. Glob. Optim. 3, 133–137 (1993)

    Article  Google Scholar 

  47. Tolson, B.A., Shoemaker, C.A.: Dynamically dimensioned search algorithm for computationally efficient watershed model calibration. Water Res. Res. 43, W01413 (2007)

    Article  Google Scholar 

  48. Törn, A., Zilinskas, A.: Global Optimization. In: Lecture Notes in Computer Science, vol. 350. Springer, Berlin (1989)

  49. Vaz, A.I.F., Vicente, L.N.: A particle swarm pattern search method for bound constrained global optimization. J. Glob. Optim. 39, 197–219 (2007)

    Article  Google Scholar 

  50. Viana, F.A.C., Haftka, R.T., Watson, L.T.: Efficient global optimization algorithm assisted by multiple surrogate techniques. J. Glob. Optim. 56, 669–689 (2013)

    Article  Google Scholar 

  51. Yang, R.J., Wang, N., Tho, C.H., Bobineau, J.P., Wang, B.P.: Metamodeling development for vehicle frontal impact simulation. J. Mech. Des. 127, 1014–1021 (2005)

    Article  Google Scholar 

  52. Yoon, J.-H., Shoemaker, C.A.: Comparison of optimization methods for groundwater bioremediation. J. Water Resour. Plan. Manag. 125, 54–63 (1999)

    Article  Google Scholar 

Download references

Acknowledgments

Partial support for this research was provided by NSF CISE 1116298 to Prof. Shoemaker and by DOE-SciDAC DE-SC0006791 to Prof. Mahowald and Prof. Shoemaker. The first author also thanks the Finnish Academy of Science and Letters, Vilho, Yrjö and Kalle Väisälä Foundation for the financial support during her research visit as Ph.D. student in Applied Mathematics at Cornell University.

Author information

Authors and Affiliations

  1. School of Civil and Environmental Engineering, Cornell University, 209 Hollister Hall, Ithaca, NY, 14853-3501, USA

    Juliane Müller

  2. School of Civil and Environmental Engineering, Cornell University, 210 Hollister Hall, Ithaca, NY, 14853-3501, USA

    Christine A. Shoemaker

Authors
  1. Juliane Müller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christine A. Shoemaker
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juliane Müller.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Müller, J., Shoemaker, C.A. Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems. J Glob Optim 60, 123–144 (2014). https://doi.org/10.1007/s10898-014-0184-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-014-0184-0

Keywords

Search

Navigation