A multitask optimization algorithm based on elite individual transfer

1.   Introduction

Multitask optimization (MTO) solves multiple optimization tasks simultaneously in the evolutionary algorithm to improve the performance of solving each task independently via intertask knowledge transfer ^[1,2]. Without loss of generality, an MTO can be expressed as ^[3,4]:

where $f_{k}({\bf x}_{k})$ is the objective function of $k$th optimization task, and ${\bf x}_{k} = (x_1, x_2, ..., x_{D_{k}})\in R^{D_{k}}$ is a $D_{k}$-dimensional decision variable in space $R$. In other words, each optimization task is to solve the minimum optimization problem of an objective function. Single-objective multitask optimization problem aims to solve multiple single-objective problems at the same time by sharing common features that are beneficial to make a faster convergence between related tasks, which greatly improves the efficiency of the algorithm ^[5,6,7]. Moreover, some difficult single-objective problems can also be solved effectively by employing the correlation between optimization tasks.

Many problems in the real world can be regarded as single-objective multitask optimization problems ^[8]. For instance, a multi-population-based evolutionary multitasking optimization algorithm is presented for dynamic flexible job-shop scheduling in ^[9]. A task-oriented knowledge-sharing strategy is presented and achieves good performance by maintaining the quality and diversity of individuals for corresponding tasks well. A multitasking harmony search algorithm is proposed for detecting high-order single nucleotide polymorphisms epistatic interactions in ^[10]. A unified coding strategy is adopted for multiple tasks. A multifactor genetic programming framework is presented in ^[11] for solving symbolic regression problems. A knowledge adoption-based evolutionary multitask algorithm is presented for the profitable tour problem in ^[12]. Evolutionary algorithms have been successfully applied to solve a variety of single- and multi-objective optimization problems ^[13,14]. Because of the good application prospects of multitask optimization, researchers have focused on this problem and developed various efficient multitask optimization algorithms in recent years ^[15,16].

Leveraging task correlation to improve search efficiency is a critical problem in evolutionary multitasking algorithms. Meanwhile, many pieces of research have been on enhancing the positive transfer and reducing the negative transfer of evolutionary multitasking algorithms. Through the above discussion, these algorithms can be roughly divided into three categories according to the way of task collaboration: domain adaptation, individual transfer and knowledge transfer-based algorithms ^[17].

Domain adaptation-based methods ^[18] map the search spaces of the source task and the target task into a unified search space to enhance the positive transfer of the evolutionary multitask algorithms. For instance, the multi-factor evolutionary optimization algorithm (MFEA) ^[19] is one of the most representative algorithms in this category that transfers knowledge between tasks through the unified space and transfers useful genetic information from one task to another. A novel evolutionary multitasking algorithm based on subspace alignment is proposed in ^[20]. Similarly, a mapping matrix obtained by subspace learning is used to transform the search space of the population and reduce the probability of negative knowledge transfer between tasks. Lately, Liu et al. ^[21] proposed a discriminative reconstruction network model that is used to transfer useful knowledge during the reproduction of offspring. It can enhance the quality of learned knowledge to promote positive transfer. However, realizing space alignment and mapping the search spaces of multiple tasks into a unified search space is still a very challenging problem. Meanwhile, the computing cost of the domain adaptation-based methods should be noticed.

Knowledge transfer-based algorithms share some parameters of prior distributions of hyperparameters ^[22,23,24] to realize knowledge transfer between optimization tasks, which are easy to execute. What knowledge, namely parameters, is transferable is a key issue for knowledge transfer-based algorithms ^[25]. Therefore, a new knowledge transfer strategy based on inter-task gene similarity is proposed in ^[26]. It can perform more fine-grained and accurate knowledge transfer. An adaptive scheme combining transfer learning with evolutionary methods is presented for expensive problems in ^[27]. It reuses knowledge by sharing a Gaussian process model. However, the above strategies are pretty time-consuming. Hence, a gradient-free evolutionary multitask algorithm (MTES) ^[28] is designed based on a multitasking gradient algorithm (MTGD) to overcome the defect. The evolutionary single-task strategy (ES) has an approximate gradient decline, and MTGD also has a fast decline rate. Therefore, MTES has a faster convergence rate. Paper ^[29] proposed a knowledge transfer strategy based on local distribution estimation (LEKT). However, these algorithms will likely get stuck in a local optimal solution when dealing with multimodal problems.

