key: cord-0045753-a3jz98xp
authors: Osaba, Eneko; Del Ser, Javier; Yang, Xin-She; Iglesias, Andres; Galvez, Akemi
title: COEBA: A Coevolutionary Bat Algorithm for Discrete Evolutionary Multitasking
date: 2020-05-25
journal: Computational Science - ICCS 2020
DOI: 10.1007/978-3-030-50426-7_19
sha: 654a2012ec3ac733198879306758a2897b9b209a
doc_id: 45753
cord_uid: a3jz98xp

Multitasking optimization is an emerging research field which has attracted lot of attention in the scientific community. The main purpose of this paradigm is how to solve multiple optimization problems or tasks simultaneously by conducting a single search process. The main catalyst for reaching this objective is to exploit possible synergies and complementarities among the tasks to be optimized, helping each other by virtue of the transfer of knowledge among them (thereby being referred to as Transfer Optimization). In this context, Evolutionary Multitasking addresses Transfer Optimization problems by resorting to concepts from Evolutionary Computation for simultaneous solving the tasks at hand. This work contributes to this trend by proposing a novel algorithmic scheme for dealing with multitasking environments. The proposed approach, coined as Coevolutionary Bat Algorithm, finds its inspiration in concepts from both co-evolutionary strategies and the metaheuristic Bat Algorithm. We compare the performance of our proposed method with that of its Multifactorial Evolutionary Algorithm counterpart over 15 different multitasking setups, composed by eight reference instances of the discrete Traveling Salesman Problem. The experimentation and results stemming therefrom support the main hypothesis of this study: the proposed Coevolutionary Bat Algorithm is a promising meta-heuristic for solving Evolutionary Multitasking scenarios.

congregated an active scientific community in recent years [28] . The principal idea behind this field is to exploit what has been learned through the optimization of one specific problem or task, when tackling of another related or unrelated optimization task. Due to its relative youth, Transfer Optimization has not been studied as deeply as other research areas. It has not been until these last years when the transferability of knowledge among tasks has become a priority among researchers from the Evolutionary Computation arena.

Within the Transfer Optimization paradigm, three separated categories can be identified: sequential transfer, multitasking and multiform optimization. The first of these classes refers to those situations in which tasks are faced sequentially, assuming that for solving a new problem/instance, the knowledge collected when solving previous tasks is used as external information [11] . The second of these categories (Multitasking) deals with different optimization tasks simultaneously by dynamically scrutinizing existing complementarities and synergies among them [16, 39] . Finally, multiform optimization aims at solving a single problem by resorting to different alternative problem formulations, which are optimized simultaneously. In all these categories, there is a clear consensus in the community on the capital importance of the correlation among the tasks to be solved for positively capitalizing on the transfer of knowledge over the search [17] .

Among the three divisions pointed out above, multitasking is the one that has arguably grasped most attention by the community. The study presented in this manuscript is focused on this specific category. Specifically, we focus on multitasking optimization through the perspective of Evolutionary Multitasking (EM, [27] ). In short, EM tackles the simultaneous optimization of several optimization tasks by relying on concepts and methods from Evolutionary Computation [1, 8] . In the last years, a particular flavor of EM grounded on the so-called Multifactorial Optimization strategy (MFO, [17] ) has shown a superior efficiency when dealing with different environments involving several continuous, discrete, singleoptimization and multi-objective optimization problems and tasks [14, 18, 38, 43] . The majority of the literature related to this area is focused on a solver belonging to this flavor: the Multifactorial Evolutionary Algorithm (MFEA, [17] ). Unfortunately, alternatives to MFEA still remain scarce to date.

Bearing this in mind, the research work presented in what follows revolves on a novel EM meta-heuristic algorithm that adopts the Bat Algorithm (BA, [41] ) at its core. Specifically, we present a Coevolutionary Bat Algorithm (COEBA) for discrete evolutionary multitasking. Through this proposal, we take a step further over the state of the art by elaborating on a new research direction in two different directions. On the one hand, we contribute to the EM area by introducing a new efficient meta-heuristic scheme. It is important to point out here that, unlike most articles published so far around EM, COEBA does not find its inspirational source in the MFO paradigm. On the other hand, COEBA is the first attempt at using BA for Transfer Optimization.

It is also relevant to underscore here that the experimentation carried out in this paper considers a less studied discrete environment comprising different instances of the Traveling Salesman Problem (TSP, [21] ). Concretely, we assess the performance of the proposed COEBA by comparing its performance to that obtained by MFEA. Our main purpose with this performance comparison is to elucidate that COEBA embodies a promising alternative to deal with EM scenarios. To this end, we have chosen 8 different TSP instances, giving rise to 15 multi-tasking environments with varying degrees of phenotypical relationship.

