Gaussian Process (GP) models are widely utilized as surrogate models in scientific and engineering fields. However, standard GP models are limited to continuous variables due to the difficulties in establishing correlation structures for categorical variables. To overcome this limitation, we introduce \textbf{WE}ighted Euclidean distance matrices \textbf{G}aussian \textbf{P}rocess (WEGP). WEGP constructs the kernel function for each categorical input by estimating the Euclidean distance matrix (EDM) among all categorical choices of this input. The EDM is represented as a linear combination of several predefined base EDMs, each scaled by a positive weight. The weights, along with other kernel hyperparameters, are inferred using a fully Bayesian framework. We analyze the predictive performance of WEGP theoretically. Numerical experiments validate the accuracy of our GP model, and by WEGP, into Bayesian Optimization (BO), we achieve superior performance on both synthetic and real-world optimization problems. The code is available at: \url{https://github.com/pmy0124nus/WEGP.}

Constrained Bayesian optimization (CBO) methods have seen significant success in black-box optimization with constraints. One of the most commonly used CBO methods is the constrained expected improvement (CEI) algorithm. CEI is a natural extension of expected improvement (EI) when constraints are incorporated. However, the theoretical convergence rate of CEI has not been established. In this work, we study the convergence rate of CEI by analyzing its simple regret upper bound. First, we show that when the objective function $f$ and constraint function $c$ are assumed to each lie in a reproducing kernel Hilbert space (RKHS), CEI achieves the convergence rates of $\mathcal{O} \left(t^{-\frac{1}{2}}\log^{\frac{d+1}{2}}(t) \right) \ \text{and }\ \mathcal{O}\left(t^{\frac{-\nu}{2\nu+d}} \log^{\frac{\nu}{2\nu+d}}(t)\right)$ for the commonly used squared exponential and Matérn kernels, respectively. Second, we show that when $f$ is assumed to be sampled from Gaussian processes (GPs), CEI achieves similar convergence rates with a high probability. Numerical experiments are performed to validate the theoretical analysis.

Training machine learning models inherently involves a resource-intensive and noisy iterative learning procedure that allows epoch-wise monitoring of the model performance. However, the insights gained from the iterative learning procedure typically remain underutilized in multi-objective hyperparameter optimization scenarios. Despite the limited research in this area, existing methods commonly identify the trade-offs only at the end of model training, overlooking the fact that trade-offs can emerge at earlier epochs in cases such as overfitting. To bridge this gap, we propose an enhanced multi-objective hyperparameter optimization problem that treats the number of training epochs as a decision variable, rather than merely an auxiliary parameter, to account for trade-offs at an earlier training stage. To solve this problem and accommodate its iterative learning, we then present a trajectory-based multi-objective Bayesian optimization algorithm characterized by two features: 1) a novel acquisition function that captures the improvement along the predictive trajectory of model performances over epochs for any hyperparameter setting and 2) a multi-objective early stopping mechanism that determines when to terminate the training to maximize epoch efficiency. Experiments on synthetic simulations and hyperparameter tuning benchmarks demonstrate that our algorithm can effectively identify the desirable trade-offs while improving tuning efficiency.

The expected improvement (EI) is one of the most popular acquisition functions for Bayesian optimization (BO) and has demonstrated good empirical performances in many applications for the minimization of simple regret. However, under the evaluation metric of cumulative regret, the performance of EI may not be competitive, and its existing theoretical regret upper bound still has room for improvement. To adapt the EI for better performance under cumulative regret, we introduce a novel quantity called the evaluation cost which is compared against the acquisition function, and with this, develop the expected improvement-cost (EIC) algorithm. In each iteration of EIC, a new point with the largest acquisition function value is sampled, only if that value exceeds its evaluation cost. If none meets this criteria, the current best point is resampled. This evaluation cost quantifies the potential downside of sampling a point, which is important under the cumulative regret metric as the objective function value in every iteration affects the performance measure. We establish in theory a high-probability regret upper bound of EIC based on the maximum information gain, which is tighter than the bound of existing EI-based algorithms. It is also comparable to the regret bound of other popular BO algorithms such as Thompson sampling (GP-TS) and upper confidence bound (GP-UCB). We further perform experiments to illustrate the improvement of EIC over several popular BO algorithms.

