dMFEA-II: An Adaptive Multifactorial Evolutionary Algorithm for Permutation-based Discrete Optimization Problems
This work provides an incremental adaptation of an existing algorithm for researchers and practitioners in optimization, specifically targeting discrete problems like routing and scheduling.
The authors tackled the challenge of adapting the Multifactorial Evolutionary Algorithm II (MFEA-II) to permutation-based discrete optimization problems, such as the Traveling Salesman and Capacitated Vehicle Routing Problems, by reformulating concepts like parent-centric interactions for discrete search spaces, and demonstrated its good performance across 5 multitasking setups with 8 datasets compared to the discrete MFEA.
The emerging research paradigm coined as multitasking optimization aims to solve multiple optimization tasks concurrently by means of a single search process. For this purpose, the exploitation of complementarities among the tasks to be solved is crucial, which is often achieved via the transfer of genetic material, thereby forging the Transfer Optimization field. In this context, Evolutionary Multitasking addresses this paradigm by resorting to concepts from Evolutionary Computation. Within this specific branch, approaches such as the Multifactorial Evolutionary Algorithm (MFEA) has lately gained a notable momentum when tackling multiple optimization tasks. This work contributes to this trend by proposing the first adaptation of the recently introduced Multifactorial Evolutionary Algorithm II (MFEA-II) to permutation-based discrete optimization environments. For modeling this adaptation, some concepts cannot be directly applied to discrete search spaces, such as parent-centric interactions. In this paper we entirely reformulate such concepts, making them suited to deal with permutation-based search spaces without loosing the inherent benefits of MFEA-II. The performance of the proposed solver has been assessed over 5 different multitasking setups, composed by 8 datasets of the well-known Traveling Salesman (TSP) and Capacitated Vehicle Routing Problems (CVRP). The obtained results and their comparison to those by the discrete version of the MFEA confirm the good performance of the developed dMFEA-II, and concur with the insights drawn in previous studies for continuous optimization.