A new Kriging–Bat Algorithm for solving computationally expensive black-box global optimization problems

Many global optimization (GO) algorithms have been introduced in recent decades to deal with the Computationally Expensive Black-Box (CEBB) optimization problems. The high number of objective function evaluations, required by conventional GO methods, is prohibitive or at least inconvenient for practical design applications. In this work, a new Kriging–Bat algorithm (K–BA) is introduced for solving CEBB problems with further improved search efficiency and robustness. A Kriging surrogate model (SM) is integrated with the Bat Algorithm (BA) to find the global optimum using substantially reduced number of evaluations of the computationally expensive objective function. The new K–BA algorithm is tested and compared with other well-known GO algorithms, using a set of standard benchmark problems with 2 to 16 design variables, as well as a real-life engineering optimization application, to determine its search capability, efficiency and robustness. Results of the comprehensive tests demonstrated the suitability and superior capability of the new K–BA.     

An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization

Response surface methods based on kriging and radial basis function (RBF) interpolation have been successfully applied to solve expensive, i.e. computationally costly, global black-box nonconvex optimization problems. In this paper we describe extensions of these methods to handle linear, nonlinear, and integer constraints. In particular, algorithms for standard RBF and the new adaptive RBF (ARBF) are described. Note, however, while the objective function may be expensive, we assume that any nonlinear constraints are either inexpensive or are incorporated into the objective function via penalty terms. Test results are presented on standard test problems, both nonconvex problems with linear and nonlinear constraints, and mixed-integer nonlinear problems (MINLP). Solvers in the TOMLAB Optimization Environment () have been compared, specifically the three deterministic derivative-free solvers rbfSolve, ARBFMIP and EGO with three derivative-based mixed-integer nonlinear solvers, OQNLP, MINLPBB and MISQP, as well as the GENO solver implementing a stochastic genetic algorithm. Results show that the deterministic derivative-free methods compare well with the derivative-based ones, but the stochastic genetic algorithm solver is several orders of magnitude too slow for practical use. When the objective function for the test problems is costly to evaluate, the performance of the ARBF algorithm proves to be superior.     

A mixed-integer simulation-based optimization approach with surrogate functions in water resources management

Efficient and powerful methods are needed to overcome the inherent difficulties in the numerical solution of many simulation-based engineering design problems. Typically, expensive simulation codes are included as black-box function generators; therefore, gradient information that is required by mathematical optimization methods is entirely unavailable. Furthermore, the simulation code may contain iterative or heuristic methods, low-order approximations of tabular data, or other numerical methods which contribute noise to the objective function. This further rules out the application of Newton-type or other gradient-based methods that use traditional finite difference approximations. In addition, if the optimization formulation includes integer variables the complexity grows even further. In this paper we consider three different modeling approaches for a mixed-integer nonlinear optimization problem taken from a set of water resources benchmarking problems. Within this context, we compare the performance of a genetic algorithm, the implicit filtering algorithm, and a branch-and-bound approach that uses sequential surrogate functions. We show that the surrogate approach can greatly improve computational efficiency while locating a comparable, sometimes better, design point than the other approaches.     

A surrogate-assisted particle swarm optimization algorithm based on efficient global optimization for expensive black-box problems

Evolutionary algorithms cannot effectively handle computationally expensive problems because of the unaffordable computational cost brought by a large number of fitness evaluations. Therefore, surrogates are widely used to assist evolutionary algorithms in solving these problems. This article proposes an improved surrogate-assisted particle swarm optimization (ISAPSO) algorithm, in which a hybrid particle swarm optimization (PSO) is combined with global and local surrogates. The global surrogate is not only used to predict fitness values for reducing computational burden but also regarded as a global searcher to speed up the global search process of PSO by using an efficient global optimization algorithm, while the local one is constructed for a local search in the neighbourhood of the current optimal solution by finding the predicted optimal solution of the local surrogate. Empirical studies on 10 widely used benchmark problems and a real-world structural design optimization problem of a driving axle show that the ISAPSO algorithm is effective and highly competitive.     

A framework for design optimization using surrogates

Design optimization is a computationally expensive process as it requires the assessment of numerous designs and each of such assessments may be based on expensive analyses (e.g. computational fluid dynamics method or finite element based method). One way to contain the computational time within affordable limits is to use computationally cheaper approximations (surrogates) in lieu of the actual analyses during the course of optimization. This article introduces a framework for design optimization using surrogates. The framework is built upon a stochastic, zero-order, population-based optimization algorithm, which is embedded with a modified elitism scheme, to ensure convergence in the actual function space. The accuracy of the surrogate model is maintained via periodic retraining and the number of data points required to create the surrogate model is identified by a k-means clustering algorithm. A comparison is provided between different surrogate models (Kriging, radial basis functions (Exact and Fixed) and Cokriging) using a number of mathematical test functions and engineering design optimization problems. The results clearly indicate that for a given fixed number of actual function evaluations, the surrogate assisted optimization model consistently performs better than a pure optimization model using actual function evaluations.     