Local Bayesian optimization is a promising practical approach to solve the high dimensional black-box function optimization problem. Among them is the approximated gradient class of methods, which implements a strategy similar to gradient descent. These methods have achieved good experimental results and theoretical guarantees. However, given the distributional properties of the Gaussian processes applied on these methods, there may be potential to further exploit the information of the Gaussian processes to facilitate the BO search. In this work, we develop the relationship between the steps of the gradient descent method and one that minimizes the Upper Confidence Bound (UCB), and show that the latter can be a better strategy than direct gradient descent when a Gaussian process is applied as a surrogate. Through this insight, we propose a new local Bayesian optimization algorithm, MinUCB, which replaces the gradient descent step with minimizing UCB in GIBO. We further show that MinUCB maintains a similar convergence rate with GIBO. We then improve the acquisition function of MinUCB further through a look ahead strategy, and obtain a more efficient algorithm LA-MinUCB. We apply our algorithms on different synthetic and real-world functions, and the results show the effectiveness of our method. Our algorithms also illustrate improvements on local search strategies from an upper bound perspective in Bayesian optimization, and provides a new direction for future algorithm design.

In practice, objective functions of real-time control systems can have multiple local minimums or can dramatically change over the function space, making them hard to optimize. To efficiently optimize such systems, in this paper, we develop a parallel global optimization framework that combines direct search methods with parallel Bayesian optimization. It consists of an iterative global and local search that searches broadly through the entire global space for promising regions and then efficiently exploits each local promising region. We prove the asymptotic convergence properties of the proposed framework and conduct several numerical experiments to illustrate its empirical performance. We also provide a real-time control problem to illustrate the efficiency of our proposed algorithm.Note to Practitioners—This work is motivated by a collision avoidance problem of vessels aided with onboard agent-based simulations. The simulation on one vessel can predict potential conflicts with other vessels on a pre-defined trajectory. In heavy congestion regions, the environment is highly dynamic and thus it is difficult to find a much safer alternative trajectory if collision is predicted on the current one. Moreover, for such real-time decisions, the control system should be quick in response to improve safety. The proposed metamodel based algorithm is designed for quick decision in such highly dynamic systems. The algorithm employs a decomposition of the response surface to better handle the multi-modal surface resulting from the highly dynamic environment. Specifically, it first looks at the large-scale trend globally (filter out the many local fluctuations that may otherwise trap the algorithm) to locate potential promising regions and then proceeds to this local regions for more detailed local search. To make quick decisions, it uses fast direct search algorithms in the local search phase and applies a parallel search scheme to enjoy the abundant computing power. Both the theoretical analysis and the simulation studies demonstrate that the proposed algorithm can provide better decisions quickly. We also note that this algorithm is not limited to real-time control or simulation-based system. In the case where each run of the experiment is expensive and the budget is limited for the final decision and when the response function is multi-modal, this algorithm can hopefully become a quite efficient and competitive approach. The multi-modal responses have broad applications in the area of control, planning and operations research, such as robot navigating and reinforcement learning.

Gaussian process (GP) model based optimization is widely applied in simulation and machine learning. In general, it first estimates a GP model based on a few observations from the true response and then uses this model to guide the search, aiming to quickly locate the global optimum. Despite its successful applications, it has several limitations that may hinder its broader use. First, building an accurate GP model can be difficult and computationally expensive, especially when the response function is multimodal or varies significantly over the design space. Second, even with an appropriate model, the search process can be trapped in suboptimal regions before moving to the global optimum because of the excessive effort spent around the current best solution. In this work, we adopt the additive global and local GP (AGLGP) model in the optimization framework. The model is rooted in the inducing points based GP sparse approximations and is combined with independent local models in different regions. With these properties, the AGLGP model is suitable for multimodal responses with relatively large data sizes. Based on this AGLGP model, we propose a combined global and local search for optimization (CGLO) algorithm. It first divides the whole design space into disjoint local regions and identifies a promising region with the global model. Next, a local model in the selected region is fit to guide detailed search within this region. The algorithm then switches back to the global step when a good local solution is found. The global and local natures of CGLO enable it to enjoy the benefits of both global and local search to efficiently locate the global optimum. Summary of Contribution: This work proposes a new Gaussian process based algorithm for stochastic simulation optimization, which is an important area in operations research. This type of algorithm is also regarded as one of the state-of-the-art optimization algorithms for black-box functions in computer science. The aim of this work is to provide a computationally efficient optimization algorithm when the baseline functions are highly nonstationary (the function values change dramatically across the design space). Such nonstationary surfaces are very common in reality, such as the case in the maritime traffic safety problem considered here. In this problem, agent-based simulation is used to simulate the probability of collision of one vessel with the others on a given trajectory, and the decision maker needs to choose the trajectory with the minimum probability of collision quickly. Typically, in a high-congestion region, a small turn of the vessel can result in a very different conflict environment, and thus the response is highly nonstationary. Through our study, we find that the proposed algorithm can provide safer choices within a limited time compared with other methods. We believe the proposed algorithm is very computationally efficient and has large potential in such operational problems.

