JAIT

I.INTRODUCTION

Because of the advantages of high efficiency and easy implementation, evolutionary algorithms (EAs) have been widely used in various optimization problems.[1], solving scheduling problems [2], intractable constraint problems [3], multi-objective optimization (MOO) [4], combinatorial optimization [5], big data [6,7], image classification [8], etc. In recent years, more and more researchers have used EAs to solve difficult problems in different research scenarios. Although the evolutionary algorithm has many advantages, it also has two limitations: it falls into local optimums and it is difficult to generalize. Multitask optimization (MTO) method can solve the above problems well. Through the knowledge transfer between different tasks, the generalization ability is effectively improved. At the same time, the knowledge of other tasks can be used to explore potential areas more effectively, improve the possibility of searches, and find the optimal solution to the current task.

Evolutionary multitask optimization (EMTO) has been widely used in feature selection, point cloud registration, sparse reconstruction, dynamic programming, and combinatorial optimization. EMTO could fully explore the search space of the current task by utilizing the search experience of other tasks, so it had good generalization ability[9]. At the same time, it could still have a good effect when dealing with data loss, and it was widely used in real scenes[10].

EMTO uses the implicit parallelism between tasks to transfer the common knowledge of different tasks, uses the effective knowledge of other tasks as potential search solutions, extracts the knowledge between different tasks, and optimizes multiple tasks simultaneously through the common knowledge. Evolutionary multitasking has flexible representation methods and different implementations. For different problems, we can design unique knowledge transfer strategies and coding methods and use the knowledge between tasks to effectively deal with the problems to be solved.

In this paper, EMTO [11–13] is studied in detail, and its solution procedure in various real-world application domains is explored. Due to the combination of MTO and an EA and its good performance, there has been a lot of research in recent years. First of all, this paper will explore the existing research of EMTO and summarize its different methods and effective improvements. Then, according to different application scenarios, we comprehensively summarize how MTO and EAs can solve problems in different scenarios. It is more convenient to understand the most advanced MTO research field and how to use MTO to solve problems. Compared with other papers, this paper studies the latest applications and methods of multitask EA. The main contributions of this paper are as follows:

(1)We introduced the basic theory of EMTO and the most advanced improvement strategies.
(2)We summarized how to use EMTO to effectively solve target problems in popular fields and explored why to use MTO in these scenarios.
(3)We introduce the challenges and potential research trends for existing EMTO problems.

The remaining parts of this paper are organized as follows. Section II introduces the principle of EMTO and potential improvement methods. Section III summarizes which scenarios of EMTO have been applied and how to use them for optimization. The challenges of EMTO and future research methods are described in Section IV. Finally, Section V summarizes the work presented in the work.

II.EMTO FUNDAMENTALS

We all know that very few problems stand alone in the real world. Questions are often interrelated and contain a lot of implicitly useful information. The information can further promote each other’s problem-solving process so that multiple problems can be solved efficiently at the same time [14]. Inspired by multitask learning [15] and the working principle of the human brain [16], the idea of multitasking was first introduced into the field of optimization by Gupta et al. in 2016 [17], and a new research problem called the MTO problem was described in the field of evolutionary computing. This enables two important problems (i.e., stuck in local optimums and difficult to generalize) in traditional EAs to be effectively solved. On this basis, the MTO problem is solved by using population-based optimization algorithms (e.g., EA), and thus the concept of EMTO is proposed. In recent years, more and more researchers have paid attention to EMTO and proposed many improved algorithms. Therefore, this section first briefly introduces the basic concepts of EMTO. Subsequently, the existing state-of-the-art improved algorithms of EMTO are summarized and analyzed.

A.THE OVERVIEW OF EMTO

In the field of evolutionary computing, previous research was roughly divided into two categories: 1) single-objective optimization (SOO) problems [18] and 2) MOO problems [4,19] The SOO problem obtains the optimal solution by optimizing a scalar fitness function, while the MOO problem obtains the optimal solution by optimizing a vector fitness function. Different from SOO and MOO, EMTO was an emerging research problem proposed in recent years that aims to utilize the synergistic facilitation between tasks to potentially facilitate information transfer, thereby promoting the optimization process of multiple tasks and achieving the simultaneous and efficient solution of multiple optimization tasks [10]. Specifically, the EMTO problem with $K$ single-objective minimization optimization tasks is considered, each with its own specific search space. It can be described in the following form:

x_{k}^{*} = arg \min_{x \in Ω_{k}} f_{k} (x), k = 1, 2, \dots, K - 1, K

(1)

where

x_{k}^{*}

is the optimal solution of task

T_{k}

in its specific search space

Ω_{k}

and

f_{k} (¯)

is the objective function of task

T_{k}

. By minimizing them, a set of globally optimal solutions

{x_{1}^{*}, x_{2}^{*}, \dots, x_{K}^{*}}

for

K

tasks can eventually be found.

Multifactorial optimization (MFO) is an EMTO paradigm that aims to achieve efficient solutions to EMTO problems using a single evolutionary population. In MFO, each individual focuses on only one task. Each task acts as an independent factor affecting individual evolution in the process of multitask evolution. Before evolution, these specific search spaces $Ω_{k}$ were first encoded into a unified search space $Y$ for representation. Then, the population is evolved through an information sharing strategy within and between tasks. Finally, individuals need to be decoded into the original search space before being evaluated. To evaluate the performance of individuals in multitask scenarios, the following four important properties are defined for each individual:

•Factorial cost: The factorial cost $ψ_{j}^{i}$ of individual $x_{i}$ on task $T_{j}$ is defined as the objective function value obtained by $x_{i}$ on this task, i.e., $ψ_{j}^{i} = f_{j} (x_{i})$ .
•Factorial rank: The factorial rank $r_{j}^{i}$ of individual $x_{i}$ on task $T_{j}$ refers to the sequence number of individual $x_{i}$ after the factorial cost of all individuals on task $T_{j}$ are arranged in ascending order.
•Skill factor: The skill factor $τ_{i}$ of individual $x_{i}$ is defined as the sequence number of the task with the smallest factorial rank of individual $x_{i}$ among all tasks, i.e., $τ_{i} = {argmin}_{j \in {1, 2, \dots, K}} {r_{j}^{i}}$ , which means that the individual performs best on task $τ_{i}$ .
•Scalar fitness: The scalar fitness $ϕ_{i}$ of individual $x_{i}$ is defined as the reciprocal of the best factorial rank, i.e., $ϕ_{i} = 1 / {min}_{j \in {1, 2, \dots, K}} {r_{j}^{i}}$ .

Among them, the skill factor is a cultural characteristic that can be obtained by imitating parents. Scalar fitness is a unified indicator for judging the pros and cons of individuals in multitask scenarios, and it can directly compare the performance of individuals. The comparison method is as follows: given two individuals $x_{a}$ and $x_{b}$ , if $ϕ_{a} > ϕ_{b}$ , it is considered that the individual $x_{a}$ dominates the individual $x_{b}$ in a multitask scenarios, and this dominance relationship is expressed as $ϕ_{a} ≫ ϕ_{b}$ .

Gupta et al. also implemented the MFO paradigm by using the genetic algorithm [20] and proposed a multifactorial evolutionary algorithm (MFEA) [17]. The algorithm was inspired by the biological hereditary traits that depend on the interaction between the two factors of genes and culture [21], and two strategies (assortative mating and vertical cultural transmission) are designed to realize it. In addition, there are some works dedicated to utilizing other population-based optimization algorithms to implement the MFO paradigm. For example, Feng et al. [22] pioneered the use of the differential evolution algorithm and the particle swarm optimization algorithm to realize MTO by designing a new effective assortative mating and proposed MFDE and multifactorial particle swarm optimization (MFPSO). Aiming at the problem that MFPSO only explored a relatively narrow area, Tang et al. [23] devised the inter-task learning-based knowledge transfer strategy to replace the inter-task information exchange in MFPSO. Zhong et al. [24] used genetic programming to implement the MFO paradigm for the first time and proposed a new multifactorial genetic programming (MFGP) algorithm. Xu et al. [25] used the fireworks algorithm to achieve MTO and proposed a new multitask fireworks algorithm. This method mainly designs a transfer spark with adaptive length to help transfer useful information between different tasks.