Individual transfer-based algorithms aim to transfer some solutions from source tasks to target tasks to enhance the convergence speed of the target tasks ^[30]. For instance, a decision variable translation strategy and a decision variable shuffling strategy are proposed in ^[31] for solving expensive optimization problems. Recently, a self-adaptive multitask evolutionary algorithm is proposed in ^[32]. It adaptively adjusts the transfer rate of the population to reduce the harm of negative transfer and balance the diversity and convergence within the population. In paper ^[33], two multitasking optimization algorithms of Multifactorial Optimization (MFO), popular particle swarm optimization (MFPSO) and differential evolution search (MFDE), are proposed to explore the versatility of MFO in multitasking optimization. There are also some algorithms in this category proposed to solve multi-objective problems, and a transfer rank is defined in ^[34], which quantifies the priority of transferred solutions to improve the probability of a positive transfer. Transferred solutions are selected from the neighbors of solutions that achieved the positive transfer in ^[35], and an incremental learning method is used to select the transferred solutions in ^[30]. An effective transferred solutions selection mechanism is essential for enhancing the convergence characteristic of their target tasks. Most individual transfer-based algorithms randomly select individuals to be transferred, and the main focus is on when to transfer and how many individuals are to be transferred. There is a lack of research on which individuals are to be transferred. Also, reducing the notorious negative transfer of these algorithms should also be treated cautiously.

In addition, to improve the effectiveness of the knowledge transfer, an evolutionary multitasking optimization algorithm based on a multi-source knowledge transfer mechanism (EMaTOMKT) ^[36] uses adaptive mating probability (AMP) strategy to determine the probability of knowledge transfer and uses task selection (MTS) strategy based on maximum mean discrepancy (MMD) ^[29] to select multiple similar tasks as learning sources. ^[37,38] proposed a new evolutionary multitasking algorithm with two-stage adaptive knowledge transfer based on population distribution. A novel method of extracting and transferring knowledge is proposed to reduce the probability of generating negative transfer. A task selection strategy ^[39] based on credit assignment is to select a task for knowledge transfer by leveraging the feedback from the transferred solutions across tasks. In MaTEA ^[40], an adaptive mechanism is used to select the auxiliary tasks to achieve knowledge transfer between tasks. This adaptive mechanism is realized by dynamically measuring the similarity between tasks and analyzing the effectiveness of knowledge transfer between tasks.

Aiming to execute more effective and robust knowledge transfer between various optimization tasks, we propose a single-objective multitask optimization based on elite individual transfer, namely, MSOET, in this paper. Considering the effectiveness of the algorithm EMaTOMKT ^[36] in solving the single-objective many-task problem, this paper quotes the idea of using the parameters of the Gaussian distribution model to generate offspring to achieve knowledge transfer. We borrow this idea to enhance the global search ability of the algorithm. However, unlike how EMaTOMKT directly employs the clustering technique and the estimation of distribution algorithms to generate the offspring, the core of the MSOET is selecting the appropriate auxiliary tasks and transferring the common features of the elite population selected from auxiliary tasks. To improve the positive transfer probability between optimization tasks, in this paper, only the individuals in the transfer population which are better than the optimal individuals in the target population are selected for knowledge transfer. The main contributions of this paper are as follows.

● Select the individuals in the transfer population for transfer: Select the individuals which are better than the target tasks for transfer, which can improve the efficiency of knowledge transfer.

● The elite individuals transferred from the auxiliary tasks are combined with the current population to build a Gaussian distribution model, which can guide the population to converge faster and help to enhance the robustness of the algorithm, to produce offspring individuals.

The rest of this paper is organized as follows. Section 2 introduces the proposed algorithm framework. In Section 3, we experimentally compare MSOET with ten evolutionary multitask optimization algorithms on nine test instances. Finally, Section 4 concludes this paper.

2.   The proposed multitask optimization based on elite individual transfer

