Variable surrogate model-based particle swarm optimization for high-dimensional expensive problems

The canonical PSO, developed by Eberhart and Kennedy in 1995, is a population- or swarm-based intelligent optimisation algorithm inspired by the social behaviours of populations of organisms such as birds (flocking) or fish (schooling) [37]. Eq. (1) and Eq. (2) describe the evolution of \(x_j\) (the position of the jth individual at generation \((t+1)\)) along the dth dimension in the canonical PSO:The feature distinguishing the canonical PSO from other EAs such as the genetic algorithm (GA) or differential evolution (DE) is that it converges rapidly but easily falls into local optima. To prevent premature convergence, a variety of modified PSOs have been proposed, including the comprehensive learning PSO [38], distance-based locally informed PSO [39], social learning PSO [40], and competitive swarm optimiser (CSO) [41]. Based on the effective performance of social learning particle swarm optimization (SLPSO), we propose a simplified SLPSO to generate candidate solutions whose primary structure is similar to the SLPSO algorithm proposed by Cheng and Jin. In this simplified SLPSO, individual \(x_j\) are updated using the following formulas:where \(1\leqslant j<N\), N is the population size, \(1\leqslant d\leqslant D\), and D is the dimension of the search space. In each generation, the population is sorted according to fitness value from bad to good, with \(x_1\) and \(x_N\) representing the worst and best solutions, respectively, at the current generation. \(x_k\) is a randomly chosen demonstrator for \(x_j\), \(j<k\leqslant N\), and \(x_{k}^{d}\left( t \right) \) represents the dth element of \(x_k\). We note that a demonstrator should be chosen for each element of \(x_j\). \(P_{j}^{L}\) is the learning probability, which is inversely proportional to the fitness of \(x_j\), \(p_j\left( t \right) \) is a randomly generated probability for \(x_j\), \(r_1\), \(r_2\), and \(r_3\) are random numbers in the range \(\left[ 0,1 \right] \), and \(\varepsilon \) is the social influence factor that controls the influence of \(\bar{x}_d\left( t \right) \). In Eq. (4), \(\bar{x}_d\left( t \right) \) is the mean position along the dth dimension of the population at generation t. If a uniform sampling method such as Latin hypercube sampling (LHS) is used in the initialisation process, \(\bar{x}_d\left( t \right) \) can be quite close to the \(1\times D\) zero vector \(o=\left[ 0,\ldots 0 \right] \). The function of the global optimum at the zero vector o can easily lead the population toward a promising region, and to avoid this coincidence, we set the parameter \(r_3\) to zero to remove the effect of \({{\bar{x}}_{d}}(t)\). This simplifies Eq. (4) toIn this study, we generated new swarms using Eq. (3) and Eq. (5), and in the following sections, the variant SLPSO is referred to as ‘PSO’ for brevity.

The functionality of an RBF network as a type of neural network was described in detail in [42] and can be represented by the following form:where \(x\in \mathbb {R}^D\) is an input vector, \(\phi \) is the basic function of the RBF network, \(\Vert \cdot \Vert \) is the 2-norm (also called the Euclidean norm), \(\omega _i\) is the weight vector, M represents both the number of input units in the RBF input layer and the number of samples for building the RBF model. Because the basic function \(\omega _i\) is one of the key factors affecting the performance of the model, many forms of \(\omega _i\) have been developed, including multi-quadric, thin plate spline, Gaussian, and cubic forms. A comparison of different choices of \(\omega _i\) in [43] revealed that the thin plate spline and linear and cubic RBFs theoretically perform better than either the multi-quadric or Gaussian RBF. Additionally, numerical investigation results have demonstrated that the cubic RBF can improve the performance of the thin plate spline and multi-quadric RBFs [44]. Furthermore, cubic RBF-assisted EAs have been successfully used in local function approximation. Based on these previous studies, the proposed method employs cubic basic function to construct RBF network, which is a common machine learning technique for fitness approximation [2, 8]. The basic function of the cubic RBF employed in this study is \(\phi \left( \Vert x-x_i \Vert \right) =\left( \Vert x-x_i \Vert \right) ^3\).

