CS Paper Radar

Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up

Benjamin Doerr, Moaad Elmoutassim, Martin S. Krejca, Guy Mushiata Kibulu

cs.NE ·submitted 2026-10-26 12:56 UTC · v1
benchmarktheory

Abstract

Besides domination-based algorithms such as the NSGA-II, the decomposition-based MOEA/D is one of the most popular and successful optimization heuristic for multi-objective problems. It decomposes the problem into several, single-objective subproblems. By solving these in a co-evolutionary manner and archiving non-dominated solutions, it approximates or computes the Pareto front. Interestingly, so far no advantages from the co-evolutionary communication of subproblem solutions were proven. In this first mathematical runtime analysis addressing this research question, we investigate how the mutation-based MOEA/D solves the classic OneMinMax benchmark when solutions are exchanged among subproblems in different distances $r$. We show, for the first time, that the MOEA/D profits from an exchange of solutions, and that already very small communication radii $r$ are sufficient to maximally profit from this feature of the algorithm. More precisely, for all values $r \ge 1$ we prove a tight runtime guarantee of $Θ(n^2)$, where $n$ is the problem size. This is asymptotically faster than the known bound of $O(n^2 \log n)$ guarantee for $r=0$, which we complement with a matching bound of $Ω(n^2 \log n)$.

Closest papers

Nearest neighbours by meaning across the whole index.

A Dynamic Decomposition Strategy for the MOEA/D With Proven Performance Guarantees

cs.NE ·2026-10-26 ·Benjamin Doerr, Martin S. Krejca, Noé Weeks
benchmarktheory similarity 0.73
Abstract

The MOEA/D is one of the most successful multi-objective evolutionary algorithms. It operates by decomposing the optimization problem into single-objective subproblems, which are then solved in a co-evolutionary manner. The performance of the MOEA/D depends critically on this decomposition. In this work, we propose a novel way to adjust this decomposition on the fly, for the case of discrete bi-objective optimization. Different from all previous works in this direction, we support our new algorithm with a proven performance guarantee. This is the first work that rigorously proves the runtime of a dynamic multi-objective evolutionary algorithm. For monotonic distortions of the simple LOTZ benchmark, it is known that classic decompositions leave large holes in the Pareto front, making it very hard for the MOEA/D to cover the entire Pareto front. In contrast, we prove that our self-adjusting MOEA/D solves all these LOTZ problems in an expected number of $O(n^4)$ function evaluations. This relatively low runtime as well as the details of our mathematical proof show that the dynamic decomposition strategy indeed evolves a decomposition adjusted to each of these problem instances.

0.47

First Mathematical Runtime Analyses of Evolutionary Multitask Multi-Objective Optimization

cs.NE ·2026-10-15 ·Danyang Zhang, Weijie Zheng
similarity 0.62
Abstract

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.

0.17

Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints

cs.NE ·2026-08-11 ·Liam Wigney, Frank Neumann
top venue similarity 0.57
Abstract

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.

0.29

Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup

cs.LG cs.AIcs.NE ·2026-11-11 ·Duc-Cuong Dang, Roman Kalkreuth, Andre Opris
publishedbenchmarktheory similarity 0.57
Abstract · Accepted as a poster at NeurIPS 2026. To appear in the conference proceedings

Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavor of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees. This paper analyzes CGP for the Max problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length $n$. We prove that the expected time for the ($1$+$1$) CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in $n$, specifically at most $O(\log^9{n})$. This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.

0.35

Converge Then Diversify: Decoupling Convergence and Diversity in Multi-Objective Bayesian Optimisation

cs.AI stat.ML ·2026-09-11 ·Chao Jiang, Yueling Huang, Miqing Li
similarity 0.55
Abstract · 26 pages,4 figures

