Evolutionary multiobjective optimization via efficient sampling-based offspring generation

Inspired by the decision variable analysis-based divide-and-conquer strategy and the efficient offspring generation approaches, we propose an optimization-based variable classification approach to handle LSMOPs. Instead of categorizing decision variables into many groups, all the decision variables are divided into two groups in the proposed method. Generally, the first group consists of decision variables related to convergence and the second one related to diversity. All the convergence-related/diversity-related decision variables are optimized independently without considering the pairwise variable interactions. Accordingly, three different sampling strategies, following the idea of efficient offspring generation, for convergence enhancement, diversity maintenance, and local search are designed.¹ An illustrative example of the proposed offspring generation strategies on an MOP with five decision variables is presented in Fig. 1, which visually shows the principles of three involved sampling strategies in SLSEA. Assume binary vector \(\textbf{b}=(0,1,0,1,1)\) is a vector for indicating the division result of an MOP with five decision variables. The vector indicates that decision variables \(x_2,x_4,x_5\) are convergence-related decision variables, while \(x_1,x_3\) are diversity-related ones. With these ad hoc sampling strategies, we are motivated to solve LSMOPs via efficient sampling under the guidance of variable classification. Note that the norm Gaussian distribution is used in two designed sampling strategies due to its popularity with symmetry, coverage, and a predefined center. The symmetry ensures unbiased sampling as we have no prior knowledge of the problem, and the coverage enables the sampling of all possible solutions. Moreover, the predefined center controls the sampling, which is expected to guide the sampling towards the Pareto optimal set. Other distributions with similar properties can also be used for perturbing the three sampling strategies. If the prior knowledge of the problem is given, the multivariate Gaussian distribution can be used for addressing this issue, which could be computationally expensive.

Algorithm 1 presents the schema of the proposed SLSEA. It mainly consists of five components, i.e., convergence sampling, variable classification, diversity sampling, local sampling, and environmental selection. First, a candidate solution set P of size n and a binary vector set B of size \(n_b\) are randomly initialized (Steps 1–2 in Algorithm 1). Next, B is used to sample a set of convergence-related solutions \(P_c\) (Steps 5\(\sim \)6 in Algorithm 1). Notably, B is updated using the proposed variable classification approach, during which the newly generated convergence-related solutions are merged into population \(P_c\). Then, the diversity-related sampling strategy (Step 7 in Algorithm 1) is adopted to sample a set of diversity-related candidate solutions \(P_d\) with the guidance of the updated B. Afterwards, a local search-related sampling is designed to sample local solutions \(P_l\) around the current population P. Finally, the combination of all the sampled candidate solutions is updated using environmental selection. Notably, different environmental selection strategies in conventional MOEAs can be used in SLSEA, and here, we use the environmental selection in NSGA-II due to its efficiency and simplicity. The procedures above are repeated until the maximum number of iterations is met.

The detailed procedures of the convergence-related sampling are given in Algorithm 2 In B, the ith binary vector \(\textbf{b}_i\) denotes an approximation of the accurate variable classifications. It is used to sample some convergence-related solutions via perturbing those convergence-related variables only. A total number of \(n_s\times n_b\) candidate solutions are sampled during the sampling, where \(n_s\) candidate solutions are sampled for each binary vector.

In addition to the convergence-related sampling in the main loop of SLSEA, this sampling is also conducted for updating the binary vectors (Step 3 in Algorithm 3). Thus, a total number of \(2n_s\times n_b\) convergence-related solutions are sampled in one generation of SLSEA.

In the proposed SLSEA, variable classification is used to update the binary vectors for better approximating the accurate variable classification, refer to Algorithm 3. An illustrative example of an MOP with five decision variables is given in Fig. 2 to show the detailed procedures. During the variable classification, the binary vector set B of size \(n_b\) is regarded as the parent population, and the quality of each binary vector is assessed based on the quality of the sampled solutions using Algorithm 4. The mating selection strategy in NSGA-II is applied to select the mating pool for generating offspring \(B'\). Notably, the single-point crossover and bit-wise mutation in the canonical GA are used for the generation of offspring binary vectors, and readers can refer to literature [8, 39] for more details. Next, a set of convergence-related solutions are sampled for each offspring binary vector using Algorithm 2, followed by the quality assessment of each offspring binary vector. Finally, \(n_d\) binary vectors are selected from \(B\cup B'\) using the environmental selection strategy in NSGA-II. Besides, the convergence-related solution set is also updated.

As a crucial part of the variable classification, the quality assessment determines the accuracy of variable classification results for guiding the sampling of convergence- and diversity-related solutions. Its detailed procedures are displayed in Algorithm 4 using two criteria:

