Reproduce “Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Martin S. Krejca, Carsten Witt

The authors analyze the r-cGA on G-OneMax, an objective where each of n positions takes one of r ordered values. They track probability across the full value range, rather than only the optimal value, and prove an upper bound of O(nr log³ n log³ r) iterations and function evaluations. This improves cubic to linear dependence on r, for r=O(n^{1/6−ε}) under parameter conditions.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.