Multifactorial evolutionary algorithm with adaptive transfer strategy based on decision tree

As mentioned before, multifactorial optimization (MFO) is an evolutionary multitasking paradigm that aims to find a group of optimal solutions simultaneously, each of which corresponds to an optimization problem. To compare individuals in a multitasking environment conveniently, it is necessary to encode and decode different individuals in a unified search space. For an unconstrained multitasking problem with n tasks, T_j denotes the jth task with a search space X_j and an objective function f_j. For the ith individual p_i, its properties are defined as follows [1]:

MFEA is a pioneer evolutionary algorithm to realize the MFO paradigm, which transfers genes and memes through assortative mating and vertical cultural operation. Algorithm 1 presents the basic framework of MFEA.

The decision tree is one of the supervised machine learning method to multistage decision making [17]. A tree structure is used to present the decision rules summarized from a series of data with characteristics and labels. Generally, a decision tree consists of a root node, some internal nodes and leaf nodes. Leaf nodes are nodes that have no appropriate descendants, while other nodes (except the root) are called internal nodes. Each internal node is associated with a test attribute, each branch represents the outcome of the test, while each leaf node assigns one or more class labels [18, 19]. A path from the root node to each leaf node corresponds to a decision test sequence.

The design of a decision tree mainly includes three tasks [17].

Task 1: Select a node splitting rule.

Task 2: Decide which nodes are terminal.

Task 3: Assign each terminal node to a class label.

Taking the playing dataset as an example, Table 1 shows an instance of playing training dataset, which has fourteen samples. Each sample consists of ID, four attributes and one category label. The attribute consists of weather (a₁), temperature (a₂), humidity (a₃) and whether there is wind (a₄). The category label (L) is whether to play today.

Figure 1 shows the decision tree trained by Table 1. n_i represents the ith node.

Positive knowledge transfer has a significant effect on the performance of multifactorial evolutionary algorithm. In MFEA, the knowledge transfer among tasks is controlled by the parameter rmp. In each task, since the solutions are randomly selected to exchange information based on the same probability, there is a possibility that the transfer turns out to be negative, thereby leading to deterioration of algorithm performance [20, 21]. Therefore, in the case of uncertain correlation between tasks, how to accurately select valuable solutions is core to improve the performance of the algorithm. To solve these problems, this paper proposed an evaluation rule to quantify the transfer ability of individuals involved in knowledge transfer.

Furthermore, the research shows that the decision tree model has the following advantages in the construction process and data processing. First of all, the decision tree uses the knowledge learned from training to directly form a hierarchical structure, which is readable and easy to understand and implement. Secondly, the decision tree is suitable for data sets with small size, and the time complexity of the decision tree algorithm is small. Finally, the decision tree is not sensitive to missing values during data processing. In addition, the decision tree can deal with irrelevant feature data, and can accurately predict the results of analysis with large data sources in a relatively short time. Therefore, in the proposed EMT-ADT algorithm, the decision tree is constructed according to the information of transferred individuals. The number of individuals for each knowledge transfer is set to 10, and five consecutive generations of transferred individuals are used as the training data to construct the decision tree model, which conforms to the characteristics of the decision tree. Based on the constructed decision tree, promising positive-transferred individuals are selected to conduct knowledge transfer between tasks, which can achieve a fast convergence and improve the solution accuracy.

For a population \(P=\{{\mathbf{x}}_{1},{\mathbf{x}}_{2},\dots ,{\mathbf{x}}_{N}\}\), an archive \(\mathrm{A}=\{{\mathbf{t}}_{1},{\mathbf{t}}_{2},\dots ,{\mathbf{t}}_{N}\}\) is used to store individuals involved in knowledge transfer; the historical transferred population \(\mathrm{TP}=\{{\mathbf{t}}_{i}|1\le i\le n\wedge\upomega \left({\mathbf{t}}_{i}\right)>\upomega \left({\mathbf{t}}_{n+1}\right)\}\) is used to store n individuals with the highest knowledge transfer ability in the archive A. Each \({\mathbf{t}}_{i}\) has an associated subset \({\Phi }_{i}\).