The main framework shown in Fig. 1 presents the overall algorithm for VSMPSO. The solid black arrow lines represent the flow direction of the algorithm, and the green dot arrow dotted line to mark the data flow direction. At the beginning of VSMPSO, the initial individuals are generated, which are all evaluated and then taken into the database DB. In each generation, the variable model management strategy was proposed to decide how to construct the surrogate model for fitness estimation and select promising solutions for fitness evaluation. In the variable model management strategy (Part I) of Fig. 1, the simple random sampling method is used to select samples from the database DB for building an RBF model. Subsequently, the RBF model will be carried out to find the most promising point in the global search space. This is followed by the knowledge transferred from the RBF model to the current population. Then, in the variable model management strategy (Part II) of Fig. 1, the infill criterion used in VSMPSO considers potential optimum points to be evaluated and put into DB.

The details for the main components in VSMPSO have been explained in Algorithm 1. The optimizer used in VSMPSO is a variant of that used in SLPSO. Steps 2–4 of Algorithm 1 describe the steps for generating the initial population (called P(1)) by Latin Hypercube Sampling (LHS) and then creating the database DB by all the initial individuals in P(1) with their real fitness values. As shown in steps 6–11, the main optimization loop contains two main components of the proposed algorithm that will be described in detail in Algorithms 2 and 3. In steps 8 and 10, the variable model management strategy is proposed to design model construction and the infill criterion, which will be described in “Variable model management strategy” section. In step 9, the knowledge from the RBF model will be transferred to P(t) (the population in generation t). Finally, the program outputs the most satisfying solution with its real fitness value and end. Overall speaking, VSMPSO contains two-layer loops. The outer loop uses the variant SLPSO as the optimizer in Algorithm 1, and the inner loop uses the canonical PSO as the optimizer in Algorithm 3. In Algorithm 3, the current RBF model is used as the objective function to drive the canonical PSO iterations, and then, the global best solution found by canonical PSO is transferred to variant SLPSO. In the following subsections, we will detail the two main components of the proposed algorithm, i.e., the variable model management strategy and the knowledge transfer from model to population.

The key issues influencing the performance of surrogates are mainly model selection and model management. First, for model selection, according to the previous work, on high-dimensional problems, constructing GP models becomes time-consuming, but RBF has been proven to perform better with small samples than other common surrogate models [45], so we determine RBF as a surrogate model. Additionally, for model management, as mentioned in the “Introduction” section, due to the lack of samples on high-dimensional expensive problems, it is not easy to construct a single surrogate model with high accuracy. Since the blessing of uncertainty and the multiple local optima of original expensive problems, an accurate surrogate model is not always necessarily in optimization. So in this work, unlike the previous work focusing on improving the accuracy of models, only one global surrogate model is trained. Furthermore, due to different samples that may construct models toward different promising areas, a global model management strategy inspired by simple random sampling is proposed to enhance the diversity of the single model between each generation and thus avoid persistent misleading in a wrong direction throughout the whole optimization process.

As observed from the pseudo-code of Algorithm 1, the RBF model is updated during each generation, in step 2 of Algorithm 2, \(\lambda =\left[ M\times 80\% \right] \) samples are selected using simple random sampling, with the number of selected samples \(\lambda \) accounting for 80% of the total sample size based on a common empirical value used in K-fold cross-validation [46] with \(K=5\). Furthermore, the effectiveness of this strategy and sample size will be further verified in “Effects of variable model management strategy” and “Parameter sensitivity analysis”. After estimating the fitness value of P(t) by the current RBF model in step 4, the current population P(t) is sorted according to the estimated fitness value from bad to good in step 5, with \(x_1\) and \(x_N\) representing the worst solution PGworst and the best solution PGbest, respectively. As shown in steps 6–7, two potential optimum points are considered to be evaluated by the original expensive function. The first is PGbest, (the global optimum individual of the current population), and the second is MGbest, (the most promising point of the current surrogate model, obtained from Algorithm 3).

