Experience-Based Evolutionary Algorithms for Expensive Optimization

In the past decade, experience-based evolutionary optimization has attracted much attention as it uses experiences gained from other optimization problems to improve the optimization efficiency of target problems, which mimics human capabilities of cognitive and knowledge generalization [15]. The optimization problems that provide experiences or knowledge are regarded as source tasks, while the target optimization problems are regarded as target tasks. To obtain useful experiences, the tasks that are related to target tasks are chosen as source tasks since they usually share domain-specific features with target tasks. Diverse experience-based evolutionary optimization methods have been proposed to use experiences gained from related tasks to tackle target tasks. They can be divided into two categories based on the direction of experience transformation.

In the first category, experiences are transformed mutually. Every considered optimization problem is a target task and also is one of the source tasks of other optimization problems. In other words, the roles of source task and target task are compatible. One representative tributary is EMTO that aims to solve multiple optimization tasks concurrently [16, 6, 17, 7, 8]. In EMTO, experiences are learned, updated, and spontaneously shared among target tasks through multi-task learning techniques. A variant of EMTO is multiforms optimization [15, 18, 19]. In multiforms optimization, multi-task learning methods are employed to learn experiences from distinct formulations of a single target task.

In the second category, experiences are transformed unidirectionally. The roles of source task and target task are not compatible, an optimization problem cannot serve as a source task and a target task simultaneously. One popular tributary is transfer optimization which employs transfer learning techniques to transform experiences from source tasks to target tasks [3, 4, 5, 20]. In transfer learning, experiences can be transformed from a single source task, multiple source tasks, or even source tasks from a different domain [21]. However, these transfer learning techniques pay more attention to experience transformation instead of experience learning. Despite diverse and complex situations of experience transformation have been studied [9, 10], the difficult of learning experiences from small (expensive) source tasks has not been well studied. Actually, a common scenario in transfer learning is that the source task(s) is/are large enough such that useful experiences can be obtained easily through solving source task(s) [21]. In contrast to transfer optimization, recently, some experience-based optimization algorithms attempted to use meta-learning methods to learn experiences from small source tasks, which are known as few-shot optimization (FSO)[22]. Since meta-learning only works for related tasks in the same domain, the situations of experience transformation are less complex than that of transfer learning. As a result, meta-learning pays more attention to experience learning instead of experience transformation. Domain-specific features are extracted as experiences and no related task needs to be solved.

Our work belongs to the FSO in the second category discussed above since the experiences are transformed unidirectionally. More importantly, our experiences are learned across many related expensive tasks, rather than gained through solving more or less source tasks. Existing studies on FSO only work for global optimization [22], leaving other optimization scenarios such as multi-objective optimization and constrained optimization still awaiting for investigation. In addition, in-depth ablation studies are lacking in the literature, making it unclear which factors affect the performance of FSO. Moreover, some studies use existing meta-learning models [23] as their surrogates. No further adaptations are made to these surrogates during optimization since they were not originally designed for optimization. Therefore, a novel meta-learning model for FSO is desirable. Our work fills the aforesaid gaps by proposing a novel meta-learning modeling method and a general experience-based SAEA framework. As a result, accurate surrogates and competitive optimization results can be achieved while the cost of surrogate initialization is only 1$d$ evaluations on the expensive target problem.

A meta deep kernel learning modeling method is developed to learn experiences in our SAEA framework. This subsection gives preliminaries about meta-learning and deep kernel learning. The former is the method of experience learning, the latter is the underlying structure of experience representation.

A diagram of our experience-based SAEA framework is illustrated in Fig. 1.

All modules about the evolutionary optimization of target task $T_{*}$ are included in a grey block. The modules beyond the grey block are associated with related tasks $T_{i}$ and experience learning, which are the main distinctions between our SAEA framework and existing SAEAs. The MDKL surrogate modeling method used in our SAEA framework consists of two procedures: meta-learning procedure and adaptation procedure. The former learns experiences from $T_{i}$, the latter uses experiences to adapt surrogates to fit $T_{*}$.

The framework of experience-based SAEA is depicted in Algorithm 1, it consists of the following major steps.