For each \({\mathbf{t}}_{i}\in TP\), if \({\mathbf{t}}_{i}\) participates in the generation of offspring \({\mathbf{y}}_{j}\) (recorded as \({\mathbf{t}}_{i}\to {\mathbf{y}}_{j}\)), the associated subset \({\Phi }_{i}\) is defined as follows.

Accordingly, the transfer amount \({\lambda }_{i,j}\) of the jth individual in \({\Phi }_{i}\) is defined as follows:where x_j is the parent of the offspring y_j.

The transfer ability \(\upomega \left({t}_{i}\right)\) of transferred individual \({t}_{i}\) is defined as follows, where u represents the size of subset \({\Phi }_{i}\).

Figure 2 shows an example of the calculation of the transfer ability, where all individuals are in a 2-D decision space.

In Fig. 2, the historical transferred population TP = {t₁,t₂,t₃,t₄,t₅} is composed of five transferred individuals. The performance of the offspring y₁ and y₄ is better than that of the parent, while the performance of the offspring y₂ and y₃ is worse than that of the parent. t₁ and t₃ participate in the generation of offspring y₁. t₂ and t₄ participate in the generation of offspring y₂. t₄ and t₅ participate in the generation of offspring y₃. t₂ and t₃ participate in the generation of offspring y₄. Since t₁ only participates in the generation of offspring y₁, and y₁ is superior to the parent, according to Eqs. (1) and (2), the associated subset of t₁ is recorded as \({\Phi }_{1}=\{{\mathbf{y}}_{1}\}\); the transfer amount of t₁ is \({\lambda }_{\mathrm{1,1}}=1\). According to Eq. (3), the transfer ability of t₁ is recorded as \(\upomega \left({\mathbf{t}}_{1}\right)={\lambda }_{\mathrm{1,1}}=1\). Similarly, t₂ participates in the generation of the offspring y₂ and y₄. y₂ is inferior to the parent, while y₄ is superior to the parent, then the associated subset of t₂ is recorded as \({\Phi }_{2}=\{{\mathbf{y}}_{2},{\mathbf{y}}_{4}\}\), \({\lambda }_{\mathrm{2,1}}=0\), \({\lambda }_{\mathrm{2,2}}=1\). According to Eq. (3), the transfer ability of t₂ is \(\upomega \left({\mathbf{t}}_{2}\right)={\lambda }_{\mathrm{2,1}}+{\lambda }_{\mathrm{2,2}}=1\). t₃ participates in the generation of the offspring y₁ and y₄. The associated subset of t₃ is recorded as \({\Phi }_{3}=\{{\mathbf{y}}_{1},{\mathbf{y}}_{4}\}\). Since the offspring y₁ and y₄ outperform their parents, then \({\lambda }_{\mathrm{3,1}}=1\), \({\lambda }_{\mathrm{3,2}}=1\). The transfer ability of t₂ is \(\upomega \left({\mathbf{t}}_{3}\right)={\lambda }_{\mathrm{3,1}}+{\lambda }_{\mathrm{3,2}}=2\). \(\upomega \left({\mathbf{t}}_{4}\right)\) and \(\upomega \left({\mathbf{t}}_{5}\right)\) are calculated in the same way. Table 2 shows the result of transfer ability of the historical transferred population TP.

In the proposed EMT-ADT algorithm, the archive A is used to store individuals involved in knowledge transfer. At each generation, n individuals selected from the auxiliary population are used to update the archive. For a multitask problem with two tasks, when optimizing task T₁, the population associated with task T₂ is regarded as an auxiliary population and vice versa. Since it is possible to select individuals with negative transfer by using random selection strategy, a decision tree model classifier is constructed to predict the transfer ability of each individual in the auxiliary population. Subsequently, transferred individuals are sorted in descending order according to transfer ability. The top n transferred individuals with high transfer ability are chosen to be placed into the archive A. Furthermore, the decision tree model classifier is used to predict the transfer ability of individuals in the archive A. The top n transferred individuals with high transfer ability are selected as the historical transferred population TP to conduct knowledge transfer for the next generation.

At each generation, the historical transferred population TP with LP generations is used as the training data, that is \(\mathrm{TP}\_\mathrm{DT}={\bigcup }_{g=G-LP}^{G-1}{TP}_{g}\). The process of the decision tree model classifier construction is described as follows.

