Half a Dozen Real-World Applications of Evolutionary Multitasking and More

Abhishek Gupta, Lei Zhou, Yew-Soon Ong, Zefeng Chen, Yaqing Hou

TL;DR

This paper provides a comprehensive roadmap for Evolutionary Multitasking (EMT), a paradigm shift where evolutionary algorithms solve multiple optimization tasks simultaneously rather than in isolation. By reviewing six diverse real-world application domains—from robotics to logistics—and providing "recipes" for future problem formulations, the authors demonstrate how inter-task knowledge transfer can significantly accelerate convergence and improve solution quality.

What Problem Does This Paper Address?

Traditional Evolutionary Algorithms (EAs) are typically "single-minded": they evolve a population of solutions to solve one specific target task. However, in the real world, problems rarely exist in a vacuum. Whether designing a fleet of different vehicles or planning paths for multiple drones, these tasks often share underlying structural similarities.

Solving them independently is computationally wasteful because it ignores the "implicit parallelism" of evolution. The challenge addressed here is how to unlock this parallelism to allow tasks to share "evolved skills." The goal is to move away from tabula rasa (starting from scratch) optimization and toward a framework where solving an easy task can provide the building blocks needed to crack a much harder, related one.

Methods

The paper categorizes EMT methodologies into two primary schools of thought:

  1. EMT with Implicit Transfer: Solutions for different tasks are encoded into a unified search space. Knowledge is exchanged naturally through standard evolutionary crossover operators. A key advancement mentioned is the Multifactorial Evolutionary Algorithm (MFEA) and its successor, MFEA-II, which uses probabilistic mixture models to adaptively control how much information is shared between tasks to avoid "negative transfer" (where unrelated tasks hinder each other).
  2. EMT with Explicit Transfer: Tasks maintain separate populations in their original search spaces. Knowledge is exchanged at specific intervals via mapping functions that translate a solution from one task's "language" to another's.

The authors also highlight the use of Representation Learning (like autoencoders) to find common ground between heterogeneous tasks that might have different numbers of variables or different physical constraints.

Datasets

As a review and position paper, it references several benchmark and real-world datasets used across different studies:

  • Data Science: Atmospheric $CO_2$ concentrations (Alert, Canada) and U.S. Diesel Retail Prices (DRP) for symbolic regression.
  • Robotics: The Meta-World environment for robot arm manipulation and classical double-pole balancing benchmarks.
  • Logistics: Real-world Package Delivery Problem (PDP) requests from a courier company in Beijing, China.
  • Engineering Design: Structural simulation data for Mazda car models (SUV, large, and small vehicles) and liquid composite molding (LCM) process simulations.
  • Software Engineering: Numerical calculus functions in C from the Numerical Recipes library.

Key Insights and Ideas

  • The "Hard-to-Easy" Boost: Interestingly, transfer isn't just a one-way street from simple to complex tasks. The paper notes that information from challenging tasks can sometimes help refine solutions for simpler ones, leading to higher overall success rates.
  • Unified Latent Spaces: One of the most elegant ideas is using 3D point cloud autoencoders to unify diverse geometries (like different car shapes). This allows the algorithm to transfer "aerodynamic features" across different vehicle types even if their raw design parameters don't match.
  • Multitasking as a Catalyst: In multi-fidelity optimization, low-fidelity tasks (cheap but inaccurate simulations) act as catalysts. They explore the search space quickly and "seed" the high-fidelity task with promising regions, drastically reducing the need for expensive, high-accuracy evaluations.
  • Heuristic Transfer: In combinatorial problems like vehicle routing, the authors suggest transferring higher-order heuristics (rules for building a route) rather than the routes themselves, which helps overcome representational mismatches between different cities or customer distributions.

Key Results

  • Efficiency Gains: In simulation-based process design (LCM), EMT achieved the same results as single-task algorithms in 50% fewer evaluations, representing a massive saving in time and computational resources.
  • Improved Success Rates: For the double-pole balancing problem, the MFEA-II algorithm achieved a 47% success rate on a difficult task where a standard single-task EA achieved only 27%.
  • Data Science Speedups: In feature selection for machine learning, using auxiliary small-data tasks to assist a large-data main task resulted in speedups of over 40%.
  • Software Testing: The MTEC (Multitask Evolutionary Coverage) approach achieved superior branch coverage in software testing compared to independent searches across the majority of programs tested.

Limitations and Future Work

The authors acknowledge several hurdles for the widespread deployment of EMT:

  • Negative Transfer: If two tasks are completely unrelated, forcing them to share information can degrade performance. Developing more robust "online" methods to detect task relationships is a priority.
  • Scalability: While EMT works well for a "half-dozen" tasks, scaling to hundreds or thousands of tasks ($K$) remains a challenge for both memory and computational complexity.
  • The "Multi-X" Frontier: The paper concludes by providing "recipes" for applying EMT to Multi-Objective, Multi-Fidelity, Multi-Level (Bilevel), and Multi-Scenario problems. The authors argue that these complex structures are naturally suited for multitasking, but require more rigorous theoretical research to ensure they can consistently outperform specialized single-task solvers.

Summary updated

Abstract

Until recently, the potential to transfer evolved skills across distinct optimization problem instances (or tasks) was seldom explored in evolutionary computation. The concept of evolutionary multitasking (EMT) fills this gap. It unlocks a population's implicit parallelism to jointly solve a set of tasks, hence creating avenues for skills transfer between them. Despite it being early days, the idea of EMT has begun to show promise in a range of real-world applications. In the backdrop of recent advances, the contribution of this paper is twofold. First, a review of several application-oriented explorations of EMT in the literature is presented; the works are assimilated into half a dozen broad categories according to their respective application domains. Each of these six categories elaborates fundamental motivations to multitask, and contains a representative experimental study (referred from the literature). Second, a set of recipes is provided showing how problem formulations of general interest, those that cut across different disciplines, could be transformed in the new light of EMT. Our discussions emphasize the many practical use-cases of EMT, and is intended to spark future research towards crafting novel algorithms for real-world deployment.
BibTeX
@misc{gupta2021half,
  author = {Abhishek Gupta and Lei Zhou and Yew-Soon Ong and Zefeng Chen and Yaqing Hou},
  title = {{Half a Dozen Real-World Applications of Evolutionary Multitasking and More}},
  year = {2021},
  eprint = {2109.13101},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.13101},
}
Figure