As mentioned in Algorithm 2, in each iteration of the optimization loop, a simple random sampling method selects different samples to construct the RBF model, and those RBF models may contribute toward different promising areas in different generations. So in Step 3 of Algorithm 3, for further data mining of the RBF model, the RBF model is considered as an objective function, which is defined as follows:where \(\textbf{x}\in {{\mathbb {R}}^{D}}\) is the feasible solution set, denotes the same search space as original expensive problem, \(F_{\textrm{RBF}}\left( \textbf{x} \right) \) is the objective function, \({{\textbf{x}}_{l}}\) and \({{\textbf{x}}_{u}}\) are the lower and upper bounds of the decision variables. In steps 4–9, a canonical PSO is employed to find the global optimum of the current RBF model. In step 6, the canonical PSO updates individuals using Eq. (1) and (2). In step 8, Pbest (the personal best of the particle) and Gbest (the global best of the swarm) are updated in each generation. After the iteration is completed, in step 11, Gbest, the final best solution of the RBF model obtained through the canonical PSO, is assigned MGbest, which is considered the most promising point of the RBF model. In the following steps, by substituting MGbest for PGworst in \(P\left( t \right) \), the knowledge transferred from the RBF model to the population is expected to be able to enhance the search performance of VSMPSO by reducing the likelihood of getting stuck in a local optimum. Furthermore, the effectiveness of the knowledge transfer strategy is further verified in “Effects of variable model management strategy” section by comparing VSMPSO with SMPSO.

All experiments are implemented on a high computing capability server with an Intel XEON E5-2620v4 processor with 64GB in RAM. Each algorithm was run 30 times in Matlab 2020B to eliminate the effect of statistical variation. We applied Friedman’s test to determine if there are any significant differences in the best fitness values obtained by the algorithms. The runs were performed using MATLAB’s Statistics Toolbox. The p values were obtained using Friedman’s test on pairwise comparisons between VSMPSO and other comparison algorithms. Normally, the p value threshold for statistical significance is 0.05 [49], and \(p\geqslant 0.05\) showed no significant difference; whereas \(p<0.05\) showed significant difference. “\({+}\)” indicates the labeled algorithm with the mean best value significantly outperformed other algorithms. The RBF model used in VSMPSO and other algorithms was implemented using the MATSuMoTo Toolbox [50]. The parameters of the optimizer SLPSO were set as recommended in [40]. For all the compared algorithms in this paper, the termination condition depended on the number of consumed function evaluations (FEs). The computational budget was less than \(11 \cdot D\) number of function evaluations (NFEs) [31, 32], which means the limited number of fitness evaluations was 11 times the dimension of the problem.

We describe the algorithm performance through two chart types to show convergence profiles and distribution of solutions, such as Figs. 2 and 3. It is noted that the original author provides the source code of SA-COSO and SAHO and the source codes of MGP-SLPSO and CAL-SAPSO are available on the internet. In [31], CAL-SLPSO is examined on problems less or equal to 30-D. So we compare statistical results with MGP-SLPSO, CAL-SAPSO, SAHO, and SACOSO on 30-D problems and then compare statistical results with MGP-SLPSO, SAHO, and SACOSO on 50- and 100-D problems. Considering the time consumption, we compare statistical results with MGP-SLPSO and SACOSO on 200-D problems.

The proposed VSMPSO can be applied in any surrogate-assisted evolutionary algorithm irrespective of the surrogate model used. In this paper, we used two widely adopted models, GP and RBF, to predict fitness values, referred to as VSMPSO(GP) and VSMPSO(RBF). VSMPSO(GP) used GP as a surrogate model, while VSMPSO(RBF) used RBF. Both VSMPSO(GP) and VSMPSO(RBF) are all based on the VSMPSO framework in Algorithms 1, 2 and 3; their only difference was the different surrogate models used.

From Table 2, MGP-SLPSO was the best on F1, VSMPSO (GP) the best on F4, VSMPSO(GP) on F7, CAL-SAPSO on F5. SAHO was the best on F2, F3, and F6. So SAHO had better optimization results than other SAEAs; however, from Table 3, SAHO and CAL-SAPSO took hundreds of times longer than other SAEAs. We considered optimization results and the running time as the bi-objective problem. In the first row of Table 3, “Best fitness” means the average value of the best fitness values obtained by 30 independent operations performed by each algorithm, and “Time” means the mean time obtained by 30 independent operations performed by each algorithm. We consider “Best fitness” and “Time” as two objectives, referred to as the non-dominated solution (NDS) and dominated solution (DS). We sorted the comparison algorithm results and marked all non-dominated solutions (NDSs) on the Pareto front with a black hollow pentagram in Fig. 3. From Table 3, we can see that VSMPSO (RBF) achieved NDS on F1, F4, F5, F6 and F7, similar to MGP-SLPSO. From Fig. 3, on F1 and F3, the dominant solution (DS) achieved by VSMPSO (RBF) is the closest to NDS. In Fig. 2, the convergence rate of VSMPSO (RBF) is second only to SAHO on F3 and has the fastest convergence curve on F7. MGP-SLPSO had the shortest running time because Matérn32 function was used as the kernel function. In our previous work [51], when the commonly used squared exponential (SE) kernel function is used, compared with using Matérn32, the running time of GP model-assisted SLPSO even increases over ten times. SE is the most commonly adopted covariance function in GP-assisted optimization algorithms, for example, in [9, 15, 52, 53].