In this section, we first give the overall framework of the proposed MSOET algorithm and then present a detailed description of the elite knowledge transfer strategy. Finally, we provide an analysis of the proposed algorithm.

2.1.   The framework of the proposed algorithm

First, different tasks may have different search spaces. The search space of all tasks is mapped to a unified search space according to Eq (2.1).

where $x_{ki}$ is the value of solution ${\bf x}$ on the $i$-th dimension of $k$th task, and $U_{ki}$ and $L_{ki}$ are the upper and lower bounds on $i$-th dimension of $k$-th task, respectively. $y_{ki}$ is the value mapped from $x_{ki}$ to the unified search space. After such a transformation, the search space of all tasks is unified to $[0, 1]^{D}$, where $D = \max\limits_{1\leq k\leq K}\{D_{k}\}$. Thus, without loss of generality, we assume that all tasks have the same search space $X = [0, 1]^{D}$. Moreover, a skill factor is introduced for each individual to facilitate the assignment of fitness values and the comparison of individuals ^[19]. The skill factor $\tau_{i}$ of $p_{i}$ is one of the component tasks, where $p_{i}$ achieves the best rank among all tasks, that is,

where $r_{ik}$ is the factorial rank, which is the index of $p_{i}$ in the list of population members that are sorted in ascending order according to the value of the objective function $f_{k}$ of the $k$th task.

The framework of the proposed MSOET is given in Algorithm 1. The flowchart of this algorithm is shown in Figure 1. First, we randomly initialize the population $P = \{P_{1}, \cdots, P_K\}$ with a size of $N$ in the unified search space $X$ and set the initial generation $t = 0$. The skill factors of individuals are assigned with a random number $k\in \{1, \cdots, K\}$, and the total number of individuals with skill factors of $k$ is $N$. Record the optimal individual of the current population as $p_k^{best}$, $k = 1, \cdots, K$. The optimal individual of single-objective optimization refers to the individual with the minimum function value in the population. When the termination condition is not satisfied, the probability model of the subpopulation is constructed by Algorithm 2.

Then, choose different ways to produce offspring according to a certain probability $pd$ (the value of $pd$ can be found in the parameter setting part of the experiment). If $rand < pd$, for solution $p_k^j$, two offspring $o_{1}$ and $o_{2}$ are generated by using crossover and mutation on $p_k^j$ and $p_k^r$ which are randomly chosen from $P_{k}$. Otherwise, $o_{1}$ and $o_{2}$ are sampled from a Gaussian distribution model $\mathcal{N}(\overline{x}_k, Cov_k)$, where $\overline{x}_k$ is the mean, and $Cov_k$ is the variance of the Gaussian distribution model obtained by Algorithm 2. $rand$ is a uniform random number in $[0, 1]$. In this way, knowledge transfer between tasks can be realized. The skill factors of $o_{1}$ and $o_{2}$ inherit that of their parents, and then evaluate offspring $o_{1}$ and $o_{2}$ in terms of the corresponding task. Population $P$ and offspring $Q$ are merged, and the best $N$ individuals are selected as the next generation population. Finally, update the optimal individual $p_k^{best}$ of the population. The optimal individual $p_k$ is found. If the function value of $p_k$ is smaller than that of $p_k^{best}$, which means that $p_k$ is better than $p_k^{best}$, then replace $P_k^{best}$ with $p_k$. Otherwise, $p_k^{best}$ remains the same, $k = 1, \cdots, K$.

2.2.   Knowledge transfer strategy based on elite individual transferred

The selection of the transferring individuals is very important to improve the efficiency of the algorithm and avoid negative transfer in multitask optimization. Therefore, we propose a knowledge transfer strategy based on elite individual transfer in this paper. Algorithm 2 is the main innovation of this paper, and the flow chart of Algorithm 2 is shown in Figure 2.

First of all, we find out the population of the source task of each task, which is used for transferring. We calculate the Kendall correlation coefficient of the factorial rank of the population member. The Kendall correlation coefficient is one of the three most famous correlation coefficients in statistics, and it has been applied to a wide range of applications. Hence, we adopt the Kendall correlation coefficient to measure the similarity between tasks.