1. 1.

   Experience learning: Before evolutionary optimization starts, a meta-learning procedure is conducted to train task-independent parameters $\bm{\gamma}^{e}$ for MDKL surrogates (line 1). $\bm{\gamma}^{e}$ are trained on $N_{m}$ datasets $\{D_{m1},\dots,D_{mN_{m}}\}$ which are collected from $N$ related tasks $\{T_{1},\dots,T_{N}\}$. $\bm{\gamma}^{e}$ are experiences that represent the domain-specific features of related tasks.

2. 2.

   Initialize surrogates with experiences: Evolutionary optimization starts when a target optimization task $T_{*}$ is given. An initial dataset $S_{*}$ is sampled (line 2) to adapt task-specific parameters $\bm{\gamma}^{*}$ on the basis of experiences $\bm{\gamma}^{e}$. After that, MDKL surrogates are updated (line 3).

3. 3.

   Reproduction: MDKL surrogates $h(\bm{\gamma}^{*})$ are combined with a SAEA optimizer $Opt$ to search for optimal solution(s) $\textbf{x}^{*}$ on $h(\bm{\gamma}^{*})$ (line 6). This is implemented by replacing the original (regression-based) surrogates in a SAEA with $h(\bm{\gamma}^{*})$.

4. 4.

   Update archive and surrogates: New optimal solution(s) $\textbf{x}^{*}$ is evaluated on target task $T_{*}$ (line 7). The evaluated solutions will be added to dataset $S_{*}$ (line 8) which serves as an archive. Further surrogate adaptation is triggered, surrogates $h(\bm{\gamma}^{*})$ are updated (line 9).

5. 5.

   Stop criterion: Once the evaluation budget has run out, the evolutionary optimization will be terminated and the optimal solutions in dataset $S_{*}$ will be outputted. Otherwise, the algorithm goes back to step 3.

In the following subsections, we first present the details of our MDKL surrogate modeling method, including how to learn experiences through meta-learning and adapt it to a specific target task. Then we explain the surrogate update strategy in our experience-based SAEA framework. Finally, we discuss the usage of MDKL surrogates and the compatibility of our SAEA framework with existing SAEAs.

In MDKL, the domain-specific features of related tasks are used as experiences, which are represented by the task-independent parameters $\bm{\gamma}^{e}$ learned across related tasks. To make MDKL more capable of expressing complex domain-specific features, the base kernel $k(\textbf{x}^{i},\textbf{x}^{j}|\ \bm{\theta})$ in GP is combined with a neural network $\phi(\textbf{w},\textbf{b})$ to construct a deep kernel (see Eq.(1)).

The main novelties of our MDKL surrogate modeling method can be summarized as follows.

• •

  A simple and efficient meta-learning structure for experience learning. Our method learns only one common neural network for all related tasks, such a neural network works as a component of the shared deep kernel. In comparison, [29, 28] generate separate deep kernels for each related task and train multiple neural networks to encode and decode task features, which makes their model complexity grow with the number of related tasks.

• •

  The explicit task-specific adaptation for the deep kernel, which is implemented by cumulating task-specific increments on the basis of the learned experiences.

The modeling of a MDKL model consists of two procedures: meta-learning procedure and adaptation procedure. To make a clear illustration, we introduce frameworks of two procedures and then explain them in detail.

Meta-learning procedure: Learning experiences
Our MDKL model uses the kernel in [30] as its base kernel:

Therefore, the deep kernel will be:

where $\bm{\gamma}=\{\textbf{w},\textbf{b},\bm{\theta},\textbf{p}\}$ is a set of deep kernel parameters. Details about alternative base kernels are available in [25].

The aim of meta-learning procedure is to learn experiences $\bm{\gamma}^{e}$ from related tasks $\{T_{1},\dots,T_{N}\}$, including neural network parameters $\textbf{w},\textbf{b}$, and task-independent base kernel parameters $\bm{\theta}^{e},\textbf{p}^{e}$. The pseudo-code of meta-learning procedure is given in Algorithm 2.

