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

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,\dots ,r-1{\}}^n\to \mathbf{N}$ defined by G-OneMax$(x_1,\dots ,x_n)={\sum }_{i=1}^n{x}_i$ and truly depending on all $r$ categories. We improve their runtime result from $\text{O}(n{r}^3{\log }^2(n)\log (r))$ to $\text{O}(nr{\log }^3(n){\log }^3(r))$, both for an optimal choice of the update strength $K$. Our result matches, up to polylogarithmic factors, the existing bound for the simpler $r$-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 $r$-valued frequency matrix.