×

zbMATH — the first resource for mathematics

On sampling methods for costly multi-objective black-box optimization. (English) Zbl 1355.90095
Pardalos, Panos M. (ed.) et al., Advances in stochastic and deterministic global optimization. Cham: Springer (ISBN 978-3-319-29973-0/hbk; 978-3-319-29975-4/ebook). Springer Optimization and Its Applications 107, 273-296 (2016).
Summary: 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.
For the entire collection see [Zbl 1359.90005].

MSC:
90C29 Multi-objective and goal programming
90C26 Nonconvex programming, global optimization
62D05 Sampling theory, sample surveys
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Altmann, J.: Observational study of behavior: sampling methods. Behaviour 49 (3), 227–266 (1974) · doi:10.1163/156853974X00534
[2] Bischl, B., Bossek, J., Horn, D., Lang, M.: mlrMBO: Model-Based Optimization for MLR (2015). R package v1.0. https://github.com/berndbischl/mlrMBO
[3] Box, G.E., Draper, N.R.: Empirical Model-Building and Response Surfaces. Wiley, New York (1987) · Zbl 0614.62104
[4] Cox, D.R., Reid, N.: The Theory of the Design of Experiments. CRC, Boca Raton (2000) · Zbl 1009.62061
[5] Doucet, A., Godsill, S., Andrieu, C.: On sequential Monte Carlo sampling methods for Bayesian filtering. Stat. Comput. 10 (3), 197–208 (2000) · doi:10.1023/A:1008935410038
[6] Fang, H., Horstemeyer, M.F.: Global response approximation with radial basis functions. Eng. Optim. 38 (04), 407–424 (2006) · doi:10.1080/03052150500422294
[7] 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) · Zbl 0090.34505 · doi:10.1007/BF01386213
[8] Hammersley, J.M.: Monte Carlo methods for solving multivariable problems. Ann. N. Y. Acad. Sci. 86 (3), 844–874 (1960) · Zbl 0111.12405 · doi:10.1111/j.1749-6632.1960.tb42846.x
[9] Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57 (1), 97–109 (1970) · Zbl 0219.65008 · doi:10.1093/biomet/57.1.97
[10] 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) · Zbl 05452147 · doi:10.1109/TEVC.2005.861417
[11] 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) · doi:10.1002/qre.909
[12] 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) · Zbl 0496.65071 · doi:10.1080/03610918208812265
[13] 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) · doi:10.1109/TCYB.2014.2307319
[14] Johnson, M.E., Moore, L.M., Ylvisaker, D.: Minimax and maximin distance designs. J. Stat. Plann. Infer. 26 (2), 131–148 (1990) · doi:10.1016/0378-3758(90)90122-B
[15] Joseph, V.R., Hung, Y.: Orthogonal-maximin Latin hypercube designs. Stat. Sin. 18 (1), 171 (2008) · Zbl 1137.62050
[16] Kalagnanam, J.R., Diwekar, U.M.: An efficient sampling technique for off-line quality control. Technometrics 39 (3), 308–319 (1997) · Zbl 0896.62106 · doi:10.1080/00401706.1997.10485122
[17] Khuri, A.I., Mukhopadhyay, S.: Response surface methodology. Wiley Interdiscip. Rev. Comput. Stat. 2 (2), 128–149 (2010) · doi:10.1002/wics.73
[18] 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) · Zbl 05452069 · doi:10.1109/TEVC.2005.851274
[19] Kocis, L., Whiten, W.J.: Computational investigations of low-discrepancy sequences. ACM Trans. Math. Softw. 23 (2), 266–294 (1997) · Zbl 0887.65031 · doi:10.1145/264029.264064
[20] 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) · Zbl 0111.33001 · doi:10.1016/0022-247X(62)90011-2
[21] LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006) · Zbl 1100.68108 · doi:10.1017/CBO9780511546877
[22] 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) · Zbl 0415.62011
[23] Meckesheimer, M., Booker, A.J., Barton, R.R., Simpson, T.W.: Computationally inexpensive metamodel assessment strategies. AIAA J. 40 (10), 2053–2060 (2002) · doi:10.2514/2.1538
[24] Montgomery, D.C.: Design and Analysis of Experiments. Wiley, Hoboken (2008)
[25] Morris, M.D., Mitchell, T.J.: Exploratory designs for computational experiments. J. Stat. Plann. Infer. 43 (3), 381–402 (1995) · Zbl 0813.62065 · doi:10.1016/0378-3758(94)00035-T
[26] 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) · Zbl 1312.90064 · doi:10.1007/s10898-014-0184-0
[27] Niederreiter, H.: Random number generation and quasi-Monte Carlo methods. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63. SIAM, Philadelphia (1992) · Zbl 0761.65002 · doi:10.1137/1.9781611970081
[28] Owen, A.B.: Controlling correlations in Latin hypercube samples. J. Am. Stat. Assoc. 89 (428), 1517–1522 (1994) · Zbl 0813.65060 · doi:10.1080/01621459.1994.10476891
[29] Panse, V.G., Sukhatme, P.V.: Statistical Methods for Agricultural Workers. Indian Council of Agricultural Research, New Delhi (1954)
[30] 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) · Zbl 1176.90555 · doi:10.1007/978-3-540-85646-7_12
[31] 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) · Zbl 05489518 · doi:10.1007/978-3-540-87700-4_78
[32] Rice, J.: Mathematical Statistics and Data Analysis. Cengage Learning, Belmont (2006)
[33] Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2, 21–42 (2000) · doi:10.21314/JOR.2000.038
[34] Rosenbaum, P.R.: Observational Studies. Springer, New York (2002) · Zbl 0985.62091 · doi:10.1007/978-1-4757-3692-2
[35] Roy, R.K.: Design of Experiments Using the Taguchi Approach: 16 Steps to Product and Process Improvement. Wiley, New York (2001)
[36] Sacks, J., Welch, W.J., Mitchell, T.J., Wynn, H.P.: Design and analysis of computer experiments. Stat. Sci. 4, 409–423 (1989) · Zbl 0955.62619 · doi:10.1214/ss/1177012413
[37] 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) · Zbl 1041.62068 · doi:10.1007/978-1-4757-3799-8_5
[38] 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) · Zbl 0185.41103 · doi:10.1016/0041-5553(67)90144-9
[39] Starnes, D.S., Tabor, J., Yates, D., Moore, D.S.: The Practice of Statistics, New York, 5th edn. W.H. Freeman (2014)
[40] Steinberg, D.M., Hunter, W.G.: Experimental design: review and comment. Technometrics 26 (2), 71–97 (1984) · Zbl 0549.62048 · doi:10.1080/00401706.1984.10487928
[41] Steponavič\.e, 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) · doi:10.1007/978-3-319-09584-4_29
[42] Tang, B.: Selecting Latin hypercubes using correlation criteria. Stat. Sin. 8 (3), 965–977 (1998) · Zbl 0905.62065
[43] Tenne, Y.: An analysis of the impact of the initial sample on evolutionary metamodel-assisted optimization. Appl. Artif. Intell. 27 (8), 669–699 (2013) · doi:10.1080/08839514.2013.823324
[44] Tenne, Y.: Initial sampling methods in metamodel-assisted optimization. Eng. Comput. 31 (4), 661–680 (2015) · doi:10.1007/s00366-014-0372-z
[45] Wagner, T.: Planning and multi-objective optimization of manufacturing processes by means of empirical surrogate models. Vulkan, Essen (2013)
[46] Wang, X., Hickernell, F.J.: Randomized Halton sequences. Math. Comput. Model. 32 (7), 887–899 (2000) · Zbl 0965.65005 · doi:10.1016/S0895-7177(00)00178-3
[47] Wu, J., Azarm, S.: Metrics for quality assessment of a multiobjective design optimization solution set. Math. Comput. Model. 123 (1), 18–25 (2001)
[48] Yates, F.: Sampling Methods for Censuses and Surveys. Charles Griffin & Co. Ltd., London (1949)
[49] Žilinskas, A.: A statistical model-based algorithm for ’black-box’ multi-objective optimisation. Int. J. Syst. Sci. 45 (1), 82–93 (2014) · Zbl 1307.93476 · doi:10.1080/00207721.2012.702244
[50] 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) · doi:10.1007/BFb0056872
[51] 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) · Zbl 05452216 · doi:10.1109/TEVC.2003.810758
[52] 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) · Zbl 05546545 · doi:10.1007/978-3-540-70928-2_64
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.