Adaptive multifactorial particle swarm optimisation

Zedong Tang, Maoguo Gong ?

School of Electronic Engineering, Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education,Xidian University, No. 2 South TaiBai Road, Xi’an 710071, People’s Republic of China

Abstract: Existing multifactorial particle swarm optimisation (MFPSO) algorithms only explore a relatively narrow area between the inter-task particles. Meanwhile, these algorithms use a fixed inter-task learning probability throughout the evolution process. However, the parameter is problem dependent and can be various at different stages of the evolution. In this work, the authors devise an inter-task learning-based information transferring mechanism to replace the corresponding part in MFPSO. This inter-task learning mechanism transfers the searching step by using a differential term and updates the personal best position by employing an inter-task crossover. By this mean, the particles can explore a broad search space when utilising the additional searching experiences of other tasks.In addition, to enhance the performance on problems with different complementarity, they design a self-adaption strategy to adjust the inter-task learning probability according to the performance feedback. They compared the proposed algorithm with the state-of-the-art algorithms on various benchmark problems. Experimental results demonstrate that the proposed algorithm can transfer inter-task knowledge efficiently and perform well on the problems with different complementarity.

1 Introduction

Multi-task optimisation(MTO)is a newly emerging research area in the field of optimisation,which aims at effective and efficient solving multiple optimisation problems simultaneously. The concept of evolutionary multi-tasking [1] is proposed, which leverages on the population-based optimisation algorithms, such as evolutionary algorithms (EAs) [2], to address the MTO problems by utilising the potential complementarity of the tasks. Multifactorial optimisation (MFO) is a recently proposed evolutionary multi-tasking paradigm. It employs a single population to solve an MTO problem, where every component task in the MTO problem acts as a contribution factor influencing the evolution of the population. In MFO, the search spaces of multiple different tasks will be first transformed into a unified search space using certain mapping approaches such as the random key scheme [3]. Then, a single population is navigating the unified search space. Each of the population is focused on one task and can transfer the problem-solving knowledge (embedded in high-quality candidate solutions) with other individuals that belongs to the other tasks according to the multifactorial inheritance principles, namely, the assortative mating and vertical cultural transmission. Practically, it is a multi-tasking knowledge transfer method.

The multifactorial EA (MFEA) was recently proposed under the MFO paradigm [4], which is based on the genetic algorithms(GAs) [5]. It practically implements the computational equivalence of the assortative mating and vertical cultural transmission to transfer the searching knowledge of different tasks. In MFEA,the useful developmental traits are transmitted to the offspring generation by generation through the interaction of genetic and cultural factors. The shared genetic material transfer is implemented via the crossover operation following the multifactorial inheritance principles of assortative mating. The cultural transmission is realised by the selective imitation strategy.The MFEA was initially invented for solving the MTO problem composed of single-objective optimisation tasks. Later on, it was extended to solve the multi-task multi-objective optimisation problem. Nowadays, the MFEA was attracting more and more research attention and successfully applied to address many challenging problems in the multi-tasking scenario [6–10].Because different EAs may feature distinctive operators specialised in exchanging information, some works are focused on realising the inter-task knowledge transfer under different evolutionary mechanisms [11, 12].

Particle swarm optimisation (PSO), invented by Eberhard and Kennedy [13], is one of the most popular EAs, which is inspired by the social behaviour of a flock of birds or a school of fish.PSOs are characterised by the learning-based information sharing mechanisms which endow PSOs with stronger efficacy than GAs to solve continuous decision variables [13–16]. Due to the simplicity and rapid convergence speed, PSO becomes a widely-adopted optimisation algorithm and has achieved wide success in solving a variety of optimisation problems [17–21].There are some previous works have been proposed to incorporate PSO into MFO paradigm. Feng et al. [11] proposed a multifactorial PSO (MFPSO) which uses an additional accelerate term to implement the inter-task information transfer. Zhang et al.[12] proposed an MFPSO with inter-task learning (MFPSO-ITL)to update the personal best position by combining the current personal best position and the personal best position from another task.

In the previous work of MFPSO,the personal best position is not updated, which weakens the exploration ability of the inter-task knowledge transfer. In MFPSO-ITL, the personal best position is generated by the linear combination of two personal best positions.These inter learning strategies are mainly focused on the exploitation of personal experience and the exploration of a relatively narrow area. In addition, in the works above on MFPSO and the variants of it, the inter-task learning probability, which controls the cross-domain information transfer, is fixed throughout the evolutionary process. However, this parameter is problem dependent. Meanwhile, it is various on different problems and at different stages of the evolutionary process. In this work, to explore a broad area, we propose an adaptive MFPSO (AMFPSO)algorithm by devising a new inter-task learning mechanism based upon two methods, inter-task simulated binary crossover and a novel velocity updating strategy. Also we make the inter-task learning parameter self-adaptive according to the performance feedback to make the algorithms adaptive to the problems. The inter-task learning strategy is probabilistically carried out with the inter-task learning probability which is adapted as per online performance feedback. The inter-task learning is implemented by combining the velocity updating and personal best crossover. The multifactorial fitness evaluation is utilised to evaluate the evolution of the particles. We evaluate the performances of the proposed AMFPSO algorithm on MTO problems and compare the proposed algorithm with the MFEA as well as a canonical PSO algorithm.Experimental results demonstrate the superiority of the proposed AMFPSO over the compared algorithms.

The remaining of this paper is organised as follows. Section 2 describes the background related to this research. The proposed AMFPSO algorithm is elaborated in Section 3. Section 4 reports and analyses the experimental results. In Section 5, we conclude the paper with some future work being mentioned.

2 Background

2.1 Multifactorial optimisation

