Volume 7, Issue 4, December 2019, Page: 68-84
A Review on Surrogate-Based Global Optimization Methods for Computationally Expensive Functions
Pengcheng Ye, School of Marine Science and Technology, Northwestern Polytechnical University, Xi'an, China; Key Laboratory for Unmanned Underwater Vehicle, Northwestern Polytechnical University, Xi’an, China
Received: Oct. 2, 2019;       Accepted: Oct. 21, 2019;       Published: Nov. 19, 2019
DOI: 10.11648/j.se.20190704.11      View  33      Downloads  19
The great computational burden caused by complicated and unknown analysis restricts the use of simulation-based optimization. In order to mitigate this challenge, surrogate-based global optimization methods have gained popularity for their capability in handling computationally expensive functions. This paper surveys the fundamental issues that arise in Surrogate-based Global Optimization (SBGO) from a practitioner’s perspective, including highlighting concepts, methods, techniques as well as engineering applications. To provide a comprehensive discussion on the issues involved, recent advances in design of experiments, surrogate modeling techniques, infill criteria and design space reduction are investigated. This review screens out nearly 130 references containing a lot of historical reviews on related research fields from about 500 publications in various subjects. Future challenges and research is also analyzed and discussed.
Global Optimization, Surrogate Models, Review, Computationally Expensive Functions, Future Challenges
To cite this article
Pengcheng Ye, A Review on Surrogate-Based Global Optimization Methods for Computationally Expensive Functions, Software Engineering. Vol. 7, No. 4, 2019, pp. 68-84. doi: 10.11648/j.se.20190704.11
Copyright © 2019 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Younis A, Dong Z (2010) Trends, features, and tests of common and recently introduced global optimization methods. Engineering Optimization 42 (8): 1-28.
Rios LM, Sahinidis NV (2013) Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization 56 (3): 1247-1293.
Xiao YY, Zhao QH, Kaku I et al. (2014) Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems. Engineering Optimization 46 (4): 562-579.
Zhao JH, Wen FS, Dong ZY et al. (2012) Optimal dispatch of electric vehicles and wind power using enhanced particle swarm optimization. IEEE Transactions on Industrial Informatics 8 (4): 889-899.
Lu L, Gao Y, Li Q et al. (2018) Numerical investigations of tip clearance flow characteristics of a pumpjet propulsor. International Journal of Naval Architecture and Ocean Engineering 10 (3): 307-317.
Younis A, Karakoc K, Dong Z et al. (2011) Application of SEUMRE global optimization algorithm in automotive magnetorheological brake design. Structural and Multidisciplinary Optimization 44 (6): 761-772.
Sun C, Song B, Wang P (2015) Parametric geometric model and shape optimization of an underwater glider with blended-wing-body. International Journal of Naval Architecture and Ocean Engineering 7 (6): 995-1006.
Lee H, Jo Y, Lee DJ et al. (2016) Surrogate model based design optimization of multiple wing sails considering flow interaction effect. Ocean Engineering 121: 422-436.
Mainini L, Willcox K (2015) Surrogate modeling approach to support real-time structural assessment and decision making. AIAA Journal 53 (6): 1612-1626.
Peherstorfer B, Kramer B, Willcox K (2017) Combining multiple surrogate models to accelerate failure probability estimation with expensive high-fidelity models. Journal of Computational Physics 341: 61-75.
Shyy W, Cho YC, Du W et al. (2011) Surrogate-based modeling and dimension reduction techniques for multi-scale mechanics problems. Acta Mechanica Sinica 27 (6): 845-865.
Wang GG, Shan S (2007) Review of metamodeling techniques in support of engineering design optimization. Journal of Mechanical design 129 (4): 370-380.
El-Taweel T, Haridy S (2014) An application of fractional factorial design in wire electrochemical turning process. The International Journal of Advanced Manufacturing Technology 75 (5-8): 1207-1218.
Kamali H, Aminimoghadamfarouj N, Nematollahi A (2014) Optimization of pressurized hot water extraction of Lavandin essential oils via central composite design. Optimization 6 (11): 4853-4861.
Satapathy SC, Naik A, Parvathi K (2013) A teaching learning based optimization based on orthogonal design for solving global optimization problems. SpringerPlus 2 (1): 1-12.
Cheng Y, Wu P (2015) Optimisation for suspension system of a railway vehicle with a new non-linear creep model developed by uniform design. International Journal of Heavy Vehicle Systems 22 (2): 157-191.
Dong H, Song B, Dong Z et al. (2016) Multi-start space reduction (MSSR) surrogate-based global optimization method. Structural and Multidisciplinary Optimization 54 (4): 907-926.
Martínez SZ, Coello CAC (2013) Combining surrogate models and local search for dealing with expensive multi-objective optimization problems. In: IEEE Congress on Evolutionary Computation, pp 2572-2579.
Ye PC, Pan G (2017) Global optimization method using adaptive and parallel ensemble of surrogates for engineering design optimization. Optimization 66 (7): 1135-1155.
Liu H, Ong YS, Cai J (2018) A survey of adaptive sampling for global metamodeling in support of simulation-based complex engineering design. Structural and Multidisciplinary Optimization 57 (1): 393-416.
Jin R, Chen W, Sudjianto A (2005) An efficient algorithm for constructing optimal design of computer experiments. Journal of Statistical Planning and Inference 134 (1): 268-287.
Viana FAC, Venter G, Balabanov V (2010) An algorithm for fast optimal Latin hypercube design of experiments. International Journal for Numerical Methods in Engineering 82 (2): 135-156.
Jin R, Chen W, Simpson TW (2001) Comparative studies of metamodelling techniques under multiple modelling criteria. Structural and Multidisciplinary Optimization 23 (1): 1-13.
Jin Y (2011) Surrogate-assisted evolutionary computation: Recent advances and future challenges. Swarm and Evolutionary Computation 1 (2): 61-70.
Dong H, Li C, Song B et al. (2018) Multi-surrogate-based differential evolution with multi-start exploration (MDEME) for computationally expensive optimization. Advances in Engineering Software 123: 62-76.
Han ZH, Chen J, Zhang KS et al. (2018) Aerodynamic shape optimization of natural-laminar-flow wing using surrogate-based approach. AIAA Journal, 56 (7): 2579-2593.
Wang LQ, Shan SQ, Wang GG (2004) Mode-pursuing sampling method for global optimization on expensive black-box functions. Engineering Optimization 36 (4): 419-438.
Holmström K (2008) An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization. Journal of Global Optimization 41 (3): 447-464.
Zhao L, Choi KK, Lee I (2011) Metamodeling method using dynamic kriging for design optimization. AIAA Journal 49 (9): 2034-2046.
Zerpa LE, Queipo N, Pintosa S et al. (2005) An optimization methodology of alkaline-surfactant- polymer flooding processes using field scale numerical simulation and multiple surrogates. Journal of Petroleum Science and Engineering 47 (3): 197-208.
Goel T, Haftka RT, Shyy W et al. (2007) Ensemble of Surrogates. Structural and Multidisciplinary Optimization 33 (3): 199-216.
Acar E, Rais-Rohani M (2009) Ensemble of metamodels with optimized weight factors. Structural and Multidisciplinary Optimization 37 (3): 279-294.
Li Z, Ruan SL, Gu JF et al. (2016) Investigation on parallel algorithms in efficient global optimization based on multiple points infill criterion and domain decomposition. Structural and Multidisciplinary Optimization 54 (4): 747-773.
Jones DR, Schonlau M, Welch WJ (1998) Efficient global optimization of expensive black-box functions. Journal of Global Optimization 13 (4): 455-492.
Xu Q, Wehrle E, Baier H (2012) Adaptive surrogate-based design optimization with expected improvement used as infill criterion. Optimization 61 (6): 661-684.
Sóbester A, Leary SJ, Keane AJ (2005) On the design of optimization strategies based on global response surface approximation models. Journal of Global Optimization 33 (1): 31-59.
Huang D, Allen TT, Notz WI et al. (2006) Global optimization of stochastic black-box systems via sequential kriging meta-models. Journal of Global Optimization 34 (3): 441-466.
Couckuyt I, Deschrijver D, Dhaene T (2014) Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization. Journal of Global Optimization 60 (3): 575-594.
Wang GG, Simpson T (2004) Fuzzy clustering based hierarchical metamodeling for design space reduction and optimization. Engineering Optimization 36 (3): 313-335.
Zhu HG, Liu L, Long T et al. (2012) Global optimization method using SLE and adaptive RBF based on fuzzy clustering. Chinese Journal of Mechanical Engineering 25 (4): 768-775.
Ye PC, Pan G (2017) Global optimization method using ensemble of metamodels based on fuzzy clustering for design space reduction. Engineering with computers 33 (3): 573-585.
Galbally D, Fidkowski K, Willcox K et al. (2010) Non-linear model reduction for uncertainty quantification in large-scale inverse problems. International journal for numerical methods in engineering 81 (12): 1581-1608.
Shan S, Wang GG (2010) Survey of modeling and optimization strategies to solve high-dimensional design problems with computationally-expensive black-box functions. Structural and Multidisciplinary Optimization 41 (2): 219-241.
Pan G, Ye PC, Wang P (2014) A novel Latin hypercube algorithm via translational propagation. Scientific World Journal.
Forrester AIJ, Sobester DA, Keane AJ (2008) Engineering design via surrogate modelling: a practical guide. John Wiley and Sons.
Simpson TW, Poplinski J, Koch PN et al. (2001) Metamodels for computer-based engineering design: survey and recommendations. Engineering with computers 17 (2): 129-150.
Mukerjee R, Wu CFJ (2007) A modern theory of factorial design. Springer Science and Business Media.
Box GEP, Wilson KB (1992) On the experimental attainment of optimum conditions. Journal of the Royal Statistical Society, 1951, 13 (1): 1-45.
Obeng D, Morrell S, Napier-Munn T (2005) Application of central composite rotatable design to modelling the effect of some operating variables on the performance of the three-product cyclone. International Journal of Mineral Processing 76 (3): 181-192.
Ghafari S, Aziz HA, Isa MH et al. (2009) Application of response surface methodology (RSM) to optimize coagulation-flocculation treatment of leachate using poly-aluminum chloride (PAC) and alum. Journal of hazardous materials 163 (2): 650-656.
Nosrati S, Jayakumar N, Hashim M (2011) Extraction performance of chromium (VI) with emulsion liquid membrane by Cyanex 923 as carrier using response surface methodology. Desalination 266 (1-3): 286-290.
Taguchi G (1986) Introduction to quality engineering: designing quality into products and processes.
Taguchi G (1987) System of experimental design: engineering methods to optimize quality and minimize costs.
Bingham D, Sitter RR, Tang B (2009) Orthogonal and nearly orthogonal designs for computer experiments. Biometrika 96 (1): 51-65.
Moon H, Dean A, Santner T (2011) Algorithms for generating maximin Latin hypercube and orthogonal designs. Journal of Statistical Theory and Practice 5 (1): 81-98.
Vieira H, Sanchez S, Kienitz KH et al. (2011) Generating and improving orthogonal designs by using mixed integer programming. European Journal of Operational Research 215 (3): 629-638.
Hou SJ, Zhang ZD, Yang XJ et al. (2014) Crashworthiness optimization of new thin-walled cellular configurations. Engineering Computations 31 (5): 879-897.
Wang GG, Dong Z, Aitchison P (2001) Adaptive response surface method-a global optimization scheme for approximation-based design problems. Engineering Optimization 33 (6): 707-733.
Gong WY, Cai ZH, Jiang LX (2008) Enhancing the performance of differential evolution using orthogonal design method. Applied Mathematics and Computation 206 (1): 56-69.
Correa A, Grima P, Tort-Martorel lX (2012) Experimentation order in factorial designs: new findings. Journal of Applied Statistics 39 (7): 1577-1591.
Georgiou SD (2011) Orthogonal designs for computer experiments. Journal of Statistical Planning and Inference 141 (4): 1519-1525.
Gopalakannan S, Senthilvelan T (2014) Optimization of machining parameters for EDM operations based on central composite design and desirability approach. Journal of Mechanical Science and Technology 28 (3): 1045-1053.
Simpson TW, Booker AJ, Ghosh D et al. (2004) Approximation methods in multidisciplinary analysis and optimization: a panel discussion. Structural and Multidisciplinary Optimization 27 (5): 302-313.
Fang KT (1980) Experimental design by uniform distribution. Acta Mathematice Applicatae Sinica 3: 363-372.
Simpson TW, Lin DK, Chen W (2001) Sampling strategies for computer experiments: design and analysis. International Journal of Reliability and Applications 2 (3): 209-240.
Fang KT, Wang Y (1993) Number-theoretic methods in statistics. CRC Press.
Fang KT, Wang Y, Bentler PM (1994) Some applications of number-theoretic methods in statistics. Statistical Science 9 (2): 416-428.
Fang KT, Lin DKJ, Winker P et al. (2000) Uniform design: theory and application. Technometrics 42 (3): 237-248.
Chuang C, Yang R, Li G et al. (2008) Multidisciplinary design optimization on vehicle tailor rolled blank design. Structural and Multidisciplinary Optimization 35 (6): 551-560.
Li W, Liu L, Gong W (2011) Multi-objective uniform design as a SVM model selection tool for face recognition. Expert Systems with Applications 38 (6): 6689-6695.
Zhu P, Zhang Y, Chen G (2009) Metamodel-based lightweight design of an automotive front-body structure using robust optimization. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering 223 (9): 1133-1147.
Mckay M, Bechman R, Conver W (1979) A comparison of three methods for selecting values of input variables in the analysis techniques for computer codes. Technometrics 21 (2): 239-245.
Viana FAC, Haftka RT, Watson LT (2013) Efficient global optimization algorithm assisted by multiple surrogate techniques. Journal of Global Optimization 56 (2): 669-689.
Husslage BG, Rennen G, Van Dam ER et al. (2011) Space-filling Latin hypercube designs for computer experiments. Optimization and Engineering 12 (4): 611-630.
Viana FAC (2013) Things you wanted to know about the Latin hypercube design and were afraid to ask. In: 10th World Congress on Structural and Multidisciplinary Optimization, pp 1-9.
Viana FAC (2015) A Tutorial on Latin Hypercube Design of Experiments. Quality and Reliability Engineering International 32 (5): 1975-1985.
Zhu H, Liu L, Long T et al. (2012) A novel algorithm of maximin Latin hypercube design using successive local enumeration. Engineering Optimization 44 (5): 551-564.
Gilkeson CA, Toropov VV, Thompson HM et al. (2013) Multi-objective aerodynamic shape optimization of small livestock trailers. Engineering Optimization 45 (11): 1309-1330.
Narayanan A, Toropov V, Wood A et al. (2007) Simultaneous model building and validation with uniform designs of experiments. Engineering Optimization 39 (5): 497-512.
Box GEP, Draper NR (1987) Empirical model-building and response surfaces. Wiley New York.
Forrester AIJ, Keane AJ (2009) Recent advances in surrogate-based optimization. Progress in Aerospace Sciences 45 (1-3): 50-79.
Wang GG (2003) Adaptive response surface method using inherited Latin hypercube design points. Journal of Mechanical Engineering 125 (2): 210-220.
Vafaeesefat A (2011) Optimization of composite pressure vessels with metal liner by adaptive response surface method. Journal of Mechanical Science and Technology 25 (11): 2811-2816.
Ye L, Yang M, Xu L et al. (2014) Optimization of inductive angle sensor using response surface methodology and finite element method. Measurement 48: 252-262.
Fan CB, Huang YB, Wang QF (2014) Sparsity-promoting polynomial response surface: A new surrogate model for response prediction. Advances in Engineering Software 77: 48-65.
Shi L, Yang RJ, Zhu P (2013) An adaptive response surface method for crashworthiness optimization. Engineering Optimization 45 (11): 1365-1377.
Hardy R (1971) Multiquadric equations of topography and other irregular surfaces. Journal of Geophysical Research 76 (8): 1905-1915.
Mullur AA, Messac A (2005) Extended radial basis functions: more flexible and effective metamodeling. AIAA Journal 43 (6): 1306-1315.
Gutmann HM (2001) A radial basis function method for global optimization. Journal of global optimization 19 (3): 201-227.
Regis RG, Shoemaker CA (2007) A stochastic radial basis function method for the global optimization of expensive functions. INFORMS Journal on Computing 19 (4): 497-509.
Yao W, Chen X, Huang Y et al. (2014) A surrogate-based optimization method with RBF neural network enhanced by linear interpolation and hybrid infill strategy. Optimization Methods and Software 29 (2): 406-429.
Kitayama S, Arakawa M, Yamazaki K (2011) Sequential approximate optimization using radial basis function network for engineering optimization. Optimization and Engineering 12 (4): 535-557.
Sacks J, Welch W, Mitchell T et al. (1989) Design and analysis of computer experiments. Statistical Science 4 (4): 409-435.
Lophaven SN, Nielsen HB, Søndergaard J (2002) DACE-A Matlab Kriging toolbox, version 2.0.
Kleijnen JP (2009) Kriging metamodeling in simulation: A review. European Journal of Operational Research 192 (3): 707-716.
Kleijnen JP (2017) Regression and Kriging metamodels with their experimental designs in simulation: a review. European Journal of Operational Research 256 (1): 1-16.
Martin J, Simpson T (2005) Use of kriging models to approximate deterministic computer models. AIAA Journal 43 (4): 853-863.
Younis A, Dong Z (2010) Metamodelling and search using space exploration and unimodal region elimination for design optimization. Engineering Optimization 42 (6): 517-533.
Sanchez E, Pintos S, Queipo NV (2008) Toward an optimal ensemble of kernel-based approximations with engineering applications. Structural and Multidisciplinary Optimization 36 (3): 247-261.
Bishop CM (1995) Neural networks for pattern recognition. Oxford university press 12 (5): 1235-1242.
Viana FAC, Haftka RT, Steffen V (2009) Multiple surrogates: how cross-validation errors can help us to obtain the best predictor. Structural and Multidisciplinary Optimization 39 (4): 439-457.
Ye PC, Pan G (2015) A novel sequential approximate optimization approach using data mining for engineering design optimization. Optimization Methods and Software 30 (6): 1255-1275.
Kitayama S, Arakawa M, Yamazaki K (2012) Sequential approximate optimization for discrete design variable problems using radial basis function network. Applied Mathematics and Computation 219 (8): 4143-4156.
Gu J, Li G, Dong Z (2012) Hybrid and adaptive meta-model-based global optimization. Engineering Optimization 44 (1): 87-104.
Sasena M, Papalambros P, Goovaerts P (2002) Exploration of metamodeling sampling criteria for constrained global optimization. Engineering Optimization 34 (3): 263-278.
Picheny V, Ginsbourger D, Richet Y (2010) Noisy expected improvement and on-line computation time allocation for the optimization of simulators with tunable fidelity. Water Resources Research 48 (5): 1-11.
Ginsbourger D, Riche RL, Carraro L (2010) Kriging is well-suited to parallelize optimization. In: Computational Intelligence in Expensive Optimization Problems. Springer Berlin Heidelberg, pp 131-162.
Ye PC, Pan G, Huang QG et al. (2015) A New Sequential Approximate Optimization Approach Using Radial Basis Functions for Engineering Optimization. In: 8th International Conference on Intelligent Robotics and Applications pp 83-93.
Zhou G, Duan LB, Zhao WZ et al. (2016) An enhanced hybrid and adaptive meta-model based global optimization algorithm for engineering optimization problems. Science China-Technological Sciences 59 (8): 1147-1155.
Villanueva D, Haftka RT, Le Riche R et al. (2013) Locating Multiple Candidate Designs with Surrogate-Based Optimization. In: 10th World Congress on Structural and Multidisciplinary Optimization, pp 20-24.
Müller J, Shoemaker CA (2014) Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems. Journal of Global Optimization 60 (2): 123-144.
Amine BM, Bartoli N, Regis RG et al. (2018) Efficient global optimization for high-dimensional constrained problems by using the Kriging models combined with the partial least squares method. Engineering Optimization 50 (12): 2038-2053.
Sudret B (2008) Global sensitivity analysis using polynomial chaos expansions. Reliability Engineering and System Safety 93 (7): 964-979.
Fu G, Kapelan Z, Reed P (2011) Reducing the complexity of multiobjective water distribution system optimization through global sensitivity analysis. Journal of Water Resources Planning and Management 138 (3): 196-207.
Marrel A, Iooss B, Veiga S et al. (2012) Global sensitivity analysis of stochastic computer models with joint metamodels. Statistics and Computing 22 (3): 833-847.
Iooss B, Lemaître P (2014) A review on global sensitivity analysis methods. Operations Research/ Computer Science Interfaces 59: 101-122.
Raghavan B, Breitkopf P, Tourbier Y et al. (2013) Towards a space reduction approach for efficient structural shape optimization. Structural and Multidisciplinary Optimization 48 (5): 987-1000.
Zhang Z, Yang X, Oseledets IV et al. (2015) Enabling high-dimensional hierarchical uncertainty quantification by ANOVA and tensor-train decomposition. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34 (1): 63-76.
Qiu H, Xu Y, Gao L et al. (2016) Multi-stage design space reduction and metamodeling optimization method based on self-organizing maps and fuzzy clustering. Expert Systems with Applications 46: 180-195.
Wang H, Li E, Li G et al. (2008) A metamodel optimization methodology based on multi-level fuzzy clustering space reduction strategy and its applications. Computers and Industrial Engineering 55 (2): 503-532.
Shi RH, Liu L, Long T et al. (2017) Sequential radial basis function using support vector machine for expensive design optimization. AIAA Journal 55 (1): 214-227.
Pawlak Z (1982) Rough sets. International Journal of Parallel Programming 11 (5): 341-356.
Shan S, Wang GG (2004) Space exploration and global optimization for computationally intensive design problems: a rough set based approach. Structural and Multidisciplinary Optimization 28 (6): 427-441.
Chu XZ, Gao L, Qiu HB et al. (2010) An expert system using rough sets theory and self-organizing maps to design space exploration of complex products. Expert Systems with Applications 37 (11): 7364-7372.
Farias FUP, Antunes AR, Bastos SM et al. (2015) Minimization of vortex induced vibrations using surrogate based optimization. Structural and Multidisciplinary Optimization 52 (4): 717-735.
Ollar J, Toropov V, Jones R (2017) Sub-space approximations for MDO problems with disparate disciplinary variable dependence. Structural and Multidisciplinary Optimization 55 (1): 279-288.
Eason JPA (2018) A trust region filter algorithm for surrogate-based optimization. https://www.mobt3ath.com/uplode/book/book-26865.pdf
Conn AR, Scheinberg K, Vicente LN (2009) Global convergence of general derivative-free trust-region algorithms to first-and second-order critical points. SIAM Journal on Optimization 20 (1): 387-415.
Wild SM, Shoemaker C (2013) Global convergence of radial basis function trust-region algorithms for derivative-free optimization. SIAM Review 55 (2): 349-371.
Gratton S, Vicente LN (2014) A surrogate management framework using rigorous trust-region steps. Optimization Methods and Software 29 (1): 10-23.
Browse journals by subject