A Group-based Approach to Improve Multifactorial Evolutionary Algorithm

1 Introduction

Classical evolutionary algorithms (EA) use population based search over the solution space to solve an optimization task. As a recently proposed learning paradigm, Multifactorial evolutionary algorithm (MFEA) [Gupta et al., 2016] aims to solve multiple optimization tasks simultaneously in a unified search space, where an individual in the population evolves based on the factorial influences received from every task and every task could be either a single objective or multiple objective optimization problem. Considering that real world problems seldom exist in isolation, a set of parameters tuned for one task are likely to be useful for a similar optimisation. This helps circumvent challenges associated with the dimensionality curse when several tasks with multidimensional search spaces are to be solved simultaneously. MFEA leverages the genetic complementaries transferring between tasks and enhances the averaged performance of solving the tasks. Its obvious advantage in time over a single-task EA demonstrates enormous potential of responding to the rapidly expanding of cloud computing industry. Multiple optimisation tasks that are received simultaneously from multiple users need to be solved within a limited amount of time in the cloud, which stresses on the time requirement for the multitasking.

Recently, MFEA has shown great potential on solving realworld problems like complicated engineering design [Cheng et al., 2017], capacitated vehicle routing Problem [Zhou et al., 2016] and so on. For instance, in engineering design, a variety of possible product designs are analysed and optimised during the conceptualisation phase (before one of them is finally chosen). Speeding up the analysis/design-optimisation stage through a multitasking solver can considerably reduce the often exorbitant design time.

What MFEA differs most from the single-task EA is the existence of genetic communication between tasks. The current version of MFEA has all the tasks share the genetic information without evaluating its potential impact on solving the tasks. In this paper, we group the tasks of similar types and transfer the genetic information only within the groups. This will differentiate the genetic information transfers among tasks so that the tasks share only the genetic information with positive mutual impact. Without solving the tasks, a proper task differentiation is difficult since it is hard to know what genetic exchange will contribute to solving the task. However, individuals (in a population) that are employed to solve the tasks in MFEAwill reflect the characteristics of the tasks (e.g. the landscape of objective functions of the tasks), which can be used to group the tasks. The similar tasks grant the individuals' commonality that facilitates the same task management.

Inspired by this idea, we propose group-based MFEA (GMFEA) that restricts individual behaviour within a group of similar tasks. Unlike the MFEA of giving an equal opportunity of inter-task genetic communication, GMFEA controls the genetic transfer among tasks belonging to the same group. We observe that the tasks having near global optima often choose individuals that follow similar solution paths, which is also verified in the experimental study (in Fig. 10). Subsequently multiple traits stemming from multiple tasks can exert a joint influence on the individual evolution in a positive way. Hence we group tasks from both the genotype and phenotype of individuals in a population. Genotypes consider genetic composition of individuals while phenotypes are their fitness values. The grouping could be conducted without prior knowledge about the task properties.

Introducing the grouping operator may compromise the population diversity resulting in poor algorithm performance. To mitigate this problem, we propose a new selection criterion that considers a tradeoff between individual fitness and population diversity. The new consideration significantly reduces the evaluation time while maintaining good performance. We summarise the main contributions below.

• We propose a group-based MFEA to control the intertask genetic communication in a dynamic way;
• We design a new selection criterion considering both fitness and diversity, which is used in the group-based mating selection and environmental selection;
• We conduct experiments in both cross-domain and intradomain problems to demonstrate performance of the new algorithm.

2 Background Knowledge and RelatedWorks

Evolutionary algorithms are optimisation metaheuristic which mimics the process of natural evolution [B¨ack et al., 1997]. EAs have been widely used to solve corresponding optimisation problems in multiple domains, e.g, single-objective optimisation [Guo and Yang, 2015] , multiobjective optimisation [Coello, 2006; Fonseca and Fleming, 1995] and so on. Recently, inspired by the concept of 'multifactorial inheritance', Gupta et al. [2016] introduce multifactorial evolutionary algorithm (MFEA) that further promotes the concurrent search to optimize multiple tasks simultaneously. The MFEA splits a population into different skill groups each of which excels at a different task. The genetic material created within a particular group turns out to be useful for another task as well. Thus, in such situations, the scope for genetic transfer across tasks can potentially lead to the discovery of otherwise hard to find global optima.

Fig. 1 elaborates four main procedures of MFEA that start from a unified representation of individuals for the tasks, and then iterates individual evaluation, genetic information transfer and environmental selection. In every iteration, only promising candidates to solve one task (in the right container) survive after an environmental selection that is conducted in the bottom container. We aim to improve the basic MFEA framework in this paper.