Multi-task optimisation is an emerging research field aiming at solving multiple tasks by utilising the shared searching experience.MTO attempts to fully and simultaneously optimise each task which may have distinct search spaces and different optima.Consider a composite problem consisting of K tasks. The problem of MTO is formulated explicitly as follows: {x?1,x?2, ...,x?K}=argmin{f1(x1),f2(x2), ...,fK(xK)}. MFO is a popular evolutionary multi-task paradigm. An objective function fiin MTO can be viewed as an existing factor influencing the evolution of individuals in the K-factorial environment. In MFO, the specific tasks’ search spaces are mapped into a unified representation space. The MFO algorithms use a single population to search the unified representation space. MFO features assortation mating,selective imitation. Assortation mating is a key characteristic which enables the implicit transfer of knowledge by utilising the crossover operators.

The unified random key scheme[3]is employed to encode search spaces into a unified representation space in MFO.Concretely,the K search spaces, V1,V2, ...,VK, is encoded into a unified random-key representation search space. The dimensionality of the task Tiis noted as Di. Dmis the maximum dimensionality of all tasks,miFor the task Tjwith Dj-dimensional search spaceit is direct that the first Djvariables of a particle are referred to as the solution. The ith variable is mapped to the range [0, 1] linearly via an equation yi=(xi?Li)/(Ui?Li), where Liand Uiare, respectively, the lower bound and the upper bound of xi. Conversely, the decode process is given by xi=(Ui?Li)·yi+Li.

To evaluate the performance of individuals, there are four terms defined in MFO.

Definition 1: Factorial cost [4] of individual xion task Tjis the objective value fjof potential solution xigiven by

Definition 2:Factorial rank [4] ofonis the rank index of xiin the sorted objective value list given by

Definition 3:Skill factor[4]is defined by the index of the task which an individual is assigned to. Skill factor of xiis given by

Definition 4: Scalar fitness [4] of xiis the inverse ofgiven by

Herein,the skill factor is defined as the cultural trait of the individual explicitly which is an inherent property of an individual in MFO in addition of chromosomes. In fact, the population of MFO is implicitly separated into several subpopulations assigned to different tasks by skill factor. The factorial rank is used to represent the relative performance of xion the jth task. So, the fitness function used in MFO is defined as the inverse of an individual’s minimal factorial rank over all tasks. This fitness function is a unified performance index in the multifactorial environment. All concepts were also described in [4].

MFEA is an implementation of MFO by using GAs[4].The basic structure of MFEA is shown in Algorithm 1(see Fig.1).In MFEA,chromosomes and cultural traits are tackled concurrently. The evolution mechanism is incorporated with multifactorial inheritance consisted of assortative mating and selective imitation to deal with the multiple tasks in MFO (see Fig. 2). The assortative mating principle states that individuals prefer knowledge transfer in a cultural alike group than in cross-cultural group to prevent excessive diversity by limiting cross-cultural transfer. Assortative mating (in line 8 of Algorithm 1 (Fig. 1)) is an important principle which keeps good traits extending over several generations in MFEA. In the case, where two parents are coming from different skill factors, offspring generates through cross-cultural crossover operation. Cross-cultural crossover in assortative mating, shown in Algorithm 2, plays an important role in the evolving mechanism of MFEA and it is the main way to implement the cross-domain transfer of information. The cross-domain transfer of problem-solving knowledge occurs probabilistically with the probability of the random mating parameter (rmp). Selective imitation implements the behaviour of imitating parents shown in Algorithm 3. Another benefit of selective imitation is that it suggests the selective evaluation,which helps the algorithm to reduce the computational efforts.

Fig. 1 Algorithm 1: Basic Structure of the MFEA

Fig. 2 In MFO, representations of variables corresponding various tasks can be encoded into a unified representation scheme. AMFPSO acts as a general solver on the unified representation space

There are several works involving variants of MFEA and applications on real-work problems. Yuan et al. [7] have proposed an exquisite variant of MFEA for permutation-based combinatorial optimisation problems (PCOPs). This work contributes to a new unified representation scheme for the PCOP and a level-based selection procedure to improve the performance on PCOPs. Sagarna and Ong [8] applied MFEA on the software tests generation. This work focuses on branch searching and is the first time to apply MFEA to real-world problems with more than two tasks. Gupta et al. [6] proposed a meaningful variant MFEA for multi-tasking multi-objective. A realisation of an off-the-shelf evolutionary multi-tasking paradigm forward multi-objective optimisation was represented in that work. Some works devoted to design a proper inter-task transfer method. Bali et al. [22] proposed an inter-task knowledge transfer method by using a linear domain adaptation.Wen and Ting [23] proposed an adaption strategy to control the number of individuals investing in the inner-task and inter-task searching. Ding et al. [24] attempted to the evolutionary multi-task framework to address expensive problems by transferring knowledge from multiple computationally cheap problems. And this work also proposed the decision variable translation and shuffling strategy to improve the performance of MFEA on dissimilarity problems. Feng et al. [25] employed a linear autoencoder to make use of the knowledge from multiple evolutionary optimisation algorithms with different evolutionary operations to improve the adaptability of evolutionary multi-tasking for various problems.

2.2 Particle swarm optimisation

PSO [13] is a popular population-based stochastic optimisation algorithm which has been used for many optimisation problems successfully. PSO is meta-heuristically inspired by the social behaviour of bird flocking. Henceforth, the population in PSO is called ‘swarm’. Each potential solution, called particle, is assigned with a velocity. PSO adjusts iteratively the velocities of particles by its personal best position and the best position found by the global swarm. The velocity vidand position xidof the dth dimension of the ith particle are updated as follows [26]:

where xi=[xi1,xi2, ...,xiD] is the position of the ith particle, and vi=[vi1,vi2, ...,viD] is the velocity assigned to the ith particle.

Equation (1) consists of three terms, momentum, cognitive and social terms [27]. There exist three parameters to adapt to problems including v, c1and c2which represent the inertia weight, cognitive coefficient and social coefficient, respectively. In the cognitive term, pi=[pi1,pi2, ...,piD] is the found-so-far position of the ith particle yielding the best fitness value. In the social terms, pg=[pg1,pg2, ...,pgD] is the best position found by the whole population currently. Each particle’s velocity on each dimension is clamped to a maximum velocity magnitude Vmax. If|vdi| exceeds Vmax, which is a parameter specified by the user, the velocity of that dimension is limited to Vmax.

PSO relies on the learning-based strategy to guide the searching direction of particles. In the canonical PSO algorithm, an individual updates its position and velocity according to the personal best position and its global best position. This can be regarded as a particle’s learning action from its owned experiences and social experiences. Several variants of PSO designing some efficient learning strategies have been developed currently [28–30].Liang et al. [28] proposed a comprehensive learning PSO(CLPSO). This work allows the particle updates its velocity using different personal best positions on different dimensions. Sabat et al. [29] proposed an integrated learning PSO. This algorithm updates the searching direction according to the hyper-spherical coordinates system. Qin et al. [30] proposed an inter-swarm interactive learning strategy PSO (IILPSO), in which particles are separated into several subwarms. An efficient inter-swarm interactive learning strategy is introduced to enable the information exchange between subswarms, which preserves the diversity of the population. Due to the efficiency and effectiveness of MFO in solving multiple tasks simultaneously, some previous works devoted to extending the single-objective PSOs to a multifactorial version of PSOs (MFPSO). Feng et al. [11]proposed an MFPSO which uses an additional accelerate term to implement the inter-task information transfer. Zhang et al. [12]proposed an MFPSO-ITL to update the personal best position by combining the current personal best position and the personal best position from another task, for the aim of generating feature subspaces.

3 Adaptive MFPSO

There are distinctive mechanisms specialised in exchanging information among the population in distinct EAs. PSO is characterised by the learning-based information mechanisms. So in this work, we develop an adaptive variant of MFPSO (AMFPSO)by employing an elaborated inter-task searching strategy to search a broad area and a self-adaptive strategy to adaptively tune inter-task learning probability. Two important concepts of multifactorial inheritance are introduced into PSO, including assortative mating and cultural transmission, which are helpful to enable the implicit information transferring. Due to the unique mechanisms based on the peer-learning in PSO, we introduce a horizontal information transfer procedure in PSO in the spirit of the neighbour imitating to transfer the knowledge among different tasks. As described in Algorithm 4 (see Fig. 3), AMFPSO has a similar structure with that of canonical PSO, however, the evolutionary mechanism of AMFPSO have been modified to adapt to the multifactorial framework.

Fig. 3 Algorithm 4: Basic structure of the AMFPSO

In Algorithm 4 (Fig. 3), every particle is assigned, respectively,skill factor tiwhich implicitly separates the whole swarm into K subswarms, where K is the number of tasks. An individual is selectively evaluated on the task according to tiwhich is viewed as the main factor influencing the particle. This is the key feature of MFO facilitating to reduce the computational costs, called selective evaluation. The corresponding function objective value is assigned to the factorial cost. The other unassigned elements of factorial costs are set to +1. In line 10, there are two strategies in the learning-based information sharing mechanism in the proposed method, which is the key feature to enable the implicit transfer of PSO. When the inner-task learning occurs, the evolving of particles performs as routine in the conventional PSO. When the inter-task learning occurs probabilistically under the probability of cross-domain learning, the particle is influenced by the leader selected from other tasks. There are two ways to enable inter-task learning in the proposed method. First, the particle could be attracted by the learned particle’s personal best position (pbest) by utilising an additional term of learned pbest in the velocity updating equation. Second, the pbest of the particle could be updated by the recombination of the current pbest and the learned particle’s pbest. We evaluate the overall factorial ranks of all individuals and pbests in P?=P<{pi|i=1, ...,Np}. The latter way of learning performs to encourage the exploration. Compared with that, the previous way encourages the exploitation. To enable inter-task knowledge transfer, there are three probabilities to need to be maintained, rlp, Pciand the probability of crossover exploration. We will discuss in these following sections. Last, the multifactorial evaluation is used to evaluate the current position and update the pbest and global beset position (gbest), which drive the evolution of the swarm.

3.1 Inter-task learning

In AMFPSO, the skill factor is viewed as the computational equivalent of the cultural trait. In the principle of memetic computation [31], the cultural trait of an individual can spread to another individual. Depending on how an agent acquires a meme,the modes of transmission are classified into two clusters, [14](a) vertical transmission of memes from the parents to the offspring; and (b) horizontal transmission of memes among peers.

To enable the inter-task knowledge transfer,we employ horizontal transmission to exchange cross-domain information among peer particles. The occurrence of inter-task learning action is determined by the random learning parameter （rlp）. The particles have two search modes. On the one hand, they can behave as routine in canonical PSO. On the other hand, they can learn searching experience from high-quality particles of other tasks by a learning-based inter-task information transfer strategy. The searching mode of a particle is controlled by Pci. In AMFPSO, the implicit transfer of knowledge is implemented via an elaborated learning strategy. When the inter-task learning occurs, particles’searching experience is transferred to other particles of another task by two learning methods in this work, (a) adding an inter-task acceleration term to the velocity updating equation, which infers the inter-task transfer of the searching step; (b) applying the crossover on the current personal best position and the inter-task particle’s personal best position when the particles change their skill factor. These two ways promote the shared problem-solving knowledge in differential aspects of exploration and exploitation.

The first method plays the main role in searching for knowledge transferring. Practically, this method is a relatively exploitative transfer method. The particle is mainly focused on the nearby area of the current position. We modify the velocity updated equation to implement the transfer of information inter-task. The velocity of canonical PSOs contains three parts as shown in (5). The first part is the inertial term. The second part is the cognition term,indicating the exploitation of its experience in the searching path and the third part is the social term representing the social experience sharing in the population [15, 32]. There exist several information sharing strategies in the literature, for example CCPSO [33], CMPSO [34], IILPSO [30] and so on, but they are for a single task. We present learning strategies herein to implement the transfer of shared cross-cultural information incorporated into the velocity updating equation. First, we select a subswarm assigned another task Tjfor the current particle xito learn from randomly. Then, a learned particle xjis selected from the learned subswarm by using roulette wheel selection((Algorithm 5) (see Fig. 4)). To keep the good structure of current good position, the rate of learning is different from different particles. So, the inter-particle learning probability is determined by the fitness of particle, described in the next section.

The learning strategy relies on a differential cooperative term inspired from the DE/target-to-best/1 differential mutation schemes[35] which helps the two-particle exchange the difference. Each dimension of the velocity updates by (4) in the probability Pci:

Fig. 4 Algorithm 5: Inter-task learning

where c3represents the weighting of the differential cooperative term and pg(k) is the gbest of the task k corresponding to skill factor.At the end of this equation is a differential term which pulls the particle out of local optimal areas. Herein, xj1and xj2are selected in the subpopulation of Tjrandomly. A random number is generated in uniform distribution ranged in [0, 1]. If it is less than Pci, this dimension of the velocity is updated by (4). Otherwise, the velocity is updated using the canonical PSO. The velocity equation is shown as follows:

In the second method, the particles can imitate the learned particles by inheriting the skill factor of them.If the particles change their skill factor,the inter-task crossover-based transfer is employed to update the personal best positions. This is a relatively explorative method which has a large exploration area covering the intermediate region of two particles’ personal best positions. Herein, the particle uses the simulated binary crossover in the inter-task learning to explore a broad area. In the canonical routine of updating the personal best position without inter-task learning, we use the scalar fitness to evaluate the candidate solutions. The personal best positions are updated by comparing the scalar fitnesses of the current position and personal best position. If the new solution’s scalar fitness is greater than the previous personal best position’s,the personal best position is replaced by the new solution. As aforementioned, we incorporate the two methods into the proposed MFPSO to absorb the advantages of them, developing an efficient inter-task learning strategy.

3.2 Multifactorial evaluation

For the sake of reducing the computational cost, we selectively evaluated the particles on the assigned task. In the proposed method, the population consists of particles assigned to different tasks. Thus, a unified performance index in the multifactorial environment is necessary in this case. Therefor we assign each particle in the population a scalar fitness which was proposed in[4]. Note that scalar fitness is a rank-based fitness function in the interval (0, 1) defined as fi=1/minj[{1,...,K}{rij}, where K is the number of tasks and rij is the rank index of the ith particle corresponding the jth task. According to the definition of scalar fitness in [4], scalar fitness is a relative criterion of evaluation. In order to calculate the scalar fitness, all particles and their personal best positions (pbests) are collected into a temporary population P?. The factorial ranks of particles and their pbests are based on the ranks in terms of the objective values of specified tasks in the scope of P?. Then the scalar fitnesses are computed by using the factorial ranks. If the particle’s scalar fitness is greater than its pbeset’s, pbest would be replaced by the particle.

The global best positions are responsible for guarantee enough pressure for driving the particle converging to separated optimal solutions of tasks. At the same time, pgcould be used to prevent the velocities of individuals assigned with differential tasks from getting excessively mixed-up. So, in this paper, we employ a specific strategy to update the gbest among population to make the knowledge transfer scheme more efficient. Since a population in AMFPSO is separated into K subpopulations assigned to K tasks,it is reasonable to store the current best solutions for all tasks,i.e. there are K global best positions forming an external repository{pg(1),pg(2), ...,pg(K)}. The pg(k) is responsible for promoting the convergence pressure of the particles in the subpopulation assigned to the kth task. In each iteration, pg(k) is updated by the individual with the best objective value in the subpopulation assigned to the task k.

3.3 Parameter self-adaptation

In the AMFPSO, there are three additional parameters, rlp, Pciand the probability of cultural transfer needed to determine.In MFO,the learning parameter rlp is used to achieve a trade-off between exploitation and exploration of the search space and indicates the frequency of cross-cultural learning process between different subpopulations. When rlp is set on a value close to 0, MFO forbids cross-cultural individuals to exchange experience and skill factor. On the contrary, a value of rlp close to 1 allows cross-cultural individuals to communicate with each other without any constrains. A larger rlp encourages the transfer of knowledge,thereby the information flows fast in the population. However, for most of the cases, the excessive exchanging between the individuals belonging to different task groups could result in degeneration of the population.

Therefore,the value of rlp must be chosen properly based on the cooperative relationship of tasks. In practice, there is generally no prior knowledge on the relationship of tasks in MFO.Consequently, the corresponding rlp parameter is hardly adjusted for the various problems in a single fixed value. At different stages of the evolutionary process, the cooperative relationship between subpopulation assigned to tasks could changes depending on the distribution of potential solutions. Therefore, a higher rlp value is required for the tasks which have more complementarities to take advantage of the problem-solving experience. While a relatively small rlp value is suitable for tasks having less complementarity to decrease negative transferring.

In this paper,a simple random searching method is introduced to adjust rlp parameter as per the performance feedback. At the beginning of the algorithm, the candidate list L of rlp are initialised by a list of the real values selected from the range[0, 0.8] evenly. The basic idea of the self-adaptive strategy is described as follows. The current rlp is stored in the candidate list L when at least one of {pg(k),k =1, ...,K} is updated by a better solution. Otherwise, the rlp is adapted. When rlp is adapted,an element is first selected from a list of candidates randomly.Then a Gaussian noise is added upon it to generate a new rlp parameter. This technique is straightforward and fast. The process is given in Algorithm 6 (see Fig. 5). As shown in Algorithm 6(Fig. 5), the process is quite simple that the computational complexity of the whole process of AMFPSO does not increase obviously compared with the original one.

Fig. 5 Algorithm 6: Self-adaption of learning parameter rlp

The parameter Pcicontrols the inter-particle velocity updating.To keep the good structure of current good position,the rate of learning is different from different particles. If a particle performs well, the probability the learning particle learns from the learned particle would be relatively low in order to keep the good position. So, the inter-particle learning probability is determined using the following equation:

where Pciranges round 0.1–0.7,is the factorial rank ofwith respect to Tj. N is the subpopulation size assigned Tj. In the inter-task learning process, the cultural transfer is implemented by the imitation of the current particle to the learned particle, where the crossover-based implicit transfer of personal best particles also occurs. This enables the knowledge transfer of personal best solutions, which makes use the problem-solving experience in this personal best level. Because this might cause large turbulence in the swarm, we control the rate of its occurrence under the probability of cultural transfer 0.1.

4 Experiments

We comprehensively evaluate the performances of the proposed AMFPSO algorithm on different kinds of MTO problems including:

? MTO problems with component tasks having different problem dimensionality (20D and 30D).

? MTO problems with component tasks having different global optima (with no or large interval).

? MTO problems with different numbers of component tasks (two tasks and three tasks).

? MTO problems used for the CEC’2017 competition [36].

In each of the above MTO problems, the component tasks are single-objective continuous optimisation problems with different complexity. We compare the proposed AMFPSO with the MFEA and canonical PSO algorithm in terms of the optimisation accuracy and convergence speed in the multi-tasking environment.Experimental results demonstrate the AMFPSO’s superiority over the compared algorithms.

4.1 Test problems

The test problems in the experiments are synthesised by using the wide-used functions described in [28]. We choose 7 continuous objective functions with differential properties. We will devise 11 test problems for validating the algorithms in terms of convergence speed and quality of solutions. The test problems are synthesised by using the mentioned objective functions. Each test problem consists of two or three component tasks.

The functions used to synthesise the composite problems are described below. These objective functions are classified into two categories [28]: (a) unimodal and simple multimodal benchmark functions, and (b) multimodal functions from popular benchmark problems. We will show those functions and properties of them as follows.

Group A: unimodual and simple multimodal problems: (1) Sphere modal; (2) Schwefel’s function 1.2; (3) Rosenbrock’s valley.

Group B: multimodal problems: (4) Ackley’s path function;(5) Griewank’s function; (6) Rastrigin’s function; (7) Weierstrass function.

Next, we will compose three sets of 2-task problems with the differential setting. What properties of the algorithms we want to test is the capacity of utilise shared problem-solving knowledge in differential complexities and differential searching spaces. Three groups suggest different complementarities in between the component tasks with different degrees of difficulties and biases on optima. The properties of three sets are described in Table 1.Each group consists of three test problems, which is synthesisedused the seven continuous functions and their variants with different dimensions and different degrees of biases. All nine test problems are listed in Table 2.

Table 1 Properties of different sets of test problems

Besides the test problems with two tasks, we also test the algorithms on the test problems with three tasks. As aforementioned, AMFPSO aims at solving multi-tasking problems effectively. To validate this feature, we test the proposed AMFPSO on a variety of composite problems in this section.Generally speaking, these multi-task optimisation problems can be classified into two categories. Set 10 is composed of the problems whose solutions are very close no more than a small gap. In this case, the individuals have more information to share. In the test problems Set 11, solutions of tasks have a larger gap in between and differential computational complexities. In this case, the complementarity of tasks is less than that in Set 10. Without loss of the generality, each composite problem consists of three constitutive independent tasks drawn from benchmark problems denoted as a composite three-factorial problem (t1, t2, t3). Two typical problems are choice in these experiments. See Table 3 for details. In this part of experiments, those translated problems are used to test the algorithms.

The CEC’17 benchmark problems [36] for MTO consist of nine various composite problems which are the combinations of commonly using benchmark single-objective problems. The benchmark problems are classified into three categories based on how their search spaces intersect and how similar they are inshape.Three categories are defined as the complete intersection(CI),partial intersection (PI) and no intersection (NI) according to the intersection of search spaces. Each category of problems also could be separated into three subjects based on the similarity of tasks, i.e. high similarity (HS), middle similarity (MS) and low similarity (LS), which infer inter-task synergy of component tasks.In summary, the all nine problems are (i) CI+HS, (ii) CI+MS,(iii) CI+LS, (iv) PI+HS, (v) PI+MS, (vi) PI+LS, (vii) NI+HS,(viii) NI+MS and (ix) NI+LS.

Table 2 Benchmark suits

Table 3 Comparison of AMFPSO, MFEA and PSO on the three-factorial composite problems with the same dimensionality

In summary,the experiments include six test cases:(i)Set 1,Set 2 and Set 3; (ii) Set 4, Set 5 and Set 6; (iii) Set 7, Set 8 and Set 9;(iv) Set 11; (v) Set 12; (vi) CEC’17 benchmark problems. The above all problems have described hereinbefore.

4.2 Performance metrics

We employ the metric defined in[36]for MTO to assess the overall performance, as a score of the algorithm. The score is shown as follows [36]. Assume we test N algorithm, A1,A2, ...,AN, on a test case having K optimisation tasks T1,T2,...,TK, and each algorithm runs L repetition. Ii,k,ldenotes the best objective values in the lth run on the task Tkof the algorithm Ai. Next, let mkand skdenote the mean and the standard deviation of the best objective values on the Tkoverall runs. Thereafter, we normalise the objective values denotedThe score Aiobtains is defined as follows:

The above measures are recorded in 30 independent runs in the terminal condition of no more than 100,000 evaluation calls in the test problems of two tasks. In the case of problems with three tasks, the terminal condition changes to 200,000 evaluation calls.

4.3 Experimental setup

The parameters c3in AMFPSO are set by using trail-and-error methods, and the inertia weight v, the cognitive coefficient c1and the social coefficient c2are used the typical values in [37]. All parameter settings for the proposed AMFPSO and other algorithms are listed as follows:

(a) PSO

? Population size, Np=100.

? Maximum NFEs for each task, MAXNFE=5×104.

? Inertia weight, v=0.4 [37].

? Acceleration constants, c1=2.05 and c2=2.05 [37, 26].

? Maximum velocity, Vmax=0.1.

(b) MFEA

? Population size, Np=100 [4].

? Maximum NFEs, MAXNFE=105.

? Maximum NFEs for three tasks, MAXNFE=2×105.

? Mutation probability, pm=0.1 [4].

? Crossover probability, pc=0.8 [4].

? Random mating probability, rmp=0.3 [4].

(c) AMFPSO

? Population size, Np=100.

? Maximum NFEs, MAXNFE=105.

? Maximum NFEs for three tasks, MAXNFE=2×105.

? Inertia weight, v=0.4 [37].

? Acceleration constants c1=2.05, c2=2.05 [37], c3=0.8.

? Maximum velocity, Vmax=0.1.

? Candidate list of rlp, L=[0.2,0.4,0.6,0.8].

4.4 Experimental results and discussions

4.4.1 Test case 1(Set 1,Set 2 and Set 3): In the first part of this experiment, we compared the proposed method with the other tested algorithms on MTO problems which contain two component problems that have the different complexity, the same dimensionality, and the same global optima. In this experiment series, for convenience, we fix the solutions of all benchmark functions on the origin of search space and all functions have minimal values equal to 0. The results of handling 3 benchmark problems over 30 independent runs are shown in Table 4. The best results of scores and mean of best objective values for each task are typed in boldface. The total scores are listed on the bottom of Table 4.

As shown in Table 4, AMFPSO and MFEA have similar performance and are both outperforming the PSO on the most problems. AMFPSO achieves best scores on Set 1, Set 2 and Set 3(–47.1293, ?42.3827, ?43.9352) against MFEA and PSO.Although the proposed AMFPSO has better scores, the means of best function values might be relatively bad in some tasks. This is mainly because although the objective values are bad in some tasks, the difference among the results of AMFPSO and the other algorithms is too small to influence the overall performances.For example, in T1of Set 1, PSO performs better. However, the disparity of the results between AMFPSO and PSO is small.By comparison the results of AMFPSO and MFEA in those problems, AMFPSO could relieve the influence of negative transfer. Besides, it is remarkable that AMFPSO improves the quality of optimal solutions, especially in multimodal tasks T1and T2in Set 3 reliably.

4.4.2 Test case 2 (Set 4, Set 5 and Set 6): The proposed MFO optimiser is tested on MTO problems which contain two component problems that have different complexity, the different dimensionality, and the same global optima. We verify the statement that cultural inherent has a positive effective on the convergence speed and global searching ability of PSO in the independent tasks with the various dimensionalities. In this part of experiments, all tasks in the composite problems all have 30 dimensions of variables. The results are shown in Table 4.

In Table 5, AMFPSO impresses on the capacity of handling problems different in dimensionalities. AMFPSO obtains the best scores (?47.1293, ?40.2899, ?53.5199) for the problems Set 4,Set 5 and Set 6, respectively, against MFEA (74.1748, 25.3644,?27.4940). In T1of Set 5, T1of Set 6, AMFPSO achieves a poor performance than PSO, but better than MFEA with respect to the mean of best objective values. On these tasks, PSO achieves better results in terms of the mean of best objective values. But the gap between AMFPSO and PSO is small. The phenomenon is led bythe fact that the information sharing by the individuals in different task sets having different dimensions are less than the situation where all tasks have the same dimensions of variables. The phenomenon is caused by the fact that the implicit transfer introduces a random perturbation in the dimensions in a task with a large dimension not intersected with the dimensions in the others with a small dimension.

Table 4 Comparison of AMFPSO,MFEA and PSO on composite two-factorial problems with the same dimensionality

Table 5 Comparison of AMFPSO,MFEA and PSO on the composite problem with different dimensionality

Table 6 Comparison of AMFPSO,MFEA and PSO on the composite problems with separated optima

4.4.3 Test case 3 (Set 7, Set 8 and Set 9): We will test the proposed AMFPSO on MTO problems which contain two component problems that have different degrees of complexity,the same dimensionality, and the different global optima. Firstly,in the case of small separation, the second function in a composite problem-set is shifted by 300 units (1 unit=1/1000) in the unified decision space and the optima of one function in the composite problem-set is in origin. The results are presented in Table 6.

The performances of AMFPSO are not such outstanding than PSO with diversity preserving technique in Set 7, Set 8 and Set 9. The AMFPSO shows its similarity with PSO, where inter-task learning plays a role in reserving diversity. MFEA has poor performance in Set 8. However, the AMFPSO has achieved good performance in some tasks. In Set 8 and Set 9, AMFPSO still achieves better optimal solutions against PSO. This mainly is because two objective functions still share some similarities in the large scale.So, at the beginning of the evolutionary process, the knowledge transfer helps the AMFPSO find potential areas quickly in both two search spaces.

4.4.4 Test case 4 (Set 10): In this case of experiments, the proposed AMFPSO is tested on MTO problems consisted of three component problems that have different degrees of complexity, the same dimensionality, and the same global optima. Fig. 6 illustrates the box plots based on the solutions obtained before reaching the max iterations over 30 independent runs for the composite problem Set 10. All the two methods, AMFPSO and MFEA,perform well on the three tasks and obtain the minimum objective values below 10?4. However, AMFPSO obtains smaller minimum objective values in T2and T3. Especially, in terms of stabilisation,AMFPSO has done better than MFEA in T2and T3. Fig. 7 shows the averaged convergence trends of AMFPSO for Set 10. The curve is compared with the one of MFEA. It is clear that the curve of AMFPSO is under the curve of MFEA on almost all of the sample points for Set 10. The proposed AMFPSO shows better performance than MFEA. In terms of quality of solutions, the results reported in Table 7 show that AMFPSO performs well on all tasks in Set 10. It is notable that the algorithm reliably discovers the optimum solution in T1and T2.

Fig. 6 Box plots of the distribution of solutions obtained by MFEA and AMFPSO on the three tasks in Set 10

4.4.5 Test case 5(Set 11): In this case,the tested algorithms run on Set 11 in which the test problem has three component problems that have different degrees of complexity, the same dimensionality,and the different global optima. The convergence trends of AMFPSO and MFEA on each task in Set 11 are presented in Fig. 8. The results on the solution quality of AMFPSO are reported in Table 8. According to the observation in this experiment, the proposed AMFPSO is provided its robustness and efficiency on the multi-tasking environments.

Fig. 7 Averaged trends of the composite problem Set 10 (Rastrigin,Rosenbrock, Weierstrass) in AMFPSO and MFEA

Table 7 Performance of AMFPSO on Set 10 problems

Fig.8 Averaged trends of the composite problem Set 11(Ackley,Rastrigin,Griewank) in AMFPSO and MFEA

Table 8 Performance of AMFPSO on Set 11 problems

Fig. 9 Box plots of the distribution of solutions obtained by MFEA and AMFPSO on the three tasks in Set 11

When the curve of AMFPSO is compared with MFEA on(T1, T2, T3) in the composite problem Set 11, the improvement on T1and T3is not observed in Table 8. However, it is observed that AMFPSO has more advantage on the T2from the aspect of convergence speed in the composite problem Set 11, AMFPSO obtains the top results of the convergence speed and solution precision on (T1, T2, T3) among two algorithms. Fig. 9 suggests that for the three tasks with separated optima. As what we see in the box plot, maximum values of three tasks AMFPSO obtains are always smaller than that MFEA obtains. All the two algorithms can obtain minimum values less than 10?8in almost all the 30 independent runs. Though the differences between AMFPSO and MFEA in terms of the objective values obtained are small, AMFPSO works better than MFEA from the aspect of robustness.

4.4.6 Test case 6 (CEC’17 MTO benchmark problems): In this part of experiments, we will run the proposed MFPSO on CEC’17 benchmark problems [The using codes of all benchmark problems are available at http://www.ntu.edu.sg/home/asysong/mfo/home.htm.] and compare it with the baseline of the benchmark problems. The average performances of the two algorithms are reported in Table 9 and the better results are shown in bold.

As what is shown in Table 9, MFPSO achieves better average performances on almost all of the problems. In terms of scores,MFPSO attains smaller scores on No. 1-2 and No. 4-8 tasks,which means MFPSO has better overall performances on these tasks compared with MFEA. Although MFPSO shows larger scores (less score is better) in No. 3 and No. 9 tasks (56.1540 versus ?56.1640 and 4.7540 versus ?4.7540), it is hard to judge whether MFEA defeats MFPSO by surveying the results on these problems. It is shown that MFPSO has a better mean of objective function compared with MFEA (8.0231 versus 20.1580 in CI+LS and 327.1625 versus 593.8957 in NI+LS). The poor performances MFPSO suffering in CI+HS and NI+LS where T2’s optimum is located on the position near the higher box boundary might be caused by the PSO’s underlying defect in handling the particles close to the boundary of decision space.Because MFPSO has lower average objective function value on one of two tasks, in this case, T1 of both the problems CI+LS and NI+LS. Although, MFPSO has poor performances on T2 of these two composite problems.

Table 9 Results of MFPSO and MFEA running on the nine composite problems

5 Conclusions and future work

In this work,we proposed an AMFPSO algorithm by devising new knowledge transfer schemes to explore a broad area by employing a new velocity updating strategy and inter-task simulated binary crossover. In addition, we incorporate a self-adaptive strategy to tune the inter-task learning probability according to the feedback of the algorithm’s performance. The performances of the proposed AMFPSO algorithm were evaluated on various kinds of multi-task single-objective continuous optimisation problems in comparison with the MFEA as well as a canonical PSO algorithm working in the single task scenario. Experimental results demonstrate the superiority of the AMFPSO over the compared algorithms.

The proposed AMFPSO is merely a preliminary attempt to make the inter-task learning probability self-adaptive, which leaves much room to be further investigated. For example, the existing knowledge transfer schemes seldom separate useless and useful transfers with respect to a specific component task, which may lead to the degraded performance when too many less helpful(or even harmful) transfers are executed. Therefore, how to identify and avoid less useful knowledge transfers (and accordingly promote more helpful transfers) with respect to a specific component task will be one of our future work.

6 References

[1] Ong, Y.S., Gupta, A.: ‘Evolutionary multitasking: a computer science view of cognitive multitasking’, Cogn. Comput., 2016, 8, (2), pp. 125–142

[2] Back,T.,Hammel,U.,Schwefel,H.P.:‘Evolutionary computation:comments on the history and current state’,IEEE Trans.Evol.Comput.,1997,1,(1),pp.3–17

[3] Ong,Y.S.:‘Towards evolutionary multitasking:a new paradigm in evolutionary computation’, Proc. Computational Intelligence, Cyber Security and Computational Models, Coimbatore, India, 2015, pp. 25–26

[4] Gupta, A., Ong, Y.S., Feng, L.: ‘Multifactorial evolution: toward evolutionary multitasking’, IEEE Trans. Evol. Comput., 2016, 20, (3), pp. 343–357

[5] Yao, X.: ‘Evolutionary computation’, in Sarker, R., Mohammadian, M. (Eds.):‘Evolutionary Optimization’ (Springer, Boston, US, 2002), pp. 27–53

[6] Gupta,A.,Ong,Y.S.,Feng,L.,et al.:‘Multiobjective multifactorial optimization in evolutionary multitasking’, IEEE Trans. Cybern., 2017, 47, (7),pp. 1652–1665

[7] Yuan, Y., Ong, Y.S., Gupta, A., et al.: ‘Evolutionary multitasking in permutation-based combinatorial optimization problems: realization with TSP,QAP, LOP, and JSP’. Proc. IEEE Region 10 Conf., Singapore, 2016,pp. 3157–3164

[8] Sagarna, R., Ong, Y.S.: ‘Concurrently searching branches in software tests generation through multitask evolution’. Proc. IEEE Symp. Series on Computational Intelligence, Athens, Greece, 2016

[9] Zhou,L.,Feng,L.,Zhong,J.,et al.:‘Evolutionary multitasking in combinatorial search spaces: a case study in capacitated vehicle routing problem’. Proc. IEEE Symp. Series on Computational Intelligence, Singapore, 2016

[10] Chandra, R., Gupta, A., Ong, Y.S., et al.: ‘Evolutionary multi-task learning for modular training of feedforward neural networks’. Proc. Int. Conf. on Neural Information Processing, Kyoto,Japan, 2016, pp. 37–46

[11] Feng, L., Zhou, W., Zhou, L., et al.: ‘An empirical study of multifactorial PSO and multifactorial DE’. Proc. IEEE Congress on Evolutionary Computation(CEC), Rio, 2017, pp. 921–928

[12] Zhang, B., Qin, A.K., Sellis, T.: ‘Evolutionary feature subspaces generation for ensemble classification’. Proc. Genetic and Evolutionary Computation Conf.,Kyoto, 2018, pp. 577–584

[13] Eberhart, R.C., Kennedy, J.: ‘A new optimizer using particle swarm theory’.Proc. Int. Symp. on Micro Machine and Human Science, Nagoya, Japan, 1995,vol. 1, pp. 39–43

[14] Chen, X., Ong, Y.S., Lim, M.H., et al.: ‘A multi-facet survey on memetic computation’, IEEE Trans. Evol. Comput., 2011, 15, (5), pp. 591–607

[15] Li, C., Yang, S., Nguyen, T.T.: ‘A self-learning particle swarm optimizer for global optimization problems’, IEEE Trans. Syst., Man, Cybern. B, Cybern.,2012, 42, (3), pp. 627–646

[16] Xin,B.,Chen,J.,Zhang,J.,et al.:‘Hybridizing differential evolution and particle swarm optimization to design powerful optimizers: a review and taxonomy’,IEEE Trans. Syst., Man, Cybern. C, Appl. Rev., 2012, 42, (5), pp. 744–767

[17] Coello Coello, C.A.: ‘Evolutionary multi-objective optimization: a historical view of the field’, IEEE Comput. Intell. Mag., 2006, 1, (1), pp. 28–36

[18] Chen,W.N.,Zhang,J.,Chung,H.S.H.,et al.:‘A novel set-based particle swarm optimization method for discrete optimization problems’, IEEE Trans. Evol.Comput., 2010, 14, (2), pp. 278–300

[19] Duan, H., Luo, Q., Shi, Y., et al.: ‘Hybrid particle swarm optimization and genetic algorithm for multi-uav formation reconfiguration’, IEEE Comput.Intell. Mag., 2013, 8, (3), pp. 16–27

[20] Gong, M., Cai, Q., Chen, X., et al.: ‘Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition’,IEEE Trans. Evol. Comput., 2014, 18, (1), pp. 82–97

[21] Hu, W.,Yen,G.G.: ‘Adaptive multiobjective particle swarm optimization based on parallel cell coordinate system’, IEEE Trans. Evol. Comput., 2015, 19, (1),pp. 1–18

[22] Bali, K.K., Gupta, A., Feng, L., et al.: ‘Linearized domain adaptation in evolutionary multitasking’. In: Proc. IEEE Congress on Evolutionary Computation (CEC), San Sebastian, Spain, 2017, pp. 1295–1302

[23] Wen,Y.W.,Ting,C.K.:‘Parting ways and reallocating resources in evolutionary multitasking’. In: Proc. IEEE Congress on Evolutionary Computation (CEC),San Sebastian, Spain, 2017, pp. 2404–2411

[24] Ding, J., Yang, C., Jin, Y., et al.: ‘Generalized multi-tasking for evolutionary optimization of expensive problems’, IEEE Trans. Evol. Comput., 2018,in press, DOI: 10.1109/TEVC.2017.2785351

[25] Feng, L., Zhou, L., Zhong, J., et al.: ‘Evolutionary multitasking via explicit autoencoding’, IEEE Trans. Cybern., 2018, in press, DOI: 10.1109/TCYB.2018.2845361

[26] Eberhart,R.C.,Shi,Y.:‘Particle swarm optimization:developments,applications and resources’.Proc.IEEE Congress on Evolutionary Computation,Seoul,South Korea, 2001, vol. 1, pp. 81–86

[27] Blum, C., Li, X.: ‘Swarm intelligence in optimization’. In: ‘Swarm intelligence’(Springer, Heidelberg, 2008), pp. 43–85

[28] Liang, J.J., Qin,A.K., Suganthan, P.N.,et al.:‘Comprehensive learning particle swarm optimizer for global optimization of multimodal functions’, IEEE Trans.Evol. Comput., 2006, 10, (3), pp. 281–295

[29] Sabat, S.L., Ali, L., Udgata, S.K.: ‘Integrated learning particle swarm optimizer for global optimization’, Appl. Soft. Comput., 2011, 11, (1), pp. 574–584

[30] Qin, Q., Cheng, S., Zhang, Q., et al.: ‘Particle swarm optimization with interswarm interactive learning strategy’, IEEE Trans. Cybern., 2016, 46, (10),pp. 2238–2251

[31] Feng, L., Ong, Y.S., Lim, M.H., et al.: ‘Memetic search with interdomain learning: a realization between cvrp and carp’, IEEE Trans. Evol. Comput.,2015, 19, (5), pp. 644–658

[32] Bonyadi, M.R., Michalewicz, Z., Li, X.: ‘An analysis of the velocity updating rule of the particle swarm optimization algorithm’, J. Heuristics, 2014, 20, (4),pp. 417–452

[33] Li, X., Yao, X.: ‘Cooperatively coevolving particle swarms for large scale optimization’, IEEE Trans. Evol. Comput., 2012, 16, (2), pp. 210–224

[34] Zhan,Z.H.,Li,J.,Cao,J.,et al.:‘Multiple populations for multiple objectives:a coevolutionary technique for solving multiobjective optimization problems’,IEEE Trans. Cybern., 2013, 43, (2), pp. 445–463

[35] Das,S.,Suganthan,P.N.:‘Differential evolution:A survey of the state-of-the-art’,IEEE Trans. Evol. Comput., 2011, 15, (1), pp. 4–31

[36] Da,B.,Ong,Y.S.,Feng,L.,et al.:‘Evolutionary multitasking for single-objective continuous optimization:Benchmark problems,performance metric,and baseline results’ [online], 2017, arXiv:1706.03470. Available at https://arxiv.org/abs/1706.03470.

[37] Jagannath, S., Panda, G.: ‘A survey on nature inspired metaheuristic algorithms for partitional clustering’, Swarm Evol. Comput., 2014, 16, pp. 1–18