Ideally, the experiences $\bm{\gamma}^{e}$ are learned from plenty of ($N_{m}$) small datasets $D_{m}$ collected from different related tasks. However, in practice, the number of available related tasks $N$ may be much smaller than $N_{m}$. Hence, the meta-learning is conducted gradually over $U$ update iterations (line 2). During each update iteration, a small batch of related tasks contribute $B$ small datasets $\{D_{m1},\dots,D_{mB}\}$ for meta-learning purpose (line 4 and line 6). Note that if $N<N_{m}$, a related task $T_{i}$ can be used multiple times in the meta-learning procedure.

For a given dataset $D_{mi}$, we denote $\bm{\theta}^{i}=\bm{\theta}^{e}+\Delta\bm{\theta}^{i}$ and $\textbf{p}^{i}=\textbf{p}^{e}+\Delta\textbf{p}^{i}$ as the task-specific kernel parameters, where $\Delta\bm{\theta}^{i},\Delta\textbf{p}^{i}$ are the distance we need to move from the task-independent parameters to the task-specific parameters (line 8). The loss function $L$ of MDKL is the likelihood function defined as follows [30]:

where $|\textbf{R}|$ is the determinant of the correlation matrix R, each element in the matrix is computed through Eq.(3). y is the fitness vector of $D_{mi}$. And $\mu$ and $\sigma^{2}$ are the mean and the variance of the prior distribution, respectively. Experiences $\bm{\gamma}^{e}=\{\textbf{w},\textbf{b},\bm{\theta}^{e},\textbf{p}^{e}\}$ is updated by gradient descent (line 9), take $\bm{\theta}^{e}$ as an example:

After $U$ iterations, $\bm{\gamma}^{e}$ has been trained sufficiently by $N_{m}$ small datasets $D_{m}$ and will be used in target task $T_{*}$ later.

Adaptation procedure: Using experiences
The meta-learning of experiences $\bm{\gamma}^{e}$ enables MDKL to handle a family of related tasks in general. To approximate a specific task $T_{*}$ well, surrogate $h(\bm{\gamma}^{e})$ needs to adapt task-specific increments $\Delta\bm{\theta}^{*}$ and $\Delta\textbf{p}^{*}$ in the way described in Algorithm 3.

There are three major differences between the meta-learning procedure and the adaptation procedure:

• •

  First, the dataset $S_{*}$ for adaptations is sampled from target task $T_{*}$. In comparison, in the meta-learning procedure, the training datasets $\{D_{m1},\dots,D_{mN_{m}}\}$ are sampled from $N$ different related tasks.

• •

  Second, the parameters to be updated are task-specific increments $\Delta\bm{\theta}^{*}$ and $\Delta\textbf{p}^{*}$, not task-independent parameters $\bm{\theta}^{e}$ and $\textbf{p}^{e}$. The gradient descent in Eq.(5) is replaced by the follows (line 7).

  $$\Delta\bm{\theta}^{*}\leftarrow\Delta\bm{\theta}^{*}-\beta\bigtriangledown_{\Delta\bm{\theta}^{*}}L(S_{*},h(\bm{\gamma}^{*})).$$

  (6)

• •

  Third, task-specific increments $\Delta\bm{\theta}^{*}$ and $\Delta\textbf{p}^{*}$ are initialized only when it is the first time to adapt task-specific parameters (lines 1-5). From the perspective of tuning parameters, we can say task-independent base kernel parameters $\bm{\theta}^{e}$ and $\textbf{p}^{e}$ are the initialization points for further adaptations. In other words, the learning of a new task starts on the basis of past experiences.

A diagram of the deep kernel implemented in our MDKL model is illustrated in Fig. 2.

The adaptation procedure has explained how experiences are used to adapt a MDKL surrogate with a dataset $S_{*}$ from the target task $T_{*}$. In this subsection, we describe the update strategy in our experience-based SAEA framework. To properly integrate experiences and data from $T_{*}$, our update strategy is designed to determine whether a MDKL surrogate should be adapted in the current iteration or not, ensuring an optimal update frequency of surrogates.

As illustrated in Algorithm 4, the surrogate update starts when a new optimal solution(s) has been evaluated on expensive functions and an updated archive $S_{*}$ is available.

