(282a) Clustering Based Surrogate Optimization (CBSO) Framework for the Global Optimization of Box-Constrained Systems.

Global optimization features in many complex problems related to oil and gas, aerospace, pharmaceutical, supply chain, chemical, and medical industries. Despite the advances in processing power and computing technologies, global optimization of systems involving high-fidelity, expensive, black-box simulations (e.g., CFD or Computational Fluid Dynamics) is complex and time-consuming.(Forrester and Keane, 2009; McBride and Sundmacher, 2019)

Widely used gradient-based algorithms are not suited for black-box optimization, as gradient evaluations are prohibitive. Derivative-free optimization (DFO) algorithms do not require gradient information, hence are more suitable. Commonly used DFO algorithms include metaheuristic algorithms such as Particle Swarm Optimization (PSO), Genetic Algorithm (GA), and Simulated Annealing (SA) and direct search algorithms such as mesh adaptive direct search (MADS), generating pattern search (GPS), and generating search set (GSS), etc. They typically require many function evaluations and cannot guarantee convergence to a global optimum. In many cases, they get stuck in a local optimum.(Rios and Sahinidis, 2013).

The time and cost for optimizing an expensive system are largely determined by the number of function evaluations. Therefore, the concept of surrogate-based global optimization (SBGO), or the idea of employing simple and computationally cheap surrogate models for global optimization has received much attention over the last few decades. This has prompted numerous works, including review articles on SBGO techniques to assist global optimization of black box systems. (Bhosekar and Ierapetritou, 2018; Queipo et al., 2005; Regis and Shoemaker, 2007)

There are two key motivations behind the development of this work. First, most SBGO works have focused on the development of global surrogates or surrogates built over the entire design space (Haftka et al., 2016), such as single surrogates (Regis and Shoemaker, 2007), multiple surrogates (Gu et al., 2012), and ensemble surrogates (Müller and Shoemaker, 2014). These approaches may face challenges for complex systems that display diverse characteristics across various subdomains or regions of the design space. Given the task of representing the function over the entire space, these surrogates tend to be highly complex. A more natural approach towards optimizing such systems is to identify the various zones or regions of the input space and develop a specific and simple surrogate for each region. Such a divide-and-conquer approach decomposes a large and complex global optimization problem into multiple simpler optimization problems. Multiple local surrogates also offer better accuracy. While clustering has been as used as means of exploration or design space reduction for global optimization using global surrogates (Dong et al., 2018; Müller and Piché, 2011; Ye and Pan, 2017), the existing body of literature on utilizing clustering and multiple local surrogates for surrogate based global optimization of single objective box-constrained problems is quite limited. Second, some SBGO algorithms exploit surrogate specific features such as the expected improvement in Kriging (Jones et al., 1998; Viana et al., 2013). As highlighted by numerous works, the choice of best surrogate may vary from system to system (Ahmad and Karimi, 2021; Bhosekar and Ierapetritou, 2018). Therefore, surrogate specific SBGO algorithms may not be the best choice across all systems. We aim to develop clustering-based optimization algorithm that is independent of surrogate model/technique.

In this work, we have developed a Clustering Based Surrogate Optimization (CBSO) algorithm that utilizes a partition-based clustering algorithm and multiple local surrogates for global optimization. The key features of our algorithm are as follows. First, the input design space is partitioned into clusters using K-means clustering and the best surrogate is developed for each cluster. We identify the best surrogate for each cluster using k-fold cross validation and we optimize each surrogate within their cluster domain. Second, the surrogate model and technique can vary from cluster to cluster for better accuracy, Third, the number of clusters are identified automatically using the elbow or silhouette method. Finally, we sample a maximum of three points using only the best clusters and their surrogates identified through local exploitation (Törn, 1986). Once the new points are sampled, we update our dataset and we cluster the new set of points to obtain a new clustering profile. We repeat the above process using the new set of clusters, and we repeat this iterative clustering-optimization process until the user-specified maximum number of functional evaluations is reached. Our proposed algorithm aims at answering the following key questions: Which is the better method (elbow vs silhouette) for K-means clustering? What is the best set of models or model library for clustering-based surrogate optimization?