where $C$ is the number of concordant pairs, and $D$ is the number of discordant pairs. A pair of solutions $(p_{i}, p_{j})$ is a concordant pair with respect to task $k$ and task $l$, if $(r_{ik} < r_{jk}, r_{il} < r_{jl})$ or $(r_{ik} > r_{jk}, r_{il} > r_{jl})$. Otherwise, $(p_{i}, p_{j})$ is a discordant pair. Then, the source task of $k$-th task is given as

Then, the transferring population of $k$-th task is $P_{k}^T = P_{l^{*}}$, and set the skill factor of $P_{k}^T$ to $k$. Then, evaluate population $P_{k}^T$ and all the individuals in $P_{k}^T$ which are better than the current population $P_{k}$ are put into the set $S$. That is, the individuals in $P_{k}^T$ whose objective function value is smaller than the smallest function of $P_{k}$ are put into the set $S$. A new set $P_{k} \cup S$ is obtained by merging the current population $P_{k}$ with the individuals in $S$. A Gaussian distribution model is constructed by the merged population $P \cup S$. The mean $\overline{{\bf x}}_k$ and variance $Cov_k$ of the Gaussian distribution model can be obtained by Eqs (2.5) and (2.6).

where $|P_{k} \cup S|$ is the number of individuals in $P_{k} \cup S$. By doing so, the good individuals in $P_{k}^T$ can help to improve the evolution of the population and enhance the global search ability of the algorithm. Through targeted selection, the offspring sampled from the Gaussian distribution composed of elite individuals and the current population are more likely to have higher quality.

2.3.   Performance analysis of the knowledge transfer based on elite individual transferred

Figure 3 shows the elite knowledge transfer of the proposed MSOET algorithm. The solid black circles on the left of Figure 3 are the current population of Task 1, and the red stars are the elite individual which transferred from Task 2 to Task 1. The black ellipse is the Gaussian distribution model trained by the current population, and the red ellipse is the Gaussian distribution model trained by the current population and elite individuals. The black and red models are recorded as Gaussian distribution models 1 and 2, respectively. The solid black circle on the right of Figure 3 is the current population of Task 2, and the solid red circle is the individual selected for transfer.

From the comparison of Gaussian distribution models 1 and 2, it can be seen that model 2, which is trained by elite individuals transferred from Task 2 and the current population, can produce offspring with better convergence than model 1, so as to accelerate the evolution of the population and improve the performance of the algorithm.

3.   Experimental studies

3.1.   The compared algorithms

We compared the proposed MSOET algorithm with the following ten most advanced evolutionary algorithms. The code for these algorithms is available on the official platform MTO-Platform at https://github.com/intLyc/MTO-Platform.

$1)$ AT-MFEA ^[41] employs domain adaptation technique for solving heterogeneous problems and proposes a novel rank loss function for acquiring a superior intertask mapping.

$2)$ IMEA ^[42] is an evolutionary multitasking optimization framework based on the island model. Information about the individuals on one island is transferred to another island through an inter-island crossover.

$3)$ LDA-MFEA ^[43] proposes a linearized domain adaptation strategy that transforms the search space of a simple task into a search space similar to its constitutive complex task.

$4)$ MFDE ^[33] proposes a multifactorial optimization based on differential evolution and presents a mating approach for multitask optimization in MFDE.

$5)$ MFEA ^[19] represents one of the most widely used implementation paradigms of the evolutionary multitasking optimization algorithms. An implicit genetic transfer strategy presented in this paper can accelerate convergence for a variety of complex optimization problems in a multitasking environment.

$6)$ MFEA-AKT ^[25] proposes a new MFEA with adaptive knowledge transfer, in which the crossover operator employed for knowledge transfer is self-adapted based on the information collected along the evolutionary search process.

$7)$ MFPSO ^[33] proposes a multifactorial optimization algorithm embarking with particle swarm optimization, and a mating approach is designed for multitask optimization in MFPSO.

$8)$ MTEA-AD ^[44] is a multitask evolutionary algorithm based on anomaly detection. The anomaly detection model identifies candidate-transferred individuals that can effectively reduce the risk of negative transfer.