For a given surrogate $h(\bm{\gamma}^{*})$, its mean squared error (MSE) on $S_{*}$ is selected as the update criterion: If the MSE after an adaptation $e_{1}$ (line 3) is larger than the MSE without an adaptation $e_{0}$ (line 1), then the surrogate will roll back to the status before the adaptation. This indicates the surrogate update has been refused and $h(\bm{\gamma}^{*})$ will not be adapted in the current iteration. Otherwise, the adapted surrogate will be chosen (line 5). Note that no matter whether surrogate adaptations are accepted or refused, the resulting surrogates will be treated as updated surrogates, which are employed to assist the SAEA optimizer in the next iteration.

Our experience-based SAEA framework is compatible with regression-based SAEAs since the original surrogates in these SAEAs can be replaced by our MDKL surrogates directly. Due to the nature of GP, when predicting the fitness of a query solution $\textbf{x}^{*}$, a MDKL surrogate produces a predictive Gaussian distribution $\mathcal{N}$$\sim$$(\hat{y}(\textbf{x}^{*}),\hat{s}^{2}(\textbf{x}^{*}))$ , the predicted mean $\hat{y}(\textbf{x}^{*})$ and covariance $\hat{s}^{2}(\textbf{x}^{*})$ are specified as [30]:

where r is a correlation vector consisting of covariances between $\textbf{x}^{*}$ and $S_{*}$, other variables are explained in Eq.(4).

Classification-based SAEAs are not compatible with our SAEA framework. The classification surrogates in these SAEAs are employed to learn the relation between pairs of solutions, or the relation between solutions and a set of reference solutions. The class labels used for surrogate training can be fluctuating during the optimization and thus hard to be learned over related tasks. Similarly, in ordinal-regression-based SAEAs, the ordinal relation values to be learned are not as stable as the fitness of expensive functions. So ordinal-regression-based SAEAs are also not compatible with our SAEA framework. In this paper, we focus on experiences-based optimization for regression-based SAEAs, while other SAEA categories are left to be discussed in future work.

The evaluation of the effectiveness of learning experiences aims at demonstrating that our MDKL model is able to learn experiences from related tasks and it outperforms other meta-learning models. For this reason, the experiment is designed to answer the following questions:

• •

  Given a small dataset $S_{*}$ from target task $T_{*}$, can MDKL learn experiences from related tasks and generate a model with the smallest MSE?

• •

  If yes, which components of MDKL contribute to the effectiveness of learning experiences? Meta-learning or/and deep kernel learning? If not, why not?

To answer the two questions above, we consider two experiments to evaluate the effectiveness of learning experiences: amplitude prediction for unknown periodic sinusoid functions, and fuel consumption prediction for a gasoline motor engine. The former is a few-shot regression problem that motivates many meta-learning studies [31, 32, 28, 23], while the latter is a real-world regression problem [33]. The results of the sinusoid function regression experiment are reported in the supplementary material.In this subsection, we focus on a Brake Special Fuel Consumption (BSFC) regression task for a gasoline motor engine [33], where BSFC is evaluated on the gasoline engine simulation (denoted by $T_{*}$) provided by Ford Motor Company.

Experimental setups:
The related tasks $T_{i}$ used in our experiment are $N=100$ gasoline engine models. These engine models have different behaviors when compared with $T_{*}$, but they share the basic features of gasoline engines. All related tasks and the target task have the same six decision variables. Each related task $T_{i}$ provides only 60 solutions, forming a dataset $D_{i}$. The size of datasets used for meta-learning $|D_{m}|$ is set to 40. Six tests are conducted where $|S_{*}|=\{$2, 3, 5, 10, 20, 40$\}$ data points are sampled from the real engine simulation $T_{*}$. The MSE is chosen as an indicator of modeling accuracy, which is measured using a dataset consisting of 12500 data points that are sampled uniformly from the engine decision space.

Comparison methods:
In this experiment, three families of modeling methods are compared with our MDKL model:

• •

  Meta-learning methods that are proposed for regression tasks: MAML [31], ALPaCA [32], and DKT [23]. The configurations of MAML, ALPaCA, DKT are the same as suggested in the original literature.

• •

  Non-meta-learning method that is widely used for regression tasks: GP model. We choose GP as a baseline since it is effective and more relevant to MDKL than other non-meta-learning modeling methods. We set the range of base kernel parameters in the GP model as $\theta\in[10^{-5},10]$ and $p\in[1,2]$.

