Multi-objective multi-criteria evolutionary algorithm for multi-objective multi-task optimization

MO-MTO is a diagram for solving multiple multi-objective optimization tasks together. Mathematically, the MO-MTOP can be defined as follows.

Given K multi-objective optimization tasks (assuming the objectives in every task are all minimization problems), denoted as T₁, T₂, …, T_K, where the k^th task has M_k (M_k > 1) objective functions F_k(x) = [f₁(x), f₂(x), …, f_Mk(x)]. The search space and the objective space of the k^th task are Ω_k and Ψ^M_k, respectively, and they satisfy that F_k: Ω_k → Ψ^M_k. The aim of a minimization MO-MTOP is to find the optimal solution set {x_k} for each task T_k, such that {x_k} satisfies

As each F_k has multiple objectives, we will have the following important concepts for each task T_k to determine whether a solution is optimal according to the related definitions in the literature of multi-objective optimization [43, 44].

Based on the above definitions, the optimal solution set {x_k} for each task T_k is actually the PS of the T_k.

To date, although the EMO-MTO is a newly emerged optimization diagram, some EMO-MTO works have been proposed and attracted increasing attention. Therefore, this part provides a brief review of the existing works.

As mentioned briefly in the Introduction part, existing works about EMO-MTO can be categorized into two major categories. The first category is about the multifactorial-based approach [3, 13, 36‐38], while the second category is about the non-multifactorial-based approach [39‐41].

In the first category, MO-MFEA is the most representative algorithm framework for solving MO-MTOPs [3]. When compared with other algorithms, the distinct feature of MO-MFEA is that the MO-MFEA evolves one population with skill factors to find the optimal solutions for multiple tasks together. In MO-MFEA, each individual in the population corresponds to one task according to their skill factors, and thereby individuals for different tasks can transfer common knowledge implicitly via genetic operations, e.g., crossover operation. By utilizing omnidirectional knowledge transfers, the MO-MFEA can achieve mutual knowledge sharing among different multi-objective optimization tasks, so that the optimization for each task can be benefited by the obtained knowledge from other tasks. To make the knowledge sharing more adaptively, Bali et al. [13] studied the intertask relationship learning and proposed an online adaptive genetic transfer method to develop the MO-MFEA-II, which can achieve better overall performance than the original MO-MFEA. Moreover, as MO-MFEA may convergence slowly if tasks are weakly relevant or even irrelevant, Zheng et al. [36] proposed to introduce additional helper tasks via the weighted sum of original tasks to improve the knowledge transfer and speed up the algorithm convergence. Furthermore, Yang et al. [37] considered not only the convergence but also the diversity of MO-MFEA and proposed a two-stage assortative mating method to enhance the knowledge transfer among diversity-related and convergence-related variables among related tasks. Besides, Binh et al. [38] proposed a reference-point-based approach and an enhanced random mating probability learning method to better exploit and transfer knowledge among individuals targeted at different tasks.

In the second category, algorithms maintain multiple populations with explicitly transfer information among the populations for solving MO-MTOPs. For example, Lin et al. [39] proposed an algorithm based on incremental learning to find suitable knowledge for the transfer among different tasks. Liang et al. [40] proposed a genetic transform strategy to transfer the individual genetic information from one task to relevant tasks. In addition, Feng et al. [41] proposed an explicit autoencoding method to achieve knowledge transfer among the population targeted at different tasks to enhance the optimization results.

However, these existing methods and algorithms for MO-MTOPs still treat the multiple tasks in the MO-MTOP as different problems and optimize them simultaneously, which requires a well-designed knowledge transferring strategy to share knowledge among tasks. Differently from these methods, the MO-MCEA proposed in this paper treats all tasks in MO-MTOP as multiple criteria of an entire MO-MTOP to guide the evolution appropriately, so as to fully utilize the knowledge in different tasks during the optimization process and obtain promising solutions for all tasks. Therefore, the contributions and novelties of this paper are justified.

In this paper, the MCOP is defined as follows:

Given an optimization problem (assuming it is a minimization problem) with K available evaluation criteria (including objective/constraint functions) on the same search space Ω, which are denoted as F₁, F₂, …, F_K, the aim of a minimization MCOP is to find the optimal solution set {x} that satisfieswhere F₀ can be arbitrary one in {F₁, F₂, …, F_K} at different search stages. Note that the “argmin” should be “argmax” if the problem is a maximization optimization problem, and the {x} will only have one element if the problem is single-objective. The key characteristic of MCOP is that when each evaluation function can guide the optimization to find acceptable optimal solutions for the problem, then the proper usage of multiple evaluation functions can obtain a satisfactory solution more efficiently. Moreover, if the F₁, F₂, …, F_K have different fidelities or accuracy scales, then the MCOP can be considered as a multifidelity optimization problem [45] or multi-scale optimization problem [46], respectively. In addition, the relationship between MCOP and MTOP is that both of them have multiple evaluation functions, while the main difference between them lies in that the MCOP requires the algorithm to optimize only one evaluation function each time, while the MTOP requires the algorithm to optimize multiple different evaluation functions together each time.

