Introduction
In the field of Evolutionary Computation (EC), a persistent "theory-practice gap" often separates mathematical analysis from empirical application. While theoreticians derive rigorous upper and lower bounds for algorithm performance, practitioners frequently rely on experimental results from complex, real-world problems. These two perspectives rarely align, as theoretical bounds are often asymptotic and practitioners' benchmarks lack the structural simplicity required for formal proof.
This research addresses this divide by adapting the well-established COCO (COmparing Continuous Optimisers) benchmarking suite for discrete, pseudo-Boolean optimization. By creating a standardized, theory-guided framework, the authors profile the behavior of $(1+λ)$ Evolutionary Algorithms (EAs) on classic benchmark functions, leading to new insights that bridge the gap between observed performance and mathematical theory.
Methodology: Adapting COCO for Discrete Optimization
The COCO platform has long served as the gold standard for benchmarking in continuous optimization, providing a unified environment for comparing algorithms. This study modifies the COCO software to handle discrete problems, specifically focusing on variants of the $(1+λ)$ EA.
In a standard $(1+λ)$ EA, the algorithm maintains a single "parent" solution and generates $λ$ offspring (mutated versions) per iteration. The best individual among the parent and offspring is selected for the next generation. The authors specifically examined:
- $(1+λ) \text{ EA}_{>0}$: A variant that enforces a "no-zero-bit-flip" rule, ensuring offspring are never identical to the parent. This resampling strategy is designed to improve efficiency on static fitness landscapes.
- Adaptive Mutation Rates: Comparing fixed mutation rates (e.g., $1/n$) against adaptive schemes where the mutation rate $r$ is adjusted online based on the success of previous iterations.
- Adaptive Population Sizes: Testing success-based rules that dynamically double or halve the number of offspring ($λ$) to optimize search efficiency.
Benchmark Problems: OneMax and LeadingOnes
The study utilizes two fundamental problems that serve as the Drosophila of evolutionary computation:
- OneMax: A linear function where the goal is to maximize the number of ones in a bit string. It represents a smooth, unimodal landscape.
- LeadingOnes: A non-separable function where the goal is to maximize the number of consecutive ones starting from the beginning of the string. This problem is more difficult as it requires a specific order of discovery.
While these problems are mathematically simple, they are essential for understanding how algorithms scale and how parameter settings influence the search trajectory across different problem dimensions ($n=500$ to $n=4000$).
Key Insights and Empirical Findings
The Dynamics of Population Size
On the OneMax problem, the study found that large offspring populations ($λ$) are a significant disadvantage during the early stages of the search. When the probability of finding an improvement is high, generating 50 offspring to find a single better solution is inefficient compared to a sequential $(1+1)$ approach. However, as the search approaches the global optimum and improvements become rare, the disadvantage of a large $λ$ diminishes.
In contrast, performance on LeadingOnes remained remarkably stable regardless of the population size $λ$. The authors attribute this to the consistent fitness gain per improvement in LeadingOnes, which mimics the "end-game" phase of a OneMax search throughout the entire optimization process.
Normalization and Scalability
By normalizing optimization times by $n \ln n$ for OneMax and $n^2$ for LeadingOnes, the authors demonstrated that algorithm performance is highly predictable across different problem dimensions. This stability suggests that the core mechanics of these $(1+λ)$ variants scale linearly with the theoretical complexity of the problems.
The Adaptive Mutation Paradox
Surprisingly, the $(1+λ) \text{ EA}_{r/2, 2r}$ (an adaptive mutation variant) was the worst performer in the study’s specific test dimensions, despite having strong theoretical support in literature. This suggests that the theoretical advantages of such adaptive schemes may only manifest at problem sizes significantly larger than those typically used in empirical benchmarking, or that the overhead of adaptation outweighs the benefits in these specific contexts.
Bridging to New Theory
One of the most significant outcomes of this benchmarking effort was the discovery that $(1+1)$ and $(1+50)$ variants performed almost identically on LeadingOnes. This empirical observation directly motivated the authors to revisit the mathematical foundations of the problem. They subsequently proved a new, refined theoretical upper bound for the $(1+λ)$ EA on LeadingOnes (Theorem 1 in the paper). Numerical evaluation showed that this new bound matches empirical data within approximately 1–2% for most cases, providing a rare instance of high-precision alignment between theory and practice.
Conclusion and Future Work
This study demonstrates the power of theory-guided benchmarking to not only evaluate existing algorithms but also to inspire new mathematical proofs. While the current suite focuses on simple functions, it provides a robust foundation for future expansion. The authors plan to extend the framework to include more complex problem features, such as modality (local optima), non-separability, and constraints, and to further automate the data visualization process to match the full capabilities of the original COCO platform.
Summary updated