• •

  MDKL related methods that are designed to investigate which components of MDKL contribute to the modeling performance: GP_Adam, DKL, and MDKL_NN. GP_Adam is a GP model fitted by Adam optimizer. The combination of GP_Adam and a neural network results in a kind of DKL algorithm. MDKL_NN is a meta-learning version of DKL, but it learns only neural network parameters through meta-learning and has no task-independent base kernel parameters.

Results and analysis:
The statistical test results of the MSE values achieved by comparison algorithms in BSFC regression experiments are summarized in Table II. Each row lists the results obtained when the same number of fitness evaluations $|S_{*}|$ are used to train models. The results of Wilcoxon rank sum test between MDKL and other compared algorithms are listed in the last row.

It can be observed that MDKL and MDKL_NN outperform other comparison modeling methods since they have achieved the smallest MSE on all tests. Consistent observations can also be made from the results of the sinusoid function regression experiments (presented in the supplementary material), MDKL has also achieved the best performance.

Additional Wilcoxon rank sum tests have been conducted between MDKL related algorithms to answer our second question (results are not reported in Table II). The statistical test results between DKL and GP_Adam are 1/5/0, indicating that the neural network in DKL makes some contributions to the performance of MDKL. The statistical test results between MDKL_NN and DKL are 6/0/0, demonstrating that the meta-learning of neural network parameters constructs a useful deep kernel and contributes to the improvement of modeling accuracy. However, there is no significant difference between the performance of MDKL and that of MDKL_NN, the meta-learning on base kernel parameters does not play a critical role on this engine problem. In comparison, the meta-learning on base kernel parameters is effective in sinusoid function regression experiments (see the supplementary material). Besides, the statistical test results between MDKL_NN and MAML are 4/2/0. Considering that MAML is a neural network regressor learned through meta-learning, we can conclude that GP is an essential component of our MDKL. In summary, all components in MDKL are necessary, and they all contribute to the effectiveness of learning experiences.

The comparison experiments on the gasoline motor engine and sinusoid functions have demonstrated the effectiveness of our MDKL modeling method in the learning of experiences. Given a small dataset of the target task, the model learned through MDKL method has the smallest MSE among all comparison models. Besides, the investigation between MDKL and its variants shows that all components in MDKL have made their contributions to the effectiveness of learning experiences. However, similar to other meta-learning studies [31, 32], we have not defined the similarity between tasks. In other words, the boundary between related tasks and unrelated tasks has not been defined. This should be a topic of further study on meta-learning. Besides, the relationship between task similarity and modeling performance has not been investigated. Instead, we study the relationship between task similarity and SAEA optimization performance in Section IV-C, since our main focus is the surrogate-assisted evolutionary optimization.

So far we have shown the effectiveness of experience learning method. In the following subsections, we aim at demonstrating the effectiveness of our experience-based SAEA framework. The experiment in this subsection is designed to answer the question below:

• •

  With the experiences learned from related tasks, can our SAEA framework helps a SAEA to save 9$d$ solutions without a loss of optimization performance?

The computational study is conducted on DTLZ testing functions [34]. All DTLZ functions have $d=10$ decision variables and 3 objectives, as the setups that have been widely used in [35, 36]. The details of generating DTLZ variants (related tasks) are provided in the supplementary material.

Comparison algorithms:
As explained in Section III-D, our experience-based SAEA framework is compatible with regression-based SAEAs. Hence, we select MOEA/D-EGO [37] as an example and replace its GP surrogates by our MDKL surrogates. The resulting algorithm is denoted as MOEA/D-EGO(EB). Note that it is not necessary to specially select a newly proposed regression-based SAEA as our example, our main objective is to save evaluations with experiences and observe if there is any damage to the optimization performance caused by the saving of evaluations. Therefore, it does not make any difference which regression-based SAEAs we choose as our example. In addition, to demonstrate the improvement of optimization performance caused by using experiences on DTLZ functions is significant, several state-of-the-art SAEAs are also compared as baselines, including ParEGO [38], K-RVEA [39], CSEA [35], OREA [40], and KTA2 [36]. Among these SAEAs, ParEGO, K-RVEA, and KTA2 use regression-based surrogates, CSEA uses a classification-based surrogate, and OREA employs an ordinal-regression-based surrogate.

