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

Source: arXiv - 2605.29477v1

Overview

This paper tightens the theoretical understanding of a compact Genetic Algorithm (cGA) when it is applied to a genuinely multi‑valued version of the classic OneMax benchmark. By improving the runtime bound from (O(n r^{3}\log^{2}n\log r)) to (O(n r\log^{3}n\log^{3}r)), the authors show that the algorithm scales almost as well on a full‑(r)‑ary search space as it does on the simpler binary‑like variants. The result bridges a gap between theory and practice for estimation‑of‑distribution algorithms (EDAs) that operate on non‑binary chromosomes.

Key Contributions

• Improved Asymptotic Runtime: Proven bound of (O(n r\log^{3}n\log^{3}r)) for the multi‑valued cGA on the truly multi‑valued OneMax function, a near‑optimal polylogarithmic improvement over the previous best.
• Generalized Drift Analysis: Development of refined drift theorems that handle processes with high self‑loop probabilities, a common situation in EDAs where many updates leave the probability vector unchanged.
• New Concentration Tools: Introduction of tailored concentration inequalities to track how probability mass concentrates into progressively smaller intervals of the frequency matrix.
• Matching Simpler Cases: Demonstrated that, up to polylogarithmic factors, the runtime matches the best known bounds for the easier (r)-valued OneMax that only distinguishes two categories per dimension.
• Guidance on Update Strength (K): Identified the optimal scaling of the cGA’s update strength parameter, offering practical advice for algorithm configuration.

Methodology

1. Problem Setting:

   • Search Space: ({0,\dots,r-1}^{n}) (each of the (n) positions can take any of (r) values).
   • Objective: (G\text{-OneMax}(x)=\sum_{i=1}^{n} x_i), i.e., the sum of all gene values – a direct extension of the classic OneMax to multi‑valued alphabets.

2. Algorithm Under Study:

   • The compact Genetic Algorithm maintains a frequency matrix (p_{i,j}) that encodes the probability of sampling value (j) at position (i).
   • In each iteration two offspring are sampled, the better one wins, and the matrix is updated by moving a small amount (1/K) toward the winner’s allele.

3. Analytical Tools:

   • Drift Analysis: The authors prove a high‑self‑loop drift theorem that quantifies expected progress even when most updates leave the state unchanged.
   • Concentration Inequalities: Custom bounds are derived to show that the probability mass quickly collapses into narrow intervals around the optimum, despite the large alphabet size.
   • Layered Interval Argument: The analysis proceeds by defining a hierarchy of intervals (large → small) and showing that the algorithm moves from one layer to the next in logarithmic time.

4. Parameter Choice:

   • The update strength (K) is set to balance exploration (large (K) slows changes) and exploitation (small (K) risks premature convergence). The optimal choice emerges from the drift calculations.

Results & Findings

The analysis shows that, after a polylogarithmic number of generations, the frequency matrix concentrates most of its mass on the optimal value for each dimension, and the algorithm then proceeds to fine‑tune the remaining bits efficiently.

Practical Implications

• Scalable EDAs for Categorical Data: Developers building optimization pipelines for problems with many discrete options (e.g., hyper‑parameter tuning with multi‑valued choices, scheduling with multiple resource levels) can now rely on cGA with confidence that runtime will not explode with the number of categories.
• Parameter‑Free Guidance: The derived optimal (K) offers a “plug‑and‑play” setting, reducing the need for costly empirical tuning.
• Algorithmic Simplicity: cGA remains lightweight (no explicit population) while achieving near‑optimal theoretical performance, making it attractive for embedded or low‑memory environments.
• Benchmark Design: The paper’s methodology can be reused to analyze other multi‑valued benchmark functions, helping the community develop a richer suite of realistic test problems beyond binary pseudo‑Boolean ones.
• Hybrid Approaches: Knowing the exact scaling behavior encourages hybrid designs where cGA handles the categorical part of a mixed‑type problem, while other components (e.g., CMA‑ES) manage continuous variables.

Limitations & Future Work

• Polylogarithmic Gaps: The bound still contains (\log^{3}n\log^{3}r) factors; tightening these to constant or lower‑order logs remains open.
• Assumption of Ideal Sampling: The analysis presumes exact sampling from the frequency matrix; in practice, finite‑precision or hardware RNG quirks could affect convergence.
• Single‑Objective Focus: Extending the results to multi‑objective or constrained multi‑valued problems is non‑trivial and was not addressed.
• Empirical Validation: While the theoretical improvement is clear, large‑scale experiments on real‑world categorical optimization tasks would solidify the practical impact.
• Alternative EDAs: Investigating whether other estimation‑of‑distribution frameworks (e.g., Bayesian networks, tree‑based models) can achieve similar or better scaling on truly multi‑valued functions is a promising direction.

Bottom line: This work shows that a simple, memory‑efficient cGA can solve genuinely multi‑valued optimization problems almost as fast as it solves binary ones, provided the update strength is chosen wisely. For developers dealing with high‑cardinality discrete decisions, the paper offers both theoretical reassurance and concrete guidance for deploying compact EDAs in production settings.

Authors

• Martin S. Krejca
• Carsten Witt

Paper Information

• arXiv ID: 2605.29477v1
• Categories: cs.NE
• Published: May 28, 2026
• PDF: Download PDF