We have evaluated our algorithm over 43 box-constrained problems with dimensions ranging from two to ten (Surjanovic and Bingham, 2013). The Latin Hypercube Sampling technique is used to sample our initial design. The surrogates considered for this work include Multivariate Adaptive Regression Spline (MARS), Polynomial Response Surface Models (PRSMs), and six types of radial basis functions (Biharmonic, Cubic, Multi-quadratic, Inverse Multiquadric, Gaussian, and Thin Plate Spline). This presentation will introduce the details of our algorithm, and discuss the results across the different model libraries and the different heuristics methods used for K-means clustering. We also present a comparison of the algorithm’s performance over these functions against several DFO solvers and algorithms, including NOMAD, SNOBFIT, and the Two Stage Framework (TSF) (developed by our lab and presented at AIChE 2019 Annual Meeting) (Garud et al., 2019).

REFERENCES:

Ahmad, M., Karimi, I.A., 2021. Revised learning based evolutionary assistive paradigm for surrogate selection (LEAPS2v2). Computers & Chemical Engineering 152, 107385. https://doi.org/10.1016/j.compchemeng.2021.107385

Bhosekar, A., Ierapetritou, M., 2018. Advances in surrogate based modeling, feasibility analysis, and optimization: A review. Computers & Chemical Engineering 108, 250–267. https://doi.org/10.1016/j.compchemeng.2017.09.017

Dong, H., Song, B., Wang, P., Dong, Z., 2018. Surrogate-based optimization with clustering-based space exploration for expensive multimodal problems. Struct Multidisc Optim 57, 1553–1577. https://doi.org/10.1007/s00158-017-1826-x

Forrester, A.I.J., Keane, A.J., 2009. Recent advances in surrogate-based optimization. Progress in Aerospace Sciences 45, 50–79. https://doi.org/10.1016/j.paerosci.2008.11.001

Garud, S.S., Mariappan, N., Karimi, I.A., 2019. Surrogate-based black-box optimisation via domain exploration and smart placement. Computers & Chemical Engineering 130, 106567. https://doi.org/10.1016/j.compchemeng.2019.106567

Gu, J., Li, G.Y., Dong, Z., 2012. Hybrid and adaptive meta-model-based global optimization. Engineering Optimization 44, 87–104. https://doi.org/10.1080/0305215X.2011.564768

Haftka, R.T., Villanueva, D., Chaudhuri, A., 2016. Parallel surrogate-assisted global optimization with expensive functions – a survey. Struct Multidisc Optim 54, 3–13. https://doi.org/10.1007/s00158-016-1432-3

Jones, D.R., Schonlau, M., Welch, W.J., 1998. Efficient Global Optimization of Expensive Black-Box Functions. Journal of Global Optimization 13, 455–492. https://doi.org/10.1023/A:1008306431147

McBride, K., Sundmacher, K., 2019. Overview of Surrogate Modeling in Chemical Process Engineering. Chemie Ingenieur Technik 91, 228–239. https://doi.org/10.1002/cite.201800091

Müller, J., Piché, R., 2011. Mixture surrogate models based on Dempster-Shafer theory for global optimization problems. J Glob Optim 51, 79–104. https://doi.org/10.1007/s10898-010-9620-y

Müller, J., Shoemaker, C.A., 2014. 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. https://doi.org/10.1007/s10898-014-0184-0

Queipo, N.V., Haftka, R.T., Shyy, W., Goel, T., Vaidyanathan, R., Kevin Tucker, P., 2005. Surrogate-based analysis and optimization. Progress in Aerospace Sciences 41, 1–28. https://doi.org/10.1016/j.paerosci.2005.02.001

Regis, R.G., Shoemaker, C.A., 2007. A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions. INFORMS Journal on Computing 19, 497–509. https://doi.org/10.1287/ijoc.1060.0182

Rios, L.M., Sahinidis, N.V., 2013. Derivative-free optimization: a review of algorithms and comparison of software implementations. J Glob Optim 56, 1247–1293. https://doi.org/10.1007/s10898-012-9951-y

Surjanovic, S., Bingham, D., 2013. Virtual Library of Simulation Experiments: Test Functions and Datasets. https://www.sfu.ca/~ssurjano/about.html (accessed 3.2.23).

Törn, A.A., 1986. Clustering Methods in Global Optimization. IFAC Proceedings Volumes 19, 247–252. https://doi.org/10.1016/S1474-6670(17)59803-1

Viana, F.A.C., Haftka, R.T., Watson, L.T., 2013. Efficient global optimization algorithm assisted by multiple surrogate techniques. J Glob Optim 56, 669–689. https://doi.org/10.1007/s10898-012-9892-5

Ye, P., Pan, G., 2017. Global optimization method using ensemble of metamodels based on fuzzy clustering for design space reduction. Engineering with Computers 33, 573–585. https://doi.org/10.1007/s00366-016-0490-x