Bayesian Optimization For Multi-Objective Mixed-Variable Problems

Optimization is an inherent part of design for complex physical systems. Often optimization problems are posed as noisy black-box problems subject to constraints, where each function call requires an extremely expensive computation or a physical experiment. Many of these problems require optimizing a mixed-variable design space (combinatorial, discrete, and continuous) for multiple non-preferential objectives. Architected material design Frazier and Wang (2015); Chen et al. (2018a, 2019); Shaw et al. (2019); Song et al. (2019a); Vangelatos et al. (2021), hyper-parameter tuning for machine learning algorithms Snoek et al. (2012); Chen et al. (2018b); Oh et al. (2018), drug design Pyzer-Knapp (2018); Korovina et al. (2020), fluid machinery Sheikh et al. (2022a, b); doi:10.1177/0309524X17709732; Sheikh et al. (2021) and, controller sensor placement Krause et al. (2008) pose such problems. Due to their cost of evaluation, Bayesian optimization is a natural candidate for their optimization.

Much research has gone into Bayesian optimization for continuous design spaces using Gaussian processes (GP) as a surrogate model and efficiently optimizing this design space with a minimum number of expensive function calls Mockus (1994); Rasmussen and Williams (2006); Brochu et al. (2010). Despite the success of continuous variable Bayesian optimization strategies, multi-objective and mixed-variable problems remain an area of open research. The inherent continuous nature of GP makes dealing with mixed-variable problems challenging. Finding a Pareto-front for multi-objective problems, and parallelizing function calls for batch updates, Q-batch, also remain challenges in the sequential setting of the BO algorithm. Hedge strategies, which use a portfolio of acquisition functions to reduce the effect of choosing a particular acquisition function, have not been formulated for multi-objective problems.

In this paper, we present a Mixed-variable, Multi-Objective Bayesian Optimization (MixMOBO) algorithm, the first generalized framework that can deal with mixed-variable, multi-objective problems in small data setting and can optimize a noisy black-box function with a small number of function calls.

Genetic algorithms, such as NSGA-II Deb et al. (2002), are well known for dealing with mixed-variable spaces and finding an optimal Pareto-frontier. However, these algorithms require a large number of black-box function calls and are not well suited to expensive small-data problems. Our approach is to use a GA to optimize the surrogate model itself and find a Pareto-frontier. Diversification is ensured by the distance metrics used while optimizing the surrogate model. This method allows cheap Q-batch samples from within the GA generation, and also allows the use of commonly used acquisition functions such as Expected Improvement (EI), Probability of Improvement (PI) and Upper Confidence Bound (UCB) Brochu et al. (2011), which work well for single objective problems. We note here that other metrics can easily be incorporated instead of a distance metric within the GA setting and is one of the areas of our future work. Using a GA on a mixed variable surrogate model in a multi-objective setting allows us to work with modified kernels that were developed for mixed-variable problems in literature. We also present a new acquisition function, ‘Stochastic Monte-Carlo’ (SMC), which performs well for multi-objective categorical variable problems Vangelatos et al. (2021).

Hedge strategies for Bayesian optimization are efficient for single objective algorithms. We present here our Hedge Multi-Objective (HedgeMO) algorithm, which uses a portfolio of acquisition functions for multi-objective problems and can work with Q-batch updates. It is an extension of GP-Hedge Brochu et al. (2011), which has regret bounds, and the same bounds hold for HedgeMO.

We note here that MixMOBO is designed for mixed-variable, multi-objective problems. Although there are algorithms in the literature that can solve problems with a subset of these attributes (e.g. mixed-variable single-objective or multi-objective continuous variable problems), no algorithm, to our knowledge, can deal with all of these attributes. In addition, MixMOBO outputs a batch of query points and uses HedgeMO, the first multi-objective hedging strategy. To the authors’ knowledge, no existing approaches can achieve all this within a single framework.

In summary, the main contributions of our work are as follows:

• •

  We present Mixed-variable, Multi-Objective Bayesian Optimization (MixMOBO), the first algorithm that can deal with mixed-variable, multi-objective problems. The framework uses GA to optimize the acquisition function on a surrogate surface, so it can use modified kernels or surrogate surfaces developed to deal with mixed-variable problems in previous studies. This extends the capabilities of previous approaches in literature to handle mixed-variable and multi-objective problems as well if adopted within our framework, since our framework is agnostic to the underlying GP kernel over mixed-variables.

• •

  GA is used to optimize surrogate models, which allows the optimization of multi-objective problems. ‘$Q$-batch’ samples can be extracted in parallel from within the GA generation without sacrificing diversification.

• •

  We present a Hedge Multi-Objective (HedgeMO) strategy for multiple objectives for which regret bounds hold. We also present an acquisition function, Stochastic Monte-Carlo (SMC), which performs well for combinatorial multi-objective problems, and use it as part of our HedgeMO portfolio.

• •

  We benchmark our algorithm against other mixed-variable algorithms and prove that MixMOBO performs well on test functions. We applied MixMOBO to a practical engineering problem: the design of a new architected meta-material that was optimized to have the maximum possible strain-energy density within the constraints of a design space. The fabrication and testing of this new material showed that is has a normalized strain energy density that is $10^{4}$ times greater than existing unblemished microlattice structures in literature.

The rest of the paper is organized in the following manner: Section 3 defines the optimization problem to be solved with MixMOBO. The detailed workings of MixMOBO and HedgeMO are presented in Section 4. Section 5 details the validation tests performed on our framework to test its efficiency and comparison to existing algorithms. Our application of MixMOBO for design of architected materials and its results are presented in Section 6.

We pose the multi-objective and mixed-variable problem as:

for maximizing the objective. Here $\vec{f}(\vec{w})=[f_{1}(\vec{w}),f_{2}(\vec{w}),\ldots$ $,f_{k}(\vec{w})]$ are the $K$ non-preferential objectives to be maximized, and $\vec{w}$ is a mixed-variable vector, defined as {$\vec{w}\in\mathcal{W}\}=\{\vec{x}\in\mathcal{X},\vec{y}\in\mathcal{Y},\vec{z}\in\mathcal{Z}\}$. $\vec{x}$ is an $m$-dimensional vector defined over a bounded set $\mathcal{X}\subset\mathbb{R}^{m}$ representing $m$ continuous variables. Ordinal and categorical variables are defined as $\vec{y}=[y_{1},\ldots,y_{n}]$ and $\vec{z}=[z_{1},\ldots,z_{o}]$, respectively. Each variable $y_{j}\in\{O_{1},\ldots,O_{j}\}$ takes one of $O_{j}$ ordinal ‘levels’ (discrete numbers on the real-number line) and each categorical variable takes a value $z_{j}\in\{C_{1},\ldots,C_{j}\}$ from $C_{j}$ unordered categories (that cannot, by definition, be ordered on the real-number line). $\mathcal{Y}$ and $\mathcal{Z}$ are the ordinal and combinatorial spaces respectively.

Generally, $\{\vec{w}_{opt}\}$ is a set of Pareto-optimal solution vectors i.e., vectors that are not Pareto-dominated by any other vector. A vector $\vec{w}$ is Pareto-dominated by $\vec{w}^{\prime}$, iff $f_{k}(\vec{w})\leq f_{k}(\vec{w}^{\prime})~{}\forall~{}k=1,...K$. This $\{\vec{w}_{opt}\}$ is the optimal set found by MixMOBO, details of which are presented in the following section.

MixMOBO is designed to deal with mixed-variable, multi-objective problems. However, no other small-data algorithm, to the authors’ knowledge, can similarly deal with all the attributes of such problems to provide an honest comparison. In the absence of such competition, we use the specific case of mixed-variable, single-objective problems to provide a comparison to state-of-the-art algorithms present for such problems and prove that even for this subset case, MixMOBO is able to perform better than existing algorithms in the literature. We then perform further experiments in both single and multi-objective settings to show the efficacy of the HedgeMO algorithm compared to stand-alone acquisition functions and the performance of SMC in the multi-objective setting.