1. According to individual transfer ability, the individual with the highest transfer ability in TP_DT is recorded as t_best.where m is the size of TP_DT.

2. For \(\forall {\mathbf{t}}_{i}\in TP\_DT\), it has two feature attributes, Euclidean distance attribute (a₁) and factorial cost attribute (a₂). The Euclidean distance dis(t_i, t_best) between t_i and t_best, which is recorded as the data x_i,1 of a₁, is put into the set Ω₁. The factorial cost f(t_i) of individual t_i, which is recorded as the data x_i,2 of a₂, is put into the set Ω₂. The transfer ability \(\upomega \left({\mathbf{t}}_{i}\right)\) of individual t_i, which is recorded as the data y_i of label attribute, is put into the set Ω₃. Let \({\mathrm{x}}_{i}={\mathrm{x}}_{i,1}\cup {\mathrm{x}}_{i,2}\), the candidate attribute set A = {a₁,a₂}, the dataset \(\mathrm{D}=\{\left({\mathrm{x}}_{1},{\mathrm{y}}_{1}\right),\left({\mathrm{x}}_{2},{\mathrm{y}}_{2}\right),\dots ,\left({\mathrm{x}}_{m},{\mathrm{y}}_{m}\right)\}\).

3. Calculate the Gini index of each feature attribute with the sets Ω₁, Ω₂ and Ω₃, where p_k represents the proportion of the current category k.

4. Calculate the Gini index of the jth splitting value b_j corresponding to the feature attribute a_i, where v represents the category for the label attribute in dataset D.

5. The splitting value b^* with the lowest Gini index is selected as the optimal splitting attribute. In the candidate attribute set A, the feature attribute a^* corresponding to b^* is selected as the current node.

Algorithm 2 presents the construction of decision tree.

Take Table 3 as an example to construct a decision tree. Euclidean distance (denoted as dis) represents the first feature attribute, while factorial cost (denoted as f) represents the second feature attribute. Firstly, determine the root node. Since the attribute dis is a numerical attribute, sort the data in ascending order. Then, the samples are split into two groups with the middle value of adjacent values from small to large. Significantly, two adjacent values are different. For example, if dis = 0.2 and dis = 0.4, the median value is 0.3. Then, the median value is used as the split point, the calculated Gini index is 0.619. Similarly, other median values and Gini indexes can also be calculated in the same way, as shown in Table 4. In Table 4, the Gini index obtained by taking 0.95 as the split point is the smallest, which is 0.32. Table 5 shows the Gini index of different split points with the factorial cost as node. In Table 5, the Gini index obtained by taking 17.5 as the split point is the smallest, which is 0.441. As seen from Tables 4 and 5, since the Gini index 0.32 in Table 4 is less than the Gini index 0.441 in Table 5, the Euclidean distance is used as the split attribute of the root node, and 0.95 is used as the split value to construct the decision tree. After calculation, the factorial cost is used as the split attribute of intermediate node on the second level, and 10.5 is used as the split value to construct the decision tree. Finally, the constructed decision tree is shown in Fig. 3.

In Fig. 3, the leaf node represents the transfer ability. x₁ represents the first feature attribute: Euclidean distance, while x₂ represents the second feature attribute: factorial cost. Take the transfer ability prediction of data (0.4, 6) as an example, firstly, we judge at the root node. Since 0.4 is less than 0.95, we turn to the left subtree to judge. At the intermediate node, 6 is less than 10.5, the data transfer ability is predicted to be 2.

For further explain the prediction of individual transfer ability, a two-task benchmark problem including Griewank problem and Rastrigin problem is selected. Both problems are characterized by multimodal and nonseparable. The detailed properties are shown as follows.

(1) Rastrgin:

(2) Griewank:

Figure 4 shows the decision tree model constructed by the proposed algorithm EMT-ADT at generation g on the two-task benchmark problem (Eqs. (9), (10)). At this time, there are six cases of transfer ability (2, 3, 4, 5, 6, 7). Take the transfer ability prediction of data (2.794, 18,694) as an example, firstly, we judge at the root node. Since 2.794 is less than 2.96472, we turn to the left subtree to judge. Similarly, 2.794 is less than 2.95378, we continue to judge on the root node of the left subtree of this node. Since 2.794 is greater than 1.08146, we judge on the root node of the right subtree of this node. Similarly, 2.794 is greater than 2.75214, we continue to judge on the root node of the right subtree of this node. Finally, 18,694 is less than 18,869.9, the transfer ability prediction result of this data is 4.

The transferability of an individual is defined as follows. If an auxiliary parent participates in the generation of an offspring for m times, and there are n offspring that are superior to the corresponding parent, then the transfer ability of the auxiliary parent is n. As seen in Fig. 4, take the leaf node marked in red circle as an example. The node in red circle indicates that an individual reaches the position of the current leaf node through decision tree classification, its corresponding transferability is 7.

Many classical optimization algorithms, such as GA (genetic algorithm), DE (differential evolution), PSO (particle swarm optimization), TLBO (teaching–learning-based optimization), and BSO (brain storm algorithm) can be used as search engine in MFO paradigm [22‐25]. Different algorithms have different search performance. Obviously, well designed search strategies can improve the search efficiency. The success-history based adaptive differential evolution algorithm (SHADE) proposed by Tanabe et al. [26] has been proved to be an effective optimization algorithm. In SHADE, a historical memory is used to store the control parameters that performed well during the evolution. New control parameters are generated by sampling the parameters in the historical memory, which may further improve the performance of the algorithm. Since SHADE outperformed many state-of-the-art DE algorithms on CEC2013 benchmark set and CEC2005 benchmarks, this paper selects SHADE as the search engine. The mutation operator is defined as follows [26].where x_i is the ith individual of the current population. x_pbest is randomly selected from the top p% individuals in the current population, while x_r1 is randomly selected from the current population.\({\widetilde{\mathbf{x}}}_{r2}\) is randomly selected from the union of the current population and the archive. The details of SHADE can be found in [26].

To improve the knowledge transfer between different tasks on MFO problems, the original mutation operator of SHADE is modified and is defined as follows.

For a multitask problem with two tasks, P is the subpopulation corresponding to the target task, and \({P}^{{\prime}}\) is the subpopulation corresponding to the auxiliary task. TP is the historical transferred population, which is used to provide the transferred individuals for the target task. x_i is the ith individual of the population P. x_pbest is randomly selected from the top p% individuals in the population \({P}^{{\prime}}\). \({\mathbf{x}}_{r1}^{{\prime}}\) and \({\mathbf{x}}_{r2}^{{\prime}}\) are randomly selected from TP. F is the scale factor. After mutation operator, the same crossover operator as in SHADE is used to generate the final offspring.

In the modified SHADE mutation operator, x_pbest can provide the promising direction for the population, which can promote the convergence. The randomly constructed difference vector \(({\mathbf{x}}_{r1}^{{\prime}}-{\mathbf{x}}_{r2}^{{\prime}})\) not only enhances the population diversity, but also promote positive knowledge transfer due to the selection of the transferred individuals with highest transfer ability.

The pseudocode of the EMT-ADT algorithm is shown in Algorithm 3. \({P}^{{\prime}}\) is the subpopulation corresponding to the auxiliary task. The archive A is used to store individuals involved in knowledge transfer. x_best is the best individual of \({P}^{{\prime}}\). NP_i is the population size of ith task. FES and MAXFES represent the current number of function evaluations and the maximal number of function evaluations, respectively.