The rest of the paper is organized as follows. Section 2 introduces the background related to both Evolutionary Multitasking and the Bat Algorithm. Next, Sect. 3 exposes in detail the main features of the proposed COEBA. The experimentation setup, analysis and discussion of the results are given in Sect. 4 . The study ends in Sect. 5 with conclusions and future research directions.

This section is dedicated to providing a brief background on Evolutionary Multitasking (Sect. 2.1) and the Bat Algorithm (Sect. 2.2).

In recent years, EM has arisen as a promising paradigm for facing simultaneous optimization tasks. There are two main features that motivated the first formulation of EM. The first one is the parallelism inherent to the population of individuals, which eases the management of diverse concurrent optimization tasks faced simultaneously. Thanks to this feature, latent synergies between tasks can be automatically harnessed during the solving process [28] . The second feature is the continuous transfer of genetic material between the individuals, which allows all tasks to benefit from each other, even for those that are not strongly correlated with the rest of the pool [17] .

It is widely accepted that the concept of EM was only materialized through the vision of the MFO until late 2017 [6] . Today, this nascent research stream is receiving interesting contributions in terms of new algorithmic schemes, such as the Coevolutionary Multitasking scheme proposed in [5] , or the multitasking multi-swarm optimization described in [37] . Additional alternatives to MFEA have also been proposed, such as the multifactorial brain storm optimization algorithm presented in [45] , the Multifactorial Differential Evolution in [10] or the hybrid particle swarm optimization-firefly algorithm introduced in [40] . Despite these recently proposed methods, MFO and its related MFEA have monopolized the research activity around this field since its inception. In fact, the authors of MFEA have recently introduced an adaptive variant of MFEA, coined as MFEA-II, thereby eliciting the momentum played by this algorithm in the field [2] .

Going into mathematical details, we can formulate EM as an environment in which K tasks or problems should be optimized in a simultaneous fashion. This environment is characterized by the existence of as many search spaces as tasks. Thus, for the k-th task, its objective function T k is characterized as f k : Ω k → R, where Ω k represents the search space of T k . Let us assume that all tasks are minimization problems, so that the main objective of EM is to find a set of solutions {x 1 , . . . , x K } such that x k = arg min x∈Ω k f k (x). A crucial aspect to properly understand EM is that all individuals x p in the population P to be evolved belong to a unified search space Ω U that relates to Ω 1 to Ω K by means of a encoding/decoding mapping functions ξ k :

to represent a taskspecific solution x p,k for each of the K tasks. Shifting our attention on MFO and MFEA, four different definitions are associated with each individual x p of the population P : Factorial Cost, Factorial Rank, Scalar Fitness and Skill Factor. With the intention accommodating this work to the extension requisites, we refer interested readers to [2, 17] for additional deeper details on how these definitions are exploited during the search over the unified space Ω U . Several significant works have been recently published around EM and MFO. In [44] , authors present an influential application of the MFEA to different discrete problems. This paper also introduces the discrete unified encoding, used as a reference in subsequent works. A related study is [47] , where MFEA was applied to the Vehicle Routing Problem. Gong et al. presented in [14] and improved version of the MFEA, endowing the algorithm with a dynamic resource allocating strategy. An interesting discrete MFEA has been also developed in [38] for the composition of semantic web services. Gupta et al. presented in [18] a multi-objective variant of MFEA, giving evidence of its efficiency on a real-world manufacturing process design problem. Finally, the work in [43] follows a similar strategy by enhancing MFEA with the incorporation of opposition-based learning. Further theoretical studies on EM and MFEO can be found in [22, 46] .

BA is a nature-inspired metaheuristic based on the echolocation system of bats. In the nature, bats emit ultrasonic pulses to the surrounding environment with navigation and hunting purposes. After the emission of these pulses, bats listen to the echoes, and based on them they can locate themselves and also identify and locate preys and obstacles. Besides that, each bat is able to find the most "nutritious" areas performing an individual search, or moving towards a "nutritious" location previously found by any other component of the swarm. It is important to mention that some rules have to be previously established with the aim of making an appropriate adaptation [41] :

1. All bats use echolocation to detect the distance, and they are assumed to be able to distinguish between an obstacle and a prey. 2. All bats fly randomly at speed v i and position x i , emitting pulses with a fixed frequency f min , varying wavelength λ and loudness A i to search for a prey.

