cs.NEMay 28, 2026

Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function

Authors: Martin S. Krejca, Carsten Witt

Organizations: Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, IP Paris, France · DTU Compute, Technical University of Denmark, Denmark

Abstract

Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, 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 G-OneMax ⁣:{0,…,r−1}n→N\colon \{0,\dots,r-1\}^n \to \mathbf{N} defined by G-OneMax(x1,…,xn)=∑i=1nxi(x_1,\dots,x_n)=\sum_{i=1}^n {x}_i and truly depending on all rr categories. We improve their runtime result from O(nr3log⁡2(n)log⁡(r))\textrm{O}\bigl(n r^3 \log^2( n)\log (r)\bigr) to O(nrlog⁡3(n)log⁡3(r))\textrm{O}\bigl(n r \log^3(n)\log^3(r)\bigr), both for an optimal choice of the update strength KK. Our result matches, up to polylogarithmic factors, the existing bound for the simpler rr-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the rr-valued frequency matrix.

Explore similar work

CardsList
May 14, 2026cs.NE

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

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>2r > 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 rr-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(n2r2log⁡n)O(n^2 r^2 \log n) and a near-tight lower bound of Ω(n2r(r+log⁡n))Ω(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(n2r(r+log⁡n))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.
Mingfeng Li, Zheng Cheng, Weijie Zheng +1
Multi-Objective OptimizationEvolutionary SearchPareto Frontier
AskPDF
Jun 11, 2026cs.NE

Improved Runtime Bound for the (μ+ 1) EA on BinVal

We study the (μ+1)(μ+1) EA on the Binary Value function BinVal. We show that it needs at most O(μlog⁡μ⋅nlog⁡n)O(μ\log μ\cdot n \log n) function evaluations to find the optimum when μ=o(n/log⁡n)μ= o(n/\log n). This substantially improves upon the recent upper bound of O(μ5nlog⁡(n/μ4))O(μ^5 n \log(n/μ^4)) by Krejca, Neumann and Witt. Our results hold for several mutation operators including standard bit mutation. In particular, our bound implies that the (μ+1)(μ+1) EA is at most a factor O(log⁡μ⋅log⁡n)O(\log μ\cdot \log n) slower on BinVal than on OneMax.
Joris Belder, Johannes Lengler, Raghu Raman Ravi
BinaryUpper BoundsCryptographically Authorized MutationMaximization
AskPDF
Jun 14, 2026cs.NE

Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound O(nD5)O(n D^5) for the expected number of fitness evaluations of CGP to construct a conjunction of nn inputs using at most D≥n−1D \geq n-1 binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to O(nD4)O(n D^4). Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.
Duc-Cuong Dang, Roman Kalkreuth, Andre Opris
Genetic AlgorithmsProgram Analysis
AskPDF