A surrogate-model based multi-modal optimization algorithm

In this article a new algorithm for optimization of multi-modal, nonlinear, black-box objective functions is introduced. It extends the recently-introduced adaptive multi-modal optimization by incorporating surrogate modelling features similar to response surface methods. The resulting algorithm has reduced computational intensity and is well-suited for optimization of expensive objective functions. It relies on an adaptive, multi-resolution mesh to obtain an initial estimation of the objective function surface. Local surrogate models are then constructed and used to generate additional trial points around the local minima discovered. The steps of mesh refinement and surrogate modelling continue until convergence is achieved. The algorithm produces progressively accurate surrogate models, which can be used for post-optimization studies such as sensitivity and tolerance analyses with minimal computational effort. This article demonstrates the effectiveness of the algorithm using comparative optimization of several multi-modal objective functions, and shows an engineering application of the design of a power electronic converter.     

Kriging Surrogate Based Multi-objective Optimization of Bulk Vinyl Acetate Polymerization with Branching

Despite the established superiority in finding the global as well as well-spread Pareto optimal (PO) points, the need of more numbers of function evaluations for population based evolutionary optimization techniques leads to a computationally demanding proposal. The case becomes more miserable if the function evaluations are carried out using a first principle based computationally expensive model, making the proposal not fit for online usage of the application. In this work, a Kriging based surrogate model has been proposed to replace a computationally expensive model to save execution time while performing an optimization task. A multi-objective optimization study has been carried out for the bulk vinyl acetate polymerization with long-chain branching using these surrogate as well as expensive models and Kriging PO solutions similar to those found by the first principle models are obtained with a close to 85% savings in function evaluations.     

A method for simulation based optimization using radial basis functions

We propose an algorithm for the global optimization of expensive and noisy black box functions using a surrogate model based on radial basis functions (RBFs). A method for RBF-based approximation is introduced in order to handle noise. New points are selected to minimize the total model uncertainty weighted against the surrogate function value. The algorithm is extended to multiple objective functions by instead weighting against the distance to the surrogate Pareto front; it therefore constitutes the first algorithm for expensive, noisy and multiobjective problems in the literature. Numerical results on analytical test functions show promise in comparison to other (commercial) algorithms, as well as results from a simulation based optimization problem.     

Applicability of surrogates to improve efficiency of particle swarm optimization for simulation-based problems

Particle swarm optimization (PSO) is a population-based, heuristic technique based on social behaviour that performs well on a variety of problems including those with non-convex, non-smooth objective functions with multiple minima. However, the method can be computationally expensive in that a large number of function calls is required. This is a drawback when evaluations depend on an off-the-shelf simulation program, which is often the case in engineering applications. An algorithm is proposed which incorporates surrogates as a stand-in for the expensive objective function, within the PSO framework. Numerical results are presented on standard benchmarking problems and a simulation-based hydrology application to show that this hybrid can improve efficiency. A comparison is made between the application of a global PSO and a standard PSO to the same formulations with surrogates. Finally, data profiles, probability of success, and a measure of the signal-to-noise ratio of the the objective function are used to assess the use of a surrogate.     

Enhanced particle swarm optimization for size and shape optimization of truss structures

This article presents an enhanced particle swarm optimization (EPSO) algorithm for size and shape optimization of truss structures. The proposed EPSO introduces a particle categorization mechanism into the particle swarm optimization (PSO) to eliminate unnecessary structural analyses during the optimization process and improve the computational efficiency of the PSO-based structural optimization. The numerical investigation, including three benchmark truss optimization problems, examines the efficiency of the EPSO. The results demonstrate that the particle categorization mechanism greatly reduces the computational requirements of the PSO-based approaches while maintaining the original search capability of the algorithms in solving optimization problems with computationally cheap objective function and expensive constraints.     

Constrained optimization by radial basis function interpolation for high-dimensional expensive black-box problems with infeasible initial points

This article develops two new algorithms for constrained expensive black-box optimization that use radial basis function surrogates for the objective and constraint functions. These algorithms are called COBRA and Extended ConstrLMSRBF and, unlike previous surrogate-based approaches, they can be used for high-dimensional problems where all initial points are infeasible. They both follow a two-phase approach where the first phase finds a feasible point while the second phase improves this feasible point. COBRA and Extended ConstrLMSRBF are compared with alternative methods on 20 test problems and on the MOPTA08 benchmark automotive problem (D.R. Jones, Presented at MOPTA 2008), which has 124 decision variables and 68 black-box inequality constraints. The alternatives include a sequential penalty derivative-free algorithm, a direct search method with kriging surrogates, and two multistart methods. Numerical results show that COBRA algorithms are competitive with Extended ConstrLMSRBF and they generally outperform the alternatives on the MOPTA08 problem and most of the test problems.     

