# Kriging-Based Space Exploration Global Optimization Method in Aerodynamic Design

Authors: Wei Zhang; Zhenghong Gao; Chao Wang; Lu Xia
Journal: International Journal of Aerospace Engineering
 (2023)

---

## Abstract

For complicated aerodynamic design problems, the efficient global optimization method suffered from the defect of the incorrect portrayal of the design space, resulting in bad global convergence and efficiency performance. To this end, a Kriging-based global optimization method, named the Kriging-based space exploration method (KSE), was proposed in this paper. It selected multiple promising local minima and classified them into partially and fully explored minima in terms of the fitting quality of the surrogate model. Then, the partially explored minima would be furtherly exploited. During the local search, an enhanced trust-region method was adopted to make deep exploitation. By combining local and global searches, the proposed method could improve the fitting quality of the surrogate model and the optimization efficiency. The KSE was compared to other global surrogate-based optimization methods on 12 bound-constrained testing functions with 2 to 16 design variables and 2 aerodynamic optimization problems with 24 to 77 design variables. The results indicated that the KSE generally took fewer function evaluations to find the global optima or reach the target value in most test problems, holding better efficiency and robustness.


---

## Body

## 1. Introduction

In aerodynamic shape design, Computational fluid dynamics (CFD) solvers and optimization algorithms were essential. The optimization algorithms have been divided into two categories: gradient-free and gradient-based methods. Generally, the gradient-based methods needed sufficient gradient calculations and inherently converged to local minima, which was not suitable for complex multimodal problems [1]. The gradient-free methods, which did not need gradient information, could be easily incorporated into existing frameworks and have been found in many engineering applications [2, 3]. The gradient-free methods could be divided into several different groups: biology-based, physics-based, social-based, music-based, chemical-based, sport-based, swarm-based, and hybrid methods which were combinations of these [4, 5]. Since the optimization field was expansive, suitable gradient-free methods would be problem dependent. However, the gradient-free methods would need massive calls and simulations for the high-fidelity design requirements, leading to an enormous computational burden. Therefore, the efficient global optimization method (EGO) [6] has greatly acquired the research and development of the global optimization method called surrogate-based optimization (SBO) [7–12], which had the potential to uncover the unconventional aircraft configurations in the aerodynamic design. For problems with multimodality, the accuracy for the surrogate model largely depended on the capability of the surrogate model in capturing the nonlinearity of the problems. Ignoring this would result in suboptimality or infeasibility of optimal solutions [13–16]. The EGO method soon acquired a reputation for its flexibility to imitate complicated functions for it had a random error estimate between the true and the surrogate functions to quantitatively measure the uncertainty in prediction [3, 17].The most attractive characteristic of the EGO method was that it could meet two requirements: the exploitation of local minima (local search ability) and the exploration of uncertain areas (global search ability). The balance of global and local search ability largely relied on the predicted standard error. However, the numerical experiments showed that the EGO did not perform very well on multimodal problems and it also suffered from the curse of dimensionality on problems with more than 30 design variables [18–20]. Thus, it would take a considerable amount of computational cost to improve the surrogate model accuracy [18] for complicated aerodynamic design problems with high multimodality and dimensionality [21]. Therefore, enhancing and balancing these two abilities was essential to improve optimization efficiency [22]. Various extensions and modifications of EGO have been developed and applied to engineering design problems. Sun et al. [23] proposed two different multiobjective EGO algorithms, where the infill criterion formed by the “Kriging believer” and “multiple good local optima” strategy was adopted to compromise exploitation and exploration. By extending the generalized EGO algorithm and adopting a constant liar strategy, Li et al. [24] used a Kriging-based unconstrained global optimization method to obtain multiple infill sample points. Xing et al. [25] proposed a P-EI method, combined with the effective design domain simplification technology, to search multiple peaks of the expected improvement (EI) function. Amine Bouhlel et al. [26] proposed a regional extreme criterion combined with the partial least squares method (KPLS(+K) model) to deal with the high-dimensional problems.Besides, there were many meaningful works to enhance and balance the global and local searches for surrogate-based global optimization: Wang and Simpson [27] applied the fuzzy K-means clustering method on many cheap sample points to reduce the design space. A stochastic RBF method for the global optimization of expensive functions was proposed by Regis and Shoemaker [28], which improved the Gutmann-RBF method by varying the size of the subdomain in different iterations [29]. Villanueva et al. [30] used the K-means clustering method to partition initial design space into different subregions and explored them separately by multiagent systems. Long et al. [31] combined a set of intelligent space exploration strategies with TR-ARSM for global optimization. In addition, the multistart approach has also proved to be an efficient global optimization strategy. Regis and Shoemaker [18] introduced A QUAsi-multistart Response Surface (AQUARS) locating the promising regions of the objective function by performing local searches around the local minima of the surrogate model, and it bounced between the local minima to obtain the global optima. Dong et al. [32] combined the multistart approach with space reduction strategy, introducing the multistart space reduction method. The MSSR reduced space size automatically based on the current best sample point. Eriksson et al. [33] proposed the TURBO algorithm which applies multiple local surrogate models to approximate the objective function and uses an implicit bandit method to perform a principled global allocation of samples across these models. Bartoli et al. [34] proposed a superefficient global optimization coupled with a mixture of expert (SEGOMOE) method, where an enrichment strategy based on a mixture of experts and adaptive surrogate models was applied to tackle multimodal problems with complex constraints. Diouane et al. [35] proposed a trust-region-like EGO method (TREGO), which alternated between traditional EGO steps and local steps within a trust region. To deal with the constrained black-box problems, some researches adopted different infill criterions to figure out the feasible regions during the optimization process [36–38], and some researches integrated surrogate model with evolutionary algorithms to deal with expensive constraints [39–41], which could dramatically improve the optimization efficiency and convergence on constrained optimization problems.These researches indicated that the design space reduction approach presented to be an efficient optimization method for multimodal and computationally expensive black-box problems. However, there were two main arguments significantly affecting the optimization stability, convergence, and efficiency:(a)
The local minima of the surrogate model would change significantly as more sample points were evaluated, and the new subspaces were generally centered at a single best point. Thus, it was difficult to select suitable local minima to construct promising subspaces. Once it was trapped in some deceptive regions, it would cost plenty of computational effort to escape and search for other possibilities [32](b)
Some algorithms tended to search for new sample points around the well-explored local minima, leading to wasted computing resources, and would ignore the potential regions where better sample points might existThe Kriging-based space exploration method (KSE) was proposed to address these problems by using multiple subregion local search strategy and the enhanced trust-region method in this paper. It combined the global search over the entire space and local search in the subspaces to balance and enhance the global exploration ability and local exploitation, thereby addressing problem (a). During the local searches, not all local minima need to be further exploited. The local minima were classified into fully and partially explored minima in terms of root mean square error (RMSE). And only the local minima with large RMSE needed further exploitation, during which an enhanced trust-region method was proposed to emphasize the optimization of the partially local minima, thereby addressing problem (b). Besides, to overcome the limitations of the original EGO, the infill criterion would be turned into minima prediction (MP) [6] to make further exploitation when all local minima were fully explored and the improvement of the EI criterion was lower than the preset threshold.The proposed KSE method was compared to alternative global optimization methods on 12 test functions with 2 to 16 design variables and 2 aerodynamic design problems with 24 to 77 design variables. The numerical results indicated that the KSE method generally used fewer function evaluations to find the global minima on most test problems compared to alternative methods. Moreover, it could use fewer function evaluations to reach a reasonably good solution to aerodynamic design problems compared to alternatives. Hence, the KSE was very promising for the global optimization of engineering design.The rest of the paper was organized as follows: part 2 introduced the background while part 3 focused on the framework of the proposed method. Part 4 and part 5 described the computational experiments and their results as well as the related discussion. Finally, the last part provided a summary and the conclusions.


## 2. Methodology

During the last decade, the EGO method [6] has become one of the most popular methods for global optimization. The EGO method was a sequential planning strategy that used a Gaussian process-based surrogate model, e.g., Kriging, and a variance-based merit function or criterion to generate candidate solutions. Therefore, the theories of EGO were briefly depicted in this section.


### 2.1. The Kriging Model

The Kriging was first proposed in the field of geostatistics by Krige [42] and Matheron [43]. After Sacks et al. [44] applied it to computer-based engineering design, the Kriging model became popular in engineering design and optimization.In the Kriging model, the values of the black-box functionf were assumed to be the outcomes of a stochastic process. In particular, it was assumed that the function value fx was a realization of a random variable Yx which was normally distributed with mean μ and variance σ2. For any two points xi and xj, the correlation between Yxi and Yxj could be modeled as
(1)CorrYxi,Yxj=exp−∑k=1dθkxik−xjkpk,where 1≤pk≤2 and θk>0k=1,..,d were hyperparameters of the model, and they provided more degree of freedom for the predictor to imitate the behavior of multimodal functions. Let y1=fx1,⋯,yn=fxn and y=y1,⋯,ynT be the vector function values. Fitting the surrogate model through the x1,y1,⋯,xn,yn was equivalent to finding the maximum likelihood estimates (MLEs) of the parameters μ,σ2,θ1,⋯,θd,p1,⋯,pd. Then, the Kriging predictor at a new point x∗ was presented as
(2)y^x∗=μ^+rTR−1y−Jn×1μ^,where μ^=Jn×1TRy−1y/Jn×1TRy−1Jn×1 and r=CorrYx∗,Yx1,⋯,CorrYx∗,YxnT. The uncertainty at x∗ could be given by mean squared error (MSE):
(3)s2x=σ∧21−rTR−1r+1−rTR−1r2Jn×1TR−1Jn×1,where σ∧2=y−Jn×1μ∧TR−1y−Jn×1μ^/n. The first term represented the uncertainty due to the correlation of the sample points, and the second term described the uncertainty of the estimated parameter μ. For more details, Jones [21] gave a taxonomy of surrogate-based optimization methods.


### 2.2. The EGO Method

The EGO method belonged to the so-called “two-stage” method: the first step consisted of fitting the surrogate model and estimating the associated hyperparameters. The second step consisted of using this surrogate model instead of the true function and searching for promising sample points. It used (4) to find new sample points.
(4)EI=fmin−y~xΦfmin−y^xsx+sxϕfmin−y^xsx,ifsx>0,0,ifsx=0.Here,fmin was the current best objective function value. The Φ and ϕ were the cumulative density function and the standard normal probability density functions.For an inequality constraint function asgx>glimit, the constraint function was also modeled by a Gaussian process. And this model could be used to calculate the probability that the constraint was met. So, the ‘probability of feasibility’ for each constraint gx would be calculated in (5):
(5)Pgx>glimit=1s^x2π∫0∞e−Gx‐glimit−g∧x2/2s∧2x,where Gx was a normally distributed random variable with mean value g^x and variance value s∧2x and Gx−glimit measured the feasibility of new points. Provided that the constraint and objective functions were all independent models, Sasena et al. [45] proposed the constrained expected improvement (CEI) method to handle constraints by multiplying the expected improvement of the objective function and the probability of feasibility as
(6)CEI=EI×Pgx−glimit.Locatelli [46] proved that the EGO method generally took plenty of function evaluations to find the global optima. During the EI-based global optimization, the sx was usually slightly lower than its true error value [47]. Unless the uncertainty of the current region became relatively low, the underestimation would cost many iterations to explore the local spaces, especially for some deceptive regions with lower estimated standard deviation, causing slower convergence rate.


### 2.3. Trust-Region Method

The trust-region method (TRM) [48] has proven to be an efficient space reduction method for its good performance in optimization [49]. It identified the promising space, where the actual global optima probably exist, in light of how well the current surrogate model predicted the improvement of the objective function. In TRM, the current best sample point was chosen as the center of the new space. The trust-region factor rk and trust-region radius δk were computed through
(7)rk=fxk−1−fxkfxk−1−f~xk=Δffk−1−f~k,(8)δk=c1xk−xk−1,rk<r1,minc2xk−xk−1,δmax,rk>r2,xk−xk−1,r2≥rk≥r1,δmin,rk<0.Thefxk and f~xk were the true and predicted values, respectively. rk could measure the improvement of objective function and accuracy of surrogate model at the same time through Δf and fk−1−f~k. If Δf>0, the current surrogate model was capable of decreasing the true objective value, and then, the trust radius δk was updated according to (8) [49], where the typical values of r1,r2,c1,c2 were used, namely, r1=0.10,r2=0.75,c1=0.75,andc2=1.25. The δmax was the upper bound of the trust radius, which was usually set to 0.5, and . indicated the L1 Euclidean norm. Otherwise, the current surrogate model could not improve the objective value for its bad fitting quality. In this case, the minimum trust radius δmin was used, which usually lies in the interval 0.01,0.1. Then, TRM was forced to exploit a small neighborhood around the present best point. The TRM allowed optimization to focus on a small region around the current point with dynamic bounds, and it was very efficient in local search, avoiding the prior knowledge of constructing local space.


