Krejca & Witt slash runtime bound for multi-valued cGA by factor of r²

In a new paper on arXiv, Martin Krejca (TU Berlin) and Carsten Witt (DTU Compute) present a refined runtime analysis of the compact genetic algorithm (cGA) on the truly multi-valued OneMax function G-OneMax. This function sums up to r-1 per dimension, unlike simpler variants that effectively collapse to two categories. The authors improve the previous best bound from O(n r³ log² n log r) — established by Adak and Witt at GECCO 2025 — down to O(n r log³ n log³ r). This removes a quadratic factor in the alphabet size r, matching (up to polylog factors) the known bound for the simpler r-valued setting that depends only on two value types.

The key technical innovations involve novel drift theorems tailored for processes with high self-loop probabilities, combined with carefully designed concentration inequalities. These tools allow the authors to analyze how probability mass in the cGA's frequency matrix migrates into successively narrower intervals over time. The result is significant because it demonstrates that multi-valued estimation-of-distribution algorithms can achieve essentially the same asymptotic runtime as their pseudo-Boolean counterparts, even when the objective function genuinely exploits all r categories. This work advances the theoretical foundations of evolutionary computation and provides a tighter understanding of how genetic algorithms scale with search space granularity.