We compared VSMPSO with MGP-SLPSO, SAHO, and SACOSO on 50D functions. In Table 5, we can observe that MGP-SLPSO achieved the best mean value on F1 and F4, and SAHO achieved the best mean value on F2, F3, F5, F6, and F7. VSMPSO(RBF) achieved a similar performance with SAHO on F7. From Table 3 and Fig. 5, VSMPSO(RBF) derived NDS on F3, F5, F6, and F7, which is one less than MGP-SLPSO and SAHO. From Fig. 4, the convergence curve of VSMPSO(RBF) is very close to the SAHO one on F6 and F7. From Fig. 5, the dominant solution(DS) achieved by VSMPSO(RBF) is the closest to NDS on F1, F2, and F4. In Table 4, the running time spent by VSMPSO(GP) is dozens or even hundreds of times that of VSMPSO(RBF); the running time spent by VSMPSO(GP) is dozens of times higher than that of VSMPSO(RBF) on F1, F4, and F6 functions, and more than 100 times higher on F2, F3, F5, and F7. The slow computational efficiency makes VSMPSO(GP) unable to run on higher dimensions. Furthermore, from Table 4 and Fig. 5, VSMPSO(GP) has no NDS on 50D functions, whereas VSMPSO(RBF) has 4 NDSs. The overall performance of VSMPSO(RBF) is better than VSMPSO(GP). Hence, in the next comparative test, we used VSMPSO(RBF) algorithm to compare with other algorithms; it is abbreviated as VSMPSO in the following algorithm comparison.

To further observe the optimization ability of VSMPSO, we extended the computational budget to 2000 FEs. From the aforementioned analysis, VSMPSO (GP) was time-consuming, and its optimal performance was inferior to VSMPSO(RBF). Therefore, in the following algorithm comparison, we only used VSMPSO (RBF), referred to as VSMPSO. Although VSMPSO did not achieve good optimization performance on the 50D with 1000 FEs, it has better performance with 2000 FEs. In Table 6, MGP-SLPSO achieved the best mean value on F1; SAHO achieved the best mean value on F2, F3, F4, and F7. VSMPSO achieved the best mean value on F5 and F6, and has similar performance and no significant difference with SAHO on F7. Furthermore, VSMPSO achieved the second-best mean value behind SAHO on F2 and F3, and the running time of VSMPSO was smaller than SAHO. MGP-SLPSO algorithm took the shortest running time. In Table 7, MGP-SLPSO achieved 7 NDSs owing to the shortest running time. VSMPSO achieved 5 NDSs same as SACOSO, and SAHO achieved 4 NDSs. VSMPSO did not achieve NDS on F1 and F2, but the DS achieved by VSMPSO is closest to the NDS in Fig. 7. The solutions achieved by VSMPSO, MGP-SLPSO and SAHO are very close to the abscissa value (i.e., the minimum fitness value) in Fig. 7. In Fig. 6, the performance of VSMPSO is stable on different functions, and the convergence curves achieved good results on F5, F6, and F7.