On theoretical grounds, MFEA amplifies the power of population-based search. As genetic building blocks corresponding to different optimisation tasks are contained within a unified pool of genetic material, they get processed by the EA in parallel [Wright et al., 2003]. Most importantly, this encourages the discovery and implicit transfer of useful genetic material from one task to another in an efficient manner. Moreover, as a single individual in the population may inherit genetic building blocks corresponding to multiple optimisation tasks, the analogy with multifactorial inheritance becomes more meaningful.

We shall note that MFEA deals with multiple fundamentally distinct optimisation tasks while coevolutionary algorithms [Trunfio, 2015] handle a single optimisation task. It is indeed conceivable to design a coevolutionary algorithm capable of multitasking. However, this requires several hyperparameters to be specified in the coevolution framework. Meanwhile, MFEA is more general than multi-objective optimisation (MOO). MOO deals with conflicts among competing objectives belonging to one given task. MFEA is to optimize each constitutive task absolutely, instead of having to establish any kind of trade-off between individual tasks.

Finally, another relevance is multitask learning that have been well studies in the machine learning field [Caruana, 1997]. The multitask learning research mainly focuses on investigation of relatedness among different tasks and knowledge transfer among the learning domains. It is not intended for solving multiple-function optimisation problems and is not rooted in the EA principle. MFEA is the state-of-art solver for solving multifactorial optimisation problems.

3 Group-basedMFEA

We first present the grouping operator in the new algorithm and then develop a new selection criterion to improve the mating selection and environmental selection.

3.1 Grouping Tasks

Grouping tasks is derived from observation that tasks having near global optima will positively influence each other when there are genetic information transfers among them. When solutions of a task move further away from other tasks, the genetic information transfers between the task and others increase redundancy gradually. We call that the tasks with near global optima are 'similar' for simplicity. Despite that combining dissimilar tasks will increase diversity from the very beginning, convergence speed afterwards and the final results of these tasks within limited rounds leave much to be desired.

Similar tasks are grouped and dissimilar tasks are separated in the grouping operation. Mating between individuals is only allowed in the same group so that negative genetic transfers could be eliminated. Grouping tasks can be implemented in two levels: genotype and phenotype.

At the genotype level, tasks are grouped by genotypic similarity of their best individuals. We resort to the clustering technique like the bisecting K-means [Steinbach et al., 2000] based on the Manhattan distance between individuals. Using one group for a searching area, M representatives are chosen from the best individuals to represent M groups or M search spaces one-on-one.

At the phenotype level, representatives conduct tests on others' districts to see any better exploration positions. We run tests between representative pairs rather than best individual pairs, which reduces the needed number of tests. Only

Algorithm 1: Grouping Tasks

• Input: BI (best individuals) Output: Groups of Individuals GB 1 Groups ← bisectingKmeans(BI). 2 Randomly choose representatives (RG) of groups while one representative is corresponding to one group. 3 k ← ⌈M/2⌉. // |Groups| =M. 4 kRG←Randomly choose k representatives fromRG. 5 t ← k. 6 Generate an empty set ERG for archive. 7 for i = 1 to k do 8 tRG←Randomly choose t representatives fromRG. 9 Change the skill factor of all representatives in tRG to τi while τi is the skill factor of i-th representative of kRG. 10 ERG←ERG∪ tRG. 11 end 12 Evaluate the representatives in ERGwith respect to their skill factors only. 13 Obtain the new best individuals (NBI) according to ERG. 14 for nbij ∈ NBI do 15 if nbij is fitter than bij then 16 Remove j from its original group. 17 Add j into the group represented by nbij . 18 end 19 end

20 Update GBI.

partial representatives are selected to run the tests on other selected representatives, and their skill factors are changed to the formers for additional evaluations and the best evaluation results are chosen for every test representative. The skill factor of an individual is the one task, on which the individual is most effective. The structure of groups and the best individuals are updated by the results. The task grouping process is described in Algorithm 1.

In order to illustrate the procedure of grouping, assume there are four tasks from T1 to T4 whose best individuals are bi∗ respectively in Fig. 2. The solid points are for the best individuals while each solid circle is for the exploitation space of each task constructed by its individuals. After the preliminary grouping, T1 and T2 reside in group g1, and T3 and T4 are in group g2. Assuming that bi1 and bi4 are selected as representatives of g1 and g2 respectively. Then bi1 conducts a test in bi4, which means that bi4 changes its skill factors to bi1's. Next, bi4 is evaluated in task T1 and luckily achieves better results than bi1's. It shows that adding task T1 into group g2 will improve solutions to T1 due to a better evolution of bi1. Finally two new groups: {T2} and {T1, T3, T4} are obtained.