We implemented the experience-based SAEA framework, MOEA/D-EGO, ParEGO, and OREA, while the code of K-RVEA, CSEA, and KTA2 is available on PlatEMO [41], an open source Matlab platform for evolutionary multi-objective optimization. To make a fair comparison, all comparison algorithms share the same initial dataset $S_{*}$ in an independent run. We also set $\bm{\theta}\in[10^{-5},100]^{d}$ and $\textbf{p}=\textbf{2}$ for all GP surrogates as suggested in [36], these GP surrogates are implemented through DACE [27]. Other configurations are the same as suggested in their original literature.

Experimental setups:
The parameter setups for this multi-objective optimization experiment are listed in Table III.

In the meta-learning procedure, we assume that plenty of DTLZ variants are available, thus $N=N_{m}=20000$, each DTLZ variant $T_{i}$ provides $|D_{i}|=|D_{m}|=20$ samples for learning experiences. During the optimization process, an initial dataset $S_{*}$ is sampled using Latin-Hypervolume Sampling (LHS) method [42], then extra evaluations are conducted until the evaluation budget has run out. Please note that our purpose is to use related tasks to save 9$d$ evaluations without a loss of SAEA optimization performance. Hence, the total evaluation budget for MOEA/D-EGO(EB) and comparison algorithms is different.

Since the testing functions have 3 objectives, we employ inverted generational distance plus (IGD+) [43] as our performance indicator, where smaller IGD+ values indicate better optimization results. 5000 reference points are generated for computing IGD+ values, as suggested in [35].

Results and analysis:
The statistical test results are reported in Tables IV.

It can be seen from Table IV that, although 90 fewer evaluations are used in surrogate initialization, MOEA/D-EGO(EB) can still achieve competitive or even smaller IGD+ values than MOEA/D-EGO on all DTLZ functions except for DTLZ7. Fig. LABEL:supp-fig:_DTLZ150 (in the supplementary material) also shows that the IGD+ values obtained by MOEA/D-EGO(EB) drop rapidly, especially during the first few evaluations, implying the experience learned from DTLZ variants are effective. Therefore, in most situations, our experience-based SAEA framework is able to assist MOEA/D-EGO in reaching competitive or even better optimization results, with the number of evaluations used for surrogate initialization reduced from 10$d$ to only 1$d$.

MOEA/D-EGO(EB) is less effective on DTLZ7 than on other DTLZ functions, which might be attributed to the discontinuity of the Pareto Front on DTLZ7. Note that MOEA/D-EGO(EB) learns experience from small datasets such as $D_{m}$ and $S_{*}$. The solutions in these small datasets are sampled randomly, hence, the probability of having optimal solutions being sampled is small. However, it is difficult to learn the discontinuity of the Pareto Front from the sampled non-optimal solutions. As a result, the knowledge of ’there are four discrete optimal regions’ cannot be learned from such small datasets ($|D_{m}|=20$) collected from related tasks.

The experience learned from related tasks makes MOEA/D-EGO more competitive when compared to other SAEAs. The use of MDKL surrogates results in significantly smaller IGD+ values on DTLZ1, DTLZ2, DTLZ3, and DTLZ5 than before. As a result, MOEA/D-EGO(EB) achieves the smallest IGD+ values on DTLZ2 and DTLZ3, and its optimization results on DTLZ1 and DTLZ5 are much closer to the best optimization results (e.g. results obtained by ParEGO and OREA) than MOEA/D-EGO. Although MOEA/D-EGO(EB) does not achieve the smallest IGD+ values on all DTLZ functions, it should be noted that MOEA/D-EGO(EB) is still the best algorithm among comparison SAEAs due to its overall performance. Table IV shows that no comparison SAEA outperforms MOEA/D-EGO(EB) on three DTLZ functions, but MOEA/D-EGO(EB) outperforms all comparison SAEAs on at least three DTLZ functions. Furthermore, the IGD+ values of MOEA/D-EGO(EB) are achieved with an evaluation budget of 60, while the IGD+ values of other SAEAs are reached with a cost of 150 evaluations (see Table III).