Multi-objective Bayesian optimisation (MOBO) is a sample-efficient approach for optimising expensive black-box functions with multiple objectives. In MOBO, the goal is to adequately approximate the Pareto front; that is, to obtain a high-quality solution set with 1) good convergence (closeness to the Pareto front) and 2) good diversity (spread across the Pareto front). Existing MOBO methods typically aim to accomplish these two tasks simultaneously, i.e., driving the search towards the Pareto front while maintaining a diverse set of nondominated solutions, such that the solutions, ideally, can gradually approach the entire front. When sufficient search budgets are available, this approach is effective. However, considering both convergence and diversity throughout the search is not easy and requires careful design. Under very tight budgets, there may not be enough solutions generated to be able to simultaneously approach the entire Pareto front. To address this issue, this paper proposes a \textit{converge-then-diversify} (CTD) approach that decouples convergence and diversity into two stages. In the first stage, CTD focuses on convergence, aiming to quickly drive the search toward a single point on the Pareto front. In the second stage, CTD focuses on diversity, aiming to spread solutions across the front. We present two simple instantiations of CTD by using widely adopted acquisition functions in the area. Experimental results show that, across all 446 pairwise comparisons, CTD statistically outperforms state-of-the-art methods in 72.9\% of the cases, performs equivalently in 21.1\%, and is statistically worse in only 6.1\%, with the advantage being particularly evident in settings with very tight evaluation budgets or in high-dimensional problems.

0.33

Insights from Multi-tasking the EAX Algorithm for the Travelling Salesperson Problem

cs.NE ·2026-08-13 ·Liam Wigney, Aneta Neumann, Yew-Soon Ong, Frank Neumann
top venue similarity 0.55
Abstract

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.

0.29

Evolving Neural Solvers for Multi-objective Combinatorial Optimization

cs.NE ·2026-11-17 ·Ya-Hui Jia, Le-Xin Wen, Yang Wang, Wei-Neng Chen, Yi Mei
similarity 0.54
Abstract · 17 pages, 3 figures, including appendices

Multi-objective combinatorial optimization (MOCO) seeks high-quality solutions that represent different trade-offs among conflicting objectives. Existing neural methods typically train a dedicated model for each preference or condition a single model on different preferences. Training dedicated models becomes more costly as the number of preferences increases, while a shared model can produce duplicate solutions for different preferences, limiting the benefit of denser preference queries. We propose the Evolving Neural Solver (ENS), which trains only a small set of preference-specific models and takes advantage of evolutionary computation to evolve them into a diverse collection of solvers for better solution quality and Pareto front coverage. ENS first trains a model at an estimated knee-point preference to target a balanced compromise, then obtains the remaining initial models through parameter transfer toward the extremes, so as to preliminarily approximate the Pareto front. It then evolves these models to find more candidates that can generate non-dominated solutions through evolution strategies. Experimental results on classic MOCO problems show that ENS outperforms state-of-the-art neural MOCO methods in terms of hypervolume in most evaluated settings.

0.17

Evaluation of portability and performance of an OpenMP5 offloaded Quantum-Inspired Evolutionary Optimization Across the GPU Ecosystem

cs.PF math.OC ·2026-09-25 ·Kasturi Venkata Srikanth, Ashish Singh, Ferdin Sagai Don Bosco, Aman Mittal, Abhishek Singh +2 more
similarity 0.53
Abstract

Quantum-inspired evolutionary optimization (QIEO) is a new class of population-based metaheuristic optimization algorithms which represents design variables as a set of qubits and searches a continuous, multi-dimensional landscape through rotation of the qubit's amplitude pair. Every generation rotates those amplitudes toward a single elite, which corresponds to that generation's best. The per-generation cost scales as $O(N_p N_g)$ for $N_p$ chromosomes and $N_g$ genes (decision variables). Production use of such solvers is rarely confined to a single machine class. Prototypes are run on laboratory servers- before moving to rented cloud workstations for more involved campaigns. The largest problems are reserved for leadership-class accelerators. This paper asks whether a \emph{single} OpenMP~5 source of QIEO, offloaded with \texttt{\#pragma omp target}, is a viable production path in each of those settings. We report three independent, campaigns of the 0/1 knapsack problem against a same-source multi-core Intel CPU baseline. The study comprises approximately 3,000 runs spanning varying chromosome and gene counts, evaluated using both chromosome-level and gene-level offload strategies on the NVIDIA Tesla V100 SXM2, NVIDIA A100 80GB, and AMD Instinct MI300X GPUs. Deployment-specific nuances such as Volta's constant-memory cliffs, Ampere's L2 persistence and \texttt{cp.async}, CDNA~3's Infinity Cache and XCD occupancy are addressed to ensure high performance of these platforms. Results reveal gene-parallel offload achieved geometric-mean speedups of 90$\times$, 136$\times$, and 155$\times$ over a single CPU core on the V100, A100, and MI300X, respectively, and 12$\times$, 17$\times$, and 16.6$\times$ over 72 host threads. Furthermore DetermineElite, the $O(N_p)$ selection of the generation-best chromosome, is found to be better suited to the host than to the device.

0.33