Can Remembering Past Samples Carry the Compact Genetic Algorithm Over a Fitness Cliff?

A model-based search algorithm keeps a probability distribution over candidate solutions instead of a population. It samples from that distribution, compares the samples, and nudges the distribution toward the winners. The compact genetic algorithm (cGA) is the simplest such algorithm: it keeps one probability per bit and moves it by a small step after each pairwise comparison. The approach has a known catastrophic failure. On a "cliff" function, where fitness rises with the number of ones until about $2n/3$, drops sharply, and then rises again toward the optimum, the cGA's small reinforcing steps pin it at the cliff edge. The Compact Genetic Algorithm Struggles on Cliff Functions proves runtimes of $n^{\Theta(n)}$ or $2^{\Theta(n)}$. It also reports median runtimes above $10^8$ evaluations at $n=18$, which is worse than the roughly $2.6\times10^5$ evaluations pure random search needs. Smart restarts do not rescue it.

This note asks whether giving the algorithm a memory fixes the problem. Instead of reacting to every comparison, the algorithm keeps an archive of past winning samples and updates its model only when that archive supports a change. The central claim is that archives help on cliffs for a specific structural reason, and noise-filtering is not that reason. The cliff is systematic deception, so a significance test will not ignore it. The help comes from the way significance-gated archives change the model: rarely, and in large jumps rather than small drifts. A large jump can move the sampling distribution past the cliff in one step, whereas small drifts are exactly what the negative-drift trap feeds on. We propose to test this with non-asymptotic runtime bounds that state their constants explicitly and a matched simulation study that checks the bounds against measured runtimes and wall-clock cost.

Core Claim

The significance-based compact genetic algorithm (sig-cGA) comes from Significance-based estimation-of-distribution algorithms, with a journal version in Significance-Based Estimation-of-Distribution Algorithms. It records the history of each bit's value in winning samples. It changes that bit's probability only when the history deviates significantly from a fair binomial, and then clears the history. As we read that work, the probability moves to a near-extreme value when it changes, not by a small increment. Our hypothesis is that this coarse, gated update means the algorithm never spends long with its sampling distribution centered on the cliff edge.

Here is the mechanism. Suppose that, by the time the cliff is reached, roughly two-thirds of the bits have been fixed near one and the rest are still at one-half. Samples then carry about $2n/3 + n/6 = 5n/6$ ones, which lands them on the far, rising side of the cliff. The deceptive comparisons that trap the cGA mostly never occur.

A useful way to state this treats the model as a fitness predictor. For a probability vector $p$, let $F(p)=\mathbb{E}_{x\sim p}[f(x)]$ be the expected fitness of the model's samples. This is the quantity that Unbiased black-box complexities of jump functions: how to cross large plateaus shows can reveal a hidden gradient on flat regions. The cGA's trap corresponds to a local maximum of $F$ reached by small moves of $p$. The sig-cGA moves $p$ between a few coarse levels, and we conjecture that in this restricted space the trap does not exist.

The claim can fail in two ways, and both would be informative. First, the significance test might fire in the wrong direction near the edge, fixing bits at zero. Second, the archive might need enough samples that the effective runtime blows up anyway.

Relation to Prior Work

Three lines of work motivate the question. The cliff analysis above supplies the failure and the target numbers. The sig-cGA papers supply the method but evaluate it only on unimodal functions (OneMax, LeadingOnes, BinaryValue), where it runs in $O(n\log n)$; they leave multimodal landscapes and leading constants open. Efficient Noisy Optimisation with the Sliding Window Compact Genetic Algorithm shows that a first-in-first-out window of recent samples (SWcGA) lets each sample take part in several comparisons. On noisy 100-bit OneMax it reaches the full noise-free fitness of 100.00 where the cGA stalls. That window is a second archive design, but it still makes small incremental updates. The contrast between these two archive designs, one gated with coarse jumps and one windowed with small steps, is what isolates our hypothesized mechanism.

On the analysis side, two papers supply tools and constraints. Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms gives a variance-based drift theorem that keeps exponential tail bounds with sharp constants even under zero or negative drift. The cliff edge is exactly a negative-drift regime, which is why we reuse this tool. The same paper warns that expectation-only analysis hides failure modes. The Runtime of the Compact Genetic Algorithm on Jump Functions and A tight runtime analysis for the cGA on jump functions give the cGA's $O(n\log n)$ behavior on short jumps and $\exp(\Omega(k))$ on long ones. They also note that optimizing the implicit constants is still open. Our constants question stays grounded in this family of results.

Research Program