## 2.1. The Kriging Model

The Kriging was first proposed in the field of geostatistics by Krige [42] and Matheron [43]. After Sacks et al. [44] applied it to computer-based engineering design, the Kriging model became popular in engineering design and optimization.In the Kriging model, the values of the black-box functionf were assumed to be the outcomes of a stochastic process. In particular, it was assumed that the function value fx was a realization of a random variable Yx which was normally distributed with mean μ and variance σ2. For any two points xi and xj, the correlation between Yxi and Yxj could be modeled as
(1)CorrYxi,Yxj=exp−∑k=1dθkxik−xjkpk,where 1≤pk≤2 and θk>0k=1,..,d were hyperparameters of the model, and they provided more degree of freedom for the predictor to imitate the behavior of multimodal functions. Let y1=fx1,⋯,yn=fxn and y=y1,⋯,ynT be the vector function values. Fitting the surrogate model through the x1,y1,⋯,xn,yn was equivalent to finding the maximum likelihood estimates (MLEs) of the parameters μ,σ2,θ1,⋯,θd,p1,⋯,pd. Then, the Kriging predictor at a new point x∗ was presented as
(2)y^x∗=μ^+rTR−1y−Jn×1μ^,where μ^=Jn×1TRy−1y/Jn×1TRy−1Jn×1 and r=CorrYx∗,Yx1,⋯,CorrYx∗,YxnT. The uncertainty at x∗ could be given by mean squared error (MSE):
(3)s2x=σ∧21−rTR−1r+1−rTR−1r2Jn×1TR−1Jn×1,where σ∧2=y−Jn×1μ∧TR−1y−Jn×1μ^/n. The first term represented the uncertainty due to the correlation of the sample points, and the second term described the uncertainty of the estimated parameter μ. For more details, Jones [21] gave a taxonomy of surrogate-based optimization methods.


## 2.2. The EGO Method

The EGO method belonged to the so-called “two-stage” method: the first step consisted of fitting the surrogate model and estimating the associated hyperparameters. The second step consisted of using this surrogate model instead of the true function and searching for promising sample points. It used (4) to find new sample points.
(4)EI=fmin−y~xΦfmin−y^xsx+sxϕfmin−y^xsx,ifsx>0,0,ifsx=0.Here,fmin was the current best objective function value. The Φ and ϕ were the cumulative density function and the standard normal probability density functions.For an inequality constraint function asgx>glimit, the constraint function was also modeled by a Gaussian process. And this model could be used to calculate the probability that the constraint was met. So, the ‘probability of feasibility’ for each constraint gx would be calculated in (5):
(5)Pgx>glimit=1s^x2π∫0∞e−Gx‐glimit−g∧x2/2s∧2x,where Gx was a normally distributed random variable with mean value g^x and variance value s∧2x and Gx−glimit measured the feasibility of new points. Provided that the constraint and objective functions were all independent models, Sasena et al. [45] proposed the constrained expected improvement (CEI) method to handle constraints by multiplying the expected improvement of the objective function and the probability of feasibility as
(6)CEI=EI×Pgx−glimit.Locatelli [46] proved that the EGO method generally took plenty of function evaluations to find the global optima. During the EI-based global optimization, the sx was usually slightly lower than its true error value [47]. Unless the uncertainty of the current region became relatively low, the underestimation would cost many iterations to explore the local spaces, especially for some deceptive regions with lower estimated standard deviation, causing slower convergence rate.


## 2.3. Trust-Region Method

The trust-region method (TRM) [48] has proven to be an efficient space reduction method for its good performance in optimization [49]. It identified the promising space, where the actual global optima probably exist, in light of how well the current surrogate model predicted the improvement of the objective function. In TRM, the current best sample point was chosen as the center of the new space. The trust-region factor rk and trust-region radius δk were computed through
(7)rk=fxk−1−fxkfxk−1−f~xk=Δffk−1−f~k,(8)δk=c1xk−xk−1,rk<r1,minc2xk−xk−1,δmax,rk>r2,xk−xk−1,r2≥rk≥r1,δmin,rk<0.Thefxk and f~xk were the true and predicted values, respectively. rk could measure the improvement of objective function and accuracy of surrogate model at the same time through Δf and fk−1−f~k. If Δf>0, the current surrogate model was capable of decreasing the true objective value, and then, the trust radius δk was updated according to (8) [49], where the typical values of r1,r2,c1,c2 were used, namely, r1=0.10,r2=0.75,c1=0.75,andc2=1.25. The δmax was the upper bound of the trust radius, which was usually set to 0.5, and . indicated the L1 Euclidean norm. Otherwise, the current surrogate model could not improve the objective value for its bad fitting quality. In this case, the minimum trust radius δmin was used, which usually lies in the interval 0.01,0.1. Then, TRM was forced to exploit a small neighborhood around the present best point. The TRM allowed optimization to focus on a small region around the current point with dynamic bounds, and it was very efficient in local search, avoiding the prior knowledge of constructing local space.


## 3. Proposed Method

### 3.1. Classification of Local Minima

From the discussion above, the EGO method attempted to explore the entire design space which would require numerous computational resources. Once it focused on some deceptive local minima, it was hard for it to escape from local minima and explore other potential regions in time. An unbalanced approach to exploitation and exploration usually caused a poor depiction of the design space, as well as the convergence and efficiency of optimization.To overcome these issues, this paper proposed the Kriging-based space exploration method (KSE). The multiple subregion local search strategy was used to explore the local regions in the entire design space, improving the depiction of the design space and surrogate model accuracy. One of the main aspects of this strategy was to select reasonable potential regions to make deep exploitation. It classified the local minima of the surrogate model into fully and partially explored local minima, from which the partially explored minima were selected to make further exploitation. The classification of partially explored local minima was relayed on the depiction of local regions, defined by the root mean square error (RMSE) of local regions. The poor fitting quality of the surrogate model would lead to substantial fluctuations in design space, resulting in misleading results for the algorithm. And a good depiction of the entire design space, which relied on depicting vicinities of local minima, could improve the fitting quality of the surrogate model. Thus, the main purpose of multiple subregion local search strategy was to make the proper depiction of potential local regions and provided efficient information for global optimization.Let design spaceD=a,b⊆ℝd and f:D⟶ℝd be any function from D to ℝd, whose local regions were nearly linear. Suppose x∗ was a local minima of the objective function f over D; then, there existed radius ρ>0, so that fx∗≤fx for all x∈Lx∗,ρ∩D=x∈D:x−x∗≤ρ. Similarly, the f^xs∗≤f^x for the surrogate model with local minima xs∗ over local space L~xs∗,ρ. For a well-performed surrogate model, the x∗ would be consistent with the xs∗ and the trend of L~xs∗,ρ in surrogate model would be similar to that of Lx∗,ρ in objective function.Otherwise, it would need more sample points to depict the neighborhood properly, likeC in Figure 1. Under this circumstance, the root mean square error (RMSE) of sample points within the local region was used to decide whether the corresponding local minima were fully explored or not, and the partially explored local minima would need further exploration. During these processes, the exploitation of partially explored local minima of the surrogate model was used to improve the fitting quality of the surrogate model in local space, and the exploitation of partially explored local minima of the objective function was used to search for better points. Local minima for the surrogate model did not always correspond to a local minima for the objective function. However, the deep exploitation in the vicinity of local minima of the surrogate model could eliminate the “fake local minima” and obtain the true local minima for the objective function. Since the local minima with better performance were more likely to be close to the global optima, the further exploitation of the local minima of objective function would make the algorithm toward the global optima more efficient. In combination, the global exploration for the target value would be promoted.Figure 1
The sketch of local minima.The above conditions could not guarantee that the surrogate model would achieve a good approximation to the objective functionf in some neighborhoods of local minima. However, if f had a relatively simple surface in the neighborhood of x∗ (e.g., if it was nearly linear), then the possibility that f was well approximated by the surrogate model in that local region would be increased by those conditions. Thus, the fully explored local minima of the surrogate model were more likely to be the local minima of the objective function, as shown in Figure 1.


### 3.2. The Enhanced Trust-Region Method

Although the traditional trust-region method (TRM) has shown the advantages of improving the optimization efficiency, it might not make sufficient search in local regions since the space radius of new design space was largely dependent on the previous best point (the radius fromxk−xk−1 was linearly dependent), which would lead to premature of the optimization. To avoid this shortcoming, this paper proposed an enhanced trust-region method (ETRM) combining the independent/dependent strategy with the stochastic perturbation strategy, as shown below.
(9)Dnew=Dindependent∪Ddependent∪Dstochastic,(10)AEI=maxfmin−fxk−1,0EI,(11)rk=minγ1rk−1,rmax,AEI≥η,rk−1,0<AEI<η,maxγ2rk−1,rmin,AEI=0,(12)Dindependent=xmin−rkb−a,xmin+rkb−a,(13)Ddependent=xmin−rkxmin−xmin,i‐1,xmin+rkxmin−xmin,i‐1,xmin∈Xmin,Xmin=xmin,1,..,xmin,i,(14)Pk=1−InkInNmax,Ipertube≔i:ωi<Pk,ωi∈0,1,i=1,⋯,d,δk=Ipertubermaxb−a.∗randd,1,Dstochastic=xmin−δk,xmin+δk.Here, theDnew was the new local space defined by the Dindependent, Ddependent, and Dstochastic, which were computed by different strategies, as shown in (9). The space radius of the ETRM changed in terms of the actual improvement of EI (AEI) while the original TRM adopted the predicted improvement based on the surrogate model as shown (8). The trust factor rk was computed through (10), where typical values of rmin=0.04, rmax=0.08, γ1=1.2, and γ2=0.8 were used, respectively. If AEI≥η, where the η was the threshold for the AEI, the EI criterion was capable of decreasing the objective function value; the space radius would be expanded according to (11). If 0<AEI<η, the space radius would keep unchanged. If AEI=0, the surrogate model was unable to obtain better points in current space; then, a conservative space radius would be selected. (12) used the independent strategy from the current best point xmin and the entire design space to construct a uniform box-shaped trust region, where aandb were the lower and upper bound of the entire design space, respectively, and  was the Euclidean norm. The purpose of this strategy was to reduce the influence of the previous sample points and make the optimization more independent to find diverse sample points in each iteration. However, the dependent information xmin−xmin,i‐1 from the previous best point Xmin=xmin,1,..,xmin,i could maintain the efficient dimension information which would help the algorithm toward the global optima quickly. Thus, the dependent information was used to improve the dimension setting of the trust region, which was indicated by the vector direction from the previous best point xmin,i‐1 to the current best point xmin, as shown in (13). Besides, to make a full exploration of the local region, a stochastic strategy for trust region was presented by (14). Here, the Pk was the probability of perturbing any dimensions of design space, and Nmax was the maximum number of iterations. For the iteration k, the number of the dimension to be perturbed was a random variable with a binomial d,Pk distribution with a mean number of perturbed dimensions d×Pk, where d was the number of all dimensions in the design space. In (14), the Pk was decided by a strictly decreasing function and would decrease as the optimization carries on. The Ipertube was the set of the index of the perturbed dimension decided by Pk and ωi, where ωi was a uniform random number generated in the range 0,1, and it would be different in each iteration to maintain the diversity of design space. Then, the Dstochastic was computed by the trust radius δk and the current best point xmin. The use of a stochastic strategy for constructing a trust region was expected to be helpful for problems with many local minima and design variables.At the initial stage of optimization, the distribution ofxmin could be very sparse and their positions would change significantly in different iterations since the surrogate model accuracy would not be very precise. Under this condition, the dependent strategy could make use of useful dimension information to accelerate the convergence speed to better points. And the stochastic strategy would help the algorithm to search for multiple diverse sample points by perturbing a large fraction of the dimensions. As the progress of optimization, the distribution of xmin would be more centralized and the distance between the best points would be smaller. By perturbing a progressively smaller fraction of dimension, the vicinity of the current best point xmin was less likely to be disturbed. At present, the trust region would be largely dependent on the independent strategy, which ensured that the neighborhood of xmin would be focused throughout the process of optimization.The ETRM measured the improvement of the objective function and combined an independent/dependent strategy with the stochastic perturbation strategy to construct the promising local regions. These strategies could deal with different situations across the optimization process, and in combination, they could preserve the diversity of design space and prevent the premature of optimization, improving the efficiency and convergence of optimization.


