Population Scalability: Why a Larger Population Isn't Always Faster

TL;DR

In the world of Evolutionary Algorithms (EAs), "more is better" is a common mantra for population size. However, Jun He and Xin Yao's research provides a rigorous mathematical reality check. Using Average Drift Analysis, they demonstrate that while populations can rescue an algorithm from deceptive traps, they often slow down the search on "simple" (unimodal) landscapes. The paper introduces Population Scalability— a ratio to measure exactly how much speedup we get by going from one individual to many.

Background: The Limits of Intuition

Why do we use populations? Intuition says they provide diversity and parallel search. But from a computational complexity standpoint, every individual in a population requires a fitness evaluation. If you use 10 individuals but only find the solution 2 times faster, your expected running time actually increases.

The authors move beyond the "cut-off point" (which only looks at asymptotic orders) to the Scalability Threshold: the precise point where increasing population size starts becoming a liability rather than an asset.

Methodology: The Time-Fitness Landscape

A key contribution of this work is the Time-Fitness Landscape. Unlike traditional Hamming distance landscapes, this version maps points based on the Expected Hitting Time of a (1+1) EA.

• Unimodal Landscapes: Every step closer in hitting time corresponds to a better fitness value.
• Deceptive Landscapes: Better fitness values actually lead the algorithm away from the optimum in terms of hitting time.

By using Average Drift Analysis, the authors can compare the "drift" (progress per generation) of a (μ+λ) EA against a (1+1) benchmark. If the drift doesn't scale linearly with λ, the population is inefficient.

Case Study 1: The Trap of Unimodal Functions

One of the paper's most provocative findings is that on unimodal functions, a population cannot shorten the expected running time of an elitist EA.

The Logic: On a unimodal landscape, the (1+1) EA is already taking the most direct route. While a (λ+λ) EA might have a higher probability of finding a better neighbor in one generation (shortening hitting time), that probability increases at most by a factor of λ. Once you factor in that you are doing λ times more work per generation, the total number of evaluations (running time) stays the same or increases.

In Table III, as population size grows from 1 to 9, the hitting time drops, but the total running time (evaluations) increases.

Case Study 2: Redemption on Deceptive Functions

Where does the population shine? On Deceptive Functions. Here, a single individual is likely to get stuck in a local optimum. A population, especially one that enforces fitness diversity, allows the algorithm to explore "worse" solutions that eventually lead to the global optimum.

The Result: For deceptive-like functions, the population scalability can be greater than λ (super-linear speedup).

In Table V, increasing λ from 1 to 5 reduces the total running time from 507 down to 140—a clear win for the population-based approach.

Critical Insight: The "Goodness" of the Benchmark

The most profound takeaway is that the value of a population is relative to the "goodness" of the (1+1) benchmark.

• If your (1+1) EA is "good" (the function is unimodal to it), a population is a waste of resources.
• If your (1+1) EA is "bad" (the function is deceptive to it), a population is your only hope of efficiency.

Conclusion & Future Work

Jun He and Xin Yao have replaced hand-waving arguments about "diversity" with rigorous drift analysis. They've shown that the scalability threshold is often lower than we think.

Limitations: The paper primarily focuses on mutation-based EAs. The impact of crossover on population scalability remains an open and highly complex question for future research. How does recombination change the "Average Drift"? That is the next frontier for the theory of evolutionary computing.