Next, we compared the algorithm performance on higher-dimensional problems. The convergence profiles of VSMPSO, SACOSO, MGP-SLPSO and SAHO on F1–F7 with 100D and 200D are shown in Figs. 8 and 10. VSMPSO is compared with MGP-SLPSO, CAL-SAPSO, SAHO and SACOSO on 100D. In Table 8, MGP-SLPSO obtains the best mean value on F1 and F4. SAHO obtains the best mean value on F2, F3, F5 and F7. VSMPSO performs the best only on F6. However, on F7, the results of VSMPSO are not significantly different from that of SAHO, and the standard deviation is smaller than SAHO. In Table 9, VSMPSO obtains 5 NDSs, which is the highest NDSs, SAHO achieves 4 NDSs, MGP-SLPSO achieves 3 NDSs, and SACOSO achieves 1 NDS. On F1 and F4, VSMPSO did not achieve NDS, but the DS achieved by VSMPSO is closest to the NDS achieved by MGP-SLPSO in Fig. 9.

Because it takes more than a week for SAHO to obtain the optimization results of one function on 200D problems, it is too expensive to compare VSMPSO with SAHO on 200D problems. So VSMPSO is compared with MGP-SLPSO and SACOSO on 200D problems. In Table 10, VSMPSO obtains the best mean value on F2, F3, and F5, and has a similar performance with SACOSO on F7. SACOSO obtains the best mean values F6 and F7. MGP-SLPSO obtains the best mean value on F1 and F4, and VSMPSO obtains the best mean value second only to MGP-SLPSO on F1 and F4. The running time is no order of magnitude difference between VSMPSO and the MGP-SLPSO, and even the time spent by VSMPSO on F5 is less than MGP-SLPSO. Thus, VSMPSO can achieve a better balance between the optimization effect and the time-consuming and obtains better optimization results on higher dimensional problems (Table 11 and Fig. 11).

To test and verify the effectiveness of sample selection strategy in VSMPSO, four different sample selection strategies are compared in empirical studies. Therefore, we design a framework of surrogate model-based PSO (SMPSO), in which the RBF model is used as a single surrogate model and SLPSO as the optimizer. The detailed explanation of SMPSO is located in Algorithm 3. The difference between SMPSO and VSMPSO is the model management strategy. SMPSO only searches for the most promising solution from the current population to evaluate, but VSMPSO takes advantage of the proposed variable model management strategy to search for the most promising solutions from the current population and the current RBF model. SMPSO-RS, SMPSO-AS, SMPSO-FS1 and SMPSO-FS2 are all based on the SMPSO framework; their only difference is in step 7 of the sample selection strategy. The details of different sample selection strategies are as follows:

SMPSO-FS1 and SMPSO-FS2 chose fixed sampling (FS) as the sample selection strategy, and the fixed sample number was \(\lambda \), the same as the sample number in VMPSO and SMPSO-RS. As noted in “Proposed VSMPSO algorithm” section, the crucial element affecting VSMPSO is the variable model management strategy. The variable model management strategy has two steps: Step 1, a simple random sampling (RS) strategy is used for selecting random \(\lambda \) samples in DB to construct the RBF model in each generation. Step 2, the current RBF model information is deeply mined by finding the minimum of the surrogate model. Two potential optimum points( PGbest and MGbest ) are considered in the variable model management strategy. PGworst, the individual with the worst predicted fitness value in the current population, is then replaced by MGbest.The following experiment results further demonstrate that this is an effective method to improve the diversity of the model and avoid local optimum without using multiple models.

The contribution of the simple random sampling strategy in VSMPSO is inferred by comparing the results of SMPSO-RS with SMPSO-AS, SMPSO-FS1, and SMPSO-FS2. From Table 12, on 30D functions, SMPSO-RS achieved better optimization results on F3 and F7 than SMPSO-AS, SMPSO-FS1, and SMPSO-FS2, and the optimization results of SMPSO-RS on F2, F4, F5, and F6 were second only to SMPSO-AS. From Fig. 12, the trend of convergence curves is consistent, except that the F1 and F3 convergence curves are slightly dispersed. From Table 12, on 50D functions, SMPSO-RS achieved better optimization results on F2, F4, F6, and F7 than SMPSO-AS, SMPSO-FS1, and SMPSO-FS2, and the optimization results of SMPSO-RS on F1, F3, and F5 were slightly less than SMPSO-AS but better than SMPSO-FS1 and SMPSO-FS2. In addition, from Fig. 14, the trend of convergence curves for SMPSO-RS are very similar to that of SMPSO-AS on most functions.