### 3.3. Detail of Proposed Method

The proposed KSE method consisted of four parts: (1) search effective samples and select local minima; (2) classify local minima into fully and partially explored local minima; (3) exploit the partially explored local minima; and (4) combine global exploration and local exploitation. The flowchart of the method is illustrated in Figure2, and the following were the detailed steps of this method.Step 1 (initial design).
In the beginning, Latin hypercube sampling (LHS) method [50] was adopted to generate initial sample points.Step 2 (global search by EI criterion).
The EGO method based on DACE, where the Gaussian kernel function was adopted, was used to explore the entire design space, during which the particle swarm optimization (PSO) algorithm was adopted as an optimizer. As for the problems with multiple constraints, the constrained expected improvement criterion (CEI) [45] would be adopted to handle constraints in KSE.Step 3 (identify the local minima).
The sample points with good performance were selected as local minima and corresponding sample cluster.Step 4 (select the partially explored local minima).
Classify the local minima into fully and partially explored local minima.Step 5 (multiple subregion local search).
Deep exploitation of all partially explored local minima, based on the ETRM, would be carried out to improve the surrogate accuracy. After all local minima have been explored to their fullest extent, the algorithm would proceed to Step2 until no partially explored local minima could be identified.Step 6 (switch criterion function).
At the last stage of optimization, the MP criterion would be adopted instead of EI criterion based on the improvement of the EI criterion. The objective function was set as (15), and the function transition factor CEI measured the improvement of the EI criterion, as shown in (16). The fmin was the objective value of the current best sample point, and EImax was the improvement of the EI criterion. In this paper, the CEI was set as 0.01, which meant if the EImax was less than 1% of fmin, the objective function turned into the MP criterion.
(15)Objective=EIcriterion,CEI≥0.01,MPcriterion,else,(16)CEI=EImaxfmin.Algorithm 1: The encoding type of KSE.
The KSE for Global OptimizationInput: (1) original design space D=Xmax,Xmin⊂ℝd,d≥1;(2) global exploration iteration numberm_global;(3) cluster numberN, cluster radius rreq;(4) maximum iteration numberMax_k;(5)FunctionCriterion: EI function;(6) threshold of RMSE:RMSEthresholdOutput: the best solution as global optima x∗,yx∗;BeginChoose an initial set of sample pointsXD=x1D,⋯,xnD∈D by LHS sampling method.EvaluateXD to obtain the corresponding response YD=y1D,⋯,ynD, and store them in the database S.Whilek<Max_kfori=1:m_globalEmploy EGO algorithm withFunctionCriterion;Store the optimized solutionx and its function response value y in the database S;k=k+1;endSelectN clusters from database S, and identify the cluster center X∗=x1∗,⋯,xN∗, other sample points within the distance rreq=0.01Xmax−Xmin2, would be classified into the corresponding cluster S∗=S1∗,⋯,SN∗. The distance between sample points with cluster center was computed by Euclidean distance.forj=1:NSort all sample pointsXc∗=x1,⋯,xn of Sj∗ in terms of their function response value Yc∗=y1,⋯,yn in ascending order;Use Cross-validation to obtain the predicted valueYc∗=y1,⋯,yn of all sample points;RMSE=1/n∑i=1nyi−yi~;ifRMSE≤RMSEthresholdStorexi∗ into fully explored local minima dataset Xf=x1f,⋯,xnf;elseStorexi∗ into partially explored local minima dataset Xp=x1p,⋯,xnp;endendifXp≠∅fori=1:nDefine local spaceVTR centered at xip by the ETRM algorithm;Employ EGO algorithm withFunctionCriterion in VTR;Store the optimized solutionx and its function response value y in the database S;k=k+1;endelseSelect current best sample point valuefbest.CEI=ComupteFunctionCriterionEImax,fbestifCEI≥0.01FunctionCriterion⟵EI criterion;elseFunctionCriterion⟵MPcriterion;endendendEndFigure 2
Flowchart of the KSE optimization process.


## 3.1. Classification of Local Minima

From the discussion above, the EGO method attempted to explore the entire design space which would require numerous computational resources. Once it focused on some deceptive local minima, it was hard for it to escape from local minima and explore other potential regions in time. An unbalanced approach to exploitation and exploration usually caused a poor depiction of the design space, as well as the convergence and efficiency of optimization.To overcome these issues, this paper proposed the Kriging-based space exploration method (KSE). The multiple subregion local search strategy was used to explore the local regions in the entire design space, improving the depiction of the design space and surrogate model accuracy. One of the main aspects of this strategy was to select reasonable potential regions to make deep exploitation. It classified the local minima of the surrogate model into fully and partially explored local minima, from which the partially explored minima were selected to make further exploitation. The classification of partially explored local minima was relayed on the depiction of local regions, defined by the root mean square error (RMSE) of local regions. The poor fitting quality of the surrogate model would lead to substantial fluctuations in design space, resulting in misleading results for the algorithm. And a good depiction of the entire design space, which relied on depicting vicinities of local minima, could improve the fitting quality of the surrogate model. Thus, the main purpose of multiple subregion local search strategy was to make the proper depiction of potential local regions and provided efficient information for global optimization.Let design spaceD=a,b⊆ℝd and f:D⟶ℝd be any function from D to ℝd, whose local regions were nearly linear. Suppose x∗ was a local minima of the objective function f over D; then, there existed radius ρ>0, so that fx∗≤fx for all x∈Lx∗,ρ∩D=x∈D:x−x∗≤ρ. Similarly, the f^xs∗≤f^x for the surrogate model with local minima xs∗ over local space L~xs∗,ρ. For a well-performed surrogate model, the x∗ would be consistent with the xs∗ and the trend of L~xs∗,ρ in surrogate model would be similar to that of Lx∗,ρ in objective function.Otherwise, it would need more sample points to depict the neighborhood properly, likeC in Figure 1. Under this circumstance, the root mean square error (RMSE) of sample points within the local region was used to decide whether the corresponding local minima were fully explored or not, and the partially explored local minima would need further exploration. During these processes, the exploitation of partially explored local minima of the surrogate model was used to improve the fitting quality of the surrogate model in local space, and the exploitation of partially explored local minima of the objective function was used to search for better points. Local minima for the surrogate model did not always correspond to a local minima for the objective function. However, the deep exploitation in the vicinity of local minima of the surrogate model could eliminate the “fake local minima” and obtain the true local minima for the objective function. Since the local minima with better performance were more likely to be close to the global optima, the further exploitation of the local minima of objective function would make the algorithm toward the global optima more efficient. In combination, the global exploration for the target value would be promoted.Figure 1
The sketch of local minima.The above conditions could not guarantee that the surrogate model would achieve a good approximation to the objective functionf in some neighborhoods of local minima. However, if f had a relatively simple surface in the neighborhood of x∗ (e.g., if it was nearly linear), then the possibility that f was well approximated by the surrogate model in that local region would be increased by those conditions. Thus, the fully explored local minima of the surrogate model were more likely to be the local minima of the objective function, as shown in Figure 1.


## 3.2. The Enhanced Trust-Region Method

Although the traditional trust-region method (TRM) has shown the advantages of improving the optimization efficiency, it might not make sufficient search in local regions since the space radius of new design space was largely dependent on the previous best point (the radius fromxk−xk−1 was linearly dependent), which would lead to premature of the optimization. To avoid this shortcoming, this paper proposed an enhanced trust-region method (ETRM) combining the independent/dependent strategy with the stochastic perturbation strategy, as shown below.
(9)Dnew=Dindependent∪Ddependent∪Dstochastic,(10)AEI=maxfmin−fxk−1,0EI,(11)rk=minγ1rk−1,rmax,AEI≥η,rk−1,0<AEI<η,maxγ2rk−1,rmin,AEI=0,(12)Dindependent=xmin−rkb−a,xmin+rkb−a,(13)Ddependent=xmin−rkxmin−xmin,i‐1,xmin+rkxmin−xmin,i‐1,xmin∈Xmin,Xmin=xmin,1,..,xmin,i,(14)Pk=1−InkInNmax,Ipertube≔i:ωi<Pk,ωi∈0,1,i=1,⋯,d,δk=Ipertubermaxb−a.∗randd,1,Dstochastic=xmin−δk,xmin+δk.Here, theDnew was the new local space defined by the Dindependent, Ddependent, and Dstochastic, which were computed by different strategies, as shown in (9). The space radius of the ETRM changed in terms of the actual improvement of EI (AEI) while the original TRM adopted the predicted improvement based on the surrogate model as shown (8). The trust factor rk was computed through (10), where typical values of rmin=0.04, rmax=0.08, γ1=1.2, and γ2=0.8 were used, respectively. If AEI≥η, where the η was the threshold for the AEI, the EI criterion was capable of decreasing the objective function value; the space radius would be expanded according to (11). If 0<AEI<η, the space radius would keep unchanged. If AEI=0, the surrogate model was unable to obtain better points in current space; then, a conservative space radius would be selected. (12) used the independent strategy from the current best point xmin and the entire design space to construct a uniform box-shaped trust region, where aandb were the lower and upper bound of the entire design space, respectively, and  was the Euclidean norm. The purpose of this strategy was to reduce the influence of the previous sample points and make the optimization more independent to find diverse sample points in each iteration. However, the dependent information xmin−xmin,i‐1 from the previous best point Xmin=xmin,1,..,xmin,i could maintain the efficient dimension information which would help the algorithm toward the global optima quickly. Thus, the dependent information was used to improve the dimension setting of the trust region, which was indicated by the vector direction from the previous best point xmin,i‐1 to the current best point xmin, as shown in (13). Besides, to make a full exploration of the local region, a stochastic strategy for trust region was presented by (14). Here, the Pk was the probability of perturbing any dimensions of design space, and Nmax was the maximum number of iterations. For the iteration k, the number of the dimension to be perturbed was a random variable with a binomial d,Pk distribution with a mean number of perturbed dimensions d×Pk, where d was the number of all dimensions in the design space. In (14), the Pk was decided by a strictly decreasing function and would decrease as the optimization carries on. The Ipertube was the set of the index of the perturbed dimension decided by Pk and ωi, where ωi was a uniform random number generated in the range 0,1, and it would be different in each iteration to maintain the diversity of design space. Then, the Dstochastic was computed by the trust radius δk and the current best point xmin. The use of a stochastic strategy for constructing a trust region was expected to be helpful for problems with many local minima and design variables.At the initial stage of optimization, the distribution ofxmin could be very sparse and their positions would change significantly in different iterations since the surrogate model accuracy would not be very precise. Under this condition, the dependent strategy could make use of useful dimension information to accelerate the convergence speed to better points. And the stochastic strategy would help the algorithm to search for multiple diverse sample points by perturbing a large fraction of the dimensions. As the progress of optimization, the distribution of xmin would be more centralized and the distance between the best points would be smaller. By perturbing a progressively smaller fraction of dimension, the vicinity of the current best point xmin was less likely to be disturbed. At present, the trust region would be largely dependent on the independent strategy, which ensured that the neighborhood of xmin would be focused throughout the process of optimization.The ETRM measured the improvement of the objective function and combined an independent/dependent strategy with the stochastic perturbation strategy to construct the promising local regions. These strategies could deal with different situations across the optimization process, and in combination, they could preserve the diversity of design space and prevent the premature of optimization, improving the efficiency and convergence of optimization.


## 3.3. Detail of Proposed Method