B.THE IMPROVED ALGORITHMS OF EMTO

With the continuous improvement of the scale and complexity of the problem to be optimized, the traditional MFEA has some shortcomings that are not suitable for problem-solving. To address these shortcomings, some works were dedicated to designing more efficient knowledge transfer strategies in order to further improve optimization performance [26–29]. Zheng et al. [30] improved on the basis of the traditional MFEA knowledge transfer strategy and designed an EMTO algorithm that could continuously and dynamically adjust the degree of knowledge transfer, called SREMTO. This algorithm could automatically adjust the degree of knowledge transfer across tasks according to the changing similarity of the search process, which promoted the efficient sharing of mutually beneficial information between tasks. In order to solve the serious impact of negative knowledge transfer in the search process, Bali et al. [31] proposed a new data-driven EMTO algorithm framework, i.e., MFEA-II. It can track the similarity between different tasks in real time through online learning and automatically control the degree of knowledge transfer between different tasks, which greatly enhances the performance of traditional MFEA. Xu et al. [32] proposed a multitask evolutionary algorithm multifactorial differential evolution with variable transformation (MFDE-VT) in which a variable transformation strategy and an inverse transformation were designed. The effectiveness of knowledge transfer is further improved by transforming the estimated optimal solutions for each task from the original search space to the vicinity of the center of the unified representation space. Ding et al. [33] designed two strategies: decision variable translation and decision variable shuffling. Based on the improvement of MFEA, a new generalized multifactorial evolutionary algorithm (G-MFEA) is proposed, which realizes the transfer of knowledge from computationally simple problems to computationally complex problems and promotes the solution of expensive optimization problems.

III.THE APPLICATION OF EMTO

As a new research direction in the field of evolutionary computing, EMTO has received extensive attention since it was proposed. It has powerful capabilities for simultaneous multitask processing and cross-domain optimization and has great potential for dealing with complex problems in multitask scenarios. In addition, the MTO algorithm has strong generalization ability and can make full use of the knowledge between different tasks to optimize its own tasks. By utilizing potentially useful knowledge among multiple tasks, the optimization process of multiple tasks can be facilitated, and better optimization results can be achieved. In recent years, it was widely used to solve various complex problems in the real world [34–37]. This section will conduct a detailed summary and analysis of the relevant applications of EMTO from the following aspects.

A.FEATURE SELECTION PROBLEM

Feature selection is an important issue and the basis for subsequent classification operations. There are many challenges in direct feature selection for high-dimensional data due to the curse of dimensionality. There were already a large number of methods for solving feature selection [38,39], such as using mathematical methods [40] and EAs [41]. The characteristics of EMTO can be better used to solve the problem of feature selection, and it was widely used in feature selection and has shown strong potential [42].

Liu et al. [43] proposed a multitask feature selection method based on graph clustering. The impact of negative knowledge transfer for irrelevant tasks is reduced through the method of graph clustering feature sharing. The method performs feature selection on multiple tasks by solving the task grouping structure and using a graph-guided regularization framework. This method uses Pearson’s correlation coefficient to calculate the correlation between different tasks, fully considers the relationship between tasks, and conducts a theoretical analysis of the model.

Chen et al. [44] proposed a high-dimensional feature selection method based on multitask particle swarm optimization. One task focuses on a more promising subset of features, while the other focuses on the full set of features. Knowledge transfer is realized by allowing individuals to choose the optimal position of another task under a certain probability to generate offspring. Finally, better solutions can be found in areas with more potential.

Jiao et al. [45] proposed a method to solve multi-objective feature selection using multitask. The two goals of this method are accuracy and the number of selected features, and an adjustment mechanism based on direction vector is proposed. The direction vector refers to the weight of the two tasks and then adjusts the direction vector of the single-objective solution according to the multi-objective solution. The diversity of the population is improved by taking the optimal solution of a single objective as the exploration space of multiple objectives, and at the same time, the similarity of subsets is fully considered according to the Hamming distance between feature subsets to reduce unnecessary search space.

B.POINT CLOUD REGISTRATION PROBLEM