More performance comparison experiments:
We also compared our MOEA/D-EGO(EB) with the best two comparison algorithms in Table IV, ParEGO and OREA, using the same evaluation budget. The results reported in Table SLABEL:supp-tab:_DTLZadditional (see the supplementary material) show that our experience-based SAEA framework is more effective than comparison algorithms when the same evaluation budget is used. Besides, the performance of our SAEA framework in the context of extremely expensive optimization has been investigated in the supplementary material (see Table SLABEL:supp-tab:_DTLZ90).

The question raised at the beginning of this subsection can be answered by the results discussed so far. Due to the integration of experiences learned from related tasks (DTLZ variants), although the evaluation cost of surrogates initialization has been reduced from 10$d$ to 1$d$, our experience-based SAEA framework is still capable of assisting regression-based SAEAs to achieve competitive or even better optimization results in most situations.

In real-world applications, it might be unrealistic to assume that some related tasks are very similar to the target task. A more common situation is that all related tasks have limited similarity to the target task. To investigate the relationship between task similarity and SAEA optimization performance, we also tested the performance in an ‘out-of-range’ situation, where the original DTLZ is excluded from the range of DTLZ variants during the MDKL meta-learning procedure. As a result, only the DTLZ variants that are quite different from the original DTLZ function can be used to learn experiences. The ‘out-of-range’ situation eliminates the probability that MDKL surrogates benefit greatly from the DTLZ variants that are very similar to the original DTLZ function. Detailed definitions of the related tasks used in the ‘out-of-range’ situation are given in the supplementary material. Apart from the related tasks used, the remaining experimental setups are the same as the setups described in Section IV-B. For the sake of convenience, we denote the situation we tested in Section IV-B as ‘in-range’ below.

The statistical test results reported in Table V

show that the ‘out-of-range’ situation achieves competitive IGD+ values to the ‘in-range’ situation on all 7 test instances. This suggests that related tasks that are very similar to the target task have a limited impact on the optimization performance of our experience-based SAEA framework. Useful experiences can be learned from related tasks that are not very similar to the target task. Crucially, when comparing the performance of the ‘out-of-range’ situation and that of MOEA/D-EGO, we can still observe competitive or improved optimization results on 6 DTLZ functions (see Table V, the row titled by ’vs MOEA/D-EGO’, or Fig. LABEL:supp-fig:_DTLZ150 in the supplementary material). Moreover, it can be seen from the last row of Table V that the ‘out-of-range’ situation achieves better/competitive/worse IGD+ values than all compared SAEAs on 27/7/8 test instances. In comparison, the corresponding statistical test results for the ‘in-range’ situation are 26/9/7. The difference between these statistical test results is not significant.

A study on the ‘out-of-range’ situation in the context of extremely expensive multi-objective optimization is presented in Section LABEL:supp-sec:_exp-out90 of the supplementary material. Consistent results can be observed from Table SLABEL:supp-tab:_DTLZ40-out and Fig. LABEL:supp-fig:_DTLZ90.

Consequently, related tasks that are very similar to the target task are not essential to the optimization performance of our experience-based SAEA framework. In the ‘out-of-range’ situation, our MOEA/D-EGO(EB) can still achieve competitive or better optimization results than MOEA/D-EGO while using only 1$d$ samples for surrogate initialization.

We also investigated the performance of our experience-based SAEA framework when different sizes of datasets $|D_{m}|$ are used in the meta-learning procedure. The experimental setups are the same as the setups of MOEA/D-EGO(EB) in Section IV-B except for $|D_{m}|$.

It is evident from Table VI that when each DTLZ variant provides $|D_{m}|$=60 samples for the meta-learning of MDKL surrogates, the performance of both MOEA/D-EGO(EB)s are improved on 2 or 3 DTLZ functions. Particularly, a significant improvement can be observed from the optimization results of DTLZ7. As we discussed in Section IV-B, the poor performance of our experience-based optimization on DTLZ7 is caused by the small $|D_{m}|$. Optimal solutions have few chances to be included in a small $D_{m}$, which makes $D_{m}$ fails to provide experiences about the discontinuity of optimal regions. In comparison, the experience of ’optimal regions’ can be learned from large datasets $D_{m}$ and thus the optimization results are improved significantly.