Based on the above, the MO-MCOP is the same as MCOP except that all evaluation functions in {F₁, F₂, …, F_K} are multi-objective functions.

This part discusses the relationship between MO-MTOP and MO-MCOP. To begin with, we consider a unified search space Ω for all different tasks in the MO-MTOP, where the search space of the kth task is Ω_k. Considering K one-to-one mapping functions φ₁, φ₂, …, and φ_K, where φ_k: Ω → Ω_k, then Eq. (1) for MO-MTOP can be rewritten as

Now, the MO-MTOP is with K tasks with the same search space (i.e., Ω), where the multi-objective evaluation function of the kth task is F_k◦φ_k and of all tasks are the same. Moreover, if considering F₁◦φ₁, F₂◦φ₂, …, and F_K◦φ_K as different evaluation functions in a MO-MCOP, then the aim of MO-MCOP, i.e., Eq. (4), can be rewritten as

Note that we have {φ_k(x)} = {x_k} for k = 1, 2, …, K as φ_k: Ω → Ω_k. Therefore, comparing Eqs. (5) and (6), the main difference between MO-MTOP and MO-MCOP is that given a set of evaluation functions, MO-MTOP aims to optimize all evaluation functions by considering them together all the time during the optimization process, while MO-MCOP attempts to obtain the optimal solutions by considering one evaluation function every time during the optimization process, where the latter (i.e., MO-MCOP) can be an easier problem, because the optimization algorithms can select an appropriate function at different stages adaptively and flexibly to guide the evolution to obtain better results. Therefore, it would be better if MO-MTOP can be treated as MO-MCOP.

Based on the above, MO-MTOP can be treated as MO-MCOP with multiple criteria (i.e., evaluation functions) and the algorithm can select the proper criterion in different stages to guide the evolution. Herein, this part further analyzes the rationality and the benefit of treating MO-MTOP as MO-MCOP in the following contents.

The overall framework of the MO-MCEA is presented in Fig. 1, which mainly has three parts. The first part is a criterion set of available evaluation functions, the second part is the criterion selection based on PCSS and APL to select one of the evaluation functions as the evaluation criterion to evolve population at different evolutionary stages, and the third part is the procedure of evolutionary optimization with the selected criterion. In the following contents, the PCSS, APL, and the complete algorithm will be introduced one by one.

The PCSS is proposed to select one multi-objective function from multiple multi-objective functions to be the selection criterion for the current generation. The idea of PCSS is straightforward: each multi-objective function will have a criterion selection probability (denoted as csp), e.g., F_i has csp_i, and the multi-objective function with a larger csp will have more opportunities to be selected as the selection criterion. Following this, given K multi-objective functions F₁, F₂, …, and F_K, and their corresponding selection probability csp₁, csp₂, …, and csp_K, the index of the function selected as the criterion will be determined by the roulette with csp₁, csp₂, …, and csp_K. Mathematically, the selection of the criterion can be written as

where cid is the index of the selected criterion (i.e., the selected criterion is denoted as F_cid), and the function roulette returns an index based on a roulette with csp₁, csp₂, …, and csp_K as the probabilities for the available indexes 1 to K_.

The initial csp is initialized evenly for different available functions and the APL aims to learn more suitable csp adaptively during the evolution, so that the PCSS can select the criterion more properly. In general, if the population has better improvements after one generation under the current selection criterion, this criterion may be more suitable for the current evolutionary stage, and vice versa. Therefore, the APL updates the csp according to the population improvement in every generation. To be specific, considering the population at gth generation (i.e., P_g) uses the cidth multi-objective function (i.e., F_cid) as the selection criterion, then the APL will update csp_cid aswhere ∆ is a fixed value for updating csp, and the “better” can be determined by comparing P_g + 1 and P_g based on various metrics that do not rely on the real Pareto front, such as C metric [52] and hypervolume [32]. Note that the proposed MO-MCEA in this paper uses the C metric to compare P_g + 1 and P_g. Besides the csp_cid, the other csp (i.e., csp_j where j ≠ cid) will also be updated aswhere K is the total number of available multi-objective tasks. Note that if a csp_i is smaller than 0.1, then it will be set as 0.1 and then all csp are normalized, so as to guarantee that the ith function still has a chance to be selected again and the sum of csp equals 1.