The point cloud registration problem [46] is an important research direction in point cloud data processing, which aims to find a rigid transformation parameter so that the source point cloud can be aligned with the target point cloud. When faced with multi-view registration problems and point cloud data registration problems containing a lot of noise and outliers, traditional methods are usually difficult to solve and have poor robustness. In recent years, EMTO has been used to solve difficult problems in point cloud registration and has shown strong advantages.

Wu et al. [47] proposed an evolutionary multitask approach for solving the problem of multi-view point cloud registration, called multiform point cloud registration (MTPCR). They modeled the multi-view registration problem as a MTO problem to solve. Among them, a bi-channel knowledge sharing strategy was mainly designed in detail, and an objective function considering local accuracy and global consistency is established. Intra-task knowledge sharing could speed up the optimization process by enabling information transfer between auxiliary tasks and the original task. Inter-task knowledge sharing avoids getting stuck in local optima by exploring the commonalities among the original tasks. By utilizing the transformation information between multiple sets of point clouds, the multi-view registration problem could be better solved.

In order to simultaneously solve the problems of poor robustness and falling into a local optimum in point cloud registration methods, Wu et al. [48] proposed an EMTO-based point cloud registration method. The method first constructs two related tasks, one focusing on registration accuracy and the other focusing on registration robustness. Then, a two-stage bidirectional knowledge transfer strategy is designed to achieve efficient information sharing between tasks. This method can guarantee its robustness while guaranteeing accuracy.

Wu et al. [49] proposed an EMTO method with solution space cutting to solve the local optimum problem in point cloud registration, called evolutionary multi-task registration with solution space cutting (EMTR-SSC). This method used one task to search for potential transformation information in the cut space to help the complex task jump out of local optima, thereby further improving the success rate of registration. Furthermore, a sparse-to-dense strategy was devised to reduce the computational cost of redundancy. An objective function that is robust to various overlap rates is proposed. Therefore, the registration method has very remarkable performance in terms of accuracy and success rate.

C.SPARSE RECONSTRUCTION PROBLEM

In real life, the sparse reconstruction problem widely exists in computer vision, pattern recognition, signal processing, and other fields. This problem aims at finding sparse solutions to large-scale systems of underdetermined coefficient equations, and it was shown to be a non-convex optimization problem and a difficult non-deterministic polynomial (NP) problem [50]. To solve the sparse reconstruction problem, traditional methods used greedy algorithm [51], relaxation theory [52], and MOO algorithm [53]. However, the above algorithms or theories all focus on solving the sparse reconstruction problem of single measurement vector (SMV), but there is no corresponding solution for the sparse reconstruction problem of multiple measurement vector (MMV). In practical applications, it is often the case that multiple sparse reconstruction tasks are to be processed simultaneously, and these different tasks often have similar sparse features. Based on the above analysis, Li et al. [54] extended the EMTO framework and proposed a new multitasking sparse reconstruction (MTSR) framework. This method uses a single population to simultaneously optimize multiple sparse reconstruction tasks and effectively solves the SMV and MMV sparse reconstruction problems in a multitask environment. MTSR makes full use of the similar sparse features between different sparse reconstruction tasks and performs knowledge transfer within and between tasks among candidate parent individuals, which greatly improves the convergence speed of the algorithm. In addition, they took the sparse unmixing problem of hyperspectral images as a practical case of sparse reconstruction problems and applied the MTSR framework to this problem, proving the efficiency of the proposed method for solving sparse reconstruction problems.

The problem of reconstructing complex networks from time series plays an important role in the design of collective dynamics control systems. For the complex network reconstruction problem (NRP), converting it into a sparse reconstruction problem and then using a convex optimization algorithm to solve it is currently the most popular method in academia. However, the existing algorithms used to solve this problem only focus on the learning process of a single network and have not tried to use the similar structural features between networks for transfer learning. Since there are often other networks with similar feature patterns to the network of interest in practical applications, making full use of the similar information between these different network reconstruction tasks can greatly improve the accuracy and efficiency of network reconstruction. Based on the above motivations, Shen et al. [55] proposed the MFEA-Net algorithm. This method attempts to use the EMTO algorithm to solve the sparse reconstruction problem transformed from the NRP and simultaneously carry out the learning and reconstruction processes of two networks on the same evolutionary population. MFEA-Net regards each NRP as a separate SOO task and uses MFEA to directly solve this difficult NP problem of non-convex optimization. This solution replaces the traditional method of converting the sparse reconstruction problem into a convex optimization problem and then solving it. At the same time, MFEA-Net designs an online learning strategy. This strategy utilizes the population information continuously generated during the optimization process to continuously learn the transfer matrix, which not only alleviates the adverse effects of negative knowledge transfer but also avoids manual parameter adjustment. In addition, MFEA-Net also used the least absolute shrinkage and selection operator [56] to initialize the population, which speeds up the convergence speed of the algorithm.