A quantile is a popular performance measure for a stochastic system to evaluate its variability and risk. To reduce the risk, selecting the actions that minimize the tail quantiles of some loss distributions is typically of interest for decision makers. When the loss distribution is observed via simulations, evaluating and optimizing its quantile can be challenging, especially when the simulations are expensive as it may cost a large number of simulation runs to obtain accurate quantile estimators. In this work, we propose a multilevel metamodel (cokriging)-based algorithm to optimize quantiles more efficiently. Utilizing nondecreasing properties of quantiles, we first search on cheaper and informative lower quantiles, which are more accurate and easier to optimize. The quantile level iteratively increases to the objective level, and the search has a focus on the possible promising regions identified by the previous levels. This enables us to leverage the accurate information from the lower quantiles to find the optimums faster and improve algorithm efficiency.

Safety is a primary concern for the various transport means. For sea transport, this includes various aspects like human safety at sea and at port, and also environmental safety and sustainability. In heavy-traffic regions where the waters are congested and vessels sail very closely together, ensuring these safety needs can be challenging. In this paper, we leverage on the rich information transmitted through the automatic identification system (AIS) and propose, for the first time, an integrated simulation-optimization approach for real time collision avoidance. This enables capturing of stochastic dynamic behavior of vessels for better prediction and fast trajectory optimization for application in real time. Specifically, a realistic agent-based model is developed based on behavioral learning in a real-environment, and incorporated into a fast collision avoidance optimization model in real time to provide robust collision avoidance that is able to account for future stochastic consequences of the actions taken. To achieve this, we develop: 1) a vessel pattern recognition method that mines the rich AIS data to produce realistic trajectory models; 2) an agent-based simulation model to enhance future trajectory prediction; and 3) a fast surrogate-based sampling technique to generate collision avoidance maneuvers for vessel captains in real time. To illustrate the feasibility of the approach, we use the case of the Singapore strait, one of the busiest straits in the world.

Computer models are widely used to simulate real processes. Within the computer model, there always exist some parameters which are unobservable in the real process but need to be specified in the model. The procedure to adjust these unknown parameters in order to fit the model to observed data and improve predictive capability is known as calibration. Practically, calibration is typically done manually. In this paper, we propose an effective and efficient algorithm based on the stochastic approximation (SA) approach that can be easily automated. We first demonstrate the feasibility of applying stochastic approximation to stochastic computer model calibration and apply it to three stochastic simulation models. We compare our proposed SA approach with another direct calibration search method, the genetic algorithm. The results indicate that our proposed SA approach performs equally as well in terms of accuracy and significantly better in terms of computational search time. We further consider the calibration parameter uncertainty in the subsequent application of the calibrated model and propose an approach to quantify it using asymptotic approximations.

Abstract With the enhancement of hardware and software engineering, the effectiveness and correctness of software is less and less doubted and customers are more aware about whether software services are available or not when needed. Software maintenance is one of the main reasons that make software unavailable and it is often very expensive to perform maintenance tasks. Common approaches of studying software maintenance are to consider it as a static by‐product of software operation and only the maintenance cost is covered. In this paper, software maintenance policies are studied with the consideration of unavailable service time. A non‐homogeneous continuous Markov chain is adopted for modeling the software operation and maintenance process, and the cost of software unavailability that is brought in by software maintenance is investigated and analyzed for searching the optimal maintenance policy, which aims at minimizing the average maintenance time cost. The optimality of our proposed policy is shown and checked by numerical examples with discussions of its possible application perspectives. Copyright © 2010 John Wiley & Sons, Ltd.

Software defects play a key role in software reliability, and the number of remaining defects is one of most important software reliability indexes. Observing the trend of the number of remaining defects during the testing process can provide very useful information on the software reliability. However, the number of remaining defects is not known and has to be estimated. Therefore, it is important to study the trend of the remaining software defect estimation (RSDE). In this paper, the concept of RSDE curves is proposed. An RSDE curve describes the dynamic behavior of RSDE as software testing proceeds. Generally, RSDE changes over time and displays two typical patterns: 1) single mode and 2) multiple modes. This behavior is due to the different characteristics of the testing process, i.e., testing under a single testing profile or multiple testing profiles with various change points. By studying the trend of the estimated number of remaining software defects, RSDE curves can provide further insights into the software testing process. In particular, in this paper, the Goel-Okumoto model is used to estimate this number on actual software failure data, and some properties of RSDE are derived. In addition, we discuss some theoretical and application issues of the RSDE curves. The concept of the proposed RSDE curves is independent of the selected model. The methods and development discussed in this paper can be applied to any valid estimation model to develop and study its corresponding RSDE curve. Finally, we discuss several possible areas for future research.