With the PCSS and APL, the flowchart of the complete MO-MCEA is given in Fig. 2 and the pseudo code of the complete MO-MCEA is shown as Algorithm 1. Note that the search spaces of all tasks will be normalized in the unified search space [0,1]^D, where D is the maximum variable dimension among all tasks. That is, solutions for different tasks are mapped to the [0, 1]^D, which is a common technique in the literature [4]. As can be seen, after the initialization, Algorithm 1 mainly has three repeated procedures. These three procedures are the criterion determination via PCSS, population evolution, and the parameter learning for PCSS through APL, which can be seen in lines 10–15, lines 16–18, and lines 19–20 of Algorithm 1, respectively. Note that the population evolution procedures in Algorithm 1 can use various existing well-designed operators including efficient crossover, mutation, and selection operators according to the needs and preferences of users. Therefore, the MO-MCEA can be extended with powerful state-of-the-art methods and operators to develop more efficient algorithms. In this paper, the optimization algorithm for each task is the NSGA-II [44]. In addition, it should also be noted that the evaluation criterion will be switched by PCSS every G generations. Moreover, every time the evaluation criterion is switched, the current population will be re-evaluated by the new evaluation criterion before going to the evolution. Therefore, NP fitness evaluations (FEs) are needed after every switch, just as shown in lines 13 and 14 of Algorithm 1. Overall, the algorithm will repeat the PCSS, population evolution, and APL iteratively until the stop criterion is met, e.g., all available FEs are consumed. Note that we use K sets (denoted as NDS₁, NDS₂, …, NDS_K) to record the current non-dominated solutions for the K tasks, respectively. During the evolutionary process, after the population evolution of one generation with F_cid (i.e., the line 16 of Algorithm 1), the corresponding NDS_cid will be updated. That is, all the solutions in the current population will merge with the solutions in NS_cid, and then, only those non-dominated solutions in the merged solution set can be remained in the NDS_cid. After the evolutionary process, all the solutions in the final population will be, respectively, evaluated by each of the K multi-objective functions and be merged with the corresponding NDS to update the NDS (the update process is similar to that in line 18), see lines 23–24 in Algorithm 1. Finally, the algorithm outputs the best-found non-dominated sets for all different tasks.

In the experimental studies, six commonly used MO-MTOPs [53] with different similarities are adopted to investigate the proposed methods and algorithm. The properties of these problems are briefly introduced in Table 1, where the task similarity is evaluated by the Spearman’s rank correlation coefficient [53]. In Table 1, the complete intersection (CI) and partial intersection (PI) indicate that the Pareto optimal solutions of the two tasks are similar in all and some dimensions, respectively, while high similarity (HS), medium similarity (MS), and low similarity (LS) mean that the two tasks have high, medium, and low similarity measured by Pearson correlation according to their function landscape. Based on this, the six problems with different properties can be categorized into different categories according to their intersection degree and task similarity. For example, the CI + HS problem has the property of complete intersection and high similarity between its two internal tasks. Moreover, as shown in Table 1, different multi-objective tasks will also have different Pareto fronts. Therefore, the composition of different intersections, similarity degrees, and Pareto fronts can help provide an in-depth observation of how the proposed algorithm may behave in various situations. In addition, the dimensions of all tasks are set as 10, because tasks with high dimensions can be difficult to solve (e.g., contains many local optima) and different algorithms may have similar results (e.g., similar very poor results) on the high-dimensional tasks, which is not ideal for algorithm comparison and analysis.

To evaluate the effectiveness and efficiency of the proposed algorithm, some state-of-the-art and latest well-performing algorithms with various characteristics are used in comparisons. The adopted algorithms include the MO-MFEA [3], MO-MFEA-II [13], and EMT with autoencoding for MO-MTOPs (denoted as MO-EMTA for simplicity) [41]. To make the comparisons fair, all these algorithms use the same widely used and representative MOEA (i.e., NSGA-II [44]) as the optimizer. By doing so, the differences of the proposed MO-MCEA and the three compared algorithms only lie in their approach or way for handling MO-MTOPs, e.g., handle MO-MTOPs as MC-MTOPs or handle MO-MTOPs via multifactorial-based approach). Moreover, an NSGA-II integrated with the single-task evolutionary optimization paradigm (i.e., solving each task separately and independently) is also adopted as a baseline in the comparisons, where the algorithm is denoted as MO-STEA in the following contents. All the algorithm settings are kept consistent with their original papers. As for the NSGA-II operators, the settings are set as the same as those used in existing EMO-MTO literature [13]. Moreover, the G and ∆ in MO-MCEA are set as 25 and 0.01, respectively. In addition, the population size of individual budgets for each task is set as 50. Therefore, the total population size of both MO-MCEA and MO-STEA is 50, while the total population size of MO-MFEA, MO-MFEA-II, and MO-EMTA are all 100.