We benchmarked MixMOBO against a range of existing state-of-the-art optimization strategies that are commonly used for optimizing expensive black-box functions with mixed-variable design spaces. We chose the following single objective optimization algorithms for comparison: CoCaBO Ru et al. (2020), which combines the multi-armed bandit (MAB) and Bayesian optimization approaches by using a mixing kernel. CoCaBO has been shown to be more efficient than GPyOpt (one-hot encoding approach GPyOptAuthors (2016)) and EXP3BO (multi-armed bandit (MAB approach Gopakumar et al. (2018)). We used CoCaBO with a mixing parameter of $0.5$. We also tested MixMOBO against GBRT, a sequential optimization technique using gradient boosted regression trees Scikit-learn (2021). TPE_Hyperopt (Tree-structured Parzen Estimator) is a sequential method for optimizing expensive black-box functions, introduced by Bergstra et al. (2011). SMAC3 is a popular Bayesian optimization algorithm in combination with an aggressive racing mechanism Hutter et al. (2011). Both of these algorithms, in addition to Random Sampling, were used as baselines. Publicly available libraries for these algorithms were used.

Six different test functions for mixed variables were chosen as benchmarks. A brief description of these test functions and their properties is given below with further details in Appendix A:

Contamination Problem: This problem, introduced by Hu et al. (2011), considers a food supply chain with various stages in the chain where food may be contaminated with pathogens. The objective is to maximize the reward of prevention efforts while making sure the chain does not get contaminated. It is widely used as a benchmark for binary categorical variables. We use the problem as a benchmark with $21$ binary categorical variables.

Encrypted Amalgamated: An anisotropic, mixed-variable function created using a combination of other commonly used test functions Tušar et al. (2019). We modify the combined function so that it can be used with mixed variables. In particular, it is adapted for categorical variables by encrypting the input space with a random vector, which produces a random landscape mimicking categorical variables Vangelatos et al. (2021). Our Encrypted Amalgamated function has $13$ inputs: $8$ categorical, $3$ ordinal variables (with $5$ categories or states each) and $2$ continuous.

NK Landscapes: This is a popular benchmark for simulating categorical variable problems using randomly rugged, interconnected landscapes Kauffman and Levin (1987); Li et al. (2006). The fitness landscape can be produced with random connectivity and number of optima. The problem is widely used in evolutionary biology and control optimization and is $NP$-complete. The probability of connectivity between $NK$ is controlled by a ‘ruggedness’ parameter, which we set at $20\%$. We test the Li et al. (2006) variant with $8$ categorical variables with $4$ categories each.

Rastringin: This is an isotropic test function, commonly used for continuous design spaces Tušar et al. (2019). We use a $9$-D Rastringin function for testing a design space of $3$ continuous and $6$ ordinal variables with $5$ discrete states.

Encrypted Syblinski-Tang: This function is isotropic Tušar et al. (2019), and we have modified it as we did with the Encrypted Amalgamated test function so that it can work with categorical variables and was used as a representative benchmark for $N$-categorical variable problems. The $10$-D variant tested here consists only of categorical variables with $5$ categories each.

Encrypted ZDT6: This is a multi-objective test function introduced by Zitzler et al. (2000) that we modified with encryption so that it can deal with mixed variables. The test function is non-convex and non-uniform in the parameter space. We test ZDT6 with 10 categorical variables with 5 states each. ZDT6 was only used for testing HedgeMO.

To the extent of our knowledge, no other optimization algorithm is capable of handling mixed-variable, multi-objective problems in small-data settings. Thus, we have no direct comparisons between MixMOBO and other published algorithms. Therefore, we tested MixMOBO against a variant of NSGA-II Deb et al. (2002) with the ZDT4 and ZDT6 test functions with mixed variables. However, we found that using a GA required more than $10^{2}$ more function calls to find the Pareto front to a similar tolerance. For visualization purposes, we do not plot the GA results.

All of the optimization algorithms were run as maximizers, with a $0.005$ noise variance built into all the benchmarks. The budget for each benchmark test was fixed at 250 function calls including the evaluations of 50 initial randomly sampled data points for all algorithms, except for SMAC3 which determines its own initial sample size. The algorithms were run in single output setting (GBRT, CoCaBO and MixMOBO’s batch mode was not used for fair comparison). Each algorithm was run 10 times for every benchmark. Our metric for optimization is the ‘Normalized Reward’, defined as (current optimum - random sampling optimum)/(global optimum - random sampling optimum). Figure 1 shows the Normalized Rewards versus the number of black-box function evaluations for MixMOBO and five other algorithms. The mean and standard deviation of the Normalized Rewards of the $10$ runs for each algorithm, along with their standard deviations (S.D.), are plotted. The width of each of the translucent colored bands is equal to $1/5$ of their S.D.

MixMOBO outperforms all of the other baselines and is significantly better in dealing with mixed-variable problems. GBRT is the next best algorithm and performs better than MixMOBO on the Rastringin function; however, note that the Rastringin function does not include any categorical variables. For problems involving categorical variables, MixMOBO clearly outperforms the others. TPE and CoCaBO have similar performances, and SMAC3 has the poorest performance. All three are outdistanced by MixMOBO.

We then perform experiments to test the performance of our HedgeMO algorithm by comparing it to four different acquisition functions which make up the entirety of its porfolio. These acquisition functions, namely, EI, PI, UCB, and SMC, along with HedgeMO are tested on three different test functions: the Encrypted Amalgamated, Encrypted Syblinski-Tang, and Encrypted ZDT6. The latter is used as the multi-objective test function. The Normalized Reward for the multi-objective Encrypted ZDT6 is defined as (current P-optimum - random sampling P-optimum)/(global P-optimum - random sampling P-optimum). Here, P-optimum$=\frac{1}{N}\sum_{i=1}^{N}exp$(-minimum Hamming distance in parameter space between $i^{th}$ global Pareto-optimal point and any point in the current Pareto-optimal set), where $N$ is the number of global Pareto-optimal points.

The results of our acquisition function comparisons are shown in Figure 2, which shows that HedgeMO performs well across all three test functions. For single-objective test functions, PI outperforms HedgeMO for Encrypted Amalgamated test function. However, for the multi-objective Encrypted ZDT6 test function, PI performs significantly worse and is outperformed by both SMC and UCB. SMC performs well on multi-objective problems combinatorial problems and hence should be a part of portfolio for a hedging algorithm.

These results prove that for a range of different problems, acquisition function choice can play a huge role in the performance of the algorithm. For a black-box function, this information can not be known a priori, making hedging necessary. HedgeMO consistently performs well in all scenarios and ensures efficiency across a range of different problems. Thus, for unknown black-box functions, HedgeMO should be the hedge strategy of choice for multi-objective problems.

We applied our MixMOBO framework to the optimization of the design of architected, microlattice structures. Advances in modeling, fabrication, and testing of architected materials have promulgated their utility in engineering applications, such as ultralight Zheng et al. (2014); Pham et al. (2019); Zhang et al. (2019), reconfigurable Xia et al. (2019), and high-energy-absorption materials Song et al. (2019b), and in bio-implants Song et al. (2020). The optimization of architected materials Bauer et al. (2016); Pham et al. (2019); Xia et al. (2019); Zhang et al. (2019) often requires searching huge combinatorial design spaces, where the evaluation of each design is expensive. Meza et al. (2014); Berger et al. (2017); Tancogne-Dejean et al. (2018).

The design space for the architected material we optimize here has $\sim$ 8.5 billion possible combinations of its 17 categorical inputs (one with 2 possible states, and the other 16 with 4 possible states). Our goal is to maximize the strain energy density of a microlattice structure. We maximize the strain energy density (which is extremely expensive to compute, even for one design) by minimizing the buckling load $P_{c}$, while maintaining the lattice’s structural integrity and stiffness before fracturing. Minimizing $P_{c}$ (a proxy for maximizing the strain energy density by instigating buckling which leads to the densification of the deformed lattice members) is a more computationally tractable cost function to evaluate (but, it is still expensive and involves solving a numerical finite element code for each evaluation of the cost function.) The manufacturing and testing details of our methodology are included in Vangelatos et al. (2021), which focuses on the material aspects of the problem.

The design space consists of choosing one of four possible unit cells (shown in the upper left of Fig. 3, each with one or more defects (shown in color) in them, at each of the 16 independent lattice sites) creating 16 of the categorical inputs with 4 possible values; and the choice of whether the cells are connected along their faces or along their edges on $45^{\text{o}}$-diagonals (shown in the upper right panel of Fig. 3) creating the $17^{th}$ categorical input with 2 possible values.

The minimization of $P_{c}$ using MixMOBO was initialized with 50 random structures and the evaluation budget, including initial samples, was set at 250. The algorithm achieved a $42\%$ improvement in the $P_{c}$ of the lattice structure over the best structure obtained with the first 50 random samples (Figure 3). The optimal microlattice obtained using $P_{c}$ as a proxy with MixMOBO has an experimentally measured normalized strain energy density that is 12,030 times greater than that of the unblemished microlattice structure with no defects that is cited in the literature to have the best strain energy density Vangelatos et al. (2020), a $4$ orders of magnitude improvement. Table 1 shows the properties of the fabricated and experimentally measured design created with MixMOBO. The choices of the units cells in the optimally designed lattice that were determined by MixMOBO are not intuitive and have no obvious pattern or structure. Images of our optimized structures using Helium Ion Microscopy (HIM) 4, shows the comparison of the Unblemished structure from literature with our MixMOBO Optimal structure, before and after loading. It is evident that the MixMOBO Optimal structure due to its densification mechanism, can handle much higher loads without breaking Vangelatos et al. (2021).

The existing optimization literature does not offer an algorithm for optimizing multi-objective, mixed-variable problems with expensive black-box functions. We have introduced Mixed-variable Multi-Objective Bayesian Optimization (MixMOBO), the first BO based algorithm for optimizing such problems. MixMOBO is agnostic to the underlying kernel. It is compatible with modified kernels and other surrogate methods developed in previous studies for mixed-variable problems. MixMOBO allows for parallel batch updates without repeated evaluations of the surrogate surface, while maintaining diversification within the solution set. We presented the Hedge Multi-Objective (HedgeMO) algorithm, a novel Hedge strategy for which regret bounds hold for multi-objective problems. A new acquisition function, Stochastic Monte-Carlo (SMC) was also proposed as part of the HedgeMO portfolio. MixMOBO and HedgeMO were benchmarked and shown to be significantly better on a variety of test problems compared to existing mixed-variable optimization algorithms. MixMOBO was then applied to the real-world optimization of an architected micro-lattice, and we increased the structure’s strain-energy density by $10^{4}$ compared to existing Unblemished structures in the literature reported to have highest strain energy density. Our future work entails further testing multi-objective and ‘$Q$-batch’ settings. We have also applied MixMOBO for optimization of draft-tubes for hydrokinetic turbines Sheikh et al. (2022b) and Cauchy symmetric meta-material structures and are currently applying it for optimization of vertical-axis wind turbines.

The authors would like to thank Chiyu ‘Max’ Jiang, research scientist at Waymo Research, and Professor Uros Seljak, Department of Physics, University of California at Berkeley (UCB) for insightful discussions regarding Bayesian optimization. We would also like to thank Zacharias Vangelatos and Professor Costas P. Grigoropoulos, Department of Mechanical Engineering, University of California at Berkeley (UCB) for the collaboration to design and manufacture architected materials, conduct nanoindentation, SEM, and HIM experiments. This work used the Extreme Science and Engineering Discovery Environment (XSEDE), which is supported by National Science Foundation grant number ACI-1548562 through allocation TG-CTS190047.

All the results in this manuscript can be replicated. The complete data sets, MixMOBO algorithm or any other supplementary material and information required for replication are available from the corresponding author on reasonable request.