The proposed KSE method consisted of four parts: (1) search effective samples and select local minima; (2) classify local minima into fully and partially explored local minima; (3) exploit the partially explored local minima; and (4) combine global exploration and local exploitation. The flowchart of the method is illustrated in Figure2, and the following were the detailed steps of this method.Step 1 (initial design).
In the beginning, Latin hypercube sampling (LHS) method [50] was adopted to generate initial sample points.Step 2 (global search by EI criterion).
The EGO method based on DACE, where the Gaussian kernel function was adopted, was used to explore the entire design space, during which the particle swarm optimization (PSO) algorithm was adopted as an optimizer. As for the problems with multiple constraints, the constrained expected improvement criterion (CEI) [45] would be adopted to handle constraints in KSE.Step 3 (identify the local minima).
The sample points with good performance were selected as local minima and corresponding sample cluster.Step 4 (select the partially explored local minima).
Classify the local minima into fully and partially explored local minima.Step 5 (multiple subregion local search).
Deep exploitation of all partially explored local minima, based on the ETRM, would be carried out to improve the surrogate accuracy. After all local minima have been explored to their fullest extent, the algorithm would proceed to Step2 until no partially explored local minima could be identified.Step 6 (switch criterion function).
At the last stage of optimization, the MP criterion would be adopted instead of EI criterion based on the improvement of the EI criterion. The objective function was set as (15), and the function transition factor CEI measured the improvement of the EI criterion, as shown in (16). The fmin was the objective value of the current best sample point, and EImax was the improvement of the EI criterion. In this paper, the CEI was set as 0.01, which meant if the EImax was less than 1% of fmin, the objective function turned into the MP criterion.
(15)Objective=EIcriterion,CEI≥0.01,MPcriterion,else,(16)CEI=EImaxfmin.Algorithm 1: The encoding type of KSE.
The KSE for Global OptimizationInput: (1) original design space D=Xmax,Xmin⊂ℝd,d≥1;(2) global exploration iteration numberm_global;(3) cluster numberN, cluster radius rreq;(4) maximum iteration numberMax_k;(5)FunctionCriterion: EI function;(6) threshold of RMSE:RMSEthresholdOutput: the best solution as global optima x∗,yx∗;BeginChoose an initial set of sample pointsXD=x1D,⋯,xnD∈D by LHS sampling method.EvaluateXD to obtain the corresponding response YD=y1D,⋯,ynD, and store them in the database S.Whilek<Max_kfori=1:m_globalEmploy EGO algorithm withFunctionCriterion;Store the optimized solutionx and its function response value y in the database S;k=k+1;endSelectN clusters from database S, and identify the cluster center X∗=x1∗,⋯,xN∗, other sample points within the distance rreq=0.01Xmax−Xmin2, would be classified into the corresponding cluster S∗=S1∗,⋯,SN∗. The distance between sample points with cluster center was computed by Euclidean distance.forj=1:NSort all sample pointsXc∗=x1,⋯,xn of Sj∗ in terms of their function response value Yc∗=y1,⋯,yn in ascending order;Use Cross-validation to obtain the predicted valueYc∗=y1,⋯,yn of all sample points;RMSE=1/n∑i=1nyi−yi~;ifRMSE≤RMSEthresholdStorexi∗ into fully explored local minima dataset Xf=x1f,⋯,xnf;elseStorexi∗ into partially explored local minima dataset Xp=x1p,⋯,xnp;endendifXp≠∅fori=1:nDefine local spaceVTR centered at xip by the ETRM algorithm;Employ EGO algorithm withFunctionCriterion in VTR;Store the optimized solutionx and its function response value y in the database S;k=k+1;endelseSelect current best sample point valuefbest.CEI=ComupteFunctionCriterionEImax,fbestifCEI≥0.01FunctionCriterion⟵EI criterion;elseFunctionCriterion⟵MPcriterion;endendendEndFigure 2
Flowchart of the KSE optimization process.


## 4. Illustrative Examples

### 4.1. Example of the EGO Method

To illustrate the limitations of the traditional EGO method, the Goldstein-Price function [51] was used as an example. This 2‐d function was usually evaluated on the −2,22, with 3 local minima. And the global optima was located at 0,−1 with the value of 3.000. Figure 3 describes the original GP function while Figure 4 shows the surrogate space constructed by the Kriging model with initial d+1∗2 sample points [18], where d was the dimension. It demonstrated that the initial surrogate mode could not achieve a good approximation of the objective function.Figure 3
Original GP function.Figure 4
Kriging prediction with initial sample points.The convergence history of the GP function is shown in Figure5, where two obvious stagnations happened. The first stagnation was in the global exploration process, during which the maximal EI value was very large and the optimizer tended to explore the entire design space and improve the surrogate accuracy, as presented in Figure 6. During the late stages of optimization, the optimizer searched the neighborhood of the global optima. Since the objective values of sample points in that local space were close to that of the global optima, the EI criterion showed very little improvement and the optimizer tended to stochastic search. Thus, the optimization was trapped again.Figure 5
Convergence history of the objective function.Figure 6
Convergence history of max EI.The sample infilling process is presented in Figure7, in which the contour was the space constructed by the Kriging model, and white triangles were the infilled sample points. At the beginning of optimization, the fitting quality of the Kriging model was not that good and it would take a large number of sample points to explore the entire design space, during which the first stagnation happened, as shown in Figure 7(a). After that, the surrogate accuracy was improved, and the optimizer would turn into an efficient searching process during which the objective value was efficiently decreased. Figure 7(b) presents that the surrogate model achieved a much better approximation to the objective function, and sample points with good results have been obtained. However, at the later stage of the optimization, the first term of the EI function would become small since the difference between the prediction value of unknown points and the current best point was very small, and the second term of the EI function would dominate the optimization trend. Thus, the optimizer tended to stochastic search in unknown regions, during which the EI criterion could not make substantial improvement. Therefore, the optimization was trapped again, as shown in Figure 7(c). After 45 sample points were updated, the global optima would be found at the 99th iteration. Figure 7(d) presents the final surrogate model.Figure 7
The infill process of the EGO method.
(a)
The first stagnation process (iteration 4 to 44)(b)
The efficient searching process (iteration 45 to 53)(c)
The second stagnation process (iteration 54 to 99)(d)
The final surrogate modelThe process above demonstrated that the EGO method explored the entire design space at the price of plenty of computational costs, for it took a large number of sample points to improve the fitting quality of the surrogate model in the entire design space and get rid of deceptive regions. Besides, the EI criterion tended to be maximized in the regions close to the bounds of the design space and far away from the previous sample points, which made it inefficient for finding the global optima. To overcome these problems, this paper proposed a Kriging-based space exploration method.


### 4.2. Example of the Proposed Method

To better demonstrate the KSE method, the optimization process of the Goldstein-Price function was shown below. Figures8 and 9 present the convergence history of the objective function value and the CEI, respectively. There were mainly four phases during the optimization process. Phase 1 was the global exploration process based on the EI criterion. However, during this process, the objective value had little improvement after many iterations due to the bad fitting quality of the Kriging model. Then, three local minima were found and multiple subregions of local searches started to make deep exploitation, during which the objective value decreased a lot, as shown in phase 2. After that, the global exploration started again to search the global optima, which was demonstrated as phase 3. During this process, the improvement of the EI criterion was very little. To speed up the convergence of optimization, the objective function was transited into the MP criterion, and the global optima was soon found, shown as phase 4.Figure 8
Convergence history of the objective function.Figure 9
Convergence history of max EI.The update of sample points is shown in Figure10. Figure 10(a) presents the global exploration based on the EI criterion. Then, three partially explored local minima were selected to make further exploitation by multiple subregion local search strategy. To perform better exploitation, the ETRM algorithm was adopted to restrict optimization in a small region with dynamic bounds, where the red-dashed rectangular were their initial design spaces, namely, as shown in Figure 10(b). The exploitation result is presented in Figure 10(c), in which the local minima disappear and the surrogate model approximated the objective function well. To detect new partially explored local minima, the global search continued and several points were updated. In Figure 10(d), all local minima were fully explored. And in terms of the value of CEI, the objective function was turned into the MP criterion and it only took 3 evaluations to locate the global optima. At last, the global optima would be found at the 58th iteration.Figure 10
The infill process of the KSE method.
(a)
Iterations 1 to 36(b)
Iterations 37 to 45(c)
Iterations 46 to 55(d)
Iterations 55 to 58The KSE method could enhance and balance the exploitation and exploration ability of optimization by locating potential local minima and combining multiple objective functions, improving the optimization efficiency and preventing premature optimization.


## 4.1. Example of the EGO Method

To illustrate the limitations of the traditional EGO method, the Goldstein-Price function [51] was used as an example. This 2‐d function was usually evaluated on the −2,22, with 3 local minima. And the global optima was located at 0,−1 with the value of 3.000. Figure 3 describes the original GP function while Figure 4 shows the surrogate space constructed by the Kriging model with initial d+1∗2 sample points [18], where d was the dimension. It demonstrated that the initial surrogate mode could not achieve a good approximation of the objective function.Figure 3
Original GP function.Figure 4
Kriging prediction with initial sample points.The convergence history of the GP function is shown in Figure5, where two obvious stagnations happened. The first stagnation was in the global exploration process, during which the maximal EI value was very large and the optimizer tended to explore the entire design space and improve the surrogate accuracy, as presented in Figure 6. During the late stages of optimization, the optimizer searched the neighborhood of the global optima. Since the objective values of sample points in that local space were close to that of the global optima, the EI criterion showed very little improvement and the optimizer tended to stochastic search. Thus, the optimization was trapped again.Figure 5
Convergence history of the objective function.Figure 6
Convergence history of max EI.The sample infilling process is presented in Figure7, in which the contour was the space constructed by the Kriging model, and white triangles were the infilled sample points. At the beginning of optimization, the fitting quality of the Kriging model was not that good and it would take a large number of sample points to explore the entire design space, during which the first stagnation happened, as shown in Figure 7(a). After that, the surrogate accuracy was improved, and the optimizer would turn into an efficient searching process during which the objective value was efficiently decreased. Figure 7(b) presents that the surrogate model achieved a much better approximation to the objective function, and sample points with good results have been obtained. However, at the later stage of the optimization, the first term of the EI function would become small since the difference between the prediction value of unknown points and the current best point was very small, and the second term of the EI function would dominate the optimization trend. Thus, the optimizer tended to stochastic search in unknown regions, during which the EI criterion could not make substantial improvement. Therefore, the optimization was trapped again, as shown in Figure 7(c). After 45 sample points were updated, the global optima would be found at the 99th iteration. Figure 7(d) presents the final surrogate model.Figure 7
The infill process of the EGO method.
(a)
The first stagnation process (iteration 4 to 44)(b)
The efficient searching process (iteration 45 to 53)(c)
The second stagnation process (iteration 54 to 99)(d)
The final surrogate modelThe process above demonstrated that the EGO method explored the entire design space at the price of plenty of computational costs, for it took a large number of sample points to improve the fitting quality of the surrogate model in the entire design space and get rid of deceptive regions. Besides, the EI criterion tended to be maximized in the regions close to the bounds of the design space and far away from the previous sample points, which made it inefficient for finding the global optima. To overcome these problems, this paper proposed a Kriging-based space exploration method.


## 4.2. Example of the Proposed Method

To better demonstrate the KSE method, the optimization process of the Goldstein-Price function was shown below. Figures8 and 9 present the convergence history of the objective function value and the CEI, respectively. There were mainly four phases during the optimization process. Phase 1 was the global exploration process based on the EI criterion. However, during this process, the objective value had little improvement after many iterations due to the bad fitting quality of the Kriging model. Then, three local minima were found and multiple subregions of local searches started to make deep exploitation, during which the objective value decreased a lot, as shown in phase 2. After that, the global exploration started again to search the global optima, which was demonstrated as phase 3. During this process, the improvement of the EI criterion was very little. To speed up the convergence of optimization, the objective function was transited into the MP criterion, and the global optima was soon found, shown as phase 4.Figure 8
Convergence history of the objective function.Figure 9
Convergence history of max EI.The update of sample points is shown in Figure10. Figure 10(a) presents the global exploration based on the EI criterion. Then, three partially explored local minima were selected to make further exploitation by multiple subregion local search strategy. To perform better exploitation, the ETRM algorithm was adopted to restrict optimization in a small region with dynamic bounds, where the red-dashed rectangular were their initial design spaces, namely, as shown in Figure 10(b). The exploitation result is presented in Figure 10(c), in which the local minima disappear and the surrogate model approximated the objective function well. To detect new partially explored local minima, the global search continued and several points were updated. In Figure 10(d), all local minima were fully explored. And in terms of the value of CEI, the objective function was turned into the MP criterion and it only took 3 evaluations to locate the global optima. At last, the global optima would be found at the 58th iteration.Figure 10
The infill process of the KSE method.
(a)
Iterations 1 to 36(b)
Iterations 37 to 45(c)
Iterations 46 to 55(d)
Iterations 55 to 58The KSE method could enhance and balance the exploitation and exploration ability of optimization by locating potential local minima and combining multiple objective functions, improving the optimization efficiency and preventing premature optimization.