In the experiments, the maximum number of available FEs is 1 × 10⁴ in total (i.e., 5 × 10³ for each task) for each independent run of all algorithms. To reduce statistical errors, each algorithm runs 30 times independently on each MO-MTOP and the results are collected for the comparisons, as suggested by the literature [53].

To evaluate the performance of MO-MCEA, four evaluation metrics are adopted in the experimental studies and comparisons. The first two metrics are the mean and standard value of the optimization results of each algorithm for each task over 30 runs. As the tasks are multi-objective optimization tasks, the widely used inverted generational distance (IGD) indicator [43] for multi-objective optimization is adopted to evaluate the performance of an algorithm on each task. The IGD value can be calculated with a set of objective vectors obtained by an algorithm A (denoted as P^A) and a set of the objective vectors uniformly distributed over the true PF (refer to “Multi-objective multi-task optimization”) of a multi-objective task (denoted as P^*), which is mathematically defined aswhere d(x, y) calculates the Euclidean distance between x and y in the objective space, and |P^*| is the number of vectors in P^*. In general, the smaller the IGD(A, P ^∗) is, the better the algorithm A is, because a smaller IGD indicates that P^A is more close to P^* or contains more data in P^*. In addition, if | P^*| is large enough to represent the PF, the IGD(P^A, P^*) can measure both the convergence and diversity of the non-dominated solutions obtained by A. In other words, in this paper, the first two metrics are the mean and standard value of the IGD value obtained by each algorithm for each task over 30 runs, respectively.

Furthermore, the third metric is the Wilcoxon’s rank sum test with a significant level α = 0.05 [43] for algorithm comparisons. Specifically, based on the Wilcoxon’s rank sum test, the symbols “ + ”, “≈”, and “−” are used to represent that the proposed MO-MCEA performs significantly better than, similar to, and significantly worse than the compared algorithms, respectively.

The fourth metric is the mean standard score (MSS) designed for comparing algorithms on MO-MTOPs [53]. This metric is defined as follows. Assuming that there are N algorithms denoted as A₁, A₂, …, A_N for an MO-MTOP with K multi-objective minimization tasks T₁, T₂, …, T_K, each algorithm runs for R repetitions and the MSS of algorithm A_i can be defined aswhere IGD′(i,k)_r is the normalized IGD value obtained by an algorithm A_i for task T_k in rth independent run. The normalization process can be written aswhere IGD(i,k)_r is the original IGD value obtained by A_i on task T_k in the rth independent run, and u_k and σ_k represent the mean and standard deviation of IGD value for task T_k over all the R repetitions of all the N algorithms, i.e., the mean and standard value of N × R IGD results.

To investigate the performance of the proposed MO-MCEA, this part compares it with four algorithms, including the state-of-the-art and well-performing MO-MTO algorithms including MO-MFEA [3], MO-MFEA-II [13], and MO-EMTA [41], and one single-task algorithm MO-STEA as the baseline. The comparison results in Table 2 show the great efficiency of MO-MCEA. As shown in Table 2, the MO-MCEA can obtain the best MSS on 3 problems, while the MO-MFEA, MO-MFEA-II, MO-EMTA, and MO-STEA get the best MSS only on 0, 1, 2, and 1 problem(s), respectively. Moreover, according to the Wilcoxon’s rank sum test, the MO-MCEA can significantly outperform MO-MFEA, MO-MFEA-II, MO-EMTA, and MO-STEA on 7, 7, 7, and 8 tasks, and produce worse results than them only on 4, 4, 4, and 3 tasks, respectively. In addition, Fig. 3 plots the solutions found by different algorithms on the multi-objective tasks of different problems for a better result visualization. As can be observed from Table 2 and Fig. 3, the MO-MCEA performs significantly better on the three complete intersection problems with different task similarities, i.e., the MO-MTOP1 to MO-MTOP3. This is consistent with the analysis given in Sect. 3.1 that treating MO-MTOP as MO-MCOP is reasonable and effective when the optimal Pareto set of different tasks share similarities. Overall, the comparison results have verified the efficiency of MO-MCEA.