D.DYNAMIC SCHEDULING PROBLEM

Dynamic schedule (DS) problem is a widely used problem, such as workshop scheduling [57–59], computer internal resource management scheduling [60–63], and resource scheduling on cloud computing [64]. There are many methods to solve DS problems. EA has been widely used to solve DS problem because of its powerful search ability. At the same time, due to the poor generalization ability of a single EA, EMTO is introduced into the solution process of DS problems, which can maintain the solution ability of the algorithm and have a strong generalization ability.

Zhang et al. [65] proposed a method to solve DS problem based on multitask GP tree, which improved the traditional multitask framework according to the characteristics of genetic programming. First of all, it is no longer necessary to evaluate the proficiency factor of all individuals during initialization. Second, in order not to waste resources on the evaluation of the parent individual again, it is no longer necessary to mix the parent and child, and only the child individuals are evaluated. Finally, the number of individuals is kept the same for each task, which reduces the computational cost. This algorithm successfully applies multitasking to complex DS problems and proposes a new multitasking framework based on GP. The proposed algorithm is more robust and improves the quality of solution.

Zhang et al. [66] proposed a new agent-assisted multitask GP method. It can significantly improve the effect of heuristic algorithms in different scenarios and can effectively solve problems for different evolutionary scheduling heuristic algorithms. This method mainly uses a feature to determine the scheduling behavior and designs an agent for each task to be solved. This agent is used to improve the efficiency of problem-solving while transferring knowledge to promising individuals, which can efficiently share knowledge among different tasks.

In order to solve the multi-objective problem in the DS problem, Zhang et al. [67] proposed a multitask and multi-objective GP method based on multi-population, which can effectively share knowledge for different tasks and generate better individuals at the same time and can find Pareto frontier faster. This algorithm is different from the traditional multitask algorithm. It uses multi-population to solve different tasks and realizes knowledge sharing through crossover operators in the population. It improves the quality of solution by improving the diversity of individuals.

E.COMBINATORIAL OPTIMIZATION PROBLEM

Due to its simple implementation and powerful search ability, EAs can obtain robust solutions without too much prior knowledge, and they have been successfully applied to combinatorial optimization problems. However, traditional EAs only solve one task at a time. On complex networks, there will be multiple combinatorial optimization tasks to be solved at the same time. In order to solve this problem, a MTO algorithm is introduced to efficiently solve several combinatorial optimization problems at the same time.

Yuan et al. [68] proposed a new evolutionary computing method based on MTO algorithm, introduced a new unified coding method and a new survivor selection method to make MTO better applied to combinatorial optimization problems. The method is tested on four problems: traveling salesman problem, quadratic assignment problem, linear scheduling problem, and job shop scheduling problem. Through the unified search space, the efficiency of knowledge transfer between different tasks is improved. At the same time, the generated individuals are ranked according to skill factors according to the new individual selection mechanism. Only a part of individuals are selected for each ranking level to evaluate their fitness, reducing the computational cost. In the test tasks, although there are still some negative knowledge migration, most multitasking processing is still effective compared with single task.

Zhou et al. [69] proposed an evolutionary multitask approach to vehicle routing problem in combinatorial optimization. Because the direct application of MFEA to the vehicle routing problem may lead to the problem of invalid decoding, which reduces the performance of MFEA, a replacement-based identical representation method and a splitting-based decoding operator are proposed to solve this problem. This method obtains the actual solution by removing the extra dimension whose value is greater than the given dimension value. At the same time, the solution of the unified search space is converted into the actual solution space using the splitting-based decoding operator.