The main steps of EMT-ADT is as follows. First, for each task T_i, the offspring is generated by Eq. (11) or (12) according to the random mating probability rmp. Meanwhile, the associated subset \({\Phi }_{i}\), the transfer amount \({\lambda }_{i,j}\) and the transfer ability \(\upomega \left({t}_{i}\right)\) are calculated according to Eqs. (1)–(3). When knowledge transfer is required during the generation of offspring, the training data D is first constructed by TP of continuous LP generation. Next, the decision tree model DT is constructed by the training data. Then, DT is used to predict the transfer ability of all individuals in \({P}^{{\prime}}\). All individuals are sorted based on the transfer ability. The top n-1 individuals and the historical best individual in \({P}^{{\prime}}\) are stored into the archive A. Then, DT is used to predict the transfer ability of all individuals in the archive A. After ranking these individuals according to their transfer ability, the top n−1 individuals and the historical best individual in \({P}^{{\prime}}\) are stored into the historical transferred population TP_g+1 at generation g + 1. When there is no knowledge transfer during the generation of offspring, the top n−1 individuals with better factorial cost and the historical best individual in \({P}^{{\prime}}\) are stored into the archive A. The individuals in the archive A are sorted according to their transfer ability. Then, the top n−1 individuals and the historical best individual in A are selected as the historical transferred population TP_g+1 at generation g + 1.

When the success rate sr_i (sr_i denotes the rate that offspring is better than its parent) is greater than the given threshold, the random mating probability rmp_i for each task is updated as follows [10].where tsr_i denotes the rate that offspring generated with knowledge transfer is better than its parent. If all offspring are generated without knowledge transfer, then TNP is set to 0; otherwise, TNP is the number of offspring generated with knowledge transfer.

The computational cost of the EMT-ADT mainly comes from assortative mating, the adaptive knowledge transfer based on decision tree and historical transferred population update. In EMT-ADT, a loop over NP (population size) is conducted, containing a loop over D (dimension) and m optimization tasks. Assortative mating is performed according to the random mating probability (rmp). Then, the runtime complexity is \(O(m\cdot NP\cdot D)\) at each iteration. For the adaptive knowledge transfer based on decision tree, the Euclidean distance between the transferred individual r_i and the optimal transferred individual r_best is calculated, which may increase the time complexity of the algorithm. Due to five consecutive iterations, the runtime complexity is \(O(5\cdot n\cdot D)\), in which n is the number of the transferred individuals. Similarly, the runtime complex of historical transferred population update is \(O(n\cdot D)\). Therefore, the total time complexity of the EMT-ADT is \(O(m\cdot NP\cdot D)\).

The aforementioned CEC2017 multitask problems are given in Table 6.

The proposed EMT-ADT is compared with eight popular multitask optimization algorithms, namely MFEA [1], MFEARR (MFEA with resource reallocation) [29], MFDE (multifactorial differential evolution) [23], AT-MFEA (affine transformation-enhanced MFEA) [8], SREMTO [13], MFMP (MFO via explicit multipopulation evolutionary framework) [10], TLTLA (two-level transfer learning algorithm) [30] and MTEA-AD (MTEA based on anomaly detection) [31]. The default parameter settings for these algorithms are given in Table 7. N denotes the population size.

In this section, the proposed EMT-ADT algorithm is compared with the above-listed algorithms to verify the performance. Tables 8, 9, 10 summarize the mean fitness (mean) and standard deviation (Std) achieved by MFEA, MFEARR, MFDE, AT-MFEA, SREMTO, MFMP, TLTLA, MTEA-AD and EMT-ADT over 30 runs. The codes are conducted with MAXFES as the termination criterion, which is set to 200,000. Three statistical test measures including the Wilcoxon signed-rank test [32], the multiple-problem Wilcoxon’s test [33] and Friedman’s test [33] are used to compare EMT-ADT with other eight algorithms. With regard to the single-problem Wilcoxon’s test, “†”, “≈” and “−” are used to indicate that EMT-ADT significantly wins, equal, and is worse than the compared algorithm, respectively. With regard to the multiple-problem Wilcoxon’s test, R⁺ and R⁻ are used to indicate that EMT-ADT is significantly better than or worse than the compared algorithm, respectively. The best solution is highlighted in bold.

To investigate the performance on more complex multitasking problems, the proposed EMT-ADT is further compared with eight state-of-the-art multitasking optimization algorithms on WCCI20-MSTO benchmark suite. Tables 11 and 12 show the comparative results of nine algorithms in terms of mean fitness.

As can be seen from Tables 11 and 12, EMT-ADT obtained 17 best values out of 20 WCCI20-MTSO test instances. MFEA, MFEARR and MTEA-AD perform well on problem P₈. SREMTO achieves the best value on the Task T₁ of problem P₉. The last rows of Tables 11 and 12 imply that EMT-ADT performs significantly better than the eight competitors over almost all the test instances.