Locally weighted regression models for surrogate-assisted design optimization

We consider engineering design optimization problems where the objective and/or constraint functions are evaluated by means of computationally expensive blackboxes. Our practical optimization strategy consists of solving surrogate optimization problems in the search step of the mesh adaptive direct search algorithm. In this paper, we consider locally weighted regression models to build the necessary surrogates, and present three ideas for appropriate and effective use of locally weighted scatterplot smoothing (LOWESS) models for surrogate optimization. First, a method is proposed to reduce the computational cost of LOWESS models. Second, a local scaling coefficient is introduced to adapt LOWESS models to the density of neighboring points while retaining smoothness. Finally, an appropriate order error metric is used to select the optimal shape coefficient of the LOWESS model. Our surrogate-assisted optimization approach utilizes LOWESS models to both generate and rank promising candidates found in the search and poll steps. The “real” blackbox functions that govern the original optimization problem are then evaluated at these ranked candidates with an opportunistic strategy, reducing CPU time significantly. Computational results are reported for four engineering design problems with up to six variables and six constraints. The results demonstrate the effectiveness of the LOWESS models as well as the order error metric for surrogate optimization.     

A hybrid of mode-pursuing sampling method and genetic algorithm for minimization of injection molding warpage

This paper presents a hybrid optimization method for minimizing the warpage of injection molded plastic parts. This proposed method combines a mode-pursuing sampling (MPS) method with a conventional global optimization algorithm, i.e. genetic algorithm, to search for the optimal injection molding process parameters. During optimization, Kriging surrogate modeling strategy is also exploited to substitute the computationally intensive Computer-Aided Engineering (CAE) simulation of injection molding process. With the application of genetic algorithm, the “likelihood-global optimums” are identified; and the MPS method generates and chooses new sample points in the neighborhood of the current “likelihood-global optimums”. By integrating the two algorithms, a new sampling guidance function is proposed, which can divert the search process towards the relatively unexplored region resulting in less likelihood of being trapped at the local minima. A case study of a food tray plastic part is presented, with the injection time, mold temperature, melt temperature and packing pressure selected as the design variables. This case study demonstrates that the proposed optimization method can effectively reduce the warpage in a computationally efficient manner.     

An adaptive multi-modal optimization algorithm for simulation-based design of power-electronic circuits

This article introduces a non-gradient optimization algorithm for the simulation-based design of nonlinear power-electronic circuits where multiple local minima may exist. The algorithm steers a simultaneous search for multiple optima by generating a multi-resolution mesh in the search space. It adaptively increases its resolution only in regions where the presence of local optima is likely, thus offering significant savings in the number of (simulation-based) objective-function evaluations. The algorithm's relatively low computational intensity, its independence of local gradient information and its capability to discover multiple local minima simultaneously make it appealing for the optimization of expensive black-box functions. The article shows an implementation of the algorithm in MATLAB^® and links it to the PSCAD^®/EMTDC transient simulation program. Examples of the application of the proposed algorithm for both analytical and simulation-based objective functions are included.     

A surrogate assisted parallel multiobjective evolutionary algorithm for robust engineering design

A number of multi-objective evolutionary algorithms have been proposed in recent years and many of them have been used to solve engineering design optimization problems. However, designs need to be robust for real-life implementation, i.e. performance should not degrade substantially under expected variations in the variable values or operating conditions. Solutions of constrained robust design optimization problems should not be too close to the constraint boundaries so that they remain feasible under expected variations. A robust design optimization problem is far more computationally expensive than a design optimization problem as neighbourhood assessments of every solution are required to compute the performance variance and to ensure neighbourhood feasibility. A framework for robust design optimization using a surrogate model for neighbourhood assessments is introduced in this article. The robust design optimization problem is modelled as a multi-objective optimization problem with the aim of simultaneously maximizing performance and minimizing performance variance. A modified constraint-handling scheme is implemented to deal with neighbourhood feasibility. A radial basis function (RBF) network is used as a surrogate model and the accuracy of this model is maintained via periodic retraining. In addition to using surrogates to reduce computational time, the algorithm has been implemented on multiple processors using a master–slave topology. The preliminary results of two constrained robust design optimization problems indicate that substantial savings in the actual number of function evaluations are possible while maintaining an acceptable level of solution quality.     

Optimization under adaptive error control for finite element based simulations