The design of \(q_1\) and \(q_2\) is intuitively designed, aiming to demonstrate the effectiveness of the reformulation process in a relatively straightforward manner. The first objective reflects the average convergence degree of the solution set, which is a simplified version of the convergence degree in LMEA. The second objective is expected to minimize the number of convergence-related decision variables, aiming to reduce the dimensionality of the sub-problem for accelerating large-scale multiobjective optimization. Nonetheless, the framework is compatible with other tailored functions of similar purpose.

During the variable classification, a set of binary vectors are optimized simultaneously. We take advantage of the binary vectors to sample some candidate solutions for diversity maintenance, as presented in Algorithm 5. We first obtain the best-converged solution \(\textbf{p}\) \(\in \) \(P\) as the baseline to ensure the convergence of the candidate solutions to be sampled (Step 1 in Algorithm 5). ||f(p)|| denotes the Euclidean distance of solution \(\textbf{p}\) in the objective space, which reflects the convergence degree of solution \(\textbf{p}\). By selecting the solution with the best convergence degree, Step 1 of Algorithm 5 is expected to guide the sampling of diversity-related solutions with good convergence. Then, we sample n candidate solutions for each binary vector by perturbing those diversity-related decision variables (i.e., elements with zero value in a binary vector). Specifically, a uniform distribution \(\mathcal {U}(0,1)\) is used to generate a random number k for perturbing the decision vector (Step 3 in Algorithm 5), encouraging the sampling of diversity-related candidate solutions. Finally, all the sampled candidate solutions are merged as population \(P_d\).

While the variable classification and diversity-related sampling aim to deal with convergence enhancement and diversity maintenance respectively, the local search-related sampling is expected to conduct local search around existing solutions. The detailed procedures of the local search-related sampling are given in Algorithm 6. Specifically, we conduct a local search around \(n_s\) solutions randomly selected from population P. Notably, this selection can also choose some dominated solutions to encourage diversity maintenance since they could be important in global optimization [40, 41]. Then, a value randomly selected from a norm Gaussian distribution is used to perturb each chosen solution. Mathematically, for a candidate solution \(\textbf{x}\), the ith variable of the perturbed solutions satisfies Gaussian distribution \(\mathcal {N}(x_i,1)\) (refer to Fig. 1c). Finally, a total number of \(n_s\times n\) candidate solutions are merged as population \(P_l\) during the local search-related sampling.

To assess the performance of the compared algorithms on large-scale multiobjective optimization, two widely used indicators, namely the IGD indicator [44] and the hypervolume (HV) indicator [45], are used. Both indicators can assess the convergence degree and distribution uniformity of a solution set in multiobjective optimization. Nevertheless, these two performance indicators are different due to the different requirements in reference points.

In the IGD indicator, a set of uniformly distributed points located precisely on the PF are required to give an accurate assessment of the quality of the solution set. By contrast, only a single point close to the nadir point of the PF is needed in HV calculation [46]. Generally, IGD calculation requires prior knowledge about the PF, which is suitable for benchmark problems with known PFs. The IGD\(+\) indicator can also be used for better assessment of the quality, which is weakly Pareto compliant, whereas IGD is Pareto incompliant [47]. Thus, it is suitable for mathematically formulated problems, e.g., DTLZ problems [48], WFG problems [49], and LSMOP problems [50]. However, for a real-world MOP such as a TREE problem [23], having a set of uniformly distributed points on its PF is impractical. Thus, we can adapt the HV indicator to assess the quality of a solution set using an approximation of the real nadir point.

In the following experiments, some test instances are selected from three benchmark test suites, i.e., DTLZ [48], LSMOP [50], and TREE [23]. In all these test instances, the number of objectives m is set to two, and the detailed settings are given as follows.

We adopt the recommended parameter settings for the compared algorithms that have achieved the best performance reported in the literature for fair comparisons. Moreover, to give an insight into the performance of SLSEA in large-scale multiobjective optimization, different variants of SLSEAs are designed as well.

The overall performance is presented in Tables 1 and  2. Specifically, these tables show IGD results and HV results achieved by the five compared MOEAs on nine LSMOP problems with 1000, 2000, and 5000 decision variables, respectively. It can be observed from the first table that SLSEA has achieved the most best results, followed by DGEA, LMOCSO, and LSMOF, while MOEA/DVA has failed to achieve any best result. Notably, MOEA/DVA has consumed four times the maximum number of FEs for decision variable analysis. Thus, it has no additional resources for further optimization, which could explain its unsatisfactory performance. To be more specific, SLSEA has achieved the best results mainly on LSMOP4, LSMOP5, LSMOP6, and LSMOP8; DGEA has performed the best on LSMOP1 and LSMOP2; LSMOF has superior performance mainly on LSMOP7; LMOCSO has shown its advantages on LSMOP3 and LSMOP9. For LSMOP3, LSMOP5, LSMOP7, and LSMOP8, the differences of the achieved IGD results are significantly (e.g., over 100 times on LSMOP3 and LSMOP7) since these problems are challenging for large-scale MOEAs to converge to the PFs. For the rest test problems, the compared algorithms have achieved competitive results, since the difficulty of these problems is about the diversity maintenance to obtain evenly distributed results. As for Table 2, LSMOF has achieved the most best results, which can be attributed to the fact that LSMOF has achieved widespread solution sets in the objective space, leading to better HV values in comparison with SLSEA (refer to Fig. 7).

