Evolutionary Multitask Optimization

To facilitate the solving of complex problems, evolutionary multitask optimization is regarded as a promising technique due to its capacity for cross-task knowledge transfer. In contrast to empirical evidences, no mathematical runtime support exists for this technique within the domain of multi-objective optimization. In this work, we aim to fill this important gap. We analyze how the representative multiobjective multifactorial evolutionary algorithm (MO-MFEA) covers the Pareto fronts of two bi-objective problems simultaneously. For the two-task problem of maximizing the classic bi-objective OMM and the multimodal OJZJ benchmarks, the MO-MFEA requires only an expected runtime of $O(n^2 \log n)$---the same as optimizing the simple OMM alone---yet achieves a speedup by a factor of $Θ(n^{k-1}/\log n)$ compared to optimizing OJZJ alone (with gap size $k$). Similarly, for the task pair comprising the classic LOTZ and the multimodal DLTB benchmarks, a speedup of $Θ(n)$ is attained over optimizing DLTB alone, while the runtime matches that of optimizing LOTZ alone.

Multi-task optimization (MTO) addresses a set of optimization tasks simultaneously, often suffering from inaccurate inter-task relationship estimation under limited evaluation budgets, leading to negative transfer. This paper introduces In-Context Guidance Multitask Optimization (ICG-MTO), a novel framework that leverages numerical foundational models to improve inter-task coupling estimation in few-shot scenarios. Unlike conventional methods that rely solely on scarce observed data, ICG-MTO employs a frozen foundational model to infer auxiliary guidance through in-context learning. The framework operates through three stages: constructing an algorithm-specific in-context query from evaluated solutions, using the foundational model to infer a guidance signal characterizing predictive relationships among tasks, and translating this signal into algorithm-specific guidance for maximum-a-posteriori coupling estimation. This approach provides regularization during the early, data-scarce stages of optimization and gradually relinquishes control as task-specific observations accumulate. We instantiate the framework in multitask Bayesian optimization as ICG-MTBO, using directional fitness-class queries to guide inter-task coupling estimation, and further instantiate it in MFEA-II using decision-space-overlap queries to guide random mating probability estimation. Experiments across synthetic benchmarks and a real-world robot arm control problem, together with evaluations under different acquisition functions and evolutionary multitasking, demonstrate the effectiveness and generality of ICG-MTO for few-shot multitask optimization.

Evolutionary multitasking allows several related problems to be solved in a single run of an algorithm. In this paper, we investigate integrating evolutionary multitasking with Edge Assembly Crossover (MT-EAX) to solve the classical Travelling Salesperson Problem (TSP). To fairly compare MT-EAX against standard EAX under strict compute budgets, we evaluate three scaling methods: generation scaling, population scaling, and balanced scaling. Our results show that generationally scaled MT-EAX is highly effective compute-wise in the early stages of the search, saving $60\%$ to $90\%$ of compute for equal or better solution quality. We observe that instance geometry has a significant impact, with clustered, normally distributed instances securing larger improvements than uniformly distributed ones. However, when scaling by population or utilising explicit solution transfer, the results are negative due to population starvation and incompatible cross-instance parent selection. We demonstrate that the advantage of MT-EAX derives from increased diversity through parallel search in early generations, which can be successfully preserved using a decoupled configuration to often strictly outperform or match standard EAX performance at final convergence.

Evolutionary multitasking is a recent approach that solves multiple related optimization problems within a single evolutionary run, rather than addressing each problem separately. We consider monotone submodular optimization problems with dynamic knapsack constraints and study a multitasking formulation in which all tasks share a common monotone submodular function $f$, but differ in their constraints. We focus on the case where elements within each constraint have uniform cost and show that this structure leads to small Pareto fronts in the multitasking formulation. This enables solution sharing across tasks and can improve performance compared to running standard evolutionary approaches independently, depending on the constraint regime. Using rigorous runtime analysis, we analyze the expected time until the proposed multitasking algorithms obtain a $(1 - 1/e)$-approximation for each task. Experimental results for the Maximum Coverage problem complement the theoretical analysis and provide further insight into the practical behavior of the approach across different budget settings.