From Table 15, SMPSO-RS achieved better optimization results on F3, F6, and F7 than SMPSO-AS, SMPSO-FS1, and SMPSO-FS2, and the optimization results of SMPSO-RS on F1, F2, F4, and F5 were slightly lower than SMPSO-AS but better than SMPSO-FS1 and SMPSO-FS2. Moreover, from Figs. 13, 15 and Table 14, SMPSO-RS achieved non-dominant solutions for both 30D and 50D problems. From Fig. 17, the dominant solution obtained by SMPSO-RS is closest to the non-dominant solution in abscissa value (that is the minimum fitness value) on F1, F2, F4, and F5. Conversely, SMPSO-FS1 and SMPSO-FS2 have similar results on Tables 12, 13 and 15, and show similar convergence curve on Figs. 12, 14 and 16. Moreover, both SMPSO-FS1 and SMPSO-FS2 have worse results than SMPSO-RS and SMPSO-AS; hence, the performance of fixed sampling methods is inferior to all sampling methods and the simple random sampling method. The performance of simple random sampling (RS) is significantly better than that of fixed sampling (FS) and SMPSO-RS performs better on complex problems. Conversely, SMPSO-AS takes more time than SMPSO-RS on 30D and 50D functions. When all samples are used for modeling in SMPSO-AS, it is time-consuming.

By comparing VSMPSO with SMPSO-RS, SMPSO-AS, SMPSO-FS1 and SMPSO-FS2, we can see the contribution of Step 2. In Step2, VSMPSO takes advantage of the variable model management strategy to search for the most promising solutions from the current population and the current RBF model to evaluation. This differs from the strategy of all SMPSO algorithms that only searches to evaluate the most promising solution from the current population. From Tables 12, 13 and 15, the results of VSMPSO are significantly different from those of other algorithms. On 30D functions, VSMPSO obtained the best results on F1, F2, F3 and F7, besides obtaining slightly lower results with SMPSO-RS on 30-D F4, F5 and F6. However, on 50D functions, VSMPSO achieved better optimization results on F1, F2, F3, F4 and F7, slightly less than SMPSO-RS on F4 and F5. Furthermore, on 100D functions, VSMPSO achieved the best optimization results on F1, F2, F3, F4, F5 and F7, besides obtaining slightly lower results with SMPSO-AS on F6. VSMPSO has clear advantages on 100D than 50D and 30D, the improvement becomes more remarkable when the dimension of decision space D increases.

From the results mentioned above, we concluded that combining the two main innovations of the proposed VSMPSO in “Proposed VSMPSO algorithm” contributed to improving the performance of the proposed algorithm. First, from the results of comparing SMPSO-RS and three other algorithms (SMPSO-AS, SMPSO-FS1, and SMPSO-FS2), the random sample selection method is the same as the one we used in VSMPSO, eliminates the weaknesses of the fixed samples. Second, comparing the results of SMPSO-RS and VSMPSO, looking for the most promising solution from two different angles, especially the most promising solution from the current RBF model, quickening the optimal speed.

The parameters in VSMPSO, like the parameters of the optimizer SLPSO and the number of consumed function evaluations (FEs), may significantly influence the proposed algorithm’s performance. For a fair comparison, the parameters of the optimizer SLPSO are set the same as the recommended parameters in [40]. For all the algorithms compared in this paper, the termination condition depends on the number of consumed function evaluations (FEs). The computational budget is less than \(11\cdot D\) number of function evaluations (NFEs) [32], which means that the limited number of fitness evaluations is 11 times the dimension of the problem. In VSMPSO, the value of \(\lambda \) is 80% of the total sample number. Then, we only need to analyze the parameters \(\lambda \) of VSMPSO, to explore the influence of different sample sizes on optimization performance. In the next experiment, we analyzed the performance comparison of VSMPSO for different sample sizes. The comparison algorithms VSMPSO-50, VSMPSO-60, VSMPSO-70, VSMPSO-80, VSMPSO-90, and VSMPSO-100 represent VSMPSO with different samples, which respectively represent the number of selected samples \(\lambda \) accounting for 50%, 60%, 70%, 80%, 90% and 100% of the total sample size, and VSMPSO-100 means all samples for modeling. Furthermore, all parameters in VSMPSO-80 are the same as those in VSMPSO, meaning the results of VSMPSO-80 are consistent with VSMPSO mentioned in the abovementioned experiments.