## 5. Test Functions

### 5.1. Experimental Setup

The performance of KSE was studied in the sense of global convergence capability, efficiency, and robustness on a broad set of global optimization test problems with 2 to 16 design variables. These included the seven Dixon [51] test functions (Branin, Goldstein-Price, Hartman3, Shekel5, Shekel7, Shekel10, and Hartman6), two test functions (SC and Shubert) with multiple local minima, and three test functions (Trid10, Sphere10, and F16) with higher dimension [32]. These test problems had their unique characteristics, and in combination, they could better represent many different situations in design problems. The detailed forms of these functions are given in Table 1. The initial LHS samples with size 2d+1 were the same for all optimization algorithms on all problems. Thirty runs on each of these benchmark problems have been made.Table 1
Bound-constrained benchmark problems for global optimization.
Test functionsDimDomainNo. of local minGlobal min valueBranin2−5,10×0,1530.3980Goldstein-Price2−2,2243.0000Hartman330,134-3.8628Shekel540,1045-10.1532Hartman660,166-3.3223SC2−2,226-1.0316Shekel740,1047-10.4029Shekel1040,10410-10.5364Shubert2−10,102>10-186.7309Trid1010−100,10010—-210.0000Sphere1010−5.12,5.1210—≤0.001F1616−1,116—25.8750The experiments of all test cases were performed on Intel(R) Core (TM) i7-8700 CPU @ 3.20 GHz computer. The obtained statistical results were compared with that of several well-known global optimization methods. One alternative was the efficient global optimization method (EGO) [6] as implemented in MATLAB by Viana [52], which was one of the most widely used surrogate-based global optimization methods, especially for engineering design problems. The model-pursuing sampling (MPS) method [53] was an adaptive surrogate model method producing discriminative samples toward the actual global optima. The mesh adaptive direct search (MADS) [54] algorithm was implemented as NOMADm [55], using the surrogate model to make it suitable for computationally expensive problems. A universal multistart approach called multilevel single linkage (MLSL) [56], with local optimization solver sequential quadratic programming (SQP), is implemented by MATLAB optimization toolbox [57]. Another alternative was trust-region-based adaptive response method (TR-ARSM) [49], which was an efficient space reduction method for multimodal problems. Trust-region implementation in Kriging-based optimization with expected improvement with restart strategy (TRIKE-Restart) was a trust-region-like approach where EI function was combined with trust-region and restart strategy [20]. We also compared the proposed method with two multistart methods: the A QUAsi-multistart Response Surface (AQUARS) [18], during which the initial points were obtained from the CGRBF method [29], and the multistart space reduction method (MSSR) [32], which was the combination of multistart approach and space reduction strategy. The parameter settings of these methods are summarized in Table 2. The acquired statistical results of AQUARS, TR-ARSM, TRIKE-Restart, and MSSR were collected from the published papers due to the lack of publicly available software to implement the competitor methods.Table 2
Parameter setting of KSE method.
MethodParameterValueKSECluster numberN5Objective function transition factorCEI0.01Distance coefficient0.01MLSL-SQPReduced sample coefficientξ0.5Fixed number in critical distanceρ4Number of local minimaw10Termination tolerance for current design variable0.001Termination tolerance for objective function value0.0001Maximum number of iteration500MPSMode-pursing sample pointsnpThe number of dimensionModel fitting tolerance coefficientcd0.01Diff toleranceεr0.00001Speed control factorr1MADSMesh size update parameterw−-1Mesh size update parameterw+1Fixed rational numberτ4Initial mesh size parameterΔ0m1Initial poll size parameterΔ0p1EGOIteration numberN800Population numberposTen times the dimensionThese methods were compared in terms of the average number of function evaluations (over 30 trials) required to get a solution withrelativeerror<1%. If ftarget was the global minima value over the domain D and fmin was the best value obtained by an algorithm, then the relative error of the algorithm was given by
(17)Relativeerror=fmin−ftargetftarget,ftarget≠0,0.001,ftarget=0.


### 5.2. Results and Discussion

Table3 gives the average number of function evaluations required by each method to reach the target value with relativeerror<1% [18]. If all 30 trials got within 1% of the global optima, then the number inside the parenthesis was the standard error of the mean. The symbol “>” indicated that at least one of the trials could not detect the target value. And Ne was the number of trials that did not get within 1% of the global minima value within 500 function evaluations.Table 3
Average number of function evaluations (over 30 trials) to get a relative error of <1%.
ProblemsKSEMLSL-SQPMPSMADSEGOThe best-published results from the comparison of TR-ARSM, MSSR, AQUARS, and TRIKE-RestartResultsNeResultsNeResultsNeResultsNeResultsNeResultsAlgorithmBranin22.7 (3.69)3024.4 (1.52)3057.3 (2.15)3031.5 (1.35)3040.8 (2.33)3025.6TRIKE-restartGoldstein-Price43.6 (4.31)3056.8 (9.63)30132.4 (6.25)3063.6 (4.77)3098.5 (10.77)3036.2TR-ARSMHartman323.4 (2.21)3042.3 (3.36)30>38.9(-)2741.7 (2.55)3042.1 (3.88)3026.5TRIKE-restartShekel5164.9 (33.3)30>368.9(-)25>446.3(-)5213.5 (37.1)30>139.9(-)9202.4TRIKE-restartHartman6131.1 (11.4)30157.1 (12.6)30>500(-)0144.6 (13.62)30154.2 (9.63)3054.5MSSRSC21.6 (3.46)3037.5 (2.77)3032.3 (5.66)3026.4 (2.11)3049 (6.37)3022.5MSSRShekel7144.3 (22.5)30>362.3(-)22>137.6(-)13168.5 (19.5)30>500 (30)0152.7AQUARSShekel10137.5 (9.62)30>414.2(-)17>455.7(-)7136.8 (11.2)30>500 (30)0121.1AQUARSShubert124.5 (11.3)30237.1 (21.7)30>500(-)0143.7 (12.6)30>437.5 (22)8122.9MSSRTrid10114.7 (13.5)30189.4 (11.4)30125.2 (5.74)30145.6 (4.55)30>500 (30)0142.4MSSRSphere10107.6 (9.85)30172.5 (8.96)30131.5 (9.68)30177.6 (11.12)30>500 (30)0115.4MSSRF16135.2 (8.57)30165.1 (7.3)30>500(-)0159.7 (8.55)30337.4 (15.9)30137.7MSSRFrom Table3, it was shown that the proposed KSE method performed much better than the EGO method, MPS method, and MLSL-SQP method on all test problems. The EGO method generally required more evaluations to get the target value, especially for the problems with high dimensionality and multimodality. The new sample points of EGO were more likely to be updated around the local minima which were well explored. The MPS method performed a little better than EGO on high-dimensional problems (Trid10 and Sphere10), but it was not efficient for complicated problems with higher multimodality (Shekel problems and Shubert function), since it was hard for MPS to detect the promising regions from the design space with multiple local minima. It was presented that MLSL-SQP was much better than EGO and MPS methods on 8 test problems, except for the difficult Shekel problems with deep and narrow global optima basins. However, the local searches of MLSL-SQP tended to full convergence around all local minima even if these local minima were unlikely to lead to better points. These three methods were well known for engineering design, so these results suggested that the KSE method was very promising for engineering optimization problems.It showed that KSE could reach the target value faster than 4 alternative methods (TR-ARSM, MSSR, AQUARS, and TRIKE-Restart) on 8 test problems (Branin, SC, Hartman3, Shekel5, Shekel7, Trid10, Sphere10, and F16), and it could be compared with the best results attained by the alternative methods on 2 other problems (Goldstein-Price and Shubert). Although alternatives based on the multistart approach (MSSR and AQUARS) could perform better than the KSE on 3 test problems (Hartman6, Shekel10, and Shubert), it could not conclude that the multistart approach had extremely advantages over the KSE, since KSE performed much better than MLSL-SQP on all test problems. It might be that these methods put much emphasis on local search. Besides, the different initial LHS methods and surrogate models in the compared papers could also influence the results. Anyway, the KSE was quite robust in the test cases mentioned in Table3. And it has shown its advantages in stability and efficiency to reach the target value in all trials on serval test problems.Figure11 shows the box plots for the number of function evaluations required to get within 1% of the target value for the KSE and some other alternatives on all test problems. Many trials of EGO and MPS could not achieve the desired target value on many test problems, and it was impossible to create accurate box plots for these methods. Hence, they were excluded from the box plots. The box plots showed that MADS was competitive with the KSE on Shekel and Shubert problems and MLSL-SQP was much worse than the KSE on all test problems in terms of the median number of function evaluations to get within 1% of the global minima value. The distributions of the number of function evaluations were much less spread out for the KSE compared to that of other methods on most test problems. Hence, the KSE was generally more robust and efficient than other methods.Figure 11
Box plot of the number of function evaluations to get within 1% of the target value.Rather than demonstrating the superiority of the proposed algorithm over other existing algorithms, the objective of the study was to show that the proposed algorithm could be a viable alternative for computationally expensive black-box global optimization, which has been shown on a wide variety of benchmark test problems.


### 5.3. Sensitivity Analysis

In this section, the KSE was tested on various cluster numbers and function transition factors. Table4 shows the results obtained by the test cases of applying KSE with different hyperparameters including (1) N=5,CEI=0.01, (2) N=3,CEI=0.01, (3) N=7,CEI=0.01, (4) N=5,CEI=0.005, (5) N=5,CEI=0.02, and (6) N=5,CEI=null. Case (1)~case (3) were compared to study the influence of cluster number. The comparisons of the other cases as well as case (1) were to research the influence of the function transition factor, during which case (6) presented the results without function transition, indicating that the objective function was always the EI criterion. The initial samples with the size of 2d+1 were the same for all cases. Each test problem has been repeated 30 times.Table 4
Average number of function evaluations (over 30 trials) to get a relative error of <1%.
ProblemsN=5,CEI=0.01N=3,CEI=0.01N=7,CEI=0.01N=5,CEI=0.005N=5,CEI=0.02N=5,CEI=nullBranin22.7 (3.69)21.2 (2.52)24.5 (1.04)23.9 (2.97)22.2 (3.01)24.6 (1.94)Goldstein-Price43.6 (4.31)44.8 (6.31)45.8 (5.15)44.9 (3.17)45.4 (3.69)45.7 (3.74)Hartman323.4 (2.21)47.8 (2.38)39.9 (3.44)22.7 (4.19)26.6 (3.22)46.9 (4.21)Shekel5164.9 (33.3)179.5 (42.8)166.7 (35.18)167.5 (31.09)166.7 (32.91)188.4 (33.22)Hartman6131.1 (11.4)166.4 (12.18)141.2 (13.55)133.3 (12.07)132.8 (13.67)169.6 (15.71)SC21.6 (3.46)39.8 (4.11)26.7 (2.19)23.9 (2.64)22.4 (3.01)39.6 (3.52)Shekel7144.3 (22.5)187.7 (25.23)158.4 (29.45)147.6 (23.11)146.4 (26.71)189.3 (23.21)Shekel10137.5 (9.62)192.3 (10.74)145.8 (9.75)141.6 (10.44)145.9 (11.09)201.8 (12.73)Shubert124.5 (11.3)177.6 (12.08)146.1 (11.70)129.1 (13.88)127.6 (10.76)184.4 (11.03)Trid10114.7 (13.5)118.8 (12.77)115.3 (13.8)119.7 (13.01)121.3 (13.69)132.3 (15.01)Sphere10107.6 (9.85)106.8 (10.18)105.2 (12.33)106.4 (9.24)110.4 (8.35)122.6 (8.11)F16135.2 (8.57)147.5 (10.12)134.7 (8.44)133.5 (9.69)139.6 (7.75)157.1 (11.24)From Table4, we could know that case (1) and case (2) achieved really good results on Branin and Goldstein-Price problems and case (3) also obtained competitive results on these two test problems, which showed that the proposed method was not that sensitive to the cluster number for problems with low multimodality and dimensionality. In the era of increasing multimodality and dimensionality, a more comprehensive clustering strategy in KSE was needed to identify the promising local minima. It was shown that case (2) obtained the best results on Hartman3, Shekel5, Hartman6, Shekel7, Shekel10, Shubert, and Trid10 test problems and competitive results on Sphere10 and F16 test problems. But case (3) also obtained the competitive results on Shekel5, SC, Shekel7, Shekel10, and Trid10 test problems.As for the function transition factorCEI, it seemed that the KSE was not sensitive to the function transition factor CEI with the appropriate cluster number, like N=5. There was little difference among the results obtained by case (1), case (4), and case (5) on all test problems, where the case (1) obtained the best results on 8 test problems, except Branin, Hartman3, Sphere10, and F16 test problems, and competitive results on Branin, Hartman3, and Sphere10 test problems. Despite this, case (6) performed worse on most test problems than the cases with a function transition factor CEI. This suggested that it was important to incorporate the function transition factor as well.Figure12 shows the box plots for the number of function evaluations required to get within 1% of the target value of all cases. It was presented that the results obtained by case (1) were better than other cases on 8 of the 12 test problems (all except Branin, Shekel5, Trid10, and Sphere10). And the distribution of function evaluations of the case (1) was more concentrated than that of other cases, although the results of the case (4) and case (5) could be competitive on all test problems, indicating that they were not very sensitive within the current interval.Figure 12
Box plot of the number of function evaluations to get within 1% of the target value.In summary, these results suggested that cluster number and function transition factor were all necessary for good performance on most test problems, and the KSE was not very sensitive to function transition factor with suitable cluster number.