Optimization problems constrained by complex dynamics can lead to computationally challenging problems especially when high accuracy and efficiency are required. We present an approach to adaptively control numerical errors in optimization problems approximated using the finite element method. The discrete adjoint equation serves as a key tool to efficiently compute both parameter sensitivities and goal-oriented error estimates at the same discretized levels. By using a recovery method for the error estimators, we avoid expensive higher order adjoint calculations. We nest the adaptivity of the mesh within the optimization algorithm, which is responsible for converging both the state and optimization algorithms and thereby allowing the reuse of state, parameters, and reduced Hessian in subsequent optimization iterations. Our approach is demonstrated on a parameter estimation problem for contamination transport in a contact tank reactor. Significant efficiency and accuracy improvements are realized in comparison to uniform grid refinement strategies and black-box optimization methods. A flexible and maintainable software interface was developed to provide access between the underlying linear algebra of a production simulator and advanced numerical algorithms such as optimization and error estimation.     

Efficient global optimization for high-dimensional constrained problems by using the Kriging models combined with the partial least squares method

In many engineering optimization problems, the number of function evaluations is often very limited because of the computational cost to run one high-fidelity numerical simulation. Using a classic optimization algorithm, such as a derivative-based algorithm or an evolutionary algorithm, directly on a computational model is not suitable in this case. A common approach to addressing this challenge is to use black-box surrogate modelling techniques. The most popular surrogate-based optimization algorithm is the efficient global optimization (EGO) algorithm, which is an iterative sampling algorithm that adds one (or many) point(s) per iteration. This algorithm is often based on an infill sampling criterion, called expected improvement, which represents a trade-off between promising and uncertain areas. Many studies have shown the efficiency of EGO, particularly when the number of input variables is relatively low. However, its performance on high-dimensional problems is still poor since the Kriging models used are time-consuming to build. To deal with this issue, this article introduces a surrogate-based optimization method that is suited to high-dimensional problems. The method first uses the ‘locating the regional extreme’ criterion, which incorporates minimizing the surrogate model while also maximizing the expected improvement criterion. Then, it replaces the Kriging models by the KPLS(+K) models (Kriging combined with the partial least squares method), which are more suitable for high-dimensional problems. Finally, the proposed approach is validated by a comparison with alternative methods existing in the literature on some analytical functions and on 12-dimensional and 50-dimensional instances of the benchmark automotive problem ‘MOPTA08’.     

On the use of metamodel-assisted,multi-objective evolutionary algorithms

This article is concerned with the optimal use of metamodels in the context of multi-objective evolutionary algorithms which are based on computationally expensive function evaluations. The goal is to capture Pareto fronts of optimal solutions with the minimum computational cost. In each generation during the evolution, the metamodels act as filters that distinguish the most promising individuals, which will solely undergo exact and costly evaluations. By means of the so-called inexact pre-evaluation phase, based on continuously updated local metamodels, most of the non-promising individuals are put aside without aggravating the overall cost. The gain achieved through this technique is amazing in single-objective problems. However, with more than one objective, noticeable performance degradation occurs. This article scrutinizes the role of metamodels in multi-objective evolutionary algorithms and proposes ways to overcome expected weaknesses and improve their performance. Minimization of mathematical functions as well as aerodynamic shape optimization problems are used for demonstration purposes.     

Expected improvement based infill sampling for global robust optimization of constrained problems

A novel adaptive sampling scheme for efficient global robust optimization of constrained problems is proposed. The method addresses expensive to simulate black-box constrained problems affected by uncertainties for which only the bounds are known, while the probability distribution is not available. An iterative strategy for global robust optimization that adaptively samples the Kriging metamodel of the computationally expensive problem is proposed. The presented approach is tested on several benchmark problems and the average performance based on 100 runs is evaluated. The applicability of the method to engineering problems is also illustrated by applying robust optimization on an integrated photonic device affected by manufacturing uncertainties. The numerical results show consistent convergence to the global robust optimum using a limited number of expensive simulations.     

Data-driven construction of Convex Region Surrogate models

With the increasing trend of solving more complex and integrated optimization problems, there is a need for developing process models that are sufficiently accurate as well as computationally efficient. In this work, we develop an algorithm for the data-driven construction of a type of surrogate model that can be formulated as a set of mixed-integer linear constraints, yet still provide good approximations of nonlinearities and nonconvexities. In such a surrogate model, which we refer to as Convex Region Surrogate (CRS), the feasible region is given by the union of convex regions in the form of polytopes, and for each region, the corresponding cost function can be approximated by a linear function. The general problem is as follows: given a set of data points in the parameter space and a scalar cost value associated with each data point, find a CRS model that approximates the feasible region and cost function indicated by the given data points. We present a two-phase algorithm to solve this problem and demonstrate its effectiveness with an extensive computational study as well as a real-world case study.