Abstract
Bayesian Optimization (BO) is a surrogate-assisted global optimization technique that has been successfully applied in various fields, e.g., automated machine learning and design optimization. Built upon a so-called infill-criterion and Gaussian Process regression (GPR), the BO technique suffers from a substantial computational complexity and hampered convergence rate as the dimension of the search spaces increases. Scaling up BO for high-dimensional optimization problems remains a challenging task.
In this paper, we propose to tackle the scalability of BO by hybridizing it with a Principal Component Analysis (PCA), resulting in a novel PCA-assisted BO (PCA-BO) algorithm. Specifically, the PCA procedure learns a linear transformation from all the evaluated points during the run and selects dimensions in the transformed space according to the variability of evaluated points. We then construct the GPR model, and the infill-criterion in the space spanned by the selected dimensions.
We assess the performance of our PCA-BO in terms of the empirical convergence rate and CPU time on multi-modal problems from the COCO benchmark framework. The experimental results show that PCA-BO can effectively reduce the CPU time incurred on high-dimensional problems, and maintains the convergence rate on problems with an adequate global structure. PCA-BO therefore provides a satisfactory trade-off between the convergence rate and computational efficiency opening new ways to benefit from the strength of BO approaches in high dimensional numerical optimization.
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
Notes
- 1.
With an abuse of terminology, the operation \(\mathbf {X} \cup \{\mathbf {x}^*\}\) is understood as appending \(\mathbf {x}^*\) at the bottom row of \(\mathbf {X}\) throughout this paper. \(\mathbf {y}\cup \{f(\mathbf {x}^*)\}\) is defined similarly.
- 2.
Alternatively, the weight can also be computed directly from the function value, e.g., through a parameterized hyperbolic function. However, we do not prefer this approach since it introduces extra parameters that require tuning, and does not possess the discount effect of the rank-based scheme since the weights remain static throughout the optimization.
- 3.
We take the Scipy implementation of DE (https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.differential_evolution.html) with a population size of 20r and the “best1bin” strategy, which uses the binary crossover and calculates the differential vector based on the current best point. Here, we set the evaluation budget to \(20020r^2\) to optimize the infill-criterion.
- 4.
On the 10-dimensional F20 problem, we observed that the standard deviation of BO over 30 runs gradually shrinks to zero after 50 iterations, making the confidence interval disappear in the corresponding subplot.
References
Aage, N., Andreassen, E., Lazarov, B.S.: Topology optimization using PETSc: an easy-to-use, fully parallel, open source topology optimization framework. Struct. Multidisciplinary Optim. 51(3), 565–572 (2014). https://doi.org/10.1007/s00158-014-1157-0
Arsenyev, I., Duddeck, F., Fischersworring-Bunk, A.: Adaptive surrogate-based multi-disciplinary optimization for vane clusters. In: ASME Turbo Expo 2015: Turbine Technical Conference and Exposition. American Society of Mechanical Engineers Digital Collection (2015). https://doi.org/10.1115/GT2015-42164
Blanchet-Scalliet, C., Helbert, C., Ribaud, M., Vial, C.: Four algorithms to construct a sparse kriging kernel for dimensionality reduction. Comput. Stat. 34(4), 1889–1909 (2019). https://doi.org/10.1007/s00180-019-00874-2
Broomhead, D.S.: Radial Basis Functions, Multi-variable Functional Interpolation and Adaptive Networks. Royals Signals and Radar Establishment (1988)
Fang, K.T., Li, R., Sudjianto, A.: Design and Modeling for Computer Experiments. CRC Press, Boca Raton (2005)
Forrester, A.I., Bressloff, N.W., Keane, A.J.: Optimization using surrogate models and partially converged computational fluid dynamics simulations. Proc. R. Soc. A: Math. Phys. Eng. Sci. 462(2071), 2177–2204 (2006). https://doi.org/10.1098/rspa.2006.1679
Forrester, A.I.J., Sóbester, A., Keane, A.J.: Engineering Design via Surrogate Modelling - A Practical Guide. Wiley, Hoboken (2008). https://doi.org/10.1002/9780470770801
Gaudrie, D., Le Riche, R., Picheny, V., Enaux, B., Herbert, V.: From CAD to eigenshapes for surrogate-based optimization. In: 13th World Congress of Structural and Multidisciplinary Optimization. Beijing. (2019). https://hal.archives-ouvertes.fr/hal-02142492
Gunn, S.R.: Support Vector Machines for Classification and Regression, Technical report (1998)
Hansen, N.: The CMA evolution strategy: a comparing review. In: Lozano, J.A., Larrañaga, P., Inza, I., Bengoetxea, E. (eds.) Towards a New Evolutionary Computation. Studies in Fuzziness and Soft Computing, vol. 192., pp. 75–102. Springer, Berlin, Heidelberg (2006). https://doi.org/10.1007/3-540-32494-1_4
Hansen, N., et al.: COmparing continuous optimizers: numbbo/COCO on Github (2019). https://doi.org/10.5281/zenodo.2594848
Hojjat, M., Stavropoulou, E., Bletzinger, K.U.: The vertex morphing method for node-based shape optimization. Comput. Methods Appl. Mech. Eng. 268, 494–513 (2014). https://doi.org/10.1016/j.cma.2013.10.015
Huang, W., Zhao, D., Sun, F., Liu, H., Chang, E.: Scalable Gaussian process regression using deep neural networks. In: Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI 2015, pp. 3576–3582. AAAI Press, Buenos Aires (2015)
Huang, Z., Wang, C., Chen, J., Tian, H.: Optimal design of aeroengine turbine disc based on kriging surrogate models. Comput. Struct. 89(1–2), 27–37 (2011). https://doi.org/10.1016/j.compstruc.2010.07.010
Jeong, S., Murayama, M., Yamamoto, K.: Efficient optimization design method using kriging model. J. Aircraft 42(2), 413–420 (2005). https://doi.org/10.1023/A:1008306431147
Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4), 455–492 (1998). https://doi.org/10.1023/A:1008306431147
Ju, S., Shiga, T., Feng, L., Hou, Z., Tsuda, K., Shiomi, J.: Designing nanostructures for phonon transport via Bayesian optimization. Phys. Rev. X 7(2), 021024 (2017). https://doi.org/10.1103/PhysRevX.7.021024
Kanazaki, M., Takagi, H., Makino, Y.: Mixed-fidelity efficient global optimization applied to design of supersonic wing. Procedia Eng. 67(1), 85–99 (2013). https://doi.org/10.1016/j.proeng.2013.12.008
Kapsoulis, D., Tsiakas, K., Asouti, V., Giannakoglou, K.: The use of Kernel PCA in evolutionary optimization for computationally demanding engineering applications. In: 2016 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1–8 (2016). https://doi.org/10.1109/SSCI.2016.7850203
Kleijnen, J.P.C.: Kriging metamodeling in simulation: a review. Eur. J. Oper. Res. 192(3), 707–716 (2009). https://doi.org/10.1016/j.ejor.2007.10.013
Lam, R., Poloczek, M., Frazier, P., Willcox, K.E.: Advances in Bayesian optimization with applications in aerospace engineering. In: 2018 AIAA Non-Deterministic Approaches Conference, p. 1656 (2018). https://doi.org/10.2514/6.2018-1656
Liu, K., Detwiler, D., Tovar, A.: Metamodel-based global optimization of vehicle structures for crashworthiness supported by clustering methods. In: Schumacher, A., Vietor, T., Fiebig, S., Bletzinger, K.-U., Maute, K. (eds.) WCSMO 2017, pp. 1545–1557. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-67988-4_116
MATLAB: version 9.5.0.944444 (R2018b). The MathWorks Inc., Natick, Massachusetts (2018)
Močkus, J.: On Bayesian methods for seeking the extremum. In: Marchuk, G.I. (ed.) Optimization Techniques 1974. LNCS, vol. 27, pp. 400–404. Springer, Heidelberg (1975). https://doi.org/10.1007/3-540-07165-2_55
Mockus, J.: Bayesian Approach to Global Optimization: Theory and Applications, vol. 37. Springer, Dordrecht (2012). https://doi.org/10.1007/978-94-009-0909-0
Palar, P.S., Liem, R.P., Zuhal, L.R., Shimoyama, K.: On the use of surrogate models in engineering design optimization and exploration: the key issues. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1592–1602 (2019). https://doi.org/10.1145/3319619.3326813
Raponi, E., Bujny, M., Olhofer, M., Aulig, N., Boria, S., Duddeck, F.: Kriging-guided level set method for crash topology optimization. In: 7th GACM Colloquium on Computational Mechanics for Young Scientists from Academia and Industry, GACM, Stuttgart (2017)
Raponi, E., Bujny, M., Olhofer, M., Aulig, N., Boria, S., Duddeck, F.: Kriging-assisted topology optimization of crash structures. Comput. Methods Appl. Mech. Eng. 348, 730–752 (2019). https://doi.org/10.1016/j.cma.2019.02.002
Raponi, E., Bujny, M., Olhofer, M., Boria, S., Duddeck, F.: Hybrid Kriging-assisted level set method for structural topology optimization. In: 11th International Conference on Evolutionary Computation Theory and Applications, Vienna (2019). https://doi.org/10.5220/0008067800700081
Rasmussen, C., Williams, C.: Gaussian Processes for Machine Learning. Adaptative Computation and Machine Learning Series. University Press Group Limited (2006)
Santner, T.J., Williams, B.J., Notz, W.I.: The Design and Analysis of Computer Experiments. Springer Series in Statistics. Springer, Dordrecht (2003). https://doi.org/10.1007/978-1-4757-3799-8
Schölkopf, B., Smola, A., Müller, K.R.: Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput. 10(5), 1299–1319 (1998). https://doi.org/10.1162/089976698300017467
van Stein, B., Wang, H., Kowalczyk, W., Emmerich, M., Bäck, T.: Cluster-based Kriging approximation algorithms for complexity reduction. Appl. Intell. 50(3), 778–791 (2019). https://doi.org/10.1007/s10489-019-01549-7
Storn, R., Price, K.: Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4), 341–359 (1997). https://doi.org/10.1023/A:1008202821328
Ueno, T., Rhone, T.D., Hou, Z., Mizoguchi, T., Tsuda, K.: COMBO: an efficient Bayesian optimization library for materials science. Mater. Discov. 4, 18–21 (2016). https://doi.org/10.1016/j.md.2016.04.001
Vapnik, V.N.: The Nature of Statistical Learning Theory. Springer, New York (1995). https://doi.org/10.1007/978-1-4757-3264-1
Viana, F.A., Simpson, T.W., Balabanov, V., Toropov, V.: Special section on multidisciplinary design optimization: metamodeling in multidisciplinary design optimization: how far have we really come? AIAA J. 52(4), 670–690 (2014). https://doi.org/10.2514/1.J052375
Vivarelli, F., Williams, C.K.I.: Discovering hidden features with Gaussian processes regression. In: Kearns, M.J., Solla, S.A., Cohn, D.A. (eds.) Advances in Neural Information Processing Systems, vol. 11, pp. 613–619. MIT Press (1999)
Wang, H., van Stein, B., Emmerich, M., Bäck, T.: A new acquisition function for Bayesian optimization based on the moment-generating function. In: 2017 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2017, Banff, AB, Canada, 5–8 October 2017, pp. 507–512. IEEE (2017). https://doi.org/10.1109/SMC.2017.8122656
Wang, Z., Hutter, F., Zoghi, M., Matheson, D., De Freitas, N.: Bayesian optimization in a billion dimensions via random embeddings (2016)
Yoshimura, M., Shimoyama, K., Misaka, T., Obayashi, S.: Topology optimization of fluid problems using genetic algorithm assisted by the Kriging model. Int. J. Numer. Method Eng. 109(4), 514–532 (2016). https://doi.org/10.1002/nme.5295
Yuan, Y.X.: A Review of Trust Region Algorithms for Optimization
Acknowledgments
Our work was supported by the Paris Ile-de-France Region and by COST Action CA15140 “Improving Applicability of Nature-Inspired Optimisation by Joining Theory and Practice (ImAppNIO)”.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Raponi, E., Wang, H., Bujny, M., Boria, S., Doerr, C. (2020). High Dimensional Bayesian Optimization Assisted by Principal Component Analysis. In: Bäck, T., et al. Parallel Problem Solving from Nature – PPSN XVI. PPSN 2020. Lecture Notes in Computer Science(), vol 12269. Springer, Cham. https://doi.org/10.1007/978-3-030-58112-1_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-58112-1_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58111-4
Online ISBN: 978-3-030-58112-1
eBook Packages: Computer ScienceComputer Science (R0)