## 5.1. Experimental Setup

The performance of KSE was studied in the sense of global convergence capability, efficiency, and robustness on a broad set of global optimization test problems with 2 to 16 design variables. These included the seven Dixon [51] test functions (Branin, Goldstein-Price, Hartman3, Shekel5, Shekel7, Shekel10, and Hartman6), two test functions (SC and Shubert) with multiple local minima, and three test functions (Trid10, Sphere10, and F16) with higher dimension [32]. These test problems had their unique characteristics, and in combination, they could better represent many different situations in design problems. The detailed forms of these functions are given in Table 1. The initial LHS samples with size 2d+1 were the same for all optimization algorithms on all problems. Thirty runs on each of these benchmark problems have been made.Table 1
Bound-constrained benchmark problems for global optimization.
Test functionsDimDomainNo. of local minGlobal min valueBranin2−5,10×0,1530.3980Goldstein-Price2−2,2243.0000Hartman330,134-3.8628Shekel540,1045-10.1532Hartman660,166-3.3223SC2−2,226-1.0316Shekel740,1047-10.4029Shekel1040,10410-10.5364Shubert2−10,102>10-186.7309Trid1010−100,10010—-210.0000Sphere1010−5.12,5.1210—≤0.001F1616−1,116—25.8750The experiments of all test cases were performed on Intel(R) Core (TM) i7-8700 CPU @ 3.20 GHz computer. The obtained statistical results were compared with that of several well-known global optimization methods. One alternative was the efficient global optimization method (EGO) [6] as implemented in MATLAB by Viana [52], which was one of the most widely used surrogate-based global optimization methods, especially for engineering design problems. The model-pursuing sampling (MPS) method [53] was an adaptive surrogate model method producing discriminative samples toward the actual global optima. The mesh adaptive direct search (MADS) [54] algorithm was implemented as NOMADm [55], using the surrogate model to make it suitable for computationally expensive problems. A universal multistart approach called multilevel single linkage (MLSL) [56], with local optimization solver sequential quadratic programming (SQP), is implemented by MATLAB optimization toolbox [57]. Another alternative was trust-region-based adaptive response method (TR-ARSM) [49], which was an efficient space reduction method for multimodal problems. Trust-region implementation in Kriging-based optimization with expected improvement with restart strategy (TRIKE-Restart) was a trust-region-like approach where EI function was combined with trust-region and restart strategy [20]. We also compared the proposed method with two multistart methods: the A QUAsi-multistart Response Surface (AQUARS) [18], during which the initial points were obtained from the CGRBF method [29], and the multistart space reduction method (MSSR) [32], which was the combination of multistart approach and space reduction strategy. The parameter settings of these methods are summarized in Table 2. The acquired statistical results of AQUARS, TR-ARSM, TRIKE-Restart, and MSSR were collected from the published papers due to the lack of publicly available software to implement the competitor methods.Table 2
Parameter setting of KSE method.
MethodParameterValueKSECluster numberN5Objective function transition factorCEI0.01Distance coefficient0.01MLSL-SQPReduced sample coefficientξ0.5Fixed number in critical distanceρ4Number of local minimaw10Termination tolerance for current design variable0.001Termination tolerance for objective function value0.0001Maximum number of iteration500MPSMode-pursing sample pointsnpThe number of dimensionModel fitting tolerance coefficientcd0.01Diff toleranceεr0.00001Speed control factorr1MADSMesh size update parameterw−-1Mesh size update parameterw+1Fixed rational numberτ4Initial mesh size parameterΔ0m1Initial poll size parameterΔ0p1EGOIteration numberN800Population numberposTen times the dimensionThese methods were compared in terms of the average number of function evaluations (over 30 trials) required to get a solution withrelativeerror<1%. If ftarget was the global minima value over the domain D and fmin was the best value obtained by an algorithm, then the relative error of the algorithm was given by
(17)Relativeerror=fmin−ftargetftarget,ftarget≠0,0.001,ftarget=0.


## 5.2. Results and Discussion

Table3 gives the average number of function evaluations required by each method to reach the target value with relativeerror<1% [18]. If all 30 trials got within 1% of the global optima, then the number inside the parenthesis was the standard error of the mean. The symbol “>” indicated that at least one of the trials could not detect the target value. And Ne was the number of trials that did not get within 1% of the global minima value within 500 function evaluations.Table 3
Average number of function evaluations (over 30 trials) to get a relative error of <1%.
ProblemsKSEMLSL-SQPMPSMADSEGOThe best-published results from the comparison of TR-ARSM, MSSR, AQUARS, and TRIKE-RestartResultsNeResultsNeResultsNeResultsNeResultsNeResultsAlgorithmBranin22.7 (3.69)3024.4 (1.52)3057.3 (2.15)3031.5 (1.35)3040.8 (2.33)3025.6TRIKE-restartGoldstein-Price43.6 (4.31)3056.8 (9.63)30132.4 (6.25)3063.6 (4.77)3098.5 (10.77)3036.2TR-ARSMHartman323.4 (2.21)3042.3 (3.36)30>38.9(-)2741.7 (2.55)3042.1 (3.88)3026.5TRIKE-restartShekel5164.9 (33.3)30>368.9(-)25>446.3(-)5213.5 (37.1)30>139.9(-)9202.4TRIKE-restartHartman6131.1 (11.4)30157.1 (12.6)30>500(-)0144.6 (13.62)30154.2 (9.63)3054.5MSSRSC21.6 (3.46)3037.5 (2.77)3032.3 (5.66)3026.4 (2.11)3049 (6.37)3022.5MSSRShekel7144.3 (22.5)30>362.3(-)22>137.6(-)13168.5 (19.5)30>500 (30)0152.7AQUARSShekel10137.5 (9.62)30>414.2(-)17>455.7(-)7136.8 (11.2)30>500 (30)0121.1AQUARSShubert124.5 (11.3)30237.1 (21.7)30>500(-)0143.7 (12.6)30>437.5 (22)8122.9MSSRTrid10114.7 (13.5)30189.4 (11.4)30125.2 (5.74)30145.6 (4.55)30>500 (30)0142.4MSSRSphere10107.6 (9.85)30172.5 (8.96)30131.5 (9.68)30177.6 (11.12)30>500 (30)0115.4MSSRF16135.2 (8.57)30165.1 (7.3)30>500(-)0159.7 (8.55)30337.4 (15.9)30137.7MSSRFrom Table3, it was shown that the proposed KSE method performed much better than the EGO method, MPS method, and MLSL-SQP method on all test problems. The EGO method generally required more evaluations to get the target value, especially for the problems with high dimensionality and multimodality. The new sample points of EGO were more likely to be updated around the local minima which were well explored. The MPS method performed a little better than EGO on high-dimensional problems (Trid10 and Sphere10), but it was not efficient for complicated problems with higher multimodality (Shekel problems and Shubert function), since it was hard for MPS to detect the promising regions from the design space with multiple local minima. It was presented that MLSL-SQP was much better than EGO and MPS methods on 8 test problems, except for the difficult Shekel problems with deep and narrow global optima basins. However, the local searches of MLSL-SQP tended to full convergence around all local minima even if these local minima were unlikely to lead to better points. These three methods were well known for engineering design, so these results suggested that the KSE method was very promising for engineering optimization problems.It showed that KSE could reach the target value faster than 4 alternative methods (TR-ARSM, MSSR, AQUARS, and TRIKE-Restart) on 8 test problems (Branin, SC, Hartman3, Shekel5, Shekel7, Trid10, Sphere10, and F16), and it could be compared with the best results attained by the alternative methods on 2 other problems (Goldstein-Price and Shubert). Although alternatives based on the multistart approach (MSSR and AQUARS) could perform better than the KSE on 3 test problems (Hartman6, Shekel10, and Shubert), it could not conclude that the multistart approach had extremely advantages over the KSE, since KSE performed much better than MLSL-SQP on all test problems. It might be that these methods put much emphasis on local search. Besides, the different initial LHS methods and surrogate models in the compared papers could also influence the results. Anyway, the KSE was quite robust in the test cases mentioned in Table3. And it has shown its advantages in stability and efficiency to reach the target value in all trials on serval test problems.Figure11 shows the box plots for the number of function evaluations required to get within 1% of the target value for the KSE and some other alternatives on all test problems. Many trials of EGO and MPS could not achieve the desired target value on many test problems, and it was impossible to create accurate box plots for these methods. Hence, they were excluded from the box plots. The box plots showed that MADS was competitive with the KSE on Shekel and Shubert problems and MLSL-SQP was much worse than the KSE on all test problems in terms of the median number of function evaluations to get within 1% of the global minima value. The distributions of the number of function evaluations were much less spread out for the KSE compared to that of other methods on most test problems. Hence, the KSE was generally more robust and efficient than other methods.Figure 11
Box plot of the number of function evaluations to get within 1% of the target value.Rather than demonstrating the superiority of the proposed algorithm over other existing algorithms, the objective of the study was to show that the proposed algorithm could be a viable alternative for computationally expensive black-box global optimization, which has been shown on a wide variety of benchmark test problems.


## 5.3. Sensitivity Analysis