$9)$ MTEA-SaO ^[45] adaptively selects a best-fitting solver for each task and enables knowledge transfer using the implicit similarities between tasks.

$10)$ SOO algorithm is that two tasks evolve separately without communication between tasks.

3.2.   Test problems

The test suite ^[46] is used to evaluate the performance of the proposed MSOET algorithm. This test suite consists of 9 test questions, each containing 2 tasks, and each task is a single-objective optimization problem. The properties of these nine test questions are shown in Table 1. Nine test questions are designed according to the global optimal degree of intersection and the similarity of the fitness landscape. According to the global optimal intersection degree, it can be divided into the complete intersection (CI), partial intersection (PI) and no intersection (NI). According to the similarity of fitness landscape between tasks, it can be divided into high similarity (HS), medium similarity (MS), and low similarity (LS). According to this classification method, nine combinations can be formed and designed, as shown in Table 1.

3.3.   Parameter settings

● Population Size $N$: The population size $N$ of all algorithms is set to 100.

● Termination Condition: The maximum generation of all algorithms is 1000.

● Hybrid Variation Parameter: SBX ^[47] is used as the crossover operator, and polynomial mutation is used as the mutation operator. Among them, $\eta_n$ is set to 2 in SBX, and the variation parameter of polynomial $\eta_m$ is set to 5.

● Number of Runs: All algorithm runs 30 times independently for each test question.

● Private Parameter: The probability $pd$ is set to 0.3 in Algorithm 1.

● The results of the compared algorithms are implemented with the official platform MTO-Platform^* on MATLAB2020b. The algorithm-specific parameters use their default values.

^*https://github.com/intLyc/MTO-Platform

● Statistical Test: The Wilcoxon rank-sum test with a level of 0.05 is used to analyze the significance of the performance between algorithms. The symbols "$\dagger$", "$\S$" and "$\ddagger$" indicate that the proposed MSOET algorithm is inferior, equal and better than the contrasted algorithm, respectively. In addition, in order to compare the algorithms intuitively, the algorithms that perform best in the test problems were marked in bold.

3.4.   Analysis of experimental results

Tables 2–4 show the average function values obtained by the proposed MSOET algorithm and the compared algorithms over 30 independent runs on the test problems. For the sake of intuition, the algorithm that performs best on the test problem is represented with a gray background. The last column of these tables shows the results of the significance analysis of these algorithms. Figures 4–6 plot the average convergence trend of the compared algorithms over 30 independent runs on the test problems. These tables and figures show that the proposed MSOET algorithm performs best in 16 of the 18 tasks. This proves the effectiveness of the proposed MSOET algorithm. The number of "$\dagger$" is far more than that of "$\ddagger$", which also shows that the proposed algorithm has advantages over other algorithms.

This phenomenon is because the proposed MSOET algorithm makes use of the cooperation between tasks to transfer the high-quality individuals of another task to the target task and work with the current population to build a model for generating offspring. Using this model can produce high-quality offspring, accelerate the evolution of the population, and improve the algorithm's performance.

4.   Conclusions

In this paper, we have proposed a new evolutionary single-objective multitasking algorithm based on elite knowledge transfer (MSOET), which can solve multiple single-objective optimization tasks at the same time. MSOET combined the excellent individuals of the transfer population with the current population to construct a Gaussian distribution model and used the calculated mean and variance to generate offspring to achieve knowledge transfer between tasks. The excellent individual can effectively and robustly improve the performance of the algorithm. From the analysis of the experimental part, we can see that compared with the existing ten advanced evolutionary single-objective multitasking algorithms, MSOET has a better convergence effect. We expect to execute more effective and robust knowledge transfer between various optimization tasks, even low-related optimization tasks, in our future works. Meanwhile, we will explore how to execute knowledge transfer on the population level instead of the individual level.

Acknowledgments

This research was funded in part by the National Natural Science Foundation of China (62172110), in part by the Natural Science Foundation of Guangdong Province (2021A1515011839, 2022A1515010130), and in part by the Programme of Science and Technology of Guangdong Province (2021A0505110004).

Conflict of interest

The authors declare that they have no conflict of interest.