To visually show the dynamic behaviors of the compared algorithms on large-scale multiobjective optimization, Fig. 6 presents the convergence profiles of the compared algorithms in terms of IGD values. The convergence profiles of LSMOF and SLSEA are similar on LSMOP1, LSMOP3, LSMOP5, LSMOP6, LSMOP7, and LSMOP8; DGEA converges similarly to SLSEA on LSMOP1, LSMOP2, LSMOP4, and LSMOP6; while SLSEA has shown overall superiority over LMOCSO and MOEA/DVA on all the test instances. It can be concluded that the search behavior of SLSEA is similar to DGEA and LSMOF since they all have effective strategies for dealing with a large number of decision variables. Nevertheless, due to the balanced consideration of convergence enhancement, diversity maintenance, and local search, SLSEA has shown better versatility in solving different LSMOPs. In contrast, LSMOF and DGEA have achieved biased performances.

Moreover, the final non-dominated solutions achieved by the five compared algorithms on nine LSMOP problems in the run associated with the best IGD value are displayed in Fig. 7. It can be seen that SLSEA has behaved similarly to DGEA on LSMOP1, LSMOP2, LSMOP6, and LSMOP8, and it has behaved similarly to LSMOF on LSMOP2, LSMOP6, LSMOP 7, and LSMOP 8, which more or less agrees with the convergence profiles in Fig. 6. Both LSMOF and DGEA have used direction vectors in the decision space, while SLSEA has used the guidance of variable classifications. Thus they have shown effectiveness in large-scale multiobjective optimization. Nevertheless, due to the differences in offspring generation, SLSEA trends take advantage of LSMOF and DGEA to achieve a balanced performance, leading to its superiority over LSMOF and DGEA.

In the Supplementary Materials, we also give the convergence profiles of the compared algorithms on five representative LSMOP problems with a maximum number of \(5\times 10^6\) (25\(\times \) of the original settings). The results indicate that SLSEA tends to converge fast at the first \(1\times 10^6\) and stagnate around \(4\times 10^6\). Thus, SLSEA is more suitable for solving LSMOPs with limited FEs.

As indicated in Algorithm 1, the computational complexity of SLSEA is mainly contributed by four functions, i.e., variable classification, diversity-related sampling, local search-related sampling, and environmental selection. For the first component, the computational complexity in terms of big O notation, as indicated in Algorithm 3, is \(O(2nm)+2\times O(n_b\times (n_s+mn_s+mn^2+mn_b^2)+n_b^2+2\times (2n_b)^2)\), i.e., \(O(mn+mn^2n_b+mn_b^3+n_bn_s+mn_sn_b+n_b^2)\) by eliminating the constant factors, which can be further simplified as \(O(mn^2n_b+mn_b^3+mn_bn_s+n_b^2)\). Algorithms 5 and 6 are similar, and their total computational complexity is \(O(mn+nlgn+n_b(n+1))\) \(+\) \(O(n_s+n_s(n+1))\). As for the last function, the computational complexity of the environmental selection in NSGA-II is \(O(m(n+nn_b+nn_s)^2)\) [8]. In summary, the computational complexity of SLSEA is \(O(mn^2n_b+mn_b^3+mn_bn_s+n_b^2)\) \(+\) \(O(mn+nlgn+n_b(n+1))\) \(+\) \(O(n_s+n_s(n+1))\) \(+\) \(O(m(n+nn_b+nn_s)^2)\). It can be simplified to \(O(m(n^2n_b+n_b^3+(n+nn_b+nn_s)^2)+n(lgn+n_b+n_s)+n_b^2)\), i.e., \(O(mn^2(n_b+(1+n_b+n_s)^2)+mn_b^3)\). The main computational complexity comes from the non-dominated sorting based environmental selection. It can be improved by using some divide-and-conquer strategies, e.g., selecting the non-dominated solutions from each subpopulation instead of selecting solutions from the combination of all solutions. Besides, if \(n_b\) and \(n_s\) are treated as constants, the final computational complexity of SLSEA will be \(O(mn^2)\) as that of NSGA-II. Thus, the efficiency of SLSEA in terms of computational complexity is acceptable.

Table 3 further displays the computation time of the five compared algorithms on two LSMOP problems and two TREE problems. It can be observed that SLSEA has consumed acceptable computation time for large-scale multiobjective optimization, which validates its efficiency in terms of computation time.