Feng et al. [37] proposed a method based on explicit EMTO, which can better transfer knowledge than traditional implicit MTO. This method constructs a sparse mapping between two tasks by building a weighted $l_{1}$ norm regularization reconstruction error from one vehicle routing task to another, which can effectively transfer knowledge between different tasks. Then, it calculates the distance matrix between tasks through the optimized vehicle routing problem solution to transfer knowledge and then uses this knowledge to assist the target search process. This method effectively improves the efficiency of computation by showing the evolutionary multitasking and enriches the similarity measurement between tasks.

IV.FUTURE RESEARCH DIRECTIONS AND CHALLENGES

EMTO method is a research hotspot in recent years. Since it was proposed in 2016, EMTO has received extensive attention from researchers. This paper summarizes the use and improvement of EMTO, as well as the extensive application of EMTO in various fields. Happily, the basic theories and applications in the field of MTO have developed rapidly in recent years and have been well applied to many research fields to solve practical problems [37, 70–73]. Compared with the original method, it has a better effect. However, EMTO is still in its infancy and needs to solve some problems and challenges. This section will explore some future research trends and challenges of EMTO.

(1)More complete theoretical supportThe current research on EMTO does not fully explain its theoretical basis, such as how to transfer knowledge, what knowledge to transfer, and the impact of negative transfer on the evolution process. With the answers to these questions, we can design more reasonable methods for the problems encountered in the future, apply them to a wider field, and improve the performance of the design algorithm.
(2)Reduce the impact of negative transferIn the process of evolution, not all the knowledge transferred by other tasks is effective for solving the current task. How to reduce the impact of negative transfer of other tasks is a very important problem, which will seriously affect the effect of the solution. A method based on task function image to consider task relevance is proposed, but theoretical research on negative transfer effects is still needed.
(3)Reduce the high cost of computingFor EMTO, the current mainstream research focuses more on the improvement of the accuracy of the current task after knowledge transfer but does not take into account the additional cost of computing. Now, there have been studies focusing on the use of low-cost tasks to assist in solving high-cost tasks [35,71]. However, it does not analyze whether multitasking is effective at the same cost of computing resources. A MTO method is still needed to effectively solve the computational cost.
(4)Performance indexRefs. [73,74] have proposed some performance indicators for multiple objectives, but this method based on comparison and voting may conflict in some cases. In order to solve the averaging problem under multiple objectives, a more reasonable performance index should be designed.
(5)Improved performance and efficiencyIn the face of more complex problems, the performance and efficiency of EMTO still need to be further improved. The current algorithms still have some problems when dealing with large-scale tasks in the face of complex scenes, such as more efficient adaptive knowledge transfer management strategy, more effective coding scheme and the unified space of multiple tasks, and more reasonable design of crossover and mutation operators between different individuals. For the above problems, many researchers have provided many solutions, but for more complex and difficult scenarios, the results are still not satisfactory.
(6)More applicationsEMTO still needs to expand its application scope, like the medical field [75]. Compared with practical engineering applications and cutting-edge technical fields, EMTO is more focused on solving academic research problems. Only by creating practical economic value in practical applications can more researchers be engaged in research in this field. At the same time, the application of specific practice also needs further improvement of the theory. The two complement each other and jointly promote the improvement of EMTO theory and practice.

V.CONCLUSIONS AND OUTLOOK

In this review, the principle of EMTO was comprehensively introduced, and the popular fields of EMTO in current research and how to use EMTO to solve problems were summarized. Finally, the remaining challenges and future research trends of EMTO were analyzed. EMTO has effectively solved some problems existing in EA, improved the effect of EA, and has been widely used. A more comprehensive summary of the most advanced methods is needed. There are also some unique techniques to be noted in different scenarios, which can improve the performance of the algorithm more effectively.

With the continuous development of EMTO, it has occupied a more important position in the academic and industrial circles. It requires continuous efforts of researchers to break through the existing challenges, continuously improve the performance of the algorithm, and make EMTO play a greater role in the future.

Evolutionary Multitask Optimization in Real-World Applications: A Survey