The theoretical part has three pieces. First, a cliff-crossing analysis of sig-cGA that states its constants explicitly, as a function of $n$ and the significance parameter. It will use the variance-based drift theorem to bound both the expected time and the upper tail of the time to reach the far side of the cliff. Second, a companion lower-bound argument for the case where the gating fails, meaning bits are wrongly fixed to zero near the edge. This tells us which parameter regimes are provably unsafe. Third, a structural lemma about the expected-fitness surface $F$ restricted to the coarse probability levels sig-cGA can reach. The lemma should state when that restricted surface has no trap at the cliff. We will not claim a matching analysis for SWcGA; it enters empirically as the small-step contrast.

The empirical part checks these bounds directly rather than just reporting best-case runs. For every bound we will plot the ratio of the bound to the measured median and to the measured 95th percentile, across $n$. A bound whose ratio stays within a small constant factor is useful for choosing parameters. A bound off by orders of magnitude is not, and we will report which we obtain. We will also report memory for the archives and wall-clock time per evaluation. The known cost of model-based guidance, such as the self-guided GA being "slightly slower" than simpler GAs in A Self-guided Genetic Algorithm for permutation flowshop scheduling problems, means evaluation counts alone could mislead.

Baselines

The naive reference point is pure random search, which needs about $2^n$ evaluations. For $n=18$ that is about $2.6\times10^5$, as reported in the cliff paper. Any archive method that cannot beat random search at $n=18$, measured in median evaluations over at least 100 independent runs, has failed on this question regardless of its asymptotics.

The strongest existing method is the standard cGA with its step-size parameter $K$ tuned per $n$. The cliff paper reports medians above $10^8$ evaluations for moderate $K$ at $n=18$, and $2^{\Theta(n)}$ for very large $K$. We will rerun it ourselves at $n=15$ and $n=18$ over the same $K=2^1,\dots,2^{19}$ grid as that paper and then extend to larger $n$. We will give every other method the same number of tuning configurations, the same random seeds, and the same evaluation cap, so that tuning effort is equal across methods. We also include the smart-restart cGA, since it is the published attempt to repair the trap.

The archive competitors are SWcGA with its window size tuned on the same grid budget, and sig-cGA with its significance parameter tuned the same way. Beating the tuned cGA means a lower median and a lower 95th-percentile evaluation count at every $n\ge15$, with the gap growing in $n$.

The ablation that isolates the key ingredient is sig-cGA with the significance-gated archive kept but the coarse jump replaced by the cGA's small increment. If this variant falls back into the trap while full sig-cGA does not, the mechanism is the coarse update. If both escape, the archive gating itself is doing the work. A second ablation keeps the coarse jump but triggers it after a fixed number of winning samples without any significance test. This tells us whether the statistical test matters at all.

Why not just…?

Why not just tune the cGA's step size, or add restarts? The cliff paper already answers this negatively. Moderate $K$ gives $n^{\Theta(n)}$, very large $K$ gives $2^{\Theta(n)}$, and smart restarts do not reach polynomial time. We still rerun the full $K$ grid, because reproducing those numbers is our calibration check.

Why not just use the sliding-window archive, which is simpler? This is a real threat. If SWcGA crosses the cliff as reliably as sig-cGA, our mechanism story is wrong: memory alone, not coarse jumps, would be the cure. The SWcGA baseline and the small-step ablation of sig-cGA are designed to settle this. Our prediction is that both small-step variants stay trapped, because systematic deception survives averaging.

Why not just use a mutation-based evolutionary algorithm or random search, and drop the model entirely? Random search is included and sets the bar. For mutation-based algorithms on this cliff we found no reported result on Lacuna, so we will run a standard one under the same budget as a sanity reference. If it dominates everything, the right conclusion is that frequency models are the wrong tool on cliffs, and we will say so.

Why not just prove $O(\cdot)$ bounds and skip the constants? Asymptotics can say that sig-cGA is polynomial on the cliff, but that is compatible with it losing to $2^{18}$ random-search evaluations at the sizes anyone actually runs. Only explicit constants, checked against simulation, can tell a practitioner which method to use at a given $n$.

Decisive Checks

The first decisive result is whether full sig-cGA beats random search and the tuned cGA at $n=18$, with medians and 95th percentiles reported over at least 100 runs. The second is whether the coarse-to-fine ablation reproduces the trap. That outcome separates "memory helps" from "coarse jumps help." The third is whether our explicit-constant bound predicts measured medians within a small factor across $n=15$ to the largest $n$ we can run.

As a control, we will run the same methods on short jump functions and on noisy OneMax. The first checks that any cliff advantage does not come with a regression where the cGA is already known to be $O(n\log n)$. The second checks that we reproduce the reported 100.00 noise-free fitness for SWcGA. If the coarse-jump hypothesis holds, the result is a mechanistic account of when archives rescue model-based search, together with bounds a practitioner can actually use. If it fails, the lower-bound analysis and ablations will show which part of the archive idea breaks, and that is equally worth publishing.