In this idealized rule, it is assumed that every bat can adjust in an automatic way the frequency (or wavelength) of the pulses, emitted at a rate r ∈ [0, 1]. This automatic adjustment depends on the proximity of the targeted prey. 3. In the real world, the bats' emissions loudness can vary in many different ways.

Nevertheless, we assume that this loudness can vary from a large positive A 0 to a minimum constant value A min .

Since its proposal, BA has emerged as one of the most successful metaheuristic solvers. It has been applied to a manifold of problems such as logistic [32] , industry [24] , or medicine [19] . The literature behind BA is huge and diverse, as manifested by comprehensive surveys on practical applications of BA [12, 42] .

Following concepts previously embraced by other alternatives in the literature [5] , one of the main characteristics of the designed COEBA is its multi-population nature. By this we mean that COEBA is a method composed by a defined number of populations, or demes [25] , comprised by the same number of individuals. More specifically, the number of groups is equal to K, i.e. the number of tasks to be optimized. Additionally, each of the K subpopulations concentrates on solving a specific task T k . This means that bats corresponding to the k-th deme are only evaluated on task T k .

As in MFEA, a unified representation Ω U is used for encoding individuals. However, the most innovative aspect of COEBA is that each subpopulation has its own search space. This involves a slight size readjustment when different demes exchange individuals among them. We will hereafter use the TSP to show this size readjustment problem. Hence, we denote the size of each problem T k (i.e. the number of cities) as D k . Let us assume that individual x i is encoded as a permutation of the integer set {1, 2, . . . , D k }. In this way, when x k p ∈ Ω k is migrated to a subpopulation in which the size of task T k to be solved is D k < D k , only integers lower than D k are considered, thus reducing the phenotype of the individual. These integers maintain the same order as in x k p . The reverse procedure applies if D k > D k . In that case, and considering that each time an individual x k p is transferred to a deme it replaces an alternative bat x k p , all integers between D k and D k are inserted in x k p in the same positions as in x k p . This multiple search space strategy enhances the exploitation of the search over the demes, making the movement operators more effective.

With all these considerations in mind, Algorithm 1 shows the pseudocode of the designed COEBA. As can be seen, in the initialization process a number X of individuals are randomly generated. After initialization, each individual is evaluated over all K tasks. Then, within an iterative process, each subpopulation is built by choosing the top X/K individuals for the corresponding task (the same bat can be selected by different tasks). Once demes are composed, each one is evolved independently by following the concepts of the discrete version of the BA [32] . To be more concise, the distance between two different bats is measured by means of the Hamming Distance, namely, the number of non-corresponding elements in the sequence. Furthermore, the inclination mechanism is also used [31] . Thanks to this feature (lines 10-14 in Algorithm 1), the method intelligently selects the movement function suited for each bat at every iteration, depending on its specific situation regarding the leading bat of the swarm. As is shown in Algorithm 1, 2-opt and insertions are used as movement functions. if v t i <n/2 then

if rand>ri then 15 Select one solution among the best ones 16 Generate a new bat by selecting the best neighbor of the chosen bat 17 if rand<Ai and f (xi)<f (x * ) then 18 Accept the new solution 19 Increase ri and reduce Ai 20 if iteration is multiple of migr then 21 Two random individuals are migrated from k to another randomly selected subpopulation 22 Return the best individual in P for each task T k Moreover, every migr iterations, each group transfers two individuals to a randomly selected population. These two bats are selected by following this criterion: the first one is selected uniformly at random among the best 10 individuals of the population, while the second one is drawn from the complete subpopulation. These two individuals substitute two randomly chosen bats, not considering the 10 best ones of the deme where the replacement is done. Finally, COEBA finishes its execution after I iterations, returning as its solution the best bat of each subpopulation. Any other stopping criterion can be adopted with no further consequences to the design of the algorithm.

To assess the performance of the designed COEBA solver, an extensive experimentation has been carried out, which is described in depth in this section. As such, Subsect 