To perform the component analysis of MO-MCEA, we compare it with its variants that do not use PCSS or APL, which are denoted as MO-MCEA-w/o-PCSS and MO-MCEA-w/o-APL, respectively. To be specific, the MO-MCEA-w/o-PCSS selects the multiple objective functions as the criterion in sequential order with a round-robin fashion, and the MO-MCEA-w/o-APL will not update the probability parameter for determining the criterion (i.e., each of the multiple objective functions has the same probability to be randomly selected as the criterion in the PCSS).

Table 3 gives the comparison results, which indicate the contributions of both PCSS and APL. As shown in Table 3, MO-MCEA can obtain the best MSS on 3 problems, while the MO-MCEA-w/o-PCSS and MO-MCEA-w/o-APL get the best MSS only on 2 and 1 problem(s), respectively. Furthermore, the Wilcoxon’s rank sum test also shows that the MO-MCEA can perform significantly better than MO-MCEA-w/o-PCSS and MO-MCEA-w/o-APL on 8 and 7 tasks and worse results only on 3 and 3 tasks, respectively, which mean that removing anyone of the PCSS and APL will degrade the performance of MO-MCEA. Therefore, it can be concluded that both PCSS and APL have their contributions to the great problem-solving ability of MO-MCEA.

To study the influence of the key parameter in MO-MCEA, i.e., G, we compare the original MO-MCEA(G = 25) with its variants using different G, i.e., G = 1, G = 5, G = 10, G = 15, G = 20, and G = 30. For simplicity, these variants are denoted as MO-MCEA(G = 1), MO-MCEA(G = 5), MO-MCEA(G = 10), MO-MCEA(G = 15), MO-MCEA(G = 20), and MO-MCEA(G = 30).

Table 4 provides the comparison results, which show that different MO-MTOPs may favor different G. As can be seen, the best MSS values in solving different MO-MTOPs are from different MO-MCEA variants and none of the variants can obtain the best MSS on all problems. Besides, the original MO-MCEA(G = 25) is shown to be more promising. Based on the Wilcoxon’s rank sum test, MO-MCEA(G = 25) obtains significantly better results than MO-MCEA(G = 1) and MO-MCEA(G = 5) on 9 and 5 tasks, and worse results only on 3 and 1 task(s), respectively. Also, the MO-MCEA(G = 25) can obtain similar results on most MO-MTOPs when compared with MO-MCEA(G = 10), MO-MCEA(G = 15), MO-MCEA(G = 20), and MO-MCEA(G = 30). In addition, although the MO-MCEA(G = 25) obtains the best MSS on 1 problem, while the MO-MCEA(G = 1) can get the best MSS on 2 problems, the MO-MCEA(G = 25) significantly outperforms MO-MCEA(G = 1) on highly intersection problems, e.g., MO-MTOP1 to MO-MTOP3. Therefore, G = 25 is in general a more promising setting for MO-MCEA and is recommended in this paper.

This part further investigates the problem-solving ability of the proposed MO-MCEA on MO-MTOPs with more than two tasks. For this, four additional problems with three tasks (i.e., MO-MTOP7 to MO-MTOP10) are developed based on the MO-MTOP1 to MO-MTOP6, where the problem characteristics can be seen in Table 5. The experimental settings are the same as those in previous experiments, with the FEs for each task as 5 × 10³ (1.5 × 10⁴ in total). In addition, the total population size of both MO-MCEA and MO-STEA is 50 (because they handle one evaluation function every time), while the total population size of MO-MFEA, MO-MFEA-II, and MO-EMTA are all 150.

Experimental results of the five algorithms over 30 runs are compared in Table 6. Table 6 shows that the MO-MCEA can obtain the best MSS value on two MO-MTOPs with high similarity (i.e., MO-MTOP7 and MO-MTOP8) and MO-EMTA gets the best MSS value on two MO-MTOPs with low similarity (i.e., MO-MTOP9 and MO-MTOP10), while other algorithms cannot gain the best MSS value on any of the four tested problems. This may be due to that MO-MCEA can treat MO-MTOP with high similarity as MO-MCOP properly and solve it efficiently. Moreover, the Wilcoxon’s rank sum test reflects that the MO-MCEA can significantly outperform MO-MFEA, MO-MFEA-II, MO-EMTA, and MO-STEA on 7, 8, 6, and 8 of the 12 tasks, and only has worse performance on 3, 4, 5, and 4 tasks, respectively. Based on the above, the experimental results have verified the effectiveness of the MO-MCEA on MO-MTOPs with three tasks.