In this section, the KSE was tested on various cluster numbers and function transition factors. Table4 shows the results obtained by the test cases of applying KSE with different hyperparameters including (1) N=5,CEI=0.01, (2) N=3,CEI=0.01, (3) N=7,CEI=0.01, (4) N=5,CEI=0.005, (5) N=5,CEI=0.02, and (6) N=5,CEI=null. Case (1)~case (3) were compared to study the influence of cluster number. The comparisons of the other cases as well as case (1) were to research the influence of the function transition factor, during which case (6) presented the results without function transition, indicating that the objective function was always the EI criterion. The initial samples with the size of 2d+1 were the same for all cases. Each test problem has been repeated 30 times.Table 4
Average number of function evaluations (over 30 trials) to get a relative error of <1%.
ProblemsN=5,CEI=0.01N=3,CEI=0.01N=7,CEI=0.01N=5,CEI=0.005N=5,CEI=0.02N=5,CEI=nullBranin22.7 (3.69)21.2 (2.52)24.5 (1.04)23.9 (2.97)22.2 (3.01)24.6 (1.94)Goldstein-Price43.6 (4.31)44.8 (6.31)45.8 (5.15)44.9 (3.17)45.4 (3.69)45.7 (3.74)Hartman323.4 (2.21)47.8 (2.38)39.9 (3.44)22.7 (4.19)26.6 (3.22)46.9 (4.21)Shekel5164.9 (33.3)179.5 (42.8)166.7 (35.18)167.5 (31.09)166.7 (32.91)188.4 (33.22)Hartman6131.1 (11.4)166.4 (12.18)141.2 (13.55)133.3 (12.07)132.8 (13.67)169.6 (15.71)SC21.6 (3.46)39.8 (4.11)26.7 (2.19)23.9 (2.64)22.4 (3.01)39.6 (3.52)Shekel7144.3 (22.5)187.7 (25.23)158.4 (29.45)147.6 (23.11)146.4 (26.71)189.3 (23.21)Shekel10137.5 (9.62)192.3 (10.74)145.8 (9.75)141.6 (10.44)145.9 (11.09)201.8 (12.73)Shubert124.5 (11.3)177.6 (12.08)146.1 (11.70)129.1 (13.88)127.6 (10.76)184.4 (11.03)Trid10114.7 (13.5)118.8 (12.77)115.3 (13.8)119.7 (13.01)121.3 (13.69)132.3 (15.01)Sphere10107.6 (9.85)106.8 (10.18)105.2 (12.33)106.4 (9.24)110.4 (8.35)122.6 (8.11)F16135.2 (8.57)147.5 (10.12)134.7 (8.44)133.5 (9.69)139.6 (7.75)157.1 (11.24)From Table4, we could know that case (1) and case (2) achieved really good results on Branin and Goldstein-Price problems and case (3) also obtained competitive results on these two test problems, which showed that the proposed method was not that sensitive to the cluster number for problems with low multimodality and dimensionality. In the era of increasing multimodality and dimensionality, a more comprehensive clustering strategy in KSE was needed to identify the promising local minima. It was shown that case (2) obtained the best results on Hartman3, Shekel5, Hartman6, Shekel7, Shekel10, Shubert, and Trid10 test problems and competitive results on Sphere10 and F16 test problems. But case (3) also obtained the competitive results on Shekel5, SC, Shekel7, Shekel10, and Trid10 test problems.As for the function transition factorCEI, it seemed that the KSE was not sensitive to the function transition factor CEI with the appropriate cluster number, like N=5. There was little difference among the results obtained by case (1), case (4), and case (5) on all test problems, where the case (1) obtained the best results on 8 test problems, except Branin, Hartman3, Sphere10, and F16 test problems, and competitive results on Branin, Hartman3, and Sphere10 test problems. Despite this, case (6) performed worse on most test problems than the cases with a function transition factor CEI. This suggested that it was important to incorporate the function transition factor as well.Figure12 shows the box plots for the number of function evaluations required to get within 1% of the target value of all cases. It was presented that the results obtained by case (1) were better than other cases on 8 of the 12 test problems (all except Branin, Shekel5, Trid10, and Sphere10). And the distribution of function evaluations of the case (1) was more concentrated than that of other cases, although the results of the case (4) and case (5) could be competitive on all test problems, indicating that they were not very sensitive within the current interval.Figure 12
Box plot of the number of function evaluations to get within 1% of the target value.In summary, these results suggested that cluster number and function transition factor were all necessary for good performance on most test problems, and the KSE was not very sensitive to function transition factor with suitable cluster number.


## 6. Test on Benchmark Problems

This section applied the proposed KSE method to two aerodynamic optimization problems. To validate the proposed algorithm’s performance, three other global optimization methods were employed for comparison. One was MLSL coupled with mesh adaptive direct search (MADS) [54] algorithm, which was implemented as NOMADm [55], using the surrogate model to make it suitable for computationally expensive problems. Another one was the constraint-importance model-pursuing sampling (CiMPS), which was an extension of the MPS method developed for handling expensive constraints by Kazemi et al. [58]. The last method was the EGO method, one of the most well-known global optimization methods for engineering problems. The default or recommended tuning parameters of these methods were used. Ten runs on each problem have been made by all methods.In this section, a high-fidelity CFD solver, CFL3D [59], was adopted to evaluate the aerodynamic characteristics of airfoils and wings. The Navier-Stokes function incorporated with shear stress transport (SST) two-equation turbulence model was used to simulate the flow field of airfoils and wings. To perform the aerodynamic design optimization, a more powerful workstation equipped with AMD Epyc 7763 64-core @ 2.45 GHz CPUs and 512 G RAM was used.


### 6.1. Case I. Transonic Airfoil Design

Case I was provided by the AIAA aerodynamic design optimization discussion group (ADODG: the drag minimization of the RAE 2822 airfoil in transonic viscous flow). The Mach number was 0.734, and the Reynolds number was 6.5e6. The RAE 2882 airfoil was optimized with a fixed life coefficient of 0.824. The pitching moment should be bigger than -0.092, and its area should not be less than that of RAE 2822. The statements of problem are summarized in Table5. More detail on this case could be referred to in [60, 61]. The problem could be expressed as a standard nonlinear optimization problem:
(18)MinCd,s.t.Cl=0.824,Cm≥−0.092,Area≥Areainitial.Table 5
RAE 2822 airfoil optimization problem description.
QuantityLowerUpperScalingMinimizeCdConcerningShape (coefficients of Bernstein function)24-0.050.051Total number of design variables24Subject toCl10.8240.8241Cm1-0.09210Area constraint1Areainitial10Total number of design variables3It was a standard airfoil optimization with medium multimodality [62], which could be used to test the proposed method. The baseline shape was the RAE 2822 airfoil. The design variables were the z-coordinates of the CST parameterization with 24 shape parameters in total. The design space is shown in Figure 13, and the computational grid is shown in Figure 14. Generate 100 sample points in the initial design space with the LHS method, and update 300 sample points during optimization progress.Figure 13
The initial design space.Figure 14
The computational grid of RAE 2822.In this case, the EGO method tried to explore everywhere of design space, leading to bad optimization convergence; the CiMPS method was very efficient in the early stage of optimization, but at early stage, the surrogate model was not stable, and it was easily trapped in local minima, leading to optimization premature in this problem; the starting points could easily lie in the neighborhood of the previously found local minima, causing wasted computational cost in researching these well-explored local minima. Figure15 presents the design results of ten trials of all methods, and most of the design results by the KSE method were better than other methods, indicating that the KSE method was more stable than the other alternatives. Figure 16 shows that the KSE took 17% iterations of MADS to reach the similar drag coefficient value and it converged to the target shape faster. Thus, the KSE method was more efficient and robust.Figure 15
The results of ten trials of each method.Figure 16
Mean convergence of best objective function values in 10 trials.The best design result of each method was selected to make a comparison. Table6 presents the result comparison of different methods which indicated that all the constraints were satisfied. Under the same limited objective function evaluations, the computational cost of the MADS was the cheapest, but the KSE obtained better design results, compared to other optimization methods. And the Cd of design result by the KSE was around 110 cts, which was similar to the result in reference [62]; therefore, it was very likely close to the global optima. Figures 17 and 18 show the comparison of the optimized airfoil shapes and pressure coefficient distribution. As we could see, the shape trend of all optimized airfoils was the same: the locations of maximal thickness were moved backward, compared to the baseline, and the radiuses of their leading edges were reduced. The upper surfaces of optimized airfoils were very similar, and the difference mainly occurred on the lower surface, which was the main source of local minima. From Figure 18, we could know that the suction peaks of all optimized airfoils got much stronger and the shock waves have been weakened compared to baseline. However, the KSE nearly eliminated the shock wave while other methods remained an obvious shock wave, leading to bad aerodynamic performance.Table 6
The best result comparison of different methods.
ClCd (counts)CmThe number of objective function evaluationCPU time (min)Baseline0.824203.1-0.0927N/AKSE0.824110.5-0.0919100+300112.02EGO0.824112.6-0.0915100+300117.11CiMPS0.824112.8-0.0910100+300110.68MADS0.824112.1-0.0908100+300105.59Figure 17
The comparison of optimized airfoil shape.Figure 18
The comparison of pressure coefficient distribution.


### 6.2. Case II. CRM Wing Optimization

The baseline of Case II was a wing with a blunt trailing edge selected from the CRM wing-body geometry [63], which was representative of a contemporary transonic commercial transport, similar to the Boeing 777. The geometry and specifications were also given by the ADODG, while the fuselage and tail were removed from the original CRM, and the root of the remaining wing was moved to the symmetry plane. This baseline geometry is shown in Figure 19. All coordinates were scaled by the mean aerodynamic chord (275.8 in). The resulting reference chord was 1.0, and the reference area was 3.407014. The moment reference point was located at x,y,z=1.2077,0.0,0.007669.Figure 19
Baseline CRM wing scaled by its mean aerodynamic chord.The problem statements are shown in Table7. The objective was to minimize the drag, subject to a lift constraint (CL=0.5) and a pitch moment constraint (CMy≥−0.17). The shape design variables were the z-coordinate movement of 72 control points on the FFD volume and 5 twist angles, which are shown in Figure 20. The control points at the trailing edge were constrained to keep the trailing edge unchanged. And the leading edge control points at the wing root were also constrained to maintain a constant incidence for the root section. There were 500 thickness constraints imposed in a 25 chordwise and 20 spanwise grid covering the full span. Each thickness constraint was set to be no smaller than 25% of the baseline thickness at all locations. Finally, the internal volume was constrained to be greater than or equal to the baseline volume. The optimization problem was shown below.
(19)MinCD,s.t.CL=0.5,CMy≥−0.17,t≥0.25tbaseline,V≥Vbaseline,ΔzTE,upper=−ΔzTE,lower,ΔzLE,upper,root=−ΔzTE,lower,root.Table 7
CRM wing optimization problem description.
QuantityLowerUpperScalingMinimizeCDConcerningTwist angle5−4o4o1Sectional shape (z-coordinates of the FFD parameterization)72-0.050.051Total number of design variables77Subject toCL10.50.51CM1-0.1710Volume constraint1Vbaseline1000Thickness constraint5000.25tbaseline1000Leading edge position11000Trailing edge position61000Total number of design constraints510Figure 20
Shape design variables of FFD.The computational grid is shown in Figure21. The mesh was marched out from the surface mesh using an O-grid topology to a far-field located at a distance of 25 times the span. The cruise Mach number was 0.85 with a Reynolds number of 5 million based on the mean aerodynamic chord. The mesh generated for optimization contained 15.5 million cells. It was a complicated 3D aerodynamic optimization problem with relatively high dimensionality and multimodality [64].Figure 21
The computational grid of the CRM wing.200 sample points were generated in the initial design space by the LHS method, and 500 sample points were to be updated as optimization progresses. Figure22 presents the cost-effectiveness comparison and optimized results of ten trials for each method, indicating that the KSE method generally achieved better results within default computational costs and was more efficient, compared to other methods. Figure 23 shows that the KSE held a better convergence speed to obtain the ideal design results. Table 8 summarizes the results of all methods. At the optima points, the lift coefficient and pitch moment coefficient constraints were all met. The discrepancy in the computational cost of all optimization algorithms was not that large under the same number of objective function evaluations. It was shown that the optima by the KSE were the best of all global optimization methods, and the drag coefficient has been reduced by 14.4 counts compared to the baseline. The drag coefficient of the result obtained by the CiMPS method was similar to that of the MADS method, which was slightly better than that of the EGO method.Figure 22
The results of ten trials of each method.Figure 23
Mean convergence of best objective function values in 10 trials.Table 8
The best result comparison of different methods.
CLCD (counts)CMThe number of objective function evaluationCPU time (h)Baseline0.50210.8-0.182N/AKSE0.50196.4-0.169200+500106.30EGO0.50200.2-0.165200+500107.66CiMPS0.50198.8-0.166200+500107.53MADS0.50199.3-0.166200+500106.26Pressure distributions on the platforms of all optimized results are shown in Figures24–27, during which the baseline was shown on the left and the optimized results were on the right, respectively. For all the optimized wing results, the lift coefficient targets were met and the pitching moment constraints were satisfied. In the optimized result of the KSE method, the shock was largely reduced, which was achieved by fine-tuning the twist distribution and airfoil shapes. The optimized results of the CiMPS and MADS methods were similar to each other, the low-pressure regions extended, which was beneficial to drag reduction, but there still existed obvious shock across the middle of the wings. As for the optimized result of the EGO method, the shock wave on the inner wing has been eliminated, while on the outer wing, the shock extended to the wingtip.Figure 24
Pressure distributions of baseline and the KSE.Figure 25
Pressure distributions of baseline and the EGO.Figure 26
Pressure distributions of baseline and the CiMPS.Figure 27
Pressure distributions of baseline and the MADS.Pressure distributions on different cross-sections are compared in Figure28. At Y=0.085m, the thickness of the airfoil on the optimized results got thicker while airfoils on other sections get thinner, since the thicknesses were allowed to decrease to 25% of the original thickness and the wave drag was strongly influenced by decreased the thickness. But the volume was constrained to be not smaller than the baseline volume, so the optimizer decreased the thickness of the airfoils on the outer wing while increasing the thickness near the root section. Lyu et al. [63] observed similar trends in their results. Most of the optimized results eliminated the shock at Y=0.085m, except for the results obtained by the EGO method. At Y=1.025m, Y=2.642m, and Y=3.544m, the shock has been eliminated on the optimized wing of the KSE method, while for other results, the shocks were still existing. All results shared a similar trend at Y =2.115 m, and the double weak shock replaced the strong shock. And at Y=3.130m, the shocks moved forward without obvious weakness.Figure 28
Geometry and pressure distributions at a different section of the baseline model and optimized results.
(a)
Y=0.085m(b)
Y=1.025m(c)
Y=2.115m(d)
Y=2.642m(e)
Y=3.130m(f)
Y=3.544m