3.2 Selection

Selection Criterion

The existing MFEA algorithm adopts a fitness-based selection criterion for effectively transferring elite genes between tasks and best individuals are always kept for each task, which implies a large accumulation of elite genes. However, population diversity is necessary when it becomes a bottleneck against the genetic information transfer. Meanwhile, the uncertainty of genetic information brought by other tasks can't ensure local diversity of a particular task, which is useful for an efficient search [L´opez et al., 2010; Ishibuchi et al., 2008; ˇCrepinˇsek et al., 2013]. In GMFEA, we propose a new selection criterion keeping a balance between individual fitness and diversity in a population.

We redefine fitness scalar (FS) as a fitness estimator to adjust factorial cost of individuals evaluated for different tasks to a common scale.

Definition 1 (Fitness Scalar): For each individual pi ∈ P on task Tj , FS is computed in Eq. 1.

where Ψij is the factorial cost of pi on task Tj, lbj and ubj are minimum and maximum factorial costs of individuals on task Tj over all individuals in P.

We use crowding distance (CD) [Deb et al., 2000; Deb et al., 2002; Yang et al., 2013] to approximately estimate individual diversity here.

Definition 2 (Crowding Distance): For each individual pi, crowding distance is computed in Eq. 2.

where D(pi, pk) = ∑Dl=1 |pi(l) -pk(l)| measures the distance between pi and pj in the genotype level using a Manhattan distance, pi(l) denotes the l-th component of pi as a vector form, and N(pi) = {pk|D(pi, pk) < neighbor size} stands for neighbours of pi ranged by the neighbor size.

Strictly speaking, CD is not a standard estimator of diversity, but density, as it serves for each individual instead of an entire population. However, maximising diversity of the population of individuals is a NP-hard problem and approximate algorithms are computationally expensive [Qu et al., 2015; Nemhauser et al., 1978]. We resort to a heuristic method of computing CD for each individual, which provides a good diversity of the population while using less computation.

Formally the selection criterion weighing against both fitness and diversity is defined in Eq. 3.

where α is the balance factor.

Mating Selection

Mating selection aims at focusing search strength on the most promising individuals [Yang et al., 2013]. We adopt it as a preparation for genetic information exchange. In this paper, we use a binary selection technique and consider both the fitness and diversity to form a promising mating pool for each group. Two individuals are randomly selected one of which

Algorithm 2: Mating Selection

Input: Groups (grouped tasks), P (population), N (population size), α Output: New populations NP 1 Reshuffle P. 2 Generate an empty set NP for archive. 3 for i = 1 to N/2 do 4 p1 ← (2 × i - 1)-th individual of P . 5 p2 ← (2 × i)-th individual of P . 6 if (α × p1.FS + (1 - α) × p1.CD) < (α × p2.F S + (1 - α) × p2.CD) then 7 NP ← NP ∪ p1. 8 else 9 NP ← NP ∪ p2. 10 end 11 end

Algorithm 3: Environmental Selection

Input: P (population), T (the set of tasks), Nτ′ (the size of individuals required by task τ ′ ) // τ ′ is also representing the relevant skill factor Output: New population NP 1 Generate an empty set NP for archive. 2 {p.CD|p ∈ P} ← 0. 3 for τ ′ ∈ T do 4 P ′ = {p ∈ P|p.τ = τ ′ }. 5 Generate a temporary set tP for archive. 6 while |tP| < Nτ do 7 q ← minp∈P ′ {α × p.F S + (1 - α) × p.CD}. 8 tP ← tP ∪ q. 9 P ′ ← updateCD(P ′ , q). 10 end 11 NP ←NP ∪ tP. 12 end

is chosen to stay in the mating pool while the other is abandoned. Eventually only half of a population is allowed to be mated, which significantly reduces computational cost in every evaluation call. Details are summarised in Algorithm 2.

Environmental Selection

Environmental selection aims to maintain promising candidate individuals for a new generation. An intuitive thought is to design a selection strategy based on fitness. However, selecting similar or even identical genotypic individuals may lead to a significant loss of diversity. In GMFEA, we follow the criterion (Eq. 3) in the selection. First all individuals' crowding distances (CDs) are set as zeros. For each task, a certain number of individuals are selected using CDs. After an individual q has been picked out, we update the CD (in Algorithm 4) for q's remaining neighbours. Thus the selection probability of q's neighbours drops for keeping a large diversity of the population. The main procedure of environmental selection is summarised in Algorithm 3.

4 Experimental Study

All experiments are performed on a desktop with Intel i7 CPU (3.4 GHz) and 8GB RAM.

Algorithm 4: Update Crowding Distance

Input: P (population), q (selected individual), D (distance matrix), N(q) = {p ∈ P |D(p, q) < neighbor size} 1 for p ∈ N(q) do 2 p.CD ← p.CD + 1 - D(p, q). 3 end 4 Normalize CD.

4.1 Function Optimisation

We begin the cross-domain experiments with four benchmark functions for continuous optimisation that are commonly used in the closely related literature [Yew-Soon Ong et al., 2006; Chauhan et al., 2013; Nguyen et al., 2007; Le et al., 2009]: a) Griewank function: 1 + ∑ni=1 z2 i 4000 - ∏ni=1 cos( zi √i ); b) Ackley function: 20 + e - 20 exp(-0.2((∑Di=1 z2 i )/D)(1/2) ) - exp(∑Di=1 cos(2πzi)/D); c) Rastrigin function: ∑Di=1 (z2 i - 10 cos(2πzi) + 10); and d) Weierstrass function: ∑Di=1 (∑20 k=0 (0.5k cos(2π · 3k (zi + 0.5)))) - D ∑20 k=0 (0.5k cos(2π · 3k · 0.5)).

In above functions, z =M∗ × (x-O∗) and M∗ are rotation matrices which influence the landscapes and O∗ decides global optima of each function. Their search spaces are summarized in Table 1. We perform experiments by varying combination of functions, M∗ and O∗. One task is instantiated after one function, which represents task's type, is chosen, and its M and O are randomly generated. D is set to 30, so the search dimension is 30.

We present two sets of cross-domain experimental results. One is in Figs. 3 - 5 that compare the performance of a single task EA (denoted as ST) to the MFEA variants. MF denotes MFEA, GMF denotes MFEA plus task grouping strategy, and GMF+S denotes GMF integrated with the new selection criterion. It is noted that the mating selection is introduced along with the new selection criterion in GMF+S and largely reduces the evaluation calls by nearly a half. 50 tasks and a population of 250 individuals evolve over 200 generations. All the results are averaged over 20 independent runs.

(a) 50 tasks, 6 positions for O

(b) 50 tasks, 11 positions for O

Figure 3: Convergence trends of 50 tasks

The random mating probability (rmp) of MFEA keeps the same parameter value 0.3 as in the original paper [Gupta et al., 2016]. GMFEA variants (GMF and GMF+S) have a full crossover and a mutation probability of 0.8 among members in the same group, and the normalised neighbour size value is set to 0.4. Due to the quasi-Newton method in MFEA variants that highly strengthens the local search, we resort to a relatively big α = 0.95 for a relatively small demand of a population diversity in the experiments. The value of α is decided by a trade-off between the run time and the objective values in the experiments (which is not shown due to the limited space).

Fig. 3 shows the convergence trends of 50 tasks with different position sets. The averaged normalised objective value is computed by 1/(20 × 50) × ∑j ˜ fj, where ˜ fj = (fj - (fj)min)/((fj)max - (fj)min), j represents task Tj, (fj)min and (fj)max are the minimum and maximum objective values among all runs of ST and MFEA variants corresponding to task Tj. 250 individuals serving for a single task earns the best beginning in ST. However, all the MFEA variants defeat ST after several generations because ST is quickly trapped in a local optimum. GMFEA variants exhibit a better convergence compared to MF, while the performance of GMF+S is between GMF and MF. For both cases, the variances are rather small (can't be shown in the figures), which implies a fast convergence and is consistent with the trends in Fig. 3.

In Fig. 4, MFEA variants show great time advantage over ST for running multiple tasks with the same size of population. GMF is more time-consuming than MF due to the time spent on grouping tasks and updating CDs. GMF+S is the fastest among all four algorithms as it reduces the number of individual evaluations.

Fig. 5 shows the changes of the number of groups of GMF+S. Global optima of 50 tasks distributed among 6 positions and 11 positions become stable within 100 generations, which endorses the reasonable strategy of grouping tasks and its utility. Fig. 6 focuses on the scalability tests of MF and GMF+S. Two larger task sets of 75 tasks and 100 tasks are considered in two position sets. The population size increases to 400 and other parameters keep the same. GMF+S outperforms MF and achieves larger scalability in all the cases.

4.2 Sudoku Puzzles

Sudoku is a puzzle game designed for a player to fill in a 9 x 9 grid with digits from 1 to 9. We draw part of Sudoku puzzles from the website (websudoku.com) while the rest of puzzles are hand-crafted.

The chosen Sudoku puzzles serve the purpose of providing intuitive benchmarks where although there may exist little similarity between tasks on the surface, there indeed exist strong underlying (latent) correlations between the optimum solutions of the tasks. It is contended that such examples are common in diverse real-world settings, thereby providing immense scope and motivation for multitask problem-solving.

Two sets of 30 Sudoku puzzles are considered in which 25 puzzles are manually generated while the rest are automated by our puzzle programs. One contains 15 groups of similar tasks while the other contains 10 groups of similar tasks. Fig. 7 gives examples of two pairs of similar tasks: A1-A2 and A3-A4. A population of 500 individuals evolve over 100 generations. GMF+S (α = 1/0.7) denotes GMF+S with two α settings of 1 and 0.7. Values of other parameters are the same as those in the previous domains.

We compute the population diversity through the wellknown entropy measurement [Tsujimura and Gen, 1998; Gupta and Ong, 2016]. E(r,c) denotes the diversity at each cells and is computed as follows:

where r and c are the row and column indexes, allele(r,c) denotes the digit filled in the cells (r, c), and pr(x) represents the occurrence probability of 'x' in one generation.

Subsequently, the population entropy is the sum of diversity of cells: E = 1 81 ∑9r=1 ∑9c=1 E(r,c).

Fig. 8 depicts the convergence trends of two sets of 30 Sudoku puzzles. We don't add the performance of ST in Fig. 8 (b) since it has similar trends in Fig. 8 (a). As shown in the first set of experiments (in Fig. 4), GMF is more timeconsuming than GMF+S while achieving similar objectives. Hence we don't show GMF in the second set. We roughly divide Fig. 8 (a) into two stages by the 20th generation and divide Fig. 8 (b) by 30th generation. In both the figures, ST converges in the fastest manner, followed by GMF+S (α = 1), GMF+S (α = 0.7) again, and the slowest MF in the former stage. In the latter stage, GMF+S (α = 0.7) converges first, followed by GMF+S (α = 1), MF and ST again.

We account for the convergence performances accompanied by population diversities in Fig. 9 (a). Only the population entropy of 15 groups of similar tasks case is given because the other is similar. ST has the lowest population diversity, which helps its fast convergence in the former stage; however, it is easily trapped in a local optimum. Although ST offers each task the whole population of individuals, GMF+S (α = 0.7) has a population diversity between MF and GMF+S (α = 1) and finally convergences to the best against all the other algorithms. On the one hand, GMF+S (α = 0.7) keeps a higher population diversity than GMF+S (α = 1), which indeed accelerates the convergence speed in the latter stage. On the other hand, MF has the highest population diversity but performs worse than GMF+S, which shows that the unlimited population diversity derived from too many negative information transfers is harmful to the convergence. Fig. 9 (b) shows the changes of number of groups of GMF+S (α = 0.7). After 50 generations, the number of groups keeps stable around 15.

In addition, we further investigate individual similarity in ST. In every iteration, we sample 300 individuals for each task (A1-A4) in terms of individual fitness in a population, and calculate the normalized Manhattan distance (MD) for every pair of individuals. Fig. 10 shows the individual similarities that are drawn from different pairs of tasks. In Fig. 10 (a), individuals from similar tasks A1 and A2 have low distance leading to good similarity. This is also expected in Fig. 10 (b) when individuals from task A3 and A4 are compared. The experimental results verify our hypothesis that tasks having near global optima are similar, which motivates the idea of grouping tasks in MFEA, and indicates the necessary of introducing diversity in the new selection process.

5 Conclusion and FutureWork

We propose the group-based MFEA that is scalable to deal with the optimisation of a significant number of tasks that can't be solved by the plain MFEA. The grouping is carefully designed using clustering algorithms and the selection is based on two well-formulated components. The performance is demonstrated by different angles over multiple domains. The results suggest effective performance with good efficiency achieved by GMFEA, which leads to promising solutions to a general many-task solver in many applications like a cloud platform. We notice that the algorithm cannot handle well the situation that few similar tasks exist in the task set, e.g. in an extreme circumstance that each group contains only one task. We will deal with this situation in the future work.