First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables

• URL: http://arxiv.org/abs/2605.14836v1
• Date: Thu, 14 May 2026 13:42:52 GMT
• Title: First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables
• Abstract summary: Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms.<n>No mathematical runtime analyses exist so far for MOEAs dealing with decision variables that take a finite number $r > 2$ of values.<n>We show that classic MOEAs encounter no significant additional difficulties when dealing with multi-valued decision variables.
• Score: 23.47753638129204
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms (MOEAs). In contrast, no mathematical runtime analyses exist so far for MOEAs dealing with decision variables that take a finite number $r > 2$ of values, despite the prevalence of such problems in practice. In this work, we begin to fill this research gap. We analyze how the classic SEMO algorithm with unit-strength local mutation computes the Pareto front of an $r$-valued counterpart of the classic \oneminmax benchmark. For the expected number of function evaluations until the Pareto front is covered by the population of this MOEA, we prove an upper bound of $O(n^2 r^2 \log n)$ and a near-tight lower bound of $Ω(n^2 r (r + \log n))$. We can close the small remaining gap between these two bounds by considering a variant of the algorithm that accepts only strictly better solutions; for this variant, we show an upper bound of $O(n^2 r (r + \log n))$, matching our lower bound (which also holds for this variant). Our results suggest that classic MOEAs encounter no significant additional difficulties when dealing with multi-valued decision variables. However, significantly more advanced tools may be required to obtain tight bounds for algorithms with more complex population dynamics.

Related papers

• Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function [5.478764356647438]
  Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function.<n>We improve their runtime result from $textrmObigl(n r3 log2, n)log (r)bigr)$ to $textrmObigl(n rlog3(n)log3(r)bigr)$ for an optimal choice of the update strength $K$.
  arXiv  Detail & Related papers  (2026-05-28T07:06:59Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm [9.966672345291707]
  We study the dynamics of the global simple evolutionary multi-objective (GSEMO) algorithm.<n>We prove a lower bound of order $Omega(n2 log n)$ for the classic CountingOnesCountingZeros (COCZ) benchmark.<n>Our methods extend to other classic benchmarks and yield, e.g., the first $Omega(nk+1)$ lower bound for the OJZJ benchmark.
  arXiv  Detail & Related papers  (2025-05-02T13:40:25Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
  Solving variational inequalities (SVIs) is a foundational problem at the heart of optimization.<n>Most research has focused on carving out specific subclasses that elude those intractability barriers.
  arXiv  Detail & Related papers  (2025-04-04T13:24:41Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Theoretical Advantage of Multiobjective Evolutionary Algorithms for Problems with Different Degrees of Conflict [4.8951183832371]
  OneMaxMin$_k$ benchmark class is a generalized variant of COCZ and OneMinMax. Two typical non-MOEA approaches, scalarization (weighted-sum approach) and $epsilon$-constraint approach, are considered. We prove that (G)SEMO, MOEA/D, NSGA-II, and SMS-EMOA can cover the full Pareto front in $O(maxk,1nln n)$ expected number of function evaluations.
  arXiv  Detail & Related papers  (2024-08-08T04:09:52Z)
• Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables [10.165640083594573]
  We extend the known quantitative analysis of genetic drift to estimation-of-distribution algorithms for multi-valued variables. Our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting.
  arXiv  Detail & Related papers  (2023-02-28T08:52:40Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [14.309243378538014]
  OJZJ problem is a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark.<n>We prove that SEMO with probability one does not compute the full Pareto front, regardless of the runtime.<n>We also show the tighter bound $frac 32 e nk+1 pm o(nk+1)$, which might be the first runtime bound for an MOEA that is tight apart from lower-order terms.
  arXiv  Detail & Related papers  (2020-12-14T03:07:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.