Figure 10 plots the trajectory of the mean fitness versus the number of function evaluations in each algorithm on WCCI20-MSTO benchmark suite. As seen in Fig. 10, EMT-ADT demonstrates a clear advantage over eight competitors.

The mean fitness values obtained by nine algorithms on WCCI20-MaTSO are shown in Table 13. It is clear that EMT-ADT show obvious advantage over the competitors. More specifically, EMT-ADT significantly outperforms the eight competitors on 94 instances out of 100 instances. The last row of Table 13 shows that the proposed EMT-ADT outperforms the MFEA, MFEARR, AT-MFEA, MTEA-AD, MFDE, TLTLA, SREMTO and MFMP on 94, 94, 95, 94, 100, 94, 94 and 100 optimization tasks, respectively.

Multitasking optimization algorithm makes full use of positive knowledge based on sharing solutions across tasks, which can improve convergence and solution quality. To verify the competitiveness of the proposed algorithm, a series of experiments are conducted against two state-of-the-art single-task methods, i.e. SHADE and LSHADE. SHADE is an adaptive DE characterized by introducing success-history based parameter adaptation, while LSHADE is an improvement of SHADE. The performance of EMT-ADT, SHADE and LSHADE on CEC2017 benchmark problems and WCCI20_MTSO benchmark problems are summarized in Tables 14 and 15.

As can be observed in Table 14, EMT-ADT achieves superior performance in terms of solution quality on almost all the CEC2017 benchmarks. More specifically, the proposed EMT-ADT wins 17 out of the 18 competitions, which demonstrates that the implicit knowledge transfer across tasks in multitasking is beneficial for improving the performance of EMT-ADT. From Table 15, it can be seen that EMT-ADT works well on more complex multitasking benchmark suits WCCI20_MTSO, better than the values obtained by SHADE and LSHADE, i.e., SHADE and LSHADE got the best result on 0 and 3 instances.

In this section, the multiple-problem Wilcoxon’s test is used to compare the significant difference (p value) between the competitor algorithm and EMT-ADT, while the Friedman test is used to rank the significance of the compared algorithms statistically. Table 16 shows that EMT-ADT provides higher R + values than MFEA, MFEARR, AT-MFEA, MTEA-AD, MFDE, TLTLA, SREMTO and MFMP. The p values of MFEA, MFEARR, AT-MFEA, MTEA-AD, SREMTO and MFMP are less than 0.05, which indicates that the proposed EMT-ADT considerably wins these competitors. For PI + HS, PI + MS and PI + LS problems, the p values of MFDE and TLTLA are greater than 0.05, which indicates that the performance of MFDE and TLTLA is similar to that of EMT-ADT on these problems. For NI + HS, NI + MS and NI + LS problems, the p value of TLTLA is greater than 0.05, which indicates that the performance of TLTLA is similar to that of EMT-ADT on these problems. Furthermore, Table 17 shows the average rank and the overall rank of the compared algorithms for CEC2017 multitask problems. In sum, the average performance of EMT-ADT is first rank on all test problem.

Figure 11 visually shows the ranking of the EMT-ADT and competitor algorithms for CEC2017 multitask problems. The left side demonstrates the ranking of nine algorithms on CEC2017 multitask problems, while the right side illustrates the bar chart of average ranking of nine algorithms. Since the size of EMT-ADT in radar graph is smaller than that of other compared algorithms, it indicates that the EMT-ADT is competitive. Moreover, EMT-ADT has the shortest bar in the bar chart, which demonstrates that the EMT-ADT is superior to other competitor algorithms.

Population size has a considerable bearing on the rate of convergence. Generally, large population size may slow the convergence rate, while small population may promote a faster convergence [34]. In the proposed algorithm, the parameter γ represents the dispersion degree of population convergence, which is used to control the population size. To analyze the effects of the parameter γ on the performance of EMT-ADT, firstly, the degree of dispersion (DOD) of the population is defined as follows.where x_i is the ith individual in the population P, and N is the population size.