Novelty Search (NS) promotes exploration by rewarding behaviorally novel solutions rather than directly optimizing predefined objectives, making it particularly useful when objective guidance is sparse or deceptive. However, existing NS methods are typically designed for a single search task. When multiple related NS tasks are considered independently, their search processes may repeatedly explore similar regions or rediscover solutions that could be useful across tasks, leading to redundant use of the evaluation budget. To address this issue, we formulate a multitask novelty search setting and propose Multitask Novelty Search with Cross-Task Collaborative Discovery (MTNS-CoD). The central idea is to coordinate discovery across tasks so that different task-specific searches explore complementary regions while useful discoveries can still be reused across tasks. Specifically, MTNS-CoD introduces a multitask repulsion mechanism to discourage redundant exploration in similar genotype regions, together with an adaptive inter-task transfer mechanism that adjusts transfer probabilities according to the observed utility of cross-task exchanges during evolution. Their joint use promotes complementary exploration while selectively reusing beneficial discoveries. We further extend MTNS-CoD to novelty-augmented optimization, where behavioral novelty and objective information are jointly considered to support exploration under deceptive objective landscapes. Experiments on synthetic benchmarks, deceptive maze navigation, MuJoCo policy optimization, and generative novelty search show that MTNS-CoD can improve behavioral discovery and search coverage over the considered single-task and multitask baselines, with additional benefits observed on problems containing deceptive objectives.

Recent LLM-guided evolutionary search methods have shown that iterative program mutation can discover strong algorithms, but they typically optimize each task independently, even when related tasks share reusable structure. We study evolutionary multitask optimization (EMO) for LLM-guided program discovery and propose EMO-STA (Shared-Then-Adapt), a two-stage framework that first evolves a shared archive of executable programs across a task family and then adapts selected shared candidates to each target task. Within EMO-STA, we explore multiple adaptation strategies, including warm-starting from the shared archive, adapting the best average shared program, and adapting the shared program that performs best on each target task. Across eight task families spanning continuous optimization, geometric construction, modeling, and algorithmic optimization, EMO-STA improves over single-task evolution under matched evolutionary-iteration budgets in most settings, with STA Best-Local providing the strongest in-distribution adaptation and STA Best-Shared yielding robust transfer to unseen tasks. Iteration-allocation experiments show that devoting a substantial fraction of the family-level iteration budget to shared evolution is effective, with roughly balanced shared and aggregate adaptation budgets often yielding the best performance. ARC and time-series feature-engineering case studies further suggest that shared evolution can mitigate overfitting in low-evidence settings by favoring programs that perform well across related tasks rather than exploiting brittle task-specific artifacts.

Multi-task optimization is a powerful approach for solving a large number of tasks in parallel. However, existing algorithms face distinct limitations: Population-based methods scale poorly and remain underexplored for large task sets. Approaches that do scale beyond a thousand tasks are mostly MAP-Elites variants and rely on a fixed, discretized archive that disregards the topology of the task space. We introduce MONET (Multi-Task Optimization over Networks of Tasks), a multi-task optimization algorithm that models the task space as a graph: tasks are nodes, and edges connect tasks in the task parameter space. This representation enables knowledge transfer between tasks and remains tractable for high-dimensional problems while exploiting the topology of the task space. MONET combines social learning, which generates candidates from neighboring nodes via crossover, with individual learning, which refines a node's own solution independently via mutation. We evaluate MONET on four domains (archery, arm, and cartpole with 5,000 tasks each; hexapod with 2,000 tasks) and show that it matches or exceeds the performance of existing MAP-Elites-based baselines across all four domains.

Pareto optimization via evolutionary multi-objective algorithms has been shown to efficiently solve constrained monotone submodular functions. Traditionally when solving multiple problems, the algorithm is run for each problem separately. We introduce multitasking formulations of these problems that are an effective way to solve multiple related problems with a single run. In our setting the given problems share a monotone submodular function $f$ but have different knapsack constraints. We examine the case where elements within a constraint have the same cost and show that our multitasking formulations result in small Pareto fronts. This allows the population to share solutions between all problems leading to significant improvements compared to running several classical approaches independently. Using rigorous runtime analysis, we analyze the expected time until the introduced multitasking approaches obtain a $(1-1/e)$-approximation for each of the given problems. Our experimental investigations for the maximum coverage problem give further insight into the dynamics behind how the approach works and doesn't work in practice for problems where elements within a constraint also have varied costs.

Recently, evolutionary multitasking has been employed to generate a ``set of Pareto sets" (SOS) for machine learning models, addressing diverse task settings across heterogeneous environments. This involves creating a repository of compact, specialized solution models that are collectively tailored to each specific task setting and environment, enabling users to select the most suitable model based on particular specifications and preferences. In this paper, we further demonstrate the versatility and applicability of the SOS concept across diverse domains, focusing on three real-world problems: engineering design problems, inventory management problems, and hyperparameter optimization problems. Additionally, as evolutionary multitasking has proven effective in generating the SOS, we investigate the performance of current evolutionary multitasking methods on these real-world problems. Subsequently, we present visualizations of the generated SOS in both decision and objective spaces, complemented by the development of a measurement to gauge the similarity between different Pareto sets corresponding to diverse tasks. Finally, we show that by systematically examining the shifts in Pareto optimal designs across different task settings though the SOS solutions, users can gain deeper understandings on the dynamic interplay between design solutions and their performance in different settings or contexts.