## 6.1. Case I. Transonic Airfoil Design

Case I was provided by the AIAA aerodynamic design optimization discussion group (ADODG: the drag minimization of the RAE 2822 airfoil in transonic viscous flow). The Mach number was 0.734, and the Reynolds number was 6.5e6. The RAE 2882 airfoil was optimized with a fixed life coefficient of 0.824. The pitching moment should be bigger than -0.092, and its area should not be less than that of RAE 2822. The statements of problem are summarized in Table5. More detail on this case could be referred to in [60, 61]. The problem could be expressed as a standard nonlinear optimization problem:
(18)MinCd,s.t.Cl=0.824,Cm≥−0.092,Area≥Areainitial.Table 5
RAE 2822 airfoil optimization problem description.
QuantityLowerUpperScalingMinimizeCdConcerningShape (coefficients of Bernstein function)24-0.050.051Total number of design variables24Subject toCl10.8240.8241Cm1-0.09210Area constraint1Areainitial10Total number of design variables3It was a standard airfoil optimization with medium multimodality [62], which could be used to test the proposed method. The baseline shape was the RAE 2822 airfoil. The design variables were the z-coordinates of the CST parameterization with 24 shape parameters in total. The design space is shown in Figure 13, and the computational grid is shown in Figure 14. Generate 100 sample points in the initial design space with the LHS method, and update 300 sample points during optimization progress.Figure 13
The initial design space.Figure 14
The computational grid of RAE 2822.In this case, the EGO method tried to explore everywhere of design space, leading to bad optimization convergence; the CiMPS method was very efficient in the early stage of optimization, but at early stage, the surrogate model was not stable, and it was easily trapped in local minima, leading to optimization premature in this problem; the starting points could easily lie in the neighborhood of the previously found local minima, causing wasted computational cost in researching these well-explored local minima. Figure15 presents the design results of ten trials of all methods, and most of the design results by the KSE method were better than other methods, indicating that the KSE method was more stable than the other alternatives. Figure 16 shows that the KSE took 17% iterations of MADS to reach the similar drag coefficient value and it converged to the target shape faster. Thus, the KSE method was more efficient and robust.Figure 15
The results of ten trials of each method.Figure 16
Mean convergence of best objective function values in 10 trials.The best design result of each method was selected to make a comparison. Table6 presents the result comparison of different methods which indicated that all the constraints were satisfied. Under the same limited objective function evaluations, the computational cost of the MADS was the cheapest, but the KSE obtained better design results, compared to other optimization methods. And the Cd of design result by the KSE was around 110 cts, which was similar to the result in reference [62]; therefore, it was very likely close to the global optima. Figures 17 and 18 show the comparison of the optimized airfoil shapes and pressure coefficient distribution. As we could see, the shape trend of all optimized airfoils was the same: the locations of maximal thickness were moved backward, compared to the baseline, and the radiuses of their leading edges were reduced. The upper surfaces of optimized airfoils were very similar, and the difference mainly occurred on the lower surface, which was the main source of local minima. From Figure 18, we could know that the suction peaks of all optimized airfoils got much stronger and the shock waves have been weakened compared to baseline. However, the KSE nearly eliminated the shock wave while other methods remained an obvious shock wave, leading to bad aerodynamic performance.Table 6
The best result comparison of different methods.
ClCd (counts)CmThe number of objective function evaluationCPU time (min)Baseline0.824203.1-0.0927N/AKSE0.824110.5-0.0919100+300112.02EGO0.824112.6-0.0915100+300117.11CiMPS0.824112.8-0.0910100+300110.68MADS0.824112.1-0.0908100+300105.59Figure 17
The comparison of optimized airfoil shape.Figure 18
The comparison of pressure coefficient distribution.


## 6.2. Case II. CRM Wing Optimization

The baseline of Case II was a wing with a blunt trailing edge selected from the CRM wing-body geometry [63], which was representative of a contemporary transonic commercial transport, similar to the Boeing 777. The geometry and specifications were also given by the ADODG, while the fuselage and tail were removed from the original CRM, and the root of the remaining wing was moved to the symmetry plane. This baseline geometry is shown in Figure 19. All coordinates were scaled by the mean aerodynamic chord (275.8 in). The resulting reference chord was 1.0, and the reference area was 3.407014. The moment reference point was located at x,y,z=1.2077,0.0,0.007669.Figure 19
Baseline CRM wing scaled by its mean aerodynamic chord.The problem statements are shown in Table7. The objective was to minimize the drag, subject to a lift constraint (CL=0.5) and a pitch moment constraint (CMy≥−0.17). The shape design variables were the z-coordinate movement of 72 control points on the FFD volume and 5 twist angles, which are shown in Figure 20. The control points at the trailing edge were constrained to keep the trailing edge unchanged. And the leading edge control points at the wing root were also constrained to maintain a constant incidence for the root section. There were 500 thickness constraints imposed in a 25 chordwise and 20 spanwise grid covering the full span. Each thickness constraint was set to be no smaller than 25% of the baseline thickness at all locations. Finally, the internal volume was constrained to be greater than or equal to the baseline volume. The optimization problem was shown below.
(19)MinCD,s.t.CL=0.5,CMy≥−0.17,t≥0.25tbaseline,V≥Vbaseline,ΔzTE,upper=−ΔzTE,lower,ΔzLE,upper,root=−ΔzTE,lower,root.Table 7
CRM wing optimization problem description.
QuantityLowerUpperScalingMinimizeCDConcerningTwist angle5−4o4o1Sectional shape (z-coordinates of the FFD parameterization)72-0.050.051Total number of design variables77Subject toCL10.50.51CM1-0.1710Volume constraint1Vbaseline1000Thickness constraint5000.25tbaseline1000Leading edge position11000Trailing edge position61000Total number of design constraints510Figure 20
Shape design variables of FFD.The computational grid is shown in Figure21. The mesh was marched out from the surface mesh using an O-grid topology to a far-field located at a distance of 25 times the span. The cruise Mach number was 0.85 with a Reynolds number of 5 million based on the mean aerodynamic chord. The mesh generated for optimization contained 15.5 million cells. It was a complicated 3D aerodynamic optimization problem with relatively high dimensionality and multimodality [64].Figure 21
The computational grid of the CRM wing.200 sample points were generated in the initial design space by the LHS method, and 500 sample points were to be updated as optimization progresses. Figure22 presents the cost-effectiveness comparison and optimized results of ten trials for each method, indicating that the KSE method generally achieved better results within default computational costs and was more efficient, compared to other methods. Figure 23 shows that the KSE held a better convergence speed to obtain the ideal design results. Table 8 summarizes the results of all methods. At the optima points, the lift coefficient and pitch moment coefficient constraints were all met. The discrepancy in the computational cost of all optimization algorithms was not that large under the same number of objective function evaluations. It was shown that the optima by the KSE were the best of all global optimization methods, and the drag coefficient has been reduced by 14.4 counts compared to the baseline. The drag coefficient of the result obtained by the CiMPS method was similar to that of the MADS method, which was slightly better than that of the EGO method.Figure 22
The results of ten trials of each method.Figure 23
Mean convergence of best objective function values in 10 trials.Table 8
The best result comparison of different methods.
CLCD (counts)CMThe number of objective function evaluationCPU time (h)Baseline0.50210.8-0.182N/AKSE0.50196.4-0.169200+500106.30EGO0.50200.2-0.165200+500107.66CiMPS0.50198.8-0.166200+500107.53MADS0.50199.3-0.166200+500106.26Pressure distributions on the platforms of all optimized results are shown in Figures24–27, during which the baseline was shown on the left and the optimized results were on the right, respectively. For all the optimized wing results, the lift coefficient targets were met and the pitching moment constraints were satisfied. In the optimized result of the KSE method, the shock was largely reduced, which was achieved by fine-tuning the twist distribution and airfoil shapes. The optimized results of the CiMPS and MADS methods were similar to each other, the low-pressure regions extended, which was beneficial to drag reduction, but there still existed obvious shock across the middle of the wings. As for the optimized result of the EGO method, the shock wave on the inner wing has been eliminated, while on the outer wing, the shock extended to the wingtip.Figure 24
Pressure distributions of baseline and the KSE.Figure 25
Pressure distributions of baseline and the EGO.Figure 26
Pressure distributions of baseline and the CiMPS.Figure 27
Pressure distributions of baseline and the MADS.Pressure distributions on different cross-sections are compared in Figure28. At Y=0.085m, the thickness of the airfoil on the optimized results got thicker while airfoils on other sections get thinner, since the thicknesses were allowed to decrease to 25% of the original thickness and the wave drag was strongly influenced by decreased the thickness. But the volume was constrained to be not smaller than the baseline volume, so the optimizer decreased the thickness of the airfoils on the outer wing while increasing the thickness near the root section. Lyu et al. [63] observed similar trends in their results. Most of the optimized results eliminated the shock at Y=0.085m, except for the results obtained by the EGO method. At Y=1.025m, Y=2.642m, and Y=3.544m, the shock has been eliminated on the optimized wing of the KSE method, while for other results, the shocks were still existing. All results shared a similar trend at Y =2.115 m, and the double weak shock replaced the strong shock. And at Y=3.130m, the shocks moved forward without obvious weakness.Figure 28
Geometry and pressure distributions at a different section of the baseline model and optimized results.
(a)
Y=0.085m(b)
Y=1.025m(c)
Y=2.115m(d)
Y=2.642m(e)
Y=3.130m(f)
Y=3.544m


## 7. Conclusion

In this paper, a Kriging-based space exploration method (KSE) was proposed for multimodal and computationally expensive black-box problems. This method combined multiple subregion local search strategy with global search to balance and enhance the exploration and exploitation ability. By multiple local search strategy, the exploitations of local minima were enhanced, which was beneficial to promoting the exploration of the entire space and improving the optimization convergence as well as efficiency. During this process, an enhanced trust-region method (ETRM) was adopted to make efficient further exploration of the promising local minima. Hence, this method was expected to perform better than traditional global optimization methods.In the numerical experiments, the KSE was compared with other global optimization methods on 12 analytical functions. The results indicated that the KSE method was robust and it generally took fewer function evaluations to get the global optima. Then, it was demonstrated for aerodynamic shape optimizations of the benchmark RAE 2822 airfoil and CRM wing with high dimensionality. Generally speaking, it was difficult for the original EGO algorithm to obtain the ideal results as a result of the curse of dimensionality. The proposed KSE could overcome the limitation of the original EGO and be more effective and stable in all optimization cases compared to other alternatives.However, the current work still had some limitations. When dealing with high-dimensional problems, a very large amount of samples would be acquired to fit a high-quality surrogate model, and plenty of time would be cost to train the hyperparameter and construct the Kriging model, which made KSE inefficient for enormously high-dimensional problems. Besides. KSE might be still trapped in local minima when a large number of local minima made design space appear strong nonlinearity in local regions. Therefore, our future work would focus on training the hyperparameter with fewer samples, and improving the surrogate accuracy in nonlinear local regions, to make KSE more robust with complicated problems.



---

*Source: 4493349-2023-02-02.xml*