TL;DR
This paper introduces dMFEA-II, the first adaptation of the adaptive Multifactorial Evolutionary Algorithm II (MFEA-II) for permutation-based discrete optimization problems. By reformulating MFEA-II's core concepts for discrete search spaces, dMFEA-II effectively tackles multiple related problems simultaneously, demonstrating improved performance over its predecessor.
What Problem Does This Paper Address?
The field of "multitasking optimization" aims to solve multiple optimization problems concurrently, leveraging potential synergies between them. This is achieved through "transfer optimization," where knowledge gained from one task can benefit others. Evolutionary Multitasking (EM) is a prominent approach within this paradigm, with the Multifactorial Evolutionary Algorithm (MFEA) being a leading algorithm. However, MFEA and its recent adaptive version, MFEA-II, were primarily designed for continuous optimization problems. Many real-world problems, such as routing and scheduling, are discrete and often represented by permutations. Directly applying MFEA-II's concepts, like parent-centric interactions and specific crossover/mutation operators, to these permutation-based search spaces is not straightforward. This paper addresses this gap by proposing a novel adaptation of MFEA-II specifically for permutation-based discrete optimization problems.
Methods
The core contribution is the adaptation of MFEA-II for discrete, permutation-based problems, resulting in dMFEA-II. Key modifications include:
- Permutation Encoding: A unified search space is established using permutation encoding, where solutions are represented as permutations of integers up to the maximum dimension of any task. For tasks with smaller dimensions, only the relevant subset of the permutation is considered.
- Dynamic Transfer Parameter Matrix (RMP): MFEA-II uses a transfer parameter matrix (RMP) to dynamically control the intensity and frequency of knowledge exchange between tasks.
dMFEA-IIimplements an adaptive strategy for this matrix, where entries are updated based on the performance of offspring relative to their parents. If a transfer leads to improvement, the RMP value increases; otherwise, it decreases, with defined bounds to maintain some level of interaction. - Dynamic Parent-Centric Crossover: MFEA-II's parent-centric crossover, designed for continuous spaces, is reformulated for permutations. This involves adapting operators like Order Crossover (OX) to ensure that offspring remain close to their parents in the discrete search space. The degree of genetic material transfer is controlled by the RMP values and a window size parameter.
- Mutation Control: A mutation parameter (
Pm) is introduced to control whether newly generated individuals undergo mutation, helping to balance exploration and exploitation. - Dynamic OX (dOX): A modified Order Crossover operator is proposed, where the cutting window size is dynamically adjusted based on the RMP values and a fraction of the permutation length. This ensures that the amount of genetic material transferred is proportional to the perceived synergy between tasks.
Datasets
The paper evaluates dMFEA-II using datasets from two well-known combinatorial optimization problems:
- Traveling Salesman Problem (TSP): Four instances from TSPLIB were used:
berlin52,eil51,st70, andeil76. - Capacitated Vehicle Routing Problem (CVRP): Four instances from the Augerat Benchmark were used:
P-n50-k7,P-n50-k8,P-n55-k7, andP-n55-k8.
These eight instances were combined to create five distinct multitasking environments, including scenarios with only TSP, only CVRP, and mixed TSP/CVRP tasks, to test dMFEA-II's ability to handle both related and unrelated problems.
Key Insights and Ideas
- Adaptivity is Key for Discrete Multitasking: The core insight is that the adaptive nature of MFEA-II, particularly its dynamic RMP matrix, is crucial for handling the complexities of discrete optimization problems. This adaptivity allows the algorithm to learn and adjust knowledge transfer strategies, mitigating negative transfer.
- Discrete Operators Need Careful Reformulation: Simply porting continuous optimization operators to discrete spaces is insufficient. The paper highlights the need for careful reformulation of concepts like parent-centric crossover and mutation to be meaningful and effective in permutation-based search.
- MFEA-II's Adaptability Translates to Discrete Domains: The success of MFEA-II in continuous domains is shown to extend to discrete problems. The algorithm's ability to dynamically manage inter-task interactions provides a significant advantage over static approaches like the original discrete MFEA.
- Negative Transfer is a Real Concern: The paper implicitly and explicitly addresses the challenge of negative transfer, where attempting to learn from unrelated tasks can degrade performance.
dMFEA-II's adaptive RMP mechanism is designed to minimize such detrimental interactions.
Key Results
The experimental results demonstrate that dMFEA-II significantly outperforms the discrete version of MFEA across various multitasking setups.
- Superior Performance:
dMFEA-IIachieved better average fitness values in 22 out of 24 comparisons against MFEA across the five test environments. - Statistical Significance: A Wilcoxon Rank-Sum test confirmed that
dMFEA-II's performance advantage is statistically significant, particularly in more complex environments with more tasks. For instance, in theTE_8environment (all 8 datasets),dMFEA-IIoutperformed MFEA with statistical significance in 6 out of 8 datasets. - Scalability:
dMFEA-IIshowed better scalability, maintaining its performance as the number of simultaneous tasks increased, whereas MFEA's performance degraded notably in larger multitasking setups.
Limitations and Future Work
- Limitations: The paper acknowledges that the proposed
dMFEA-IIis an initial adaptation. While successful, further analysis is needed. The specific parameter tuning process fordMFEA-IIand MFEA is not detailed, which could influence reproducibility. - Future Work: The authors propose several directions:
- Scalability Analysis: Further investigate the scalability of
dMFEA-IIwith a larger number of TSP and VRP instances. - RMP Dynamics Analysis: Conduct a deeper analysis of the RMP matrix update dynamics to better understand its behavior during the search.
- Generalization: Extend the developed method to other combinatorial optimization problems beyond TSP and CVRP, potentially from different domains.
Summary updated