In conclusion, for our experience-based SAEA framework, a large $|D_{m}|$ for meta-learning procedure indicates more useful experiences can be learned from related tasks, which further improves the performance of experience-based optimization. Therefore, when applying our experience-based SAEA framework to real-world optimization problems, it is preferable to collect more data from related tasks for experience learning.

The experiments on multi-objective benchmark testing functions have investigated the performance of our SAEA framework in depth. In this subsection, we use our proposed framework to solve a real-world gasoline motor engine calibration problem, which is an expensive constrained single-objective optimization problem. This experiment covers the optimization scenarios of single-objective optimization, constrained optimization, and real-world applications. It serves as an example to demonstrate the generality and broad applicability of our proposed framework.

The calibration problem has 6 adjustable engine parameters, namely the throttle angle, waste gate orifice, ignition timing, valve timings, state of injection, and air-fuel-ratio. The calibration aims at minimizing the BSFC while satisfying 4 constraints in terms of temperature, pressure, CA50, and load simultaneously [33].

Comparison algorithms:
Since the comparison algorithms in the DTLZ optimization experiments are not designed for handling constrained single-objective optimization, our comparison is conducted with two state-of-the-art constrained optimization algorithms used in industry [33]: a variant of EGO designed to handle constrained optimization problems (denoted by cons_EGO), and a GA customized for this calibration problem (denoted by adaptiveGA). The settings of comparison algorithms are the same as suggested in [33]. In this experiment, we apply our SAEA framework to cons_EGO and investigate its optimization performance. The GP surrogates in cons_EGO are replaced by our MDKL surrogates to conduct the comparison, and the resulting algorithm is denoted as cons_EGO(EB).

Experimental setups:
The setup of related tasks ($N,D_{i}$) is the same as described in Section IV-A. In the meta-learning procedure, both the support set and the query set contain 6 data points, thus $|D_{m}|=12$. The total evaluation budget for all algorithms is set to 60. For adaptiveGA, all evaluations are used in the optimization process as it is not a SAEA. For cons_EGO, 40 samples are used to initialize surrogates and 20 extra evaluations are used in the optimization process. For cons_EGO(EB), only 6 samples are used to initialize MDKL surrogates, and the remaining evaluations are used for further optimization.

Optimization results and analysis:
The average normalized BSFC results and the average number of feasible solutions found over the number of evaluations used are plotted in Figs. 3a and 3c, respectively. The statistical results of three comparison algorithms are illustrated in Figs. 3b and 3d.

From Fig. 3a, it can be observed that the minimal BSFC obtained by cons_EGO(EB) decreases drastically in the first few evaluations, implying that the experiences learned from related tasks are effective. In comparison, the minimal BSFC obtained by adaptiveGA and cons_EGO drops in a relatively slower rate, even though cons_EGO has used 34 more samples to initialize its surrogates. The star marker denotes the point at which cons_EGO(EB) has evaluated 20 samples after surrogate initialization. It is worth noting that when 20 samples have been evaluated in the optimization, cons_EGO(EB) achieves a smaller BSFC value than cons_EGO. After the star marker, the decrease of BSFC becomes slower as cons_EGO(EB) has reached the optimal region. Therefore, further improvement in the normalized BSFC value is not significant and thus hard to observe. The advantages of our experience-based SAEA framework can also be observed in constraint handling. In Figs. 3c and 3d, cons_EGO(EB) finds more feasible solutions than two comparison algorithms. These results indicate that our SAEA framework improves the performance of cons_EGO on both objective function and constraint functions. Meanwhile, only 1$d$ evaluations are used to initialize surrogates.

Discussion on runtime:
It should be noted that real engine performance evaluations on engine facilities are very costly in terms of both time and financial budget [11]. Since a single real engine performance evaluation can cost several hours [44, 11], the time cost of the meta-learning procedure is negligible as it takes only a few minutes. Savings from reduced real engine performance evaluations on engine facilities and the reduced development cycle due to our SAEA framework could amount to millions of dollars [11]. Our SAEA framework is an effective and efficient method to solve this real-world calibration problem.