Software reliability modeling & estimation plays a critical role in software development, particularly during the software testing stage. Although there are many research papers on this subject, few of them address the realistic time delays between fault detection and fault correction processes. This paper investigates an approach to incorporate the time dependencies between the fault detection, and fault correction processes, focusing on the parameter estimations of the combined model. Maximum likelihood estimates of combined models are derived from an explicit likelihood formula under various time delay assumptions. Various characteristics of the combined model, like the predictive capability, are also analyzed, and compared with the traditional least squares estimation method. Furthermore, we study a direct, useful application of the proposed model & estimation method to the classical optimal release time problem faced by software decision makers. The results illustrate the effect of time delay on the optimal release policy, and the overall software development cost.

In software reliability modeling, the parameters of the model are typically estimated from the test data of the corresponding component. However, the widely used point estimators are subject to random variations in the data, resulting in uncertainties in these estimated parameters. Ignoring the parameter uncertainty can result in grossly underestimating the uncertainty in the total system reliability. This paper attempts to study and quantify the uncertainties in the software reliability modeling of a single component with correlated parameters and in a large system with numerous components. Another characteristic challenge in software testing and reliability is the lack of available failure data from a single test, which often makes modeling difficult. This lack of data poses a bigger challenge in the uncertainty analysis of the software reliability modeling. To overcome this challenge, this paper proposes utilizing experts' opinions and historical data from previous projects to complement the small number of observations to quantify the uncertainties. This is done by combining the maximum-entropy principle (MEP) into the Bayesian approach. This paper further considers the uncertainty analysis at the system level, which contains multiple components, each with its respective model/parameter/ uncertainty, by using a Monte Carlo approach. Some examples with different modeling approaches (NHPP, Markov, Graph theory) are illustrated to show the generality and effectiveness of the proposed approach. Furthermore, we illustrate how the proposed approach for considering the uncertainties in various components improves a large-scale system reliability model.

Generally, software reliability models can provide accurate reliability measurement in the later phase of testing. However, predictions in the early phase of software testing are useful as cost-effective and timely feedback. Early prediction is also feasible in practice with information from previous releases or similar projects. Such information has been utilized well for early reliability prediction with NHPP models by assuming the same failure rate between two similar projects. Alternatively, in this paper, we propose to "reuse" failure data from past projects/releases with ANN models to improve early reliability for current project/release. To illustrate the proposed approach, two numerical examples are developed. Better prediction performance is observed in early phase of testing compared with original ANN model without failure data reuse. Furthermore, the optimal switching point from proposed approach to original ANN model in the whole testing phase is studied, with specific analysis on the two examples

It is well-known that accurate reliability estimates can be obtained by using software reliability models only in the later phase of software testing. However, prediction in the early phase is important for cost-effective and timely management. Also this requirement can be achieved with information from previous releases or similar projects. This basic idea has been implemented with nonhomogeneous Poisson process (NHPP) models by assuming the same testing/debugging environment for similar projects or successive releases. In this paper we study an approach to using past fault-related data with artificial neural network (ANN) models to improve reliability predictions in the early testing phase. Numerical examples are shown with both actual and simulated datasets. Better performance of early prediction is observed compared with original ANN model with no such historical fault-related data incorporated. Also, the problem of optimal switching point from the proposed approach to original ANN model is studied, with three numerical examples

Most of the models for software reliability analysis are based on reliability growth models which deal with the fault detection process only. In this paper, some useful approaches to the modeling of both software fault detection and fault correction processes are discussed. Since the estimation of model parameters in software testing is essential to give accurate prediction and help make the right decision about software release, the problem of estimating the parameters is addressed. Taking into account the dependency between the fault correction process and the fault detection process, a new explicit formula for the likelihood function is derived and the maximum likelihood estimates are obtained under various time delay assumptions. An actual set of data from a software development project is used as an illustrative example. A Monte Carlo simulation is carried out to compare the predictive capability between the LSE method and the MLE method

Software inspection has been broadly accepted as a cost effective approach for defect removal during the whole software development lifecycle. To keep inspection under control, it is essential to measure its effectiveness. As human-oriented activity, inspection effectiveness is due to many uncertain factors that make such study a challenging task. Bayesian networks modeling is a powerful approach for the reasoning under uncertainty and it can describe inspection procedure well. With this framework, some extensions have been explored in this paper. The number of remaining defects in the software is proposed to be incorporated into the framework, with expectation to provide more information on the dynamic changing status of the software. In addition, a different approach is adopted to elicit the prior belief of related probability distributions for the network. Sensitivity analysis is developed with the model to locate the important factors to inspection effectiveness.