Abstract
We investigate the impact of different sampling techniques on the performance of multi-objective optimization methods applied to costly black-box optimization problems. Such problems are often solved using an algorithm in which a surrogate model approximates the true objective function and provides predicted objective values at a lower cost. As the surrogate model is based on evaluations of a small number of points, the quality of the initial sample can have a great impact on the overall effectiveness of the optimization. In this study, we demonstrate how various sampling techniques affect the results of applying different optimization algorithms to a set of benchmark problems. Additionally, some recommendations on usage of sampling methods are provided.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Altmann, J.: Observational study of behavior: sampling methods. Behaviour 49 (3), 227–266 (1974)
Bischl, B., Bossek, J., Horn, D., Lang, M.: mlrMBO: Model-Based Optimization for MLR (2015). R package v1.0. https://github.com/berndbischl/mlrMBO
Box, G.E., Draper, N.R.: Empirical Model-Building and Response Surfaces. Wiley, New York (1987)
Cox, D.R., Reid, N.: The Theory of the Design of Experiments. CRC, Boca Raton (2000)
Doucet, A., Godsill, S., Andrieu, C.: On sequential Monte Carlo sampling methods for Bayesian filtering. Stat. Comput. 10 (3), 197–208 (2000)
Fang, H., Horstemeyer, M.F.: Global response approximation with radial basis functions. Eng. Optim. 38 (04), 407–424 (2006)
Halton, J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2 (1), 84–90 (1960)
Hammersley, J.M.: Monte Carlo methods for solving multivariable problems. Ann. N. Y. Acad. Sci. 86 (3), 844–874 (1960)
Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57 (1), 97–109 (1970)
Huband, S., Hingston, P., Barone, L., While, L.: A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. Evol. Comput. 10 (5), 477–506 (2006)
Ilzarbe, L., Álvarez, M.J., Viles, E., Tanco, M.: Practical applications of design of experiments in the field of engineering: a bibliographical review. Qual. Reliab. Eng. Int. 24 (4), 417–428 (2008)
Iman, R.L., Conover, W.: A distribution-free approach to inducing rank correlation among input variables. Commun. Stat. Simul. Comput. 11 (3), 311–334 (1982)
Jiang, S., Ong, Y.S., Zhang, J., Feng, L.: Consistencies and contradictions of performance metrics in multiobjective optimization. IEEE Trans. Cybern. 44 (12), 2391–2404 (2014)
Johnson, M.E., Moore, L.M., Ylvisaker, D.: Minimax and maximin distance designs. J. Stat. Plann. Infer. 26 (2), 131–148 (1990)
Joseph, V.R., Hung, Y.: Orthogonal-maximin Latin hypercube designs. Stat. Sin. 18 (1), 171 (2008)
Kalagnanam, J.R., Diwekar, U.M.: An efficient sampling technique for off-line quality control. Technometrics 39 (3), 308–319 (1997)
Khuri, A.I., Mukhopadhyay, S.: Response surface methodology. Wiley Interdiscip. Rev. Comput. Stat. 2 (2), 128–149 (2010)
Knowles, J.: ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans. Evol. Comput. 10 (1), 50–66 (2006)
Kocis, L., Whiten, W.J.: Computational investigations of low-discrepancy sequences. ACM Trans. Math. Softw. 23 (2), 266–294 (1997)
Kushner, H.J.: A versatile stochastic model of a function of unknown and time varying form. J. Math. Anal. Appl. 5 (1), 150–167 (1962)
LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)
McKay, M.D., Beckman, R.J., Conover, W.J.: Comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21 (2), 239–245 (1979)
Meckesheimer, M., Booker, A.J., Barton, R.R., Simpson, T.W.: Computationally inexpensive metamodel assessment strategies. AIAA J. 40 (10), 2053–2060 (2002)
Montgomery, D.C.: Design and Analysis of Experiments. Wiley, Hoboken (2008)
Morris, M.D., Mitchell, T.J.: Exploratory designs for computational experiments. J. Stat. Plann. Infer. 43 (3), 381–402 (1995)
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 (2), 123–144 (2014)
Niederreiter, H.: Random number generation and quasi-Monte Carlo methods. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63. SIAM, Philadelphia (1992)
Owen, A.B.: Controlling correlations in Latin hypercube samples. J. Am. Stat. Assoc. 89 (428), 1517–1522 (1994)
Panse, V.G., Sukhatme, P.V.: Statistical Methods for Agricultural Workers. Indian Council of Agricultural Research, New Delhi (1954)
Poles, S., Fu, Y., Rigoni, E.: The effect of initial population sampling on the convergence of multi-objective genetic algorithms. In: Multiobjective Programming and Goal Programming, pp. 123–133. Springer, Berlin (2009)
Ponweiser, W., Wagner, T., Biermann, D., Vincze, M.: Multiobjective optimization on a limited budget of evaluations using model-assisted \(\mathcal{S}\)-metric selection. In: Parallel Problem Solving from Nature–PPSN X, pp. 784–794. Springer, Berlin (2008)
Rice, J.: Mathematical Statistics and Data Analysis. Cengage Learning, Belmont (2006)
Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2, 21–42 (2000)
Rosenbaum, P.R.: Observational Studies. Springer, New York (2002)
Roy, R.K.: Design of Experiments Using the Taguchi Approach: 16 Steps to Product and Process Improvement. Wiley, New York (2001)
Sacks, J., Welch, W.J., Mitchell, T.J., Wynn, H.P.: Design and analysis of computer experiments. Stat. Sci. 4, 409–423 (1989)
Santner, T.J., Williams, B.J., Notz, W.I.: Space-filling designs for computer experiments. In: The Design and Analysis of Computer Experiments. Springer Series in Statistics, pp. 121–161. Springer, New York (2003)
Sobol, I.M.: On the distribution of points in a cube and the approximate evaluation of integrals. USSR Comput. Math. Math. Phys. 7, 86–112 (1967)
Starnes, D.S., Tabor, J., Yates, D., Moore, D.S.: The Practice of Statistics, New York, 5th edn. W.H. Freeman (2014)
Steinberg, D.M., Hunter, W.G.: Experimental design: review and comment. Technometrics 26 (2), 71–97 (1984)
Steponavičė, I., Hyndman, R.J., Smith-Miles, K., Villanova, L.: Efficient identification of the Pareto optimal set. In: Learning and Intelligent Optimization, pp. 341–352. Springer, New York (2014)
Tang, B.: Selecting Latin hypercubes using correlation criteria. Stat. Sin. 8 (3), 965–977 (1998)
Tenne, Y.: An analysis of the impact of the initial sample on evolutionary metamodel-assisted optimization. Appl. Artif. Intell. 27 (8), 669–699 (2013)
Tenne, Y.: Initial sampling methods in metamodel-assisted optimization. Eng. Comput. 31 (4), 661–680 (2015)
Wagner, T.: Planning and multi-objective optimization of manufacturing processes by means of empirical surrogate models. Vulkan, Essen (2013)
Wang, X., Hickernell, F.J.: Randomized Halton sequences. Math. Comput. Model. 32 (7), 887–899 (2000)
Wu, J., Azarm, S.: Metrics for quality assessment of a multiobjective design optimization solution set. Math. Comput. Model. 123 (1), 18–25 (2001)
Yates, F.: Sampling Methods for Censuses and Surveys. Charles Griffin & Co. Ltd., London (1949)
Žilinskas, A.: A statistical model-based algorithm for ‘black-box’ multi-objective optimisation. Int. J. Syst. Sci. 45 (1), 82–93 (2014)
Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms – a comparative case study. In: Parallel Problem Solving from Nature - PPSN-V, pp. 292–301. Springer, Heidelberg (1998)
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7 (2), 117–132 (2003)
Zitzler, E., Brockhoff, D., Thiele, L.: The hypervolume indicator revisited: on the design of Pareto-compliant indicators via weighted integration. In: Evolutionary Multi-Criterion Optimization, pp. 862–876. Springer, Berlin (2007)
Acknowledgements
This research was partly financially supported by the Linkage project “Optimizing experimental design for robust product development: a case study for high-efficiency energy generation” funded by the Australian Research Council.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Steponavičė, I., Shirazi-Manesh, M., Hyndman, R.J., Smith-Miles, K., Villanova, L. (2016). On Sampling Methods for Costly Multi-Objective Black-Box Optimization. In: Pardalos, P., Zhigljavsky, A., Žilinskas, J. (eds) Advances in Stochastic and Deterministic Global Optimization. Springer Optimization and Its Applications, vol 107. Springer, Cham. https://doi.org/10.1007/978-3-319-29975-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-29975-4_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-29973-0
Online ISBN: 978-3-319-29975-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)