Figure 12 shows the degree of dispersion obtained by EMT-ADT on CEC2017 multitask problems. As seen from Fig. 12, the dispersion of the population is different during the evolution process for different problems with different tasks. To determine the parameter γ for better performance of EMT-ADT, CI + MS, PI + MS and NI + MS problems are selected to test the performance of EMT-ADT with different values of the parameter γ, i.e. γ = 0.0005, γ = 0.001, γ = 0.005, γ = 0.01, γ = 0.015, on all tasks.

Figure 13 and Table 18 respectively show the convergence curves and the ranking results on CI + MS, PI + MS and NI + MS problems with different values of the parameter γ. As can be seen in Fig. 13 and Table 18, the algorithm performs better with γ = 0.001. Therefore, γ is set to 0.001 in the proposed algorithm.

As mentioned before, the population size is adjusted at γ = 0.001, the algorithm performs the best. Since the dispersion of the population is different during the evolution process for different problems with different tasks, the mean dispersion degree of the population on nine CEC2017 multitask problems is calculated, as seen in Fig. 14. The location of red circle is recorded as (FES, γ), which represents the time when the population is adjusted. Therefore, when FES is 50,000, that is FES/MAXFES = cos(γ)/4, the population size should be adjusted to achieve better performance.

In this section, two real-world problems called the traveling salesman problem (TSP) [35] and traveling repairman problem (TRP) [36] are used to verify the practicability of the proposed EMT-ADT algorithm. More specifically, TSP and TRP are constructed as a multitask optimization problem, which is asked for a tour with minimum cost.

Given a list of n cities and a list of maintenance times for n cities, TSP aims to minimize the total time to visit these cities, while TRP aims to minimize the sum of the elapsed times for all customers that have to wait before being served [37]. Each city is allowed to visit only once, and finally returns to the origin city. Given a distance matrix \(\mathrm{C}=\{\mathrm{c}({x}_{i},{x}_{j})|i,j=\mathrm{1,2},\dots ,n\}\), where c(x_i, x_j) is the distance between two cities x_i and x_j. Let \(\mathbf{x}=({x}_{1},{x}_{2},\dots ,{x}_{n})\) to be a tour, i.e. a solution of the objective function. P(x₁, x_n) represents the path from x₁ to x_n. For the TSP problem, the total time \(ls(p\left({x}_{1},{x}_{n}\right))\) from starting city x₁ to x_n is computed as

For the TRP problem, the total time \(lr(p\left({x}_{1},{x}_{n}\right))\) from starting city x₁ to x_n is computed as

Generally, a unified representation scheme is used in multitask optimization algorithm, in which every solution is encoded by a random key between 0 and 1. Since the paths in TSP and TRP problems should be a set of integers without duplication, the real number encoding is converted to permutation number encoding. Specifically, all dimension values of the solution x are sorted in ascending order. Afterwards, the permutation solution \({\mathbf{x}}^{{\prime}}\) of solution x is obtained according to the ranking of dimension values. Figure 15 shows a simple example. For a solution x = (0.21, 0.34, 0.84, 0.67, 0.11, 0.08, 0.55), its permutation solution \({\mathbf{x}}^{{\prime}}\)= (3, 4, 7, 6, 2, 1, 5) denotes that the traveler starts from the third city, visits the fourth, seventh, sixth, second, first and fifth cities, and then returns to the third city.

In this experiment, we investigate the EMT-ADT, MFDE, MFPSO and the MFMP. Ten groups of problems are randomly selected from TSPLIB [38]. Suppose travelers travel between cities at a speed of 60 km/h. Each group is composed of a TSP test case and a TRP test case. For each test case, the average time spent by the traveler obtained by each algorithm on 30 independent runs is presented in Table 19. The number following the instance name indicates the number of city nodes. Table 19 shows that EMT-ADT achieves a tour with minimum cost against all peer competitors on almost all the instances. EMT-ADT wins 18 out of the 20 competitions, which demonstrates the superior performance of the proposed EMT-ADT. Figures 16 and 17 show the optimal TSP tour and the optimal TRP tour obtained by different algorithms on the eil51 instance, respectively. Experimental results show that EMT-ADT obtains better solutions than three state-of-the-art multitasking optimization algorithms.