As introduced in Sect. 1, the experiments performed in this work consider the TSP as their benchmark problem to be optimized simultaneously. Readers interested on the formulation and theoretical aspects of this classical problem are referred to [3] or [26] . Arguably, TSP has become one of the most often used problems for performance analysis of discrete optimization algorithms. A plethora of meta-heuristic solvers have been applied to the TSP, or to any of its variants, from traditional techniques such as the Genetic Algorithm [15] , Ant Colony Optimization [9] or Tabu Search [13] , to modern discrete solvers such as Firefly Algorithm [20] , Cuckoo Search [33] , or the Water Cycle Algorithm [30] . Before proceeding further, it is important to bear in mind that the goal of the experiments is not to reach the optimal solution of the TSP instances under consideration, but to statistically compare the performance of both MFEA and COEBA when using the same instances and evaluation conditions. This being said, the performance of COEBA and its counterpart MFEA has been measured over 8 TSP instances, which are combined to yield 15 different test scenarios. All instances have been retrieved from the TSPLIB repository [36] . Specifically, the first 8 instances of the Padberg/Rinaldi benchmark have been employed: pr76, pr107, pr124, pr136, pr144, pr152, pr226, and pr264.

For the sake of fairness in the comparisons, similar parameters and operators have been used for both MFEA and COEBA. This way, we can objectively conclude which solver reaches better outcomes using similar evaluation conditions. To ensure the replicability of this study, parameters employed for the implemented algorithms are depicted in Table 1 . For this parameter setting, not only [17, 42, 44] , but also good practices reported in the community for tackling routing problems [29] . In addition, all bats are initialized uniformly at random. As the termination criterion, each algorithm is stopped after I = 500 · 10 3 objective function evaluations. As mentioned before, 15 different test scenarios have been built for the experimentation. Each of these multitasking configurations implies that both COEBA and MFEA should face the resolution of all the tasks assigned to that scenario simultaneously. Among these test cases, 10 of them are composed by 4 TSP instances, 4 scenarios are comprised by 6 TSP instances, and the last one includes all the 8 instances. Table 2 summarizes all the considered configurations. The main rationale for building these tests scenarios is twofold: i) to reach conclusions over a diverse and heterogeneous set of multitasking scenarios, involving each TSP instance in exactly the same number of cases, and ii) to exploit the possible genetic complementarities of the instances. Finally, all tests have been carried out on an Intel Xeon E5 -2650 v3 computer, with 2.30 GHz and a RAM of 32 GB. Moreover, each test case has been run 20 times to account for the statistical significance of performance gaps encountered during the experimentation. Table 3 depicts the comparisons in the results reached by COEBA and MFEA. Due to lack of space, we omit all the average outcomes for each test case. Instead, we show graphically the comparison using two colored circles. A green circle ( ) implies that COEBA has performed better than MFEA in terms of fitness average. On the contrary, a red circle ( ) means that MFEA has achieved better results on average. Using Test Case 4 3 as an example, and considering Table 2 , we observe that COEBA performs better in pr76, pr226, and pr264, while MFEA is better in pr107. Thus, analyzing the content of the Table 3 , we conclude that COEBA clearly outperforms MFEA over these EM scenarios, being superior to MFEA in all but 4 TSP instances evolved jointly. It is also crucial to highlight that COEBA obtains better outcomes in all the eight instances evolved jointly in Test Case 8. ---Test Case 4 10 ---

For extending the coverage and insights provided by this experimentation, we depict in Table 4 the outcomes obtained by COEBA and MFEA for the 8 TSP instances that compose Test Case 8. We show the average, best and standard deviation of results for each instance. Furthermore, we also provide the best known optima reported for each TSP instance in the literature. These results confirm that the proposed COEBA is a promising meta-heuristic for solving EM environments, outperforming MFEA in terms of both average and best outcomes in this context. Even though it is not the goal of this work, it is also relevant to note that the difference between the optimal outcomes and the average results obtained by COEBA ranges between 0.4% and 5.6%, thereby showing that our proposal not only performs competitively for multitasking environments, but also gets close to optimality of the tasks under consideration. In order to buttress our conclusions with the statistical significance of these identified gaps, the Wilcoxon Rank-Sum test has been applied, rendering the results depicted in the last row of Table 4 . The confidence interval has been set to 95%. We have compared the outcomes obtained for all the 8 TSP instances separately. Accordingly, the last row of Table 4 represent the outcomes of these statistical tests. Specifically, a green circle ( ) means that COEBA outperforms MFEA with statistical significance. On the contrary, the red circle ( ) would have indicated the non-existence of evidences for ensuring the statistical significance of a gap between MFEA and COEBA. As can be seen in this table, Wilcoxon Rank-Sum test confirms that COEBA significantly outperforms MFEA in all the 8 instances embedded in this test scenario. The obtained average z-value is −2.68, with an average p-value equal to 0.00888. Considering that the critical z c value is −1.64, and because −2.68 < −1.64 and 0.00888 < 0.05, these outcomes support the significance of the performance differences at 95% confidence level. Thus, the difference is significant at this confidence level, thereby concluding that the COEBA is statistically better than MFEA for this test scenario.

This manuscript has elaborated on the design, implementation and validation of a novel approach for solving evolutionary multitasking environments, wherein tasks are optimization problems. For reaching this goal, we have introduced the Coevolutionary Bat Algorithm (COEBA), which finds its source of inspiration from the concepts of evolutionary co-evolution and the discrete adaptation of the Bat Algorithm. A subpopulation is devoted for the optimization of each problem, with a migration policy that allow exchanging genotype information and exploiting synergies among problems. For showcasing the application of the proposed multitasking approach, an experimental setup has been devised embracing instances of the Traveling Salesman Problem as benchmark problems to be jointly solved. We have compared the outcomes attained by COEBA with the ones furnished by Multifactorial Evolutionary Algorithm (MFEA) over 15 different multitasking test cases. The results validate our hypothesis: COEBA is a promising meta-heuristic for addressing multitasking scenarios.

Several research lines have been planned to gain insight beyond the findings reported in this study. In the short term, we will gauge the scalability of COEBA by analyzing its performance and computational efficiency when simultaneously solving test cases comprising TSP instances of larger dimensionality. We also plan to design additional search mechanisms (such as alternative migration strategies), all targeted at reinforcing the transfer of knowledge among related tasks (positive transfer ), and lowering the genotype exchange among those tasks that are not related to each other (correspondingly, negative transfer ). In the longer term, we will explore the application of COEBA to problems stemming from other research fields [35] with discrete optimization problems at their core, such as community detection in social networks.

Handbook of Evolutionary Computation

Multifactorial evolutionary algorithm with online transfer parameter estimation: MFEA-II

The traveling salesman problem: a survey

Multitask learning

Coevolutionary multitasking for concurrent global optimization: with case studies in complex engineering design

Evolutionary multitasking for single-objective continuous optimization: benchmark problems, performance metric, and baseline results

Job shop scheduling with genetic algorithms

Bio-inspired computation: where we stand and what's next

Ant colony system: a cooperative learning approach to the traveling salesman problem

An empirical study of multifactorial PSO and multifactorial DE

Memes as building blocks: a case study on evolutionary optimization+ transfer learning for routing problems

A brief review of natureinspired algorithms for optimization/kratki pregled algoritmov po vzoru iz narave za optimizacijo

A tabu search heuristic for the undirected selective travelling salesman problem

Evolutionary multitasking with dynamic resource allocating strategy

Genetic algorithms for the traveling salesman problem

Genetic transfer or population diversification? Deciphering the secret ingredients of evolutionary multitask optimization

Multifactorial evolution: toward evolutionary multitasking

Multiobjective multifactorial optimization in evolutionary multitasking

Enhanced singular value decomposition for prediction of drugs and diseases with hepatocellular carcinoma based on multi-source bat algorithm based random walk

Solving travelling salesman problem using firefly algorithm

The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization

Multipopulation evolution framework for multifactorial optimization

Computer solutions of the traveling salesman problem

Bi-population based discrete bat algorithm for the low-carbon job shop scheduling problem

Integer programming formulation of traveling salesman problems

Towards evolutionary multitasking: a new paradigm in evolutionary computation. In: Senthilkumar

Evolutionary multitasking: a computer science view of cognitive multitasking

Good practice proposal for the implementation, presentation, and comparison of metaheuristics for solving routing problems

A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem

An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems

A discrete and improved bat algorithm for solving a medical goods distribution problem with pharmacological waste collection

Discrete cuckoo search algorithm for the travelling salesman problem

A survey on transfer learning

Nature-Inspired Optimization Algorithms for Fuzzy Controlled Servo Systems

TSPLIB: a traveling salesman problem library

Multitasking multi-swarm optimization

Evolutionary multitasking for semantic web service composition

Parting ways and reallocating resources in evolutionary multitasking

Multifactorial PSO-FA hybrid algorithm for multiple car design benchmark

Nature Inspired Cooperative Strategies for Optimization (NICSO 2010)

Bat algorithm: literature review and applications

Multifactorial differential evolution with opposition-based learning for multi-tasking optimization

Evolutionary multitasking in permutation-based combinatorial optimization problems: realization with TSP, QAP, LOP, and JSP

Multifactorial brain storm optimization algorithm

Towards effective mutation for knowledge transfer in multifactorial differential evolution

Evolutionary multitasking in combinatorial